编程竞赛题目（一）

厚积薄发

' l6 _* @4 I8 |/ d, lSorting It All OutDescription
- E3 r1 ~. J4 z0 \+ ^6 S! N% E
An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not.
/ t. X# A" \' A0 wInput
$ j- i" v0 q- O6 ]; d
Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n <= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character "<" and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input.
Output

/ g) ]. H; Y. yFor each problem instance, output consists of one line. This line should be one of the following three:
/ e" f) }) g( }
Sorted sequence determined after ** relations: yyy...y.
9 @: ]7 N- d1 ~- i5 L! }" |( |3 }Sorted sequence cannot be determined.
Inconsistency found after ** relations.
5 Y+ `/ l( @4 w
. ?* Y/ `! j6 g+ swhere ** is the number of relations processed at the time either a sorted sequence is determined or an inconsistency is found, whichever comes first, and yyy...y is the sorted, ascending sequence.

8 o( L- O" m6 |3 K9 T7 q输入样例

4 6
3 h% L6 Q  z5 ]9 g- uA<B
' R3 e! Y3 J1 K3 MA<C
, ^) j, D$ O3 Y/ N# bB<C
C<D
B<D
A<B
3 2
4 S" Z0 k3 E) ]( {' qA<B
B<A
26 1
  }4 |/ |* u$ t' F! TA<Z
" i/ F$ `- K5 C/ ?0 0

输出样例

Sorted sequence determined after 4 relations: ABCD.
/ ?8 h1 u- s$ q! g: JInconsistency found after 2 relations.
& z1 C4 d4 ^" e4 I' gSorted sequence cannot be determined.

Source

( N& }  x9 @+ s8 W2 [East Central North America 2001

程序解题1：

//By Jackie Cheung
#include <iostream>
#include <string>
#include <cassert>
- E0 e) y7 H: C1 S0 W0 j! utypedef  struct tagNODE
{
+ l( _* d  C9 ~. ~5 M0 l6 Z( ]    char val;
+ X. v: [; E* N4 A    struct tagNODE* link;
2 \( Z2 F3 I7 c) h; Z# l6 `2 d}NODE;
( O5 ~' b5 P0 V  F" M0 g. z' Y' nusing namespace std;
void Marshall(bool** arrary,int n)
& ^0 k1 g/ v; s# H8 ?{
% d) G' w, `: |    for(int i=0;i<n;i++)
; t2 {  E& D6 ?) g+ f    {
9 h: ^8 V, ?8 J. A        for (int j=0;j<n;j++)
5 u2 s. I4 c5 t- }, E; G        {
            if(true==arrary[j])
                for (int k=0;k<n;k++)
                {
# S1 [# b& h4 M9 D                    arrary[j][k]=arrary[j][k] || arrary[k];
                }
        }
$ w6 W7 Q1 o* l# |, [4 q    }
};
8 _) O) c1 n3 M" t. Rbool  SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)
{
+ Q8 j) B$ d+ j3 V    Seq[n-nLeft]=static_cast<char>('a'+nIndex);
    bool bFlag=false;
