编程竞赛题目（一）

厚积薄发

! l* a1 _0 e  X$ v5 _- a
Sorting It All OutDescription
! O' Q2 V% s9 j# M7 @6 Y
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.
5 d( U$ y3 D7 W+ h3 d- O7 _Input
0 R; _3 S6 _1 k& B" w1 [
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.
! m3 q- ?' ~" ]3 m: p2 i, ^Output

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

- O) L$ q' C: z' P7 F- n3 zSorted sequence determined after ** relations: yyy...y.
" F& [- `( ^; h+ R! T9 @Sorted sequence cannot be determined.
Inconsistency found after ** relations.

/ n; c2 B4 @, \+ y2 kwhere ** 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.
- Z$ z5 G  R1 ^# C
8 x' T5 G& j8 `( n( H" q, l输入样例

1 }- P; h2 a( _* f. W. k- @4 6
! ^9 Z) S6 F8 f2 lA<B
' k% k) g( P- ]; }, tA<C
B<C
C<D
# i' n; T# \- `- M6 c) N+ V4 @+ lB<D
A<B
3 2
, I. U/ j1 |6 B. c5 h3 FA<B
B<A
26 1
: y3 Q. w: z6 S$ rA<Z
  I  u- O" `$ l0 @, m6 U7 X0 0

输出样例

Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.

2 z2 l/ k4 `  B& D% w

Source

East Central North America 2001

; {: f' x- ?/ H' }& E% {4 }  Q. ]

程序解题1：

//By Jackie Cheung
#include <iostream>
. B' V+ o$ w, O6 Q! ^#include <string>
#include <cassert>
- {* Q( B+ f0 f# m0 D1 H$ ?( D4 ~. Mtypedef  struct tagNODE
{
    char val;
    struct tagNODE* link;
% R' @" }$ s: w" V, J}NODE;
7 i5 M9 Y6 U% pusing namespace std;
# I  z8 N0 c3 \4 `9 V& Y) Zvoid Marshall(bool** arrary,int n)
{
6 b$ {' \# m5 X4 A4 e4 I# X    for(int i=0;i<n;i++)
    {
        for (int j=0;j<n;j++)
+ _- [6 l/ [# Z5 T3 l7 d# D, T        {
9 l( I) t/ f0 o# K            if(true==arrary[j])
, v- B" G+ y! n* \9 X$ A  g                for (int k=0;k<n;k++)
                {
9 e; e- U7 ^8 c6 e                    arrary[j][k]=arrary[j][k] || arrary[k];
                }
        }
    }
9 \' ~4 V$ ^( Q};
( R9 u- J: u$ _; E- Ebool  SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)
{
  W% \# S, }" G3 z( d    Seq[n-nLeft]=static_cast<char>('a'+nIndex);
" k: o. V9 f" ]  a' V    bool bFlag=false;
    if(1==nLeft)
    {
        Seq[n]='\0';
- ^  Y" H) b/ @. u: w6 q        return true;
    }
    for (int i=0;i<n;i++)
) U. X* C2 m; z" b    {
, Q5 W+ u/ ]# P+ l0 U/ J        if(true==array[nIndex])
        {
            
            bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);
        }
        if(true==bFlag)
5 {' ]- t2 m7 k3 Q0 q$ F& N, Z$ ]            return true;
4 [) c. w6 U& ]% _5 k, O    }
    return false;
};
2 Z" Z" H) t6 k' u4 h, yint main()
7 U( b2 s; }. c3 x/ d9 M9 Y3 @{
    int nSeqLen;
: A1 a0 S1 T& r1 Z3 z. Y    int nRelNum;
8 F: l0 X+ G  ]* K/ c4 }* |7 P    cout<<"Input the length of the sequence:"<<endl;
$ o# p7 f) p$ z& B" U8 O$ S    cin>>nSeqLen;
" ?7 ]- C9 H" Y* I& p" s  j    cout<<"Input the number of relations between the elements:"<<endl;
    cin>>nRelNum;
