编程竞赛题目（一）

厚积薄发

5 M7 @4 S* \, mSorting It All OutDescription
0 p6 c9 B, `4 h. ~* \! F! g6 }
/ E2 t, v/ A, X/ y. X0 eAn 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

5 ~7 H8 w& y7 O. I" w8 _8 d( q9 ~) kInput 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.
, h5 a0 \* v  t3 A5 s# tOutput

, C* v  A" m' N  w4 Q& A/ s: EFor each problem instance, output consists of one line. This line should be one of the following three:

Sorted sequence determined after ** relations: yyy...y.
Sorted sequence cannot be determined.
' R( e+ x& W* F# n$ m7 Q: ?( yInconsistency found after ** relations.

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.
/ ?: s6 O/ ~7 c! O( p2 t
) E- v7 }' Z! g9 M$ y9 s$ G( t7 R0 U输入样例

+ m* ]) Q8 o6 D8 j% o; U' g4 6
9 v; ^7 ^" ]6 H5 s+ d7 M4 H& iA<B
A<C
B<C
C<D
B<D
A<B
; c' z# f6 K- }7 t/ J1 S3 2
A<B
B<A
4 a- C8 L- d8 G% G4 q, E+ V8 U26 1
A<Z
9 I7 @. z- K; {0 0

/ s$ e4 M; Y* }输出样例

" g7 i! q! s& [) {8 lSorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
$ F- X' ?2 `- T9 m# y0 lSorted sequence cannot be determined.

Source

# M' ]+ K9 F+ m! NEast Central North America 2001

* b7 A& ], g/ `" C$ r7 E6 M2 ^

程序解题1：

//By Jackie Cheung
, ?% t* |9 i% c* N% O4 r#include <iostream>
5 s" d) l; `; d/ |+ c1 }+ s5 f#include <string>
8 b! J) p( B9 m$ ^) I4 W& p& d3 j#include <cassert>
2 X! X: v8 y* l( \4 d; Ftypedef  struct tagNODE
& q. m) E. e! ?3 L" H, W8 @3 ?{
    char val;
    struct tagNODE* link;
}NODE;
' `/ ?7 E8 M& n' H+ v) v6 Yusing namespace std;
void Marshall(bool** arrary,int n)
& F5 w1 ~+ B; [, O{
    for(int i=0;i<n;i++)
    {
+ a9 Q6 j+ o' N1 x9 D( ?  d9 S, [        for (int j=0;j<n;j++)
# \! J. z; f6 x) F, W% @* Y$ ]        {
( `  f" x, Z0 Q$ x6 |            if(true==arrary[j])
- g2 i( r  ?7 f. K                for (int k=0;k<n;k++)
; Z$ t% O% v3 }3 S' v6 C/ L3 R( |                {
& T2 c' o! P6 f, W                    arrary[j][k]=arrary[j][k] || arrary[k];
                }
        }
    }
4 y. u& X' b! Q9 S% q+ y};
, L, i; L' y3 U3 m8 hbool  SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)
0 t* n5 |. s' p) Q. L6 v{
) \/ B3 X7 d9 @8 p3 z- d0 c    Seq[n-nLeft]=static_cast<char>('a'+nIndex);
* ^: X7 k! s* L3 F, T    bool bFlag=false;
    if(1==nLeft)
    {
        Seq[n]='\0';
8 M: ]2 r7 O: d        return true;
% \4 p3 _+ O, M    }
    for (int i=0;i<n;i++)
" Z* s7 r! R& H7 o9 |    {
/ t9 b. [8 w' T8 B1 c8 L' {        if(true==array[nIndex])
/ o* M+ Y7 W) g( `2 e- V1 s        {
& k! F) D; s% ]- t) ]            
2 e" m1 W) H% ]            bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);
        }
( B" z% ?) T' o( \. d        if(true==bFlag)
' Y! u# B3 Z& M1 f            return true;
    }
