编程竞赛题目（一）

厚积薄发

* Y% R$ T( O" W9 V! S" |8 @
Sorting It All OutDescription
/ \  b: v9 N# o, O* L8 I8 x
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
+ Z& t( M4 [# {
2 |8 ]" {1 g. W+ k! U; p2 j1 Q1 oInput 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.
8 n* ]$ p- e4 Y; aOutput
. s2 d  s1 I6 G& Z" j0 J" m+ r
7 I+ g% I- h+ r# kFor each problem instance, output consists of one line. This line should be one of the following three:
2 u; k7 r9 L( w0 s
Sorted sequence determined after ** relations: yyy...y.
6 S7 u) @) ?$ }: a3 J% c' eSorted sequence cannot be determined.
6 u( s* a+ _0 O/ R& B- N1 gInconsistency found after ** relations.
( J) F8 P: \% ^0 y4 _  ]
$ z6 g' D: b4 x7 B3 K0 w+ G- ?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.
# ^6 p$ e% v" H. U2 z; {
& Q& G$ T5 B* |5 f- m$ w4 K, ~输入样例

% y4 u( v7 v  Q6 q4 M% h' d+ \4 6
4 b" s# Z2 @5 S- }( X2 B: p0 z/ Z. q9 eA<B
/ K: N9 w1 I' j- V# p- G  D' lA<C
4 w9 p) ?3 }7 ~! eB<C
- o+ Q) d+ L+ `  pC<D
+ i) o0 p7 r" f$ B2 dB<D
A<B
3 2
* ]. o2 c7 T- m: A3 Z3 b# XA<B
4 |, g- S$ B# E" Y/ uB<A
1 s- E, y6 l) V+ E4 C2 c: x26 1
A<Z
0 0

输出样例

6 I. b9 G3 u; v( fSorted sequence determined after 4 relations: ABCD.
- K$ S; Z: l8 T  h- G" Q, `Inconsistency found after 2 relations.
, Q8 ~% s0 e+ {7 }  @" L* z9 pSorted sequence cannot be determined.

