编程竞赛题目（一）

厚积薄发

( A0 |# K$ \6 q
Sorting It All OutDescription

0 W+ h2 v% W# z) @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.
Input

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.
: O  j. R. P$ C- T& _" L. Z/ aOutput

For each problem instance, output consists of one line. This line should be one of the following three:

. _9 i8 x& l' U; }2 u" SSorted sequence determined after ** relations: yyy...y.
Sorted sequence cannot be determined.
Inconsistency found after ** relations.
8 K1 _: r! D2 h5 N& J, A, q
3 ^- ]9 N4 p0 {- |3 k8 z1 I+ o7 Awhere ** 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.

输入样例

1 k! ]8 H  |3 `5 J4 6
/ ?0 s' ^) o5 o: O6 NA<B
+ {& m, X3 v* q& Z0 `2 bA<C
4 n9 k' a" p) i1 Q: ^B<C
C<D
+ [8 U$ P2 k' n/ k: iB<D
A<B
4 x! d: {# R8 i: ^3 c3 2
A<B
% t! q! m4 C6 G' r6 PB<A
( c& [( s# a" {- c+ n/ z$ x26 1
- ]( P. V5 g% j5 E6 PA<Z
0 0

9 E6 _7 f" b$ ?: P7 W# F输出样例

! m; N" o9 {8 K( y* B+ I6 eSorted sequence determined after 4 relations: ABCD.
# Y7 g  T% P! y; U0 O# ]4 IInconsistency found after 2 relations.
7 ~" u4 E5 I- N  r4 N! NSorted sequence cannot be determined.

Source
0 U3 K* z; G1 g+ H
East Central North America 2001

; q9 w& E' G" l  Q: E/ }

程序解题1：

0 r! x# {  m) K9 Y: ^6 L" J//By Jackie Cheung
% d: O& L9 o% M8 i7 d#include <iostream>
$ J0 N1 t+ n2 L! W/ b#include <string>
#include <cassert>
% x3 V2 K) X. o8 ~: A. a* `typedef  struct tagNODE
{
    char val;
    struct tagNODE* link;
; D$ [% i) J9 }9 J! F. X4 ~- V}NODE;
9 A" J) P6 S, R+ x; p- ausing namespace std;
% F4 K7 L# N) Q: `void Marshall(bool** arrary,int n)
% `  g5 S3 }% ]" [{
% N& G2 H. I. f& S: F    for(int i=0;i<n;i++)
! m, U* N! m) |, X: i( c" ^, Z    {
* A6 e5 T, {8 u  N) i        for (int j=0;j<n;j++)
8 J* a, G+ g0 E& W        {
            if(true==arrary[j])
- ?3 S& t4 z: X7 p- p* e4 z                for (int k=0;k<n;k++)
! [* k1 m0 }: T                {
                    arrary[j][k]=arrary[j][k] || arrary[k];
                }
. B5 x. l) R, S/ R        }
; T* v) R: f5 ^% P    }
};
bool  SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)
+ J' d) M0 G! d1 y6 I{
    Seq[n-nLeft]=static_cast<char>('a'+nIndex);
( ]" H- H7 `0 H+ `. g    bool bFlag=false;
5 k: V) I1 u! z. U2 U    if(1==nLeft)
    {
$ F# E9 ^- V7 X7 e' G. w. b' Q        Seq[n]='\0';
; W( D9 ?- j0 m8 c        return true;
6 \8 K- z& d4 O& `8 O  r    }
1 F! b! l2 F' O6 X4 o! C4 Y) P" D! U    for (int i=0;i<n;i++)
! e* m6 [+ b3 |4 T+ ?    {
        if(true==array[nIndex])
9 n3 G$ A8 F: F3 l4 \+ J( c        {
            
            bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);
. s; E( j% I  a  V6 o) M6 _& M        }
4 T' j- `6 i) Q) e1 }        if(true==bFlag)
            return true;
    }
9 [, }* A' J" q    return false;
5 X/ o# U! T& r' G9 W- C+ P};
* a" K7 T  K) p) ?/ w+ J: Nint main()
9 T  u" P3 i- b. a0 c5 B$ W* {{
    int nSeqLen;
    int nRelNum;
% |3 D$ e  C/ ^% R6 F' W$ A  u    cout<<"Input the length of the sequence:"<<endl;
. b5 h; T. `+ z* a8 D: N    cin>>nSeqLen;
    cout<<"Input the number of relations between the elements:"<<endl;
    cin>>nRelNum;
    //1:if nRelNum<nSeqLen-1,then the relation can not be determined!
9 |$ F( J, f/ R6 E8 D9 Z+ g6 C    if(nRelNum<nSeqLen-1)
1 U; {8 a' b) K6 N    {
        cout<<"The relation can not be determined!"<<endl;
/ ~* u* [* |8 c: s) m' p) [7 _: T) _        return 0;
& G2 v8 n9 k3 Y) e6 b    }
    string* strRelations=new string[nRelNum];
    char* Seq=new char[nSeqLen+1];
    bool** array=new bool*[nSeqLen];

, o0 G$ g: w- k1 ~  _    for(int i=0;i<nRelNum;i++)
    {
% F1 E$ N8 `# V0 \9 `        cout<<"Input the "<<i+1<<"th relation:"<<endl;
% t9 b% Y8 {& V        cin>>strRelations;
    }
/ o  `8 q: @/ i1 M* J: o/ |* ?   
. M* L3 }. [* ~( J8 M  b5 b7 S4 s    for (int i=0;i<nSeqLen;i++)
, ^! ]; z: u3 h# L" k    {
        array=new bool[nSeqLen];
! U7 S' P: @3 V% X/ S$ Y        for (int j=0;j<nSeqLen;j++)
8 X; v& K* C6 X* H            array[j]=false;
. a  a: i8 Y- ^# [# I    }
# h% U  U8 s% S    //The main loop
    for (int i=0;i<nRelNum;i++)
; a1 w: u! \9 K  C( t7 q* E    {
        char a=strRelations[0];
0 Q! ^" w# ?% N  [' d" r        char b=strRelations[2];
/ t0 _9 H+ H2 u$ j! v' ~# _. X4 R        assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
, R+ V' o7 L& s        array[a-'a'][b-'a']=true;

        Marshall(array,nSeqLen);
. ]6 b3 R7 O! D
        //Check for Inconsistency after  every relation
        for (int m=0;m<nSeqLen;m++)
$ N7 O* C  d& E  ]7 I: e% V        {
            if(true==array[m][m])
2 g# V1 O& ~$ [. P" g7 h; q& m* ~            {
! F, d9 w- n( X, x0 f                cout<<"Inconsistency found after"<<i+1<<"th  relation!"<<endl;
$ A2 e) X6 V% O* |0 B                    delete []strRelations;
                    for(int k=0;k<nSeqLen;k++)
                        delete []array[k];
                    delete []array;
; C! C5 {2 H# E2 K                    delete []Seq;
3 C1 v7 X6 D( ~1 {7 K2 ]  E                    return 0;

: o* Z+ F. a' K  c            }
# x$ M7 L6 J( [2 Z* o6 N# A        }

        //Check for the determined sequence after  every relation   
        for (int j=0;j<nSeqLen;j++)
) t$ R7 {# p8 _) Z3 N/ e        {
            if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))
            {
1 c+ m9 I/ F# a, `1 I( f                cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;
                delete []strRelations;
5 W! r# M) R: {) W2 d                for(int m=0;m<nSeqLen;m++)
4 K/ x1 k* o7 y6 ~" h/ `                    delete []array[m];
                delete []array;
* j" Q0 e# l5 [. V7 e- W                delete []Seq;
* a) P+ u7 `0 |& _                return 0;
            }
        }
; h* O/ a0 u1 Q! K
6 f+ B0 j' s, `$ q. D" O5 n8 d
6 m( X; s0 O, c% L+ Z    }
5 ?, r, c# K1 i1 Z# T# h    //If the program has come to here ,then the relationship hasn't been determined!!!
, |) E+ m8 }9 n8 D6 s    cout<<"The relation can not be determined!"<<endl;
* n, B7 @: V6 ?  M( P2 }    delete []strRelations;
    for(int m=0;m<nSeqLen;m++)
        delete []array[m];
* w! a+ |2 q0 z+ c& o    delete []array;
    delete []Seq;
" _4 E$ h1 ]+ M7 y0 g, [% y   
    return 0;
6 U/ g4 J7 T1 {( {- I}
/ m' g: A( d7 [8 x, z
' R3 g% S  b8 {4 x/ z6 Z程序解题二：#include"stdio.h"
void main()
{
    int n_m[100][2];
    char re[1000][3],
) l0 C1 ]1 o+ U( r) u  G    temp[26];
    int i=0,j=0;
    scanf("%d%d",&n_m[0],&n_m[1]);
" t* P/ g4 W- p    for( ;j<n_m[1];j++)
    scanf("%s",&re[j]);
. u5 G4 w8 _4 C1 l# q4 b! x" z- [+ @    while(n_m[0]!=0&&n_m[1]!=0)
    {
, Z- W2 B; I% M, A+ f+ ~9 @. ?    i++;
    scanf("%d%d",&n_m[0],&n_m[1]);
    for( int f=0;f<n_m[1];f++,j++)
    scanf("%s",&re[j]);
( `3 |% x9 Y& Q  [8 \    }
% B3 G( W- K, Z, h% M5 l    i=0;
: j; z" H0 l- R: C. W    j=0;
5 o/ b9 X. D& B   for( ;n_m[0]!=0&&n_m[1]!=0;i++)
- Q& o4 H6 M9 B    {
* i6 X, G6 Z- k- |       int a=0,b=0,l=1;
7 }9 f0 O  B. }( M       for(a=j;a<j+n_m[1]-1;a++)
         for(b=a+1;b<j+n_m[1];b++)
. Y0 j$ s* X, D* d- X" Q7 W         {
& g1 @3 A0 `  m0 H# M# a! X              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])
            {
            l=0;
4 h" e9 o* l; }- W3 h            printf("Inconsistency found after %d relations.\n",n_m[1]);
# l  p/ t/ W/ _7 G2 W# }& ]9 Z' r            break;
$ c* Q) M3 U' Z% f6 [3 I* e            }
6 g/ O; y% R0 r' i6 h, ?9 k! z         }
% ?, d7 A- `- K9 c( ~* F7 t      if(l==0)
          continue;//Inconsistency found after x relations.
# h7 D& j* J: H% O& P    else{
  }7 m2 `' n: x( _( X& |           if(n_m[1]<n_m[0]-1)
        {
1 b4 r; x' X* [3 a5 t( d2 h( e0 i            printf("Sorted sequence cannot be determined.\n");
            l=0;
        }
        else
        {
          if(n_m[1]==n_m[0]-1)
          {   
              int k=0,p=0;
              for( ;k<n_m[1]-1;k++)
                  for(p=k+1;p<n_m[1];p++)
1 }, S; t3 y+ c                      if(re[0]==re[0]||re[2]==re[2])
                      {
                      printf("Sorted sequence cannot be determined.\n");
" S( F: R! d" M                      break;
, U1 T& m) y- f2 `+ @                      l=0;
% D9 Z- t! G1 I% t: L' J5 l                      }
          }
2 |' n# @" s. u% k2 X: u; S! b/ x        }
" {- V# ^8 u' {6 x  q        if(l==0)
0 z$ M. z3 Y; S& i        continue;//Sorted sequence cannot be determined.
! z% {- m$ ^4 \" K; A
, t1 o/ |; A4 }8 N6 L" v        else
9 [" R. ]* |; z4 ?  s% L( L         {
3 z& D. R, m9 p8 `, V* C# T           
0 v  X' ^9 t' H) c# o            for(int k=0;k<n_m[0];k++)
- F- F5 [: R* E4 N$ e             temp[k]=k+65;
            for(k=0;k<n_m[1];k++,j++)
            {
                int t1=0,t2=0;
              for(int s=0;s<n_m[0];s++)
+ Y7 s. f* i/ K4 X3 I. D: Q& `* R              {
% [$ F1 T3 l9 I& ^               if(temp==re[0])
# q; K/ o) Y' l! G  G* f% F- K. d                   t1=s;
                      if(temp==re[2])
                   t2=s;
/ o' O, D: G% X; |3 C% P; W              }
              if((t1>t2)&&re[1]=='<')
              {
                char t3=temp[t1];
- f2 ^) m' t& B$ Z4 K/ z8 b                temp[t1]=temp[t2];
0 J% N- R! J6 o+ W                temp[t2]=t3;
              }
            }
: k( M6 d2 i# w& t. E6 f! \; }        int count=0;
4 v' B9 p; U- m4 l4 j, ?! X' _& ^        for(int s=0;s<n_m[0]-1;s++)
        for(int d=j-n_m[1];d<j;d++)
& {2 B. K5 y5 d& {            if(re[d][0]==temp&&re[d][2]==temp[s+1])
, s% I* w# C( \7 \# e; V; m            {
                count++;
                break;
            }
            if(count==n_m[0]-1)
            {
5 v+ [, G; ?# D# A0 R' X                printf("Sorted sequence determined after %d relations:",n_m[1]);
' S. T1 S% X( s- d0 i  ]$ C                for(int f=0;f<n_m[0];f++)
                  printf("%c",temp[f]);
                 printf("\n");
            }
            else
               printf("Sorted sequence cannot be determined.\n");
        }
9 v9 u6 V/ U) d6 P* |9 d  t2 b3 N    }
    }
}
. |& g4 q+ O; E7 d7 A8 b

' [  M7 L5 B, y( d* C2 F6 M& A
9 @' [: e' C% B' x+ Z8 X
5 ?0 J4 q. k) D% T. x6 b

! x4 w( o8 c" q) F" v( E7 o/ R: B

0 n/ G% @/ _( V; {9 L& b

来源：编程爱好者acm题库