编程竞赛题目（一）

厚积薄发

( M7 |4 \& Y/ B- d2 y; N1 s, |
( i% H5 C4 _% T9 I8 R- R/ Z: W- PSorting It All OutDescription

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.
; Z: ?1 q4 V) V. k7 h4 oInput

& q* T7 r* l0 zInput 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

For each problem instance, output consists of one line. This line should be one of the following three:
& e0 Q1 J$ L$ j
Sorted sequence determined after ** relations: yyy...y.
Sorted sequence cannot be determined.
Inconsistency found after ** relations.
8 @9 ?" x- F2 g5 ?3 ~; E
6 c: ?( \5 K$ B. U* r" S/ Owhere ** 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.

% H5 K, x: C5 j/ F8 D输入样例

4 6
( x% ]' e. ^8 PA<B
A<C
B<C
* A( {3 V1 \; y* iC<D
B<D
9 ?# w" v% I: u  g' DA<B
9 a. }5 t+ W, B7 n( c. f% @3 2
A<B
B<A
26 1
6 @0 G' i5 h1 t2 DA<Z
0 0
1 a4 i/ @9 p8 b0 k6 s

' h. l" @, ^# U! b3 _" S2 K输出样例

1 V5 R: Y# x+ |2 ZSorted sequence determined after 4 relations: ABCD.
- R1 o8 l2 s& Q. M) L2 w9 h" QInconsistency found after 2 relations.
Sorted sequence cannot be determined.

9 u+ _$ l% h& w9 e8 B

Source
$ s) o$ i3 g1 w4 |
East Central North America 2001

程序解题1：

& P# ^7 ]9 l; q1 j7 E- l//By Jackie Cheung
#include <iostream>
#include <string>
( X9 c* F& ~. W- s  B2 X' A#include <cassert>
typedef  struct tagNODE
{
    char val;
    struct tagNODE* link;
}NODE;
using namespace std;
. G2 y  R- h9 K- @! Z& G9 }void Marshall(bool** arrary,int n)
% m% T3 H% `  L0 R  i, k5 h{
/ Q) V% [6 y5 C, ^    for(int i=0;i<n;i++)
/ w9 ~7 o; p& X7 H" @    {
        for (int j=0;j<n;j++)
2 [& D+ t/ N6 b3 R        {
, [& R/ Z/ F) p( J" U            if(true==arrary[j])
: O$ X' G4 |4 y% }0 e' u                for (int k=0;k<n;k++)
$ H- v" |$ Q( u* q( T7 K" i                {
                    arrary[j][k]=arrary[j][k] || arrary[k];
; v) S+ z  Z% p' O                }
& B2 I+ Z: n* [        }
    }
};
" s1 A7 Q! [4 f1 pbool  SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)
{
    Seq[n-nLeft]=static_cast<char>('a'+nIndex);
    bool bFlag=false;
/ ?' u9 W& C$ ^  z# e8 x% k    if(1==nLeft)
8 _: a: M; d) O    {
" i. y8 W; |/ B( P6 W        Seq[n]='\0';
" c* D6 r7 n$ h' |7 F        return true;
) Q1 J$ k( b' s4 X* H5 ^    }
2 g, x$ F. Y3 [5 C3 j) d& G  Q    for (int i=0;i<n;i++)
    {
        if(true==array[nIndex])
        {
            
            bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);
        }
1 J" w# C, T. E2 i8 I* l9 Q        if(true==bFlag)
            return true;
4 l; y; V0 G4 S9 t    }
    return false;
};
$ q; v) l8 O  Dint main()
{
  m# l1 p! d  P+ G7 j    int nSeqLen;
+ c/ C/ t, x- z' d  ^& l; P5 l    int nRelNum;
    cout<<"Input the length of the sequence:"<<endl;
/ Q& w6 r, n% f5 G$ u# X    cin>>nSeqLen;
    cout<<"Input the number of relations between the elements:"<<endl;
$ n- h& g# ^+ g; r; X5 m    cin>>nRelNum;
7 f) S% Q+ F9 t. j6 x/ m    //1:if nRelNum<nSeqLen-1,then the relation can not be determined!
    if(nRelNum<nSeqLen-1)
    {
( c8 y2 ~- x' W3 a6 J4 Q; _        cout<<"The relation can not be determined!"<<endl;
5 F9 \; ~4 P- U' v& h        return 0;
    }
    string* strRelations=new string[nRelNum];
    char* Seq=new char[nSeqLen+1];
8 A/ d% B. j! O8 g5 M    bool** array=new bool*[nSeqLen];
6 n+ W  }! z; U" u2 Y( g
8 L1 c- f( A; J' q# x% j, h  k    for(int i=0;i<nRelNum;i++)
% l( e7 H/ T2 _4 I0 F5 _7 Y" s% d    {
4 i! z. D1 ?+ e- x6 c8 k        cout<<"Input the "<<i+1<<"th relation:"<<endl;
- A* r' E6 {. @        cin>>strRelations;
9 ~: Y) }5 Q' C: b" l    }
   
0 U; H' e7 y" w, m    for (int i=0;i<nSeqLen;i++)
    {
( ~; W6 ^2 C  m% ]3 Q        array=new bool[nSeqLen];
. k! M4 `7 k; n" y        for (int j=0;j<nSeqLen;j++)
0 i. W6 G0 ^# A1 i% a            array[j]=false;
, H6 ~2 ^* q* p2 q    }
    //The main loop
    for (int i=0;i<nRelNum;i++)
% s% Q7 Q1 Y% `    {
        char a=strRelations[0];
        char b=strRelations[2];
( q" @9 u: Z6 q  q        assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
        array[a-'a'][b-'a']=true;
4 x$ |' @" s! y( V! e6 ?0 t+ d
        Marshall(array,nSeqLen);
7 B/ n7 @; m* Q" _) _9 \3 P
( t  M  }  `7 x% m5 L" z5 V        //Check for Inconsistency after  every relation
        for (int m=0;m<nSeqLen;m++)
        {
            if(true==array[m][m])
            {
- U  y) b2 u  R' Z( C                cout<<"Inconsistency found after"<<i+1<<"th  relation!"<<endl;
                    delete []strRelations;
                    for(int k=0;k<nSeqLen;k++)
                        delete []array[k];
5 `0 l" H7 u- z$ D9 ^                    delete []array;
                    delete []Seq;
                    return 0;

8 T1 H) Z. j$ }4 @6 r            }
        }

& ~% c# _! ]8 Y5 @1 Z9 [        //Check for the determined sequence after  every relation   
6 ~8 A" s$ a8 _. `8 Y        for (int j=0;j<nSeqLen;j++)
9 Q& q: ~) I4 n; e0 s" W6 [7 |, J9 z        {
            if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))
            {
                cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;
, p& _& _+ ^2 |  D$ y                delete []strRelations;
                for(int m=0;m<nSeqLen;m++)
                    delete []array[m];
                delete []array;
                delete []Seq;
! l" j3 u$ m& h( e2 m                return 0;
            }
        }