8 E3 y2 b4 ^& H% [+ H9 f) t6 c) w    //1:if nRelNum<nSeqLen-1,then the relation can not be determined!
) z* m$ r- R$ x    if(nRelNum<nSeqLen-1)
    {
        cout<<"The relation can not be determined!"<<endl;
, P) t2 u& q& [3 c        return 0;
' ^1 X7 k0 m7 z& ^1 t: T, \    }
    string* strRelations=new string[nRelNum];
    char* Seq=new char[nSeqLen+1];
    bool** array=new bool*[nSeqLen];
4 G# h/ |& I" E! e7 o
" i0 \2 @" n8 ]6 z& K  M9 m9 q# S    for(int i=0;i<nRelNum;i++)
9 Y8 X9 [4 t. V! L7 x2 ~    {
, K, x. p1 Z/ r8 N7 [5 o        cout<<"Input the "<<i+1<<"th relation:"<<endl;
: O  y6 k+ X0 f' _& W( C5 W# H        cin>>strRelations;
( [7 [/ I- ?- d8 q! u    }
   
    for (int i=0;i<nSeqLen;i++)
1 C3 r4 p, \5 n2 i& `: Q: a0 x    {
        array=new bool[nSeqLen];
1 P- G6 E# Z3 G7 z        for (int j=0;j<nSeqLen;j++)
            array[j]=false;
. `4 S) w5 H. T    }
    //The main loop
    for (int i=0;i<nRelNum;i++)
, P9 Q7 \2 M) q7 Y1 y( H- H    {
        char a=strRelations[0];
        char b=strRelations[2];
& k! p. q" W/ g) I' s        assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
+ q- K- `9 @+ t6 H" B) O! \3 |  `        array[a-'a'][b-'a']=true;

" [3 x+ \4 [  u+ g        Marshall(array,nSeqLen);
: X. q9 B/ }, K
+ B" }! p& n. Q9 I        //Check for Inconsistency after  every relation
        for (int m=0;m<nSeqLen;m++)
        {
            if(true==array[m][m])
            {
                cout<<"Inconsistency found after"<<i+1<<"th  relation!"<<endl;
/ _5 L0 J* ?  J4 g                    delete []strRelations;
                    for(int k=0;k<nSeqLen;k++)
1 T1 o* D# w/ V8 M4 N                        delete []array[k];
! S8 r; ?8 P3 x                    delete []array;
                    delete []Seq;
2 [# t% q3 U" r! J% {& T# T& N! Z                    return 0;

; `( g" U' L  o5 W0 i            }
+ P+ h# x1 a8 y* l3 {        }

; e# N- N2 i; L" l        //Check for the determined sequence after  every relation   
+ b6 K% ?( m$ o, u8 l& f        for (int j=0;j<nSeqLen;j++)
0 Z) }: @+ I7 ?# m6 [        {
            if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))
            {
                cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;
                delete []strRelations;
9 f- ~" H& _5 @, P' {                for(int m=0;m<nSeqLen;m++)
                    delete []array[m];
                delete []array;
                delete []Seq;
                return 0;
5 V( d% m9 T: K: N/ A: A3 ?" O            }
        }

# t; R$ L, g# h/ c# b
. @8 G! B4 `4 C; `8 G    }
    //If the program has come to here ,then the relationship hasn't been determined!!!
    cout<<"The relation can not be determined!"<<endl;
    delete []strRelations;
    for(int m=0;m<nSeqLen;m++)
8 l& b- E9 R0 B7 O1 y7 T+ h, b        delete []array[m];
4 E; g! ~# T1 j( n% A* w* D5 J    delete []array;
+ `! E% T0 d2 G    delete []Seq;
   
; \9 C# f: V  \0 M1 o4 K    return 0;
& C& e- N1 b. r, T; r$ h5 h7 Q0 D}
" v) M! h# \" Q5 E; V
程序解题二：#include"stdio.h"
: O4 N* S" k$ O. a8 pvoid main()
8 r) E; g# x( I  F{
    int n_m[100][2];
9 |8 }: U3 V; v$ V' g5 K- _8 I$ k* n    char re[1000][3],
! z. r7 W) L* F- M6 w) x  f( ^    temp[26];
3 u) ?0 M9 B6 U+ {8 R    int i=0,j=0;
$ G& \& Z: s, c- W    scanf("%d%d",&n_m[0],&n_m[1]);
; o( ^) P, H9 t" K+ c3 [# t    for( ;j<n_m[1];j++)
: }+ d& {. r# y: i/ y) b; `    scanf("%s",&re[j]);
    while(n_m[0]!=0&&n_m[1]!=0)
    {
" c- f! K0 h+ x( Q' F. t( p    i++;
$ l/ D! w) b) B# Z    scanf("%d%d",&n_m[0],&n_m[1]);
    for( int f=0;f<n_m[1];f++,j++)
    scanf("%s",&re[j]);
    }