& y$ h6 S. |3 w+ r) R    return false;
: t, N3 \& ]' e) H/ a! x) Q* W};
int main()
4 Y- R; ]$ C+ R{
, W8 {& s$ Y9 n0 L    int nSeqLen;
    int nRelNum;
: Z  l8 q% C- [! A3 f( n+ V! _    cout<<"Input the length of the sequence:"<<endl;
    cin>>nSeqLen;
    cout<<"Input the number of relations between the elements:"<<endl;
4 L1 ?8 [, l8 i8 j+ [4 y  @    cin>>nRelNum;
    //1:if nRelNum<nSeqLen-1,then the relation can not be determined!
2 T: H5 b1 P/ W* i% ^    if(nRelNum<nSeqLen-1)
    {
5 G, I5 l, c# h+ K        cout<<"The relation can not be determined!"<<endl;
        return 0;
    }
    string* strRelations=new string[nRelNum];
* C; W* r$ {3 T* _    char* Seq=new char[nSeqLen+1];
    bool** array=new bool*[nSeqLen];
# v9 }& Y0 s# T+ n, }6 }- G
    for(int i=0;i<nRelNum;i++)
, `$ I; T& j7 L2 D" d' a    {
        cout<<"Input the "<<i+1<<"th relation:"<<endl;
        cin>>strRelations;
    }
) e- i- \8 Z% v# }" x: b5 b& R3 D' v7 P   
    for (int i=0;i<nSeqLen;i++)
    {
        array=new bool[nSeqLen];
        for (int j=0;j<nSeqLen;j++)
            array[j]=false;
    }
& ]3 z3 v8 x9 P, ^2 c5 Y+ I    //The main loop
& w. g6 C  K" k7 Z* u    for (int i=0;i<nRelNum;i++)
    {
6 E3 j* r5 d/ s! ?1 O        char a=strRelations[0];
/ o& k% o0 |/ j' P8 S$ u        char b=strRelations[2];
        assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
        array[a-'a'][b-'a']=true;

' V4 C: J1 I* M8 O        Marshall(array,nSeqLen);
  z9 b, Y& {; A+ v, ]# S% H. v3 X
        //Check for Inconsistency after  every relation
        for (int m=0;m<nSeqLen;m++)
- U: h" ]* b' u        {
            if(true==array[m][m])
            {
                cout<<"Inconsistency found after"<<i+1<<"th  relation!"<<endl;
1 H0 I2 U# w9 _4 `* m! P/ k6 J. k$ G" `                    delete []strRelations;
                    for(int k=0;k<nSeqLen;k++)
& N7 ]+ U$ ?7 s: a- L                        delete []array[k];
                    delete []array;
4 ^( U" b6 v3 g3 x; K* S                    delete []Seq;
                    return 0;

4 l4 r4 p  e0 m$ R            }
' b  ~+ {, W) S" P; V' Y) p        }

        //Check for the determined sequence after  every relation   
6 R5 U% K4 \7 d" S* P        for (int j=0;j<nSeqLen;j++)
. ?3 y* N6 P! a, J& i2 a' b# t* }        {
            if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))
0 u7 v% o2 A0 Q' Z0 _* l/ ?            {
                cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;
                delete []strRelations;
/ C1 Z$ t/ u9 w- m) E1 i; C                for(int m=0;m<nSeqLen;m++)
2 Z) e2 P+ s4 \                    delete []array[m];
, P# r; _$ {6 s  B                delete []array;
                delete []Seq;
                return 0;
            }
        }
- E5 z  Z+ F1 O9 T8 p) g0 u
: `5 @  u% k% N4 w. j& ~
    }
    //If the program has come to here ,then the relationship hasn't been determined!!!
    cout<<"The relation can not be determined!"<<endl;
8 r0 H( c7 P( |# `% ~8 H    delete []strRelations;
    for(int m=0;m<nSeqLen;m++)
        delete []array[m];
6 Z: C, ]; E: }8 Q4 P# w( g$ W7 p    delete []array;
( @% \5 J. X) G0 x- p1 a$ G6 U% l& \: \    delete []Seq;
   
& z1 U: ~9 B  F# l( }) u    return 0;
}