Source
: ]$ f! {2 o7 R* C: j8 L4 g
East Central North America 2001

# ^- M% G+ Y* k: \/ o, K+ m8 X/ I

程序解题1：

# S! w& n5 M+ }1 [  T//By Jackie Cheung
3 q5 R- x8 r1 g& |5 j0 k& w1 F#include <iostream>
#include <string>
#include <cassert>
: w* x' g% G8 D* Stypedef  struct tagNODE
- x# r. P+ |6 o  @5 S9 D) h" Y{
* k& t& z% c( }; c, U8 V8 Q# c" [    char val;
3 K8 E  [2 a+ b3 ^2 B9 Y2 m* v) R    struct tagNODE* link;
}NODE;
using namespace std;
3 E2 i( X! k( U6 C1 }void Marshall(bool** arrary,int n)
{
2 d! U! {  a( L- K2 }! ~9 b    for(int i=0;i<n;i++)
, O# e& r2 u) Z  L& K$ W    {
        for (int j=0;j<n;j++)
* j: @( ~) q) W6 Y% N( s5 x        {
            if(true==arrary[j])
" _5 ?( H9 \, q& b9 H2 K- t                for (int k=0;k<n;k++)
                {
                    arrary[j][k]=arrary[j][k] || arrary[k];
                }
  S# E! [) J) N( B, f4 s7 i6 j. z7 f4 [/ v        }
8 R5 f0 U# L& h; o' X  x2 A9 Z    }
};
( O" G1 ~# ^0 r2 K) x* _6 \bool  SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)
{
$ l9 N- |# L7 X8 _- q7 d    Seq[n-nLeft]=static_cast<char>('a'+nIndex);
& p. D" l. T5 Y  {    bool bFlag=false;
    if(1==nLeft)
    {
3 ]" ~7 ]: H. ^8 K2 @/ L" g- ~" ^        Seq[n]='\0';
% \# f! P2 O  E- C        return true;
1 L9 g8 Z7 H5 c    }
2 F& o, T/ w/ P. f4 F    for (int i=0;i<n;i++)
    {
) e/ O+ |% R  ~0 N        if(true==array[nIndex])
        {
            
            bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);
        }
  I' u6 `: j2 W        if(true==bFlag)
            return true;
    }
! b& H( Q7 v6 S  r, r7 n" G    return false;
" E8 H/ a7 u" {0 ^  i: j};
( W' y" v' d) H* gint main()
{
9 Z' f/ ^2 p# U% V    int nSeqLen;
$ G. K9 I+ L: B    int nRelNum;
  @5 N' B; b; Y1 u2 ?    cout<<"Input the length of the sequence:"<<endl;
    cin>>nSeqLen;
    cout<<"Input the number of relations between the elements:"<<endl;
0 S  U5 c- ~2 b6 S5 c7 j    cin>>nRelNum;
    //1:if nRelNum<nSeqLen-1,then the relation can not be determined!
    if(nRelNum<nSeqLen-1)
: D8 ?; P7 W! u1 g7 B% I/ ]$ V    {
! |3 y  `! f% q. ?        cout<<"The relation can not be determined!"<<endl;
2 i+ c9 d# h- C6 f        return 0;
    }
' H( E9 U+ I: ^( n/ ?: ~    string* strRelations=new string[nRelNum];
! j# N1 m3 I* p7 a+ W8 ]/ S3 ?' g    char* Seq=new char[nSeqLen+1];
; _: w4 r4 y+ |; ?+ ?    bool** array=new bool*[nSeqLen];

% r6 _# n6 B  o, ?' T4 q7 i" u    for(int i=0;i<nRelNum;i++)
    {
+ t" Q3 x* \9 d& r1 D        cout<<"Input the "<<i+1<<"th relation:"<<endl;
        cin>>strRelations;
    }
* d1 f) w2 k+ k2 e0 F   
9 t% a4 X& F. T  J3 |; R" M4 @' i    for (int i=0;i<nSeqLen;i++)
& v1 U/ I1 `' D    {
* {% Q0 C( d# P" |, D        array=new bool[nSeqLen];
        for (int j=0;j<nSeqLen;j++)
4 W, [2 u6 c% x- b/ t/ J            array[j]=false;
# Q0 X1 Q1 ^) D  b. Z( k# p    }
  s% x7 u9 Z2 l9 ?% T; a    //The main loop
/ b$ S/ {0 f3 z, Z" r    for (int i=0;i<nRelNum;i++)
* r: d& i; b6 m( l+ r  F* r; C    {
        char a=strRelations[0];
; U! N. @5 C1 ^4 ?7 f3 ^        char b=strRelations[2];
4 V9 T" U1 w5 f* E* E$ [- b        assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
        array[a-'a'][b-'a']=true;

        Marshall(array,nSeqLen);
$ H! j, A" E% s$ @1 C0 }
+ V" J0 n3 }: g7 s/ Q/ @; O        //Check for Inconsistency after  every relation
        for (int m=0;m<nSeqLen;m++)
9 X) y) R, q8 {6 d        {
            if(true==array[m][m])
9 l1 V* Q! K6 i9 Y: p+ Y" K            {
- I% {& C! B. e( b* k7 W                cout<<"Inconsistency found after"<<i+1<<"th  relation!"<<endl;
4 Z6 `1 r0 C( j6 Q; w                    delete []strRelations;
                    for(int k=0;k<nSeqLen;k++)
! t: \. f5 _- l) F7 a                        delete []array[k];
* T; Q; z: j( ~( |                    delete []array;
                    delete []Seq;
                    return 0;

            }
        }
2 m+ y. b, l# J( P
        //Check for the determined sequence after  every relation   
        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;
0 x1 t. l6 x4 ?& I" Y                delete []strRelations;
. F$ \% g6 Q4 }3 n  D                for(int m=0;m<nSeqLen;m++)
                    delete []array[m];
8 F- B$ [7 k* z! g0 d                delete []array;
, u3 c7 I  k* N" w                delete []Seq;
! o: R0 s0 a1 w! [2 [                return 0;
            }
        }
6 V+ r: _) \2 ^* T. G- f
/ r, t; T' f. L: N8 D7 ^. k
9 Y' f% w7 W) y! _    }
    //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++)
& o8 p+ R" P: ~, r: u        delete []array[m];
    delete []array;
    delete []Seq;
* ]: \0 [: v: R. H+ U   
: S" b/ V9 V/ d$ y    return 0;
}
/ `* |3 ^0 f- f3 S) f
; J8 i/ Y* [% j  m8 E程序解题二：#include"stdio.h"
void main()
{
* d7 Y4 o. U5 T5 E! E2 U( z' _- J    int n_m[100][2];
    char re[1000][3],
    temp[26];
' i9 Q0 o2 Q7 i% |( }& @  {2 y4 J3 Q  y    int i=0,j=0;
2 d' P( e& m1 S0 H% l7 m( y) d    scanf("%d%d",&n_m[0],&n_m[1]);
3 y) a( \# Z- Q7 L/ t3 j    for( ;j<n_m[1];j++)
: G  h2 m9 @# i* Q    scanf("%s",&re[j]);
& m0 a& I1 Z% y, I. u$ t    while(n_m[0]!=0&&n_m[1]!=0)
; @' r% q6 [6 I# ~( [    {
    i++;
) }& i1 c4 W6 ~    scanf("%d%d",&n_m[0],&n_m[1]);
3 m" c# x' Q  I* H1 R2 J! \- N    for( int f=0;f<n_m[1];f++,j++)
    scanf("%s",&re[j]);
! L- L! y8 x5 L2 b$ ^- V    }
2 c( b$ Y% V6 t3 o    i=0;
& g, n1 s8 S5 a: i; t    j=0;
7 ]# _$ B: I+ S. M: y  b   for( ;n_m[0]!=0&&n_m[1]!=0;i++)
    {
* W. i- s3 A# c3 u" i       int a=0,b=0,l=1;
/ F; y0 r9 b/ Q' q5 U# J       for(a=j;a<j+n_m[1]-1;a++)
         for(b=a+1;b<j+n_m[1];b++)
         {
; z6 M/ P+ T  _1 O              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;
" c# g3 a9 y" Z* |6 u0 b            printf("Inconsistency found after %d relations.\n",n_m[1]);
4 g, F! y3 x6 O* [9 ?            break;
            }
         }
) e, ?5 t" W  o3 ^      if(l==0)
          continue;//Inconsistency found after x relations.
    else{
9 w) B! g0 C+ l$ \6 h+ Y+ m' Q' f           if(n_m[1]<n_m[0]-1)
        {
/ P7 k3 e" l7 y5 O* \) V* F            printf("Sorted sequence cannot be determined.\n");
# c8 l2 \9 G; w$ v& o7 [$ N            l=0;
        }
4 e" U# \. O% r8 c  ]1 t9 B        else
! ^3 K, Q6 ]" E5 G% K; o$ l        {
          if(n_m[1]==n_m[0]-1)
* T* M9 T, A9 V9 ]3 Z1 L          {   
* I5 p) }& M5 c5 U7 y              int k=0,p=0;
              for( ;k<n_m[1]-1;k++)
                  for(p=k+1;p<n_m[1];p++)
& i( ~# C1 ~0 x- z% w4 J' d                      if(re[0]==re[0]||re[2]==re[2])
+ I5 ~& y5 [$ i8 E                      {
) V! p% F4 x1 K5 V: X                      printf("Sorted sequence cannot be determined.\n");
# n0 F" m) ~& ]7 @                      break;
                      l=0;
4 M0 T& G; I( }/ W+ X; z& T                      }
          }
        }
        if(l==0)
" A( h' X3 H! J5 `0 \7 I7 f        continue;//Sorted sequence cannot be determined.

        else
: |% D! X4 e* b/ f8 x; s7 h% H         {
           
, G+ G+ Z" A- ]            for(int k=0;k<n_m[0];k++)
             temp[k]=k+65;
2 i" l8 Q6 U! D            for(k=0;k<n_m[1];k++,j++)
3 p6 `0 q; S5 z6 Y( |& ]7 j1 D. b            {
2 G' ^% ]! L% U- E                int t1=0,t2=0;
% \5 I0 L2 M7 u              for(int s=0;s<n_m[0];s++)
' G4 x9 x2 V3 w+ g1 |              {
: V6 n4 v) c+ l' I& d6 ^; J- L' U( V) q               if(temp==re[0])
1 t3 s" T" d: g4 Q7 S! p                   t1=s;
/ p' D. H2 v* X5 F$ `* m  d                      if(temp==re[2])
                   t2=s;
6 g; e1 b& A6 ~) k8 e2 [- }/ \              }
              if((t1>t2)&&re[1]=='<')
              {
                char t3=temp[t1];
                temp[t1]=temp[t2];
                temp[t2]=t3;
              }
            }
* |+ y0 u% z5 q- @9 n        int count=0;
3 D8 ?: S2 d+ T" K( n" ~        for(int s=0;s<n_m[0]-1;s++)
* C! s) @% R# I( @/ `2 t: h        for(int d=j-n_m[1];d<j;d++)
* q, {2 _$ B1 Y2 D( U            if(re[d][0]==temp&&re[d][2]==temp[s+1])
- a- b1 h7 [* h6 A$ b" e7 ]            {
                count++;
2 c" E1 ?; B: z" K% b5 r! |                break;
4 F( S3 K. l, s* w: J( O            }
: x1 p4 l( Z% `$ \% |            if(count==n_m[0]-1)
) g- ^+ n+ Y3 M' A9 ^- @            {
                printf("Sorted sequence determined after %d relations:",n_m[1]);
+ Y5 u, ~6 P, C" a6 P                for(int f=0;f<n_m[0];f++)
3 D; E2 U  S9 W) e8 X2 \9 g                  printf("%c",temp[f]);
6 @5 n" X! `) }9 y1 \7 S                 printf("\n");
# Q( {: C' ]3 r3 y            }
            else
: V  Q/ s. q+ c! F# E% D               printf("Sorted sequence cannot be determined.\n");
        }
    }
; V' t9 ^. O  L    }
2 R3 o, \: o! H}


$ Z, s# ~8 U* l. K) a* ]0 B

# }- p6 c7 K( |+ ?* u3 T



+ l. Z4 ~" \# E. c4 \

来源：编程爱好者acm题库