/ }/ [' Y8 t5 E9 {# R    i=0;
- f% }* u% q$ ~$ c" X- q" h  q& a    j=0;
' d8 g' \7 M# O. C   for( ;n_m[0]!=0&&n_m[1]!=0;i++)
& ~: i7 V9 s3 o4 n5 H; u3 R% l5 t    {
       int a=0,b=0,l=1;
% |: ?3 w3 S# L1 c       for(a=j;a<j+n_m[1]-1;a++)
& o; D5 J+ K+ ~; O5 E# N8 [3 N         for(b=a+1;b<j+n_m[1];b++)
  J  ]- k; {  H4 [, E8 |         {
              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;
  _* f7 Y. _$ X. f0 k            printf("Inconsistency found after %d relations.\n",n_m[1]);
            break;
            }
' X) j4 Y+ }' \3 F1 @- Q3 Q         }
      if(l==0)
: f$ B) B" E! i  w' `! N          continue;//Inconsistency found after x relations.
# Z7 Y% \6 I5 d7 a* j. i8 I    else{
           if(n_m[1]<n_m[0]-1)
! P1 S; M8 y/ X# Y- R( `        {
            printf("Sorted sequence cannot be determined.\n");
            l=0;
# w% U2 u) z" `* I; e: Y4 ~4 T        }
' p# m0 R3 J2 T- q, W0 I        else
6 Q. h6 P5 W( F# k9 \% K        {
  d+ r8 E7 V: s) l+ c7 E6 J, E# B  Y* i          if(n_m[1]==n_m[0]-1)
" j9 \6 p) u8 r' ~/ U          {   
              int k=0,p=0;
              for( ;k<n_m[1]-1;k++)
/ V3 W2 R( V9 _! O6 U- m( E8 Z' V5 e                  for(p=k+1;p<n_m[1];p++)
                      if(re[0]==re[0]||re[2]==re[2])
                      {
                      printf("Sorted sequence cannot be determined.\n");
6 y/ g9 P1 r7 d; F0 I                      break;
# H# d$ {3 I$ |9 M                      l=0;
- S) h# C6 s/ |) f8 ?                      }
$ I4 \1 P+ ?& [( V1 u2 M/ w- \8 Q! V          }
        }
/ g" w2 o* G# @# f4 y        if(l==0)
. [, F% Z5 y: b) }        continue;//Sorted sequence cannot be determined.

5 C! C: g- L& R9 ^        else
         {
           
$ t" t. ?: ~! z4 n, g            for(int k=0;k<n_m[0];k++)
3 o. z: `/ M% i" @             temp[k]=k+65;
            for(k=0;k<n_m[1];k++,j++)
0 x- R0 d) c1 h7 o4 C+ W            {
                int t1=0,t2=0;
              for(int s=0;s<n_m[0];s++)
              {
               if(temp==re[0])
                   t1=s;
2 U# h) e( ~- j) h8 M) M* ?                      if(temp==re[2])
                   t2=s;
              }
              if((t1>t2)&&re[1]=='<')
              {
                char t3=temp[t1];
# c: Z- C+ t+ d) e. U                temp[t1]=temp[t2];
2 L" S1 Z' P, _7 f+ L1 M3 y! _                temp[t2]=t3;
/ ~0 S& k4 D" V! S$ b              }
            }
        int count=0;
; v2 z0 M) a. ]% a8 G        for(int s=0;s<n_m[0]-1;s++)
' y! P( w+ A% Z6 N8 Z+ h; j        for(int d=j-n_m[1];d<j;d++)
            if(re[d][0]==temp&&re[d][2]==temp[s+1])
            {
! i6 W/ a# J) B1 y                count++;
                break;
. h; C4 V& Z0 b" @& H# Q% M            }
            if(count==n_m[0]-1)
            {
                printf("Sorted sequence determined after %d relations:",n_m[1]);
                for(int f=0;f<n_m[0];f++)
                  printf("%c",temp[f]);
                 printf("\n");
            }
' i/ r6 [& y7 ]! x8 m, }+ x6 G- _            else
               printf("Sorted sequence cannot be determined.\n");
        }
) d8 k) }# N  X1 e6 T    }
    }
}

4 |6 d& W+ [5 C: P( M: L
7 g" h7 ?# R6 v* k


6 }6 N) d' S  Q
( y. d9 k4 N- ^0 ]% m  H9 ?; f- V
  v7 t$ R/ Z+ ]
4 _' d% ]$ G! H

来源：编程爱好者acm题库