编程竞赛题目（一）

厚积薄发

; ~3 k7 W9 w$ O# I4 X9 v, T
Sorting It All OutDescription
, u. @- `% Q0 k4 U; w# A4 E# {
3 h2 r( I# g2 D. P$ s6 nAn 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.
, z) [1 E* M6 w, kInput
0 E( c$ Q+ Y/ X0 g1 x% H
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

! l' Q) l5 }: t3 gFor each problem instance, output consists of one line. This line should be one of the following three:

) w! V$ |1 T& {& LSorted sequence determined after ** relations: yyy...y.
Sorted sequence cannot be determined.
Inconsistency found after ** relations.
3 ~- h" ~$ u( F. J. B
8 E' [- A6 [6 |where ** 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.

输入样例

4 6
A<B
A<C
B<C
9 k/ P! x: ]+ pC<D
B<D
A<B
/ p2 A  h* }* m$ _0 r5 |, |% @3 2
) H4 S3 K& ]2 L; B& A4 c) @A<B
  T1 S6 b) R& h, r/ S7 bB<A
26 1
A<Z
0 0
; a( E* F& G1 p

输出样例

* A# |* t6 P4 Z( I7 L' JSorted sequence determined after 4 relations: ABCD.
8 w1 K: b+ D. e' ]' F- ~0 }" h4 v+ GInconsistency found after 2 relations.
Sorted sequence cannot be determined.

Source
: O  Y/ s9 j9 X( A! ?) b' W
East Central North America 2001

程序解题1：

//By Jackie Cheung
#include <iostream>
' c8 }; m3 [! W3 ~) I2 a#include <string>
; m! m" F4 y2 G6 e0 @( O* D9 y#include <cassert>
1 j9 e* |( J6 l: _/ U. D. X6 ktypedef  struct tagNODE
{
6 V2 t$ K: ^5 W9 ^- y    char val;
) z- t9 I7 z1 i/ ^3 d    struct tagNODE* link;
9 p& ~' c) G# p, E* V, D}NODE;
9 V, Z- y+ h. r6 p0 }4 [9 Iusing namespace std;
void Marshall(bool** arrary,int n)
) ?) N" o( J4 J" _{
3 ^/ n4 R" c- N    for(int i=0;i<n;i++)
) W1 o: S% }- B" D! ~" O    {
4 q  D% y5 Y& c        for (int j=0;j<n;j++)
        {
            if(true==arrary[j])
                for (int k=0;k<n;k++)
1 c7 J4 q- l/ G6 P  [                {
                    arrary[j][k]=arrary[j][k] || arrary[k];
. P  |) D5 C" J  ~# z9 X                }
. ^6 F6 k* S0 _  F% w9 k        }
* g4 d) V/ P7 B) A  C# `    }
* {' t7 |* g+ d};
bool  SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)
{
    Seq[n-nLeft]=static_cast<char>('a'+nIndex);
    bool bFlag=false;
    if(1==nLeft)
    {
2 x6 F  ^( q( f7 k4 N0 u        Seq[n]='\0';
& D- u; q( V" n1 _* V$ L2 u3 t6 n, Q        return true;
. W9 z+ n) Q5 t; ^    }
    for (int i=0;i<n;i++)
    {
        if(true==array[nIndex])
" \- P  D  c& z" w2 N0 V        {
; N$ g7 w0 w' s2 V4 }5 N# s            
: {+ f* K6 B  d$ ?8 d) x            bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);
  W* j/ q: R' C        }
        if(true==bFlag)
            return true;
    }
    return false;
# [; a# N0 @  X. a: U};
int main()
{
    int nSeqLen;
1 q9 ~( `2 a/ x4 t. c    int nRelNum;
  s- n$ z+ ~( t, K8 a6 ?    cout<<"Input the length of the sequence:"<<endl;
    cin>>nSeqLen;
* T. x4 s# g6 H1 ~    cout<<"Input the number of relations between the elements:"<<endl;
$ D  O5 N/ l6 p& T* _4 I    cin>>nRelNum;
    //1:if nRelNum<nSeqLen-1,then the relation can not be determined!
2 S# Y' p/ v( c$ C    if(nRelNum<nSeqLen-1)
/ x& D0 _0 t! G$ {$ o    {
. N  }& e0 M4 j) k! x        cout<<"The relation can not be determined!"<<endl;
- E# u, N( G! s        return 0;
    }
    string* strRelations=new string[nRelNum];
* T, A9 E! s8 Q$ i" `    char* Seq=new char[nSeqLen+1];
    bool** array=new bool*[nSeqLen];

    for(int i=0;i<nRelNum;i++)
    {
# ]( c* _+ w' Q& N+ E  H        cout<<"Input the "<<i+1<<"th relation:"<<endl;
7 O$ ^' D2 E) S+ p; D/ J2 Q, V' i        cin>>strRelations;
& R9 L( x9 i; @4 \( x    }
   
    for (int i=0;i<nSeqLen;i++)
! l) f% i: H3 U2 \4 J1 b* w    {
3 \" P( ?9 Y# Q, o( b$ X6 m        array=new bool[nSeqLen];
        for (int j=0;j<nSeqLen;j++)
2 A1 i) B$ A: \+ T! O            array[j]=false;
    }
* V3 }, d; Y6 `3 l6 G* D    //The main loop
    for (int i=0;i<nRelNum;i++)
    {
. D8 R8 X" _) j        char a=strRelations[0];
+ J' X/ [7 }! t% k        char b=strRelations[2];
/ S# r2 m" Y3 G- h" X# N9 D8 p        assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
        array[a-'a'][b-'a']=true;

        Marshall(array,nSeqLen);
  R- H1 `" z$ X% p  `
  B1 g7 X1 f* l2 v7 S: ?. W        //Check for Inconsistency after  every relation
        for (int m=0;m<nSeqLen;m++)
        {
            if(true==array[m][m])
& [' t8 r2 b  L) \. {2 D+ E& D1 O            {
4 I' H! d4 H0 |  g+ D) k8 G                cout<<"Inconsistency found after"<<i+1<<"th  relation!"<<endl;
                    delete []strRelations;
9 p- h+ }/ k; h: ]3 ]; x                    for(int k=0;k<nSeqLen;k++)
                        delete []array[k];
                    delete []array;
                    delete []Seq;
7 \& c7 ~* `/ t) g                    return 0;

            }
        }
  z, Y4 ?& E: _
        //Check for the determined sequence after  every relation   
: e1 M  L9 j) e2 ?/ S8 K        for (int j=0;j<nSeqLen;j++)
- x% n( q2 u/ j        {
            if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))
            {
! \& o7 I' }) w! z3 R                cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;
                delete []strRelations;
. c5 ?3 F8 W; Z5 K6 }                for(int m=0;m<nSeqLen;m++)
* c* ]3 ?' y' a9 f; R- H                    delete []array[m];
9 K0 |% u, L+ C8 `                delete []array;
: y  W* O. P! R$ q4 F% q1 K                delete []Seq;
* h% o% b( z- g6 d                return 0;
            }
- T3 L+ O* C* @5 j        }
8 e% M5 W; \0 s7 z( K/ i

" f1 H6 f4 w! K' G2 W, D0 N3 [* e4 {    }
    //If the program has come to here ,then the relationship hasn't been determined!!!
' I. h9 l2 t. ^5 J: y    cout<<"The relation can not be determined!"<<endl;
    delete []strRelations;
' d' A5 |( s# [6 V% B    for(int m=0;m<nSeqLen;m++)
* B4 M% I+ L. R5 z        delete []array[m];
    delete []array;
    delete []Seq;
   
. q3 z& S5 G$ A$ w    return 0;
}
. L0 H/ I* k4 i# k" K  `) f
8 k& @$ a$ ]8 _/ m: N程序解题二：#include"stdio.h"
void main()
( q/ d2 [+ I2 {9 |5 A0 C5 z{
0 r, M* ^5 a8 {+ b4 P! W    int n_m[100][2];
% Z9 H: W$ g' X9 }% A5 N    char re[1000][3],
) j2 ~, M/ y- ~/ i2 R- D    temp[26];
    int i=0,j=0;
4 R! E( U. f) _* b    scanf("%d%d",&n_m[0],&n_m[1]);
    for( ;j<n_m[1];j++)
6 Q( Q7 I4 g; d7 c9 A; D2 _    scanf("%s",&re[j]);
    while(n_m[0]!=0&&n_m[1]!=0)
9 K1 g1 i" X# w3 H$ B    {
( E" w# `% O0 @& z% e1 o9 Z% }1 z    i++;
    scanf("%d%d",&n_m[0],&n_m[1]);
    for( int f=0;f<n_m[1];f++,j++)
    scanf("%s",&re[j]);
$ S9 r: @* ?) H: g/ e' [3 ~    }
    i=0;
5 _$ P% o# g3 R    j=0;
7 Y* b+ H  E* Q   for( ;n_m[0]!=0&&n_m[1]!=0;i++)
    {
       int a=0,b=0,l=1;
       for(a=j;a<j+n_m[1]-1;a++)
0 R' x2 o* {' ?1 T0 y2 y( m  a         for(b=a+1;b<j+n_m[1];b++)
6 G  s/ ~5 t, E         {
+ {3 q+ t. F4 p3 c1 L              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])
            {
6 Z4 i! t3 m9 p4 c. `' \            l=0;
; c& I: ]5 p3 B( t5 v3 }- N            printf("Inconsistency found after %d relations.\n",n_m[1]);
  o1 D  \7 t# K6 Q            break;
            }
         }
      if(l==0)
: M" N3 J1 E* Q) Y2 b' V! E          continue;//Inconsistency found after x relations.
( t/ {1 d6 v, U6 S! _4 b    else{
- [8 p6 G5 r& Y5 u9 q( {2 |' k           if(n_m[1]<n_m[0]-1)
        {
            printf("Sorted sequence cannot be determined.\n");
            l=0;
        }
        else
2 D6 ~6 ^, g* J        {
          if(n_m[1]==n_m[0]-1)
% Y' e. L5 ?" H! t9 T: q* B          {   
# J- A7 _( E) U' _: z( Y              int k=0,p=0;
6 k/ f& ]# R8 y) h              for( ;k<n_m[1]-1;k++)
9 J2 v. T4 s/ R) R) B0 R; g                  for(p=k+1;p<n_m[1];p++)
/ m. K, d4 g' b                      if(re[0]==re[0]||re[2]==re[2])
8 b0 F! M! ]3 {" J7 k                      {
) r' ?7 e3 V- a; R                      printf("Sorted sequence cannot be determined.\n");
' P$ p' E: C- J: n9 m                      break;
                      l=0;
                      }
          }
        }
        if(l==0)
        continue;//Sorted sequence cannot be determined.

        else
         {
9 l+ K; X2 W) s! M- T3 u( S! \           
            for(int k=0;k<n_m[0];k++)
             temp[k]=k+65;
            for(k=0;k<n_m[1];k++,j++)
            {
# A7 f3 o/ s5 ~$ a; \' t: ]                int t1=0,t2=0;
              for(int s=0;s<n_m[0];s++)
: |  c; t7 `5 {: @              {
5 a) T2 X0 ~/ f. Q               if(temp==re[0])
9 e# G' j- M7 R2 X4 z+ a                   t1=s;
                      if(temp==re[2])
* q) ]4 Q+ ~: r" q5 }                   t2=s;
  r; M7 @- r% {              }
) C4 O) k- m7 S* P% w              if((t1>t2)&&re[1]=='<')
              {
6 z& a- A7 h" g. h& A0 N) L0 P                char t3=temp[t1];
( M5 p, t4 B% }8 N4 e  r  }! ]                temp[t1]=temp[t2];
                temp[t2]=t3;
3 i% \4 |* f4 y  P              }
/ [9 T: w3 @  q0 N. g2 o2 r            }
        int count=0;
6 Z# t! F. i5 I/ R& s& u        for(int s=0;s<n_m[0]-1;s++)
! Z9 k  Z. m8 Q        for(int d=j-n_m[1];d<j;d++)
; _* q: o5 m, X            if(re[d][0]==temp&&re[d][2]==temp[s+1])
            {
                count++;
, m9 T, @8 N9 h0 A1 f                break;
            }
" n* N+ r0 R3 Z1 `  s            if(count==n_m[0]-1)
            {
& q+ N  `! z4 }: P                printf("Sorted sequence determined after %d relations:",n_m[1]);
- h* J* l% _" @8 F- `                for(int f=0;f<n_m[0];f++)
( h, M4 c2 r: g6 g- v/ [% Q' g2 |                  printf("%c",temp[f]);
. Z7 M. V+ q8 \$ T# y. l' S                 printf("\n");
1 N4 A4 \8 f3 H            }
% \+ {& {) \# A* D' e/ v8 Q* w            else
1 ?1 W1 c, p0 N+ [               printf("Sorted sequence cannot be determined.\n");
        }
" g; ?& B1 h; Y! E    }
    }
0 z& Z' |0 s, t& ~- H$ Z! U# k}


; b/ k- n4 K& W2 \5 G: K- X; G


3 y6 \" B$ ]! n3 R3 c7 l0 V& _$ ^
5 \7 U  @" C4 G$ @

来源：编程爱好者acm题库