程序解题二：#include"stdio.h"
void main()
" O- r9 K- F7 p{
9 l/ o4 c7 M3 o' ]( L# d" j    int n_m[100][2];
2 ^" \4 U1 O4 [" H7 @. I8 L1 I    char re[1000][3],
    temp[26];
    int i=0,j=0;
) l3 }- ~4 k' W    scanf("%d%d",&n_m[0],&n_m[1]);
/ Z: E, A1 o& V3 ]    for( ;j<n_m[1];j++)
    scanf("%s",&re[j]);
    while(n_m[0]!=0&&n_m[1]!=0)
    {
    i++;
    scanf("%d%d",&n_m[0],&n_m[1]);
% \* m! j/ M6 `# X    for( int f=0;f<n_m[1];f++,j++)
) b0 ?7 Q' f. \- T    scanf("%s",&re[j]);
    }
( Y: S* V6 v  Z- A9 k3 ?- Y! m    i=0;
9 t" t; C% Y, d    j=0;
   for( ;n_m[0]!=0&&n_m[1]!=0;i++)
    {
1 U7 C; k8 F& u4 ^& [       int a=0,b=0,l=1;
' P: P$ n8 J" u+ q. }. V; \! m       for(a=j;a<j+n_m[1]-1;a++)
         for(b=a+1;b<j+n_m[1];b++)
         {
              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])
            {
, X, V- b* o/ |/ h& I0 _* g2 j4 T            l=0;
            printf("Inconsistency found after %d relations.\n",n_m[1]);
2 C; k: Z! x  s2 A3 l            break;
            }
         }
$ ?1 p1 D7 a. N9 M9 H7 {4 T      if(l==0)
8 b2 ^& v2 g) t0 `7 N( }          continue;//Inconsistency found after x relations.
- k2 Z8 Z7 B' t# Q    else{
+ ]0 |2 c( v0 k5 o           if(n_m[1]<n_m[0]-1)
* h) z) @0 Y+ N2 y4 k2 T0 \        {
            printf("Sorted sequence cannot be determined.\n");
7 e1 m2 R, g) Y! V; S0 l            l=0;
& g, l; _3 \) M        }
. c# _+ H% i7 v# W& _0 C- [$ s0 P        else
        {
          if(n_m[1]==n_m[0]-1)
          {   
              int k=0,p=0;
' w& {2 h# Q) y0 D: T  x; B              for( ;k<n_m[1]-1;k++)
8 L" ?2 J' Q! b4 o9 h, t                  for(p=k+1;p<n_m[1];p++)
                      if(re[0]==re[0]||re[2]==re[2])
; ~" x6 J* ^( i, r                      {
                      printf("Sorted sequence cannot be determined.\n");
4 n5 M; u9 o. I/ F$ q& [8 f+ @: K                      break;
                      l=0;
! P2 ^8 W) N' q- O/ p                      }
          }
        }
! p1 _& b  @" u9 p9 u- {$ ?        if(l==0)
        continue;//Sorted sequence cannot be determined.
' d+ p  {+ M: X: c
        else
         {
# S* _: u$ {, \( A5 e           
5 Q! }% L* O; f) D' C% c) i            for(int k=0;k<n_m[0];k++)
$ f9 L4 }* N* W* N8 f7 b# ^             temp[k]=k+65;
            for(k=0;k<n_m[1];k++,j++)
: B  X  d1 f: b, q7 {* E) U$ P' o            {
( Z! k6 S9 s' f                int t1=0,t2=0;
              for(int s=0;s<n_m[0];s++)
              {
( n) d# P/ k7 m' N. \( G+ b               if(temp==re[0])
                   t1=s;
                      if(temp==re[2])
% m, m- ~5 x( a7 H" |7 q                   t2=s;
$ @# F8 F! q$ E  t              }
              if((t1>t2)&&re[1]=='<')
( F1 D9 l) f/ o! u  H              {
                char t3=temp[t1];
                temp[t1]=temp[t2];
$ u% d0 H3 P: X                temp[t2]=t3;
              }
% n/ K5 }- E0 j% Z# K            }
        int count=0;
        for(int s=0;s<n_m[0]-1;s++)
& ^2 v) l$ `/ P3 l        for(int d=j-n_m[1];d<j;d++)
            if(re[d][0]==temp&&re[d][2]==temp[s+1])
2 J/ i; V- V7 S  F# w& _            {
, ^  V/ c) e; Q5 @                count++;
. W" `3 S# V) M; `7 I                break;
, j- b: F3 L6 V4 P- a. R4 h            }
1 ], A6 z, J, E* C4 Q            if(count==n_m[0]-1)
2 d& ^1 P: `0 T: d            {
                printf("Sorted sequence determined after %d relations:",n_m[1]);
+ g0 e2 ~3 D. [- U3 a* a7 d0 z( t                for(int f=0;f<n_m[0];f++)
: V7 Z5 n3 N5 i. e8 C                  printf("%c",temp[f]);
                 printf("\n");
+ t: z- ?, [4 s$ S% G            }
            else
5 H$ {" ]% t+ @' \( h) b               printf("Sorted sequence cannot be determined.\n");
( g6 \: \1 ]+ W* x0 \        }
2 w/ G* w2 J9 g6 S( E' }3 z* A    }
    }
}
/ g. y! H* H3 f4 M1 E
0 [! Y# x7 e$ Y' u' V2 J+ B
& r% x+ W. Y" v3 f5 c
5 ]2 }; W- ]4 S6 J4 E! D6 z
0 V& C" L. i7 r- ^. Y

来源：编程爱好者acm题库