2 x. q1 W( T: A" A3 F

, w! ]; {/ E2 U    }
    //If the program has come to here ,then the relationship hasn't been determined!!!
    cout<<"The relation can not be determined!"<<endl;
    delete []strRelations;
' X; M/ A8 F- i. @+ d8 k. U    for(int m=0;m<nSeqLen;m++)
        delete []array[m];
    delete []array;
    delete []Seq;
   
2 _, e" q2 c- l9 [/ A; D$ C    return 0;
, Z# I* |& }7 X0 {: j% U}
! R* U- l! L- S( k+ D( F
程序解题二：#include"stdio.h"
# G) u5 f" f3 j; g1 Y3 h5 Svoid main()
7 q$ l) H# p3 Z2 ~" N" F0 K{
    int n_m[100][2];
; [9 r( v- h& k    char re[1000][3],
0 u1 T0 Q9 X- X+ h0 S) T) s    temp[26];
    int i=0,j=0;
    scanf("%d%d",&n_m[0],&n_m[1]);
8 x, L; L. ?/ _: M* v# D( x    for( ;j<n_m[1];j++)
    scanf("%s",&re[j]);
  ?* l- b; _% x$ `. l    while(n_m[0]!=0&&n_m[1]!=0)
, Q% R0 _: L4 t% B" f0 v    {
    i++;
6 p0 z- T1 s& y% k' H, D9 ?/ e    scanf("%d%d",&n_m[0],&n_m[1]);
    for( int f=0;f<n_m[1];f++,j++)
    scanf("%s",&re[j]);
    }
& J! E5 g' y8 u2 j    i=0;
    j=0;
/ R6 O# L( u9 c; U' S. O   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++)
         for(b=a+1;b<j+n_m[1];b++)
         {
; N8 b% j6 j  u3 E2 Z              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])
            {
* N% K  s( R: @9 |            l=0;
. o# @% T4 S" k            printf("Inconsistency found after %d relations.\n",n_m[1]);
            break;
9 Y- i3 J& t9 R) k& J4 m; J            }
         }
      if(l==0)
6 {. ?6 x) b! v: c) o          continue;//Inconsistency found after x relations.
    else{
           if(n_m[1]<n_m[0]-1)
! E1 z5 ]; ]0 X& q. z/ k        {
            printf("Sorted sequence cannot be determined.\n");
            l=0;
# e+ |4 u, p0 O        }
! B3 R: T+ Y6 U. u7 I2 W        else
4 Y3 s4 u' v2 H  [3 u' K        {
          if(n_m[1]==n_m[0]-1)
          {   
              int k=0,p=0;
! ^. Q; n9 K2 T: h! c              for( ;k<n_m[1]-1;k++)
                  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");
! N- ~, q5 w8 V/ a                      break;
                      l=0;
                      }
          }
        }
        if(l==0)
8 X/ E2 h8 ]" O: s        continue;//Sorted sequence cannot be determined.

- W4 v) i' |' g( x6 I6 l6 A$ O( A2 J        else
0 _! f( `7 Y8 u* O3 w% t( K) H         {
9 k1 w( r; c# B/ b% s) X( U           
            for(int k=0;k<n_m[0];k++)
* W( K* K/ t* I1 R4 I             temp[k]=k+65;
- r% |# @8 t% S' W; r: {- e) S            for(k=0;k<n_m[1];k++,j++)
            {
0 \- J$ X3 P) @$ n5 Y1 K0 C; Y; @4 t                int t1=0,t2=0;
1 [+ D4 w& `. ^, i: h4 Z& \              for(int s=0;s<n_m[0];s++)
              {
$ t8 F; d6 I- z6 H! ~8 o; L               if(temp==re[0])
                   t1=s;
+ F9 y; M/ l" M6 r' R0 |; R                      if(temp==re[2])
( G4 r7 k  x: o  {% O                   t2=s;
              }
              if((t1>t2)&&re[1]=='<')
              {
                char t3=temp[t1];
" L7 y6 O1 O2 S                temp[t1]=temp[t2];
2 n) v& V! _6 v* S8 C0 o2 x+ b                temp[t2]=t3;
              }
            }
8 W) {. M/ n: ?9 x% j( ^        int count=0;
; P) M8 |' c% ~" d: x( ^2 y        for(int s=0;s<n_m[0]-1;s++)
0 N& P7 m0 l6 z6 @- a7 I/ p% O        for(int d=j-n_m[1];d<j;d++)
" C/ |0 |3 v9 t0 }            if(re[d][0]==temp&&re[d][2]==temp[s+1])
; v) {8 l( ^* C            {
* t8 G. C1 i+ J7 h- K/ S                count++;
0 `; X7 ?4 P3 b                break;
  K0 y# T' Q* q4 M0 \+ {! T            }
8 w2 o5 x( ^5 Q4 r2 R- i/ o            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++)
0 G$ v6 b  B1 N3 @' k- ?- d/ j- ^& W  F                  printf("%c",temp[f]);
1 U, m% k& X& C( e% {3 p                 printf("\n");
            }
            else
               printf("Sorted sequence cannot be determined.\n");
        }
6 Q- E& D& {- h# I    }
    }
}


& r$ e5 b0 N6 n
+ g2 b; t5 l& a5 K9 |


% I  P5 j3 _% C9 @# |( r

来源：编程爱好者acm题库