/ m3 F. q( Q' m2 d6 r* f+ h$ O4 X    if(1==nLeft)
    {
        Seq[n]='\0';
8 h; T' e( G( c* Y& O% \        return true;
1 `& ?' m6 g; x" C- C6 |7 ]1 D- k    }
/ d2 X7 E7 t1 r' ~* E    for (int i=0;i<n;i++)
+ U; |# b/ m. d. W    {
        if(true==array[nIndex])
        {
            
            bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);
        }
: o4 O5 X+ u! X8 y! B        if(true==bFlag)
            return true;
    }
1 Q/ V  t) ^+ C! p$ Y# Y# J    return false;
};
+ ?, N9 q- u) C- c1 l/ T: Jint main()
{
    int nSeqLen;
5 o/ I# k! i  O    int nRelNum;
    cout<<"Input the length of the sequence:"<<endl;
7 E6 R+ P+ Z5 O) R    cin>>nSeqLen;
+ t7 r/ q5 W. W    cout<<"Input the number of relations between the elements:"<<endl;
/ y, S5 P) K2 A9 l4 B. G    cin>>nRelNum;
& j8 s- |- m3 ]6 P( A$ i    //1:if nRelNum<nSeqLen-1,then the relation can not be determined!
    if(nRelNum<nSeqLen-1)
! U4 u# s) X, U0 ~    {
/ f: T' w1 Y, V, u4 i) k( D        cout<<"The relation can not be determined!"<<endl;
        return 0;
    }
    string* strRelations=new string[nRelNum];
5 K& w; u% ?4 u8 Q; o" ~' [    char* Seq=new char[nSeqLen+1];
    bool** array=new bool*[nSeqLen];
. M" N( X3 X$ j/ d9 L1 e
    for(int i=0;i<nRelNum;i++)
! t8 P$ W7 o! g8 G    {
        cout<<"Input the "<<i+1<<"th relation:"<<endl;
9 _$ [9 u4 E" \        cin>>strRelations;
$ G8 z8 {1 F+ G! K    }
1 M) w* A# D/ m  u/ o; h" p   
    for (int i=0;i<nSeqLen;i++)
    {
4 [: k! a$ \  T$ C. s6 G, I* ?, W        array=new bool[nSeqLen];
  M, M" d8 {1 d: B& d1 `5 u        for (int j=0;j<nSeqLen;j++)
# E9 B1 M- V9 g2 j1 z5 Q" q            array[j]=false;
    }
! ?6 ]! ]4 D1 j+ V& r! ]6 E, ]    //The main loop
8 X! o  ^; q, \9 }' a    for (int i=0;i<nRelNum;i++)
9 J6 r$ [+ R9 ^4 ^    {
        char a=strRelations[0];
        char b=strRelations[2];
3 O0 s. j, T) O# f        assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
        array[a-'a'][b-'a']=true;

        Marshall(array,nSeqLen);
4 S; W7 l4 R* P/ o4 C# A. }: a& B, m
* V! p5 i& }/ H( q+ {. E" ~, I. l8 }        //Check for Inconsistency after  every relation
- N$ Q% A$ K" @) o5 T* q        for (int m=0;m<nSeqLen;m++)
        {
# h/ [- L! |& [, B  G3 d            if(true==array[m][m])
) C1 V) t; U0 W- }9 t            {
2 E8 z* \+ l3 f; S                cout<<"Inconsistency found after"<<i+1<<"th  relation!"<<endl;
* c' e+ o( K# y! |+ \6 y  E) D                    delete []strRelations;
4 o/ a! h' B7 @3 @                    for(int k=0;k<nSeqLen;k++)
4 n2 K1 @. n+ @* r7 {. E                        delete []array[k];
# W# o+ T5 B9 b7 l" N1 I                    delete []array;
                    delete []Seq;
                    return 0;

( a* r+ {0 J5 ~  V            }
% V! ~9 h. ^: m3 t. m1 S. r        }
+ s' C, b0 |1 e9 e
- L' a4 z0 P# ]5 z: L; [        //Check for the determined sequence after  every relation   
2 `+ F8 d. V5 [& l1 I/ [        for (int j=0;j<nSeqLen;j++)
        {
            if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))
            {
                cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;
                delete []strRelations;
                for(int m=0;m<nSeqLen;m++)
                    delete []array[m];
  o) R# Z' h- h1 M+ ~9 B                delete []array;
                delete []Seq;
                return 0;
            }
& J8 w# A- b  j        }


    }
    //If the program has come to here ,then the relationship hasn't been determined!!!
    cout<<"The relation can not be determined!"<<endl;
8 U4 v  @% F+ _! a+ g- K. O    delete []strRelations;
    for(int m=0;m<nSeqLen;m++)
) G+ j7 K1 V4 i8 X/ E9 I        delete []array[m];
# N1 u0 l& d1 ]7 _# K/ _    delete []array;
    delete []Seq;
9 o) V/ f4 w% ?! t$ ^3 W* e& |   
    return 0;
) h/ ~& t8 J' @/ `; X- P}

1 \* q) j* m0 D, W% G2 ^2 M6 p6 |程序解题二：#include"stdio.h"
- |' ?! I) e2 T9 Gvoid main()
& m( B0 i! H: l' e{
    int n_m[100][2];
    char re[1000][3],
+ x! _, \- e9 T; f9 m    temp[26];
    int i=0,j=0;
% |5 K1 G7 @; f# D, }. B    scanf("%d%d",&n_m[0],&n_m[1]);
    for( ;j<n_m[1];j++)
    scanf("%s",&re[j]);
    while(n_m[0]!=0&&n_m[1]!=0)
6 l% _- ^: s- ?( y4 h    {
    i++;
    scanf("%d%d",&n_m[0],&n_m[1]);
    for( int f=0;f<n_m[1];f++,j++)
; i7 y, B( I/ Z& q    scanf("%s",&re[j]);
    }
    i=0;
    j=0;
9 V# M. V0 E9 g0 Q  k   for( ;n_m[0]!=0&&n_m[1]!=0;i++)
4 n' W2 C3 |# |# H+ {    {
       int a=0,b=0,l=1;
( ?' e5 w8 M3 B6 `7 c3 `/ F       for(a=j;a<j+n_m[1]-1;a++)
         for(b=a+1;b<j+n_m[1];b++)
- X+ o! j6 ]. h! E         {
8 Q! s* b. `9 a' m& _              if(re[a][0]==re[0]&&re[a][2]==re[2]&&re[a][1]!=re[1]||re[a][0]==re[2]&&re[a][2]==re[0]&&re[a][1]==re[1])
/ @$ N; H+ |. t3 a( w4 H0 I            {
5 j5 j# }  D) |+ d! O' q3 B% G9 @            l=0;
            printf("Inconsistency found after %d relations.\n",n_m[1]);
& i  _, H+ F8 P8 r            break;
7 |( O" b" \! e            }
9 D3 D( J" T% F* D2 h! S: W. o         }
      if(l==0)
          continue;//Inconsistency found after x relations.
    else{
+ j/ z  l4 {  V           if(n_m[1]<n_m[0]-1)
        {
            printf("Sorted sequence cannot be determined.\n");
            l=0;
6 b1 ]' X7 i: y7 Y: s/ j        }
        else
        {
: n8 ~: W7 @  J" p" J) j" Z$ `% n          if(n_m[1]==n_m[0]-1)
          {   
              int k=0,p=0;
              for( ;k<n_m[1]-1;k++)
# C+ G# C. U  C' @, E                  for(p=k+1;p<n_m[1];p++)
                      if(re[0]==re[0]||re[2]==re[2])
: a% P9 t; g5 k1 x8 @                      {
8 U& c2 @+ K) [                      printf("Sorted sequence cannot be determined.\n");
                      break;
. [6 L8 ?5 D/ l  a* M                      l=0;
                      }
) l0 k, r, J8 x" o9 l, ~/ B          }
9 y# m  x9 Q2 S- {' h2 {9 R  k        }
+ u/ H5 D* V+ X        if(l==0)
- N+ y! L% ], o) f: f        continue;//Sorted sequence cannot be determined.
# {- I5 s, C% d  g9 v: y3 G  D7 W/ X4 L, \
1 [$ o- o- o; R; b! R$ t3 Q        else
         {
           
8 a( ?$ D( W- Z0 M6 x            for(int k=0;k<n_m[0];k++)
             temp[k]=k+65;
0 }! J$ E1 ~4 T( Z, X6 e: q            for(k=0;k<n_m[1];k++,j++)
            {
4 d9 y6 @1 ^; \, V$ V; z                int t1=0,t2=0;
              for(int s=0;s<n_m[0];s++)
0 ^# O  F+ J2 |( @- r$ G9 M  l' z              {
& z( p+ Q+ S- M3 b               if(temp==re[0])
  x  v6 P& _* k! \                   t1=s;
3 ]9 u1 ]. l: s- y9 z8 B                      if(temp==re[2])
                   t2=s;
6 Y' r* @+ Y1 ~* h              }
              if((t1>t2)&&re[1]=='<')
              {
, W! }' b5 h! Q. Q0 W                char t3=temp[t1];
                temp[t1]=temp[t2];
                temp[t2]=t3;
              }
' f7 P6 T1 Q8 g, r1 q3 p$ }0 D            }
        int count=0;
        for(int s=0;s<n_m[0]-1;s++)
        for(int d=j-n_m[1];d<j;d++)
& \$ o* f, T% N1 o0 [; ~            if(re[d][0]==temp&&re[d][2]==temp[s+1])
9 B$ O9 f: |7 ~& q6 R$ ~, H            {
                count++;
; y, n" C; P  j8 q5 x                break;
            }
" f% U2 z/ V9 g; w4 n            if(count==n_m[0]-1)
            {
# Y& W+ G; z2 _* G                printf("Sorted sequence determined after %d relations:",n_m[1]);
! |( F' h# H  d8 F1 f                for(int f=0;f<n_m[0];f++)
! a% C. y  S3 v3 Y. J# e                  printf("%c",temp[f]);
                 printf("\n");
5 Y; O& O7 ^6 V+ i) u            }
- D# ^# a" H, n# Q% s9 V5 u8 P            else
               printf("Sorted sequence cannot be determined.\n");
, J! C) b8 K- h  S6 _  ~! Y$ _: V        }
( m4 _1 T8 k' b* R# S    }
    }
0 s/ O& v. J  j. e* N- ]}

5 T7 ~! T6 o5 z4 K2 N


% s2 z$ T1 @9 e, y0 d, C
0 J# `3 ~2 F3 E2 q) c1 E1 W
. W% Z8 c) K) x" v" t, V8 E, h

来源：编程爱好者acm题库