编程竞赛题目（一）

厚积薄发

3 u# a: g7 s. b; bSorting It All OutDescription

; p7 B3 t0 m. b8 ~1 _# T) t% zAn 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.
0 g$ }# h: m% S. _Input
7 B3 m! K2 p" p- P* s% k
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.
Output

For 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.
Inconsistency found after ** relations.
5 Z1 J7 D0 O9 F0 M9 ]+ e# M9 H! n+ \6 X
- B' Y! X" `% X' f* ]( dwhere ** 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.

- R! X/ `4 ?# _8 o! H8 L, n1 U! M输入样例

4 6
A<B
A<C
  }' m5 G% A+ q7 b2 q( F! cB<C
C<D
B<D
A<B
3 2
A<B
B<A
& Q& B- W" c1 v) A* Y26 1
A<Z
0 0
0 J  b( f$ A* Z7 B. B2 M1 p0 P

输出样例

Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
; w) u* D% I% ^$ e" jSorted sequence cannot be determined.

Source

* n8 s0 f; q- @9 G. H- `7 dEast Central North America 2001

. [$ m( V+ G% K# g  Z- j1 E

程序解题1：

3 ~/ F1 h5 R" q9 Y4 }* [//By Jackie Cheung
" ^' k! i! W5 |. N#include <iostream>
#include <string>
; F$ j8 u  ?% g. a1 y  A#include <cassert>
typedef  struct tagNODE
{
    char val;
    struct tagNODE* link;
6 W9 d8 f, {; r/ O}NODE;
. u- f: y6 O- \4 k- }8 k2 ^using namespace std;
void Marshall(bool** arrary,int n)
{
% m# T* j0 T5 e% P$ x9 \! n9 f    for(int i=0;i<n;i++)
    {
7 X, M: L5 l4 a0 a        for (int j=0;j<n;j++)
" z" [' \3 X, t$ |; {        {
            if(true==arrary[j])
$ B$ n8 J1 N- D                for (int k=0;k<n;k++)
6 f# G& W, d+ I. r' t3 y8 X                {
+ H" \# f' S  y" X) b( ]                    arrary[j][k]=arrary[j][k] || arrary[k];
' A$ R0 [3 j8 m; p% {                }
        }
    }
};
bool  SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)
% W1 x1 e. m6 |) s. a0 x{
    Seq[n-nLeft]=static_cast<char>('a'+nIndex);
    bool bFlag=false;
2 v4 n- c8 W6 l8 W  h9 M' W    if(1==nLeft)
    {
; l/ {' w/ N/ m" t        Seq[n]='\0';
        return true;
    }
9 B/ l$ ~% u+ \" s# F    for (int i=0;i<n;i++)
6 `2 u; B$ ]4 h$ k8 p1 ~    {
        if(true==array[nIndex])
! M+ R5 M0 U, \- I0 F0 E        {
            
# h  O; ]& K* I% @9 [            bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);
. H; `1 @! B8 K8 q        }
& {* d! \5 c$ Y/ L        if(true==bFlag)
            return true;
$ [, x5 Q* T: d4 J- A: {- O5 z    }
    return false;
. x, Q: v6 B* c4 _1 ~4 d/ v, x};
) u( k- T" a, c& i; q* {* n9 pint main()
{
, O6 W7 R7 a+ |3 J    int nSeqLen;
- R; V% g# h$ |" Y    int nRelNum;
    cout<<"Input the length of the sequence:"<<endl;
3 {; a# F' f; B+ E    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!
' J- B4 ^3 T4 z) [# ?% ?    if(nRelNum<nSeqLen-1)
+ ^! v. _1 w6 c0 i6 }$ c    {
# }+ Q& Z: }- ~% a        cout<<"The relation can not be determined!"<<endl;
        return 0;
    }
7 ]4 w: S3 |' B+ r    string* strRelations=new string[nRelNum];
    char* Seq=new char[nSeqLen+1];
! n# ?3 ?3 S9 Z/ d    bool** array=new bool*[nSeqLen];

& d; o; _+ J$ F( o' {    for(int i=0;i<nRelNum;i++)
% C* U6 y* J8 h% ^/ u, _5 k+ |# F# S    {
        cout<<"Input the "<<i+1<<"th relation:"<<endl;
) ~7 L4 O7 l. O/ D$ E        cin>>strRelations;
5 P( P' C' H/ ~. k: V  c7 [' G    }
" [7 b% \) t- ~. [   
    for (int i=0;i<nSeqLen;i++)
; \  h! W; J/ S. ]& H3 B, T2 S$ F+ d. G) |$ P    {
) S1 m: r$ g6 u. {4 ~  [! N  O* \( a        array=new bool[nSeqLen];
0 t# I1 e1 W5 d4 P        for (int j=0;j<nSeqLen;j++)
' \& P5 L- n* L6 X) P+ }            array[j]=false;
    }
    //The main loop
    for (int i=0;i<nRelNum;i++)
: B* x6 K. |; b/ j    {
2 o; T' q! h" P5 w+ ~! j        char a=strRelations[0];
5 t# g. Y0 ?3 G1 x        char b=strRelations[2];
        assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
8 ^+ x! V/ a1 g: Y3 C) s4 c        array[a-'a'][b-'a']=true;
4 F' s, h! a. y. R7 _  t
        Marshall(array,nSeqLen);
$ L" l( L5 {3 _) _
: ~; b; @% l+ J3 m        //Check for Inconsistency after  every relation
4 ]9 S, `; q! y, {        for (int m=0;m<nSeqLen;m++)
        {
+ M6 i% U& e9 [/ }            if(true==array[m][m])
            {
                cout<<"Inconsistency found after"<<i+1<<"th  relation!"<<endl;
7 @! [% p  h0 A9 {% ]) L                    delete []strRelations;
                    for(int k=0;k<nSeqLen;k++)
                        delete []array[k];
                    delete []array;
                    delete []Seq;
, i! n8 |6 f8 U+ P. d* ?7 Q                    return 0;

            }
        }

        //Check for the determined sequence after  every relation   
9 e( l( d5 q7 j) c; Z        for (int j=0;j<nSeqLen;j++)
5 p  P& N0 O+ v8 X+ ]2 X7 N* ~        {
            if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))
            {
                cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;
                delete []strRelations;
8 T2 G( F; u3 T4 }                for(int m=0;m<nSeqLen;m++)
: _$ a% B# d1 S                    delete []array[m];
                delete []array;
: @8 m9 @: x+ t) m/ E                delete []Seq;
6 t2 \, j+ {5 D                return 0;
" ^$ g2 ]; Z2 D; [9 e0 o            }
, U/ H' r7 o( c        }
5 _6 M2 q- Q9 H6 u4 h# `- S2 u6 U
0 i- C/ P% Y* C$ Q4 s
. A+ z, m2 v) U! ]5 R0 B+ }0 ^    }
    //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++)
' I6 V) |; Z% C        delete []array[m];
    delete []array;
- L# X9 }" [$ P, I3 S! w! j- P    delete []Seq;
   
! R  `( J+ H: j" Y/ |    return 0;
! E6 c3 r$ l( u+ [1 |}

5 b& \  G, t0 g4 u- ^, o9 ?3 E程序解题二：#include"stdio.h"
! D9 e3 A8 _2 k, i% P3 tvoid main()
{
    int n_m[100][2];
    char re[1000][3],
    temp[26];
    int i=0,j=0;
    scanf("%d%d",&n_m[0],&n_m[1]);
/ o9 k/ ?8 Q* P' u    for( ;j<n_m[1];j++)
* ]0 `' j, j5 k    scanf("%s",&re[j]);
    while(n_m[0]!=0&&n_m[1]!=0)
* d1 R# R  s: v% s    {
1 {0 f7 g7 N$ \( \    i++;
8 g' H' x3 u0 ~! P. C    scanf("%d%d",&n_m[0],&n_m[1]);
# c7 M4 W: O; U) B$ _    for( int f=0;f<n_m[1];f++,j++)
    scanf("%s",&re[j]);
    }
    i=0;
6 V- p" P& d7 Q8 |) I    j=0;
$ ]0 z+ @0 D& q( U   for( ;n_m[0]!=0&&n_m[1]!=0;i++)
  e9 d. J6 i* Y) H' L. J    {
       int a=0,b=0,l=1;
8 m! D1 W6 k5 Y2 g! B9 u       for(a=j;a<j+n_m[1]-1;a++)
8 B: m; Z' W( F5 [1 s5 ^' K         for(b=a+1;b<j+n_m[1];b++)
+ c$ T$ M2 w3 C* V5 r( q         {
: k/ E( P: H+ Z# ?! Z5 ~              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])
            {
- E3 |# y1 M' V: {4 ]( s( s: {            l=0;
            printf("Inconsistency found after %d relations.\n",n_m[1]);
            break;
            }
' o; r* J$ l, y1 q3 h$ f" j  c         }
, x' D8 _5 [2 k0 B) E& p      if(l==0)
& \0 H  Y1 t+ R' V* \3 {" `5 o5 q7 I          continue;//Inconsistency found after x relations.
    else{
/ ^  Q" D) z0 L           if(n_m[1]<n_m[0]-1)
" Q9 n1 {# V# h1 j! x" d        {
            printf("Sorted sequence cannot be determined.\n");
            l=0;
        }
        else
        {
/ z& v7 f& g1 n. j          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++)
                      if(re[0]==re[0]||re[2]==re[2])
                      {
                      printf("Sorted sequence cannot be determined.\n");
3 d2 {' ?* s3 P0 G1 x" u                      break;
                      l=0;
6 w. X7 `3 V2 \5 n8 z) O                      }
' T: V& Y4 M- }3 m' l          }
: W5 J  L* U7 Y* i  V" S, F        }
& f- X8 l* f) J0 i        if(l==0)
        continue;//Sorted sequence cannot be determined.

        else
         {
5 `  C+ K) s7 I% s" n2 D           
            for(int k=0;k<n_m[0];k++)
             temp[k]=k+65;
3 I: _, x' _6 Q, C: |5 ~7 |            for(k=0;k<n_m[1];k++,j++)
1 _4 X  F3 y/ U            {
                int t1=0,t2=0;
              for(int s=0;s<n_m[0];s++)
              {
) ^2 w6 Q+ V( j9 t2 t0 `               if(temp==re[0])
                   t1=s;
7 s4 {0 e- J3 |  |( C9 r0 N  Q                      if(temp==re[2])
                   t2=s;
              }
- G- i& C$ z; o8 Q2 R/ L! E* p              if((t1>t2)&&re[1]=='<')
              {
                char t3=temp[t1];
                temp[t1]=temp[t2];
' a- Q5 i6 u' b                temp[t2]=t3;
- j( _" @8 I( D. Z3 ~: L              }
            }
9 U: D) ~" x0 q- g2 _9 j$ G3 F        int count=0;
% H& i) B* z- N1 C6 t2 I        for(int s=0;s<n_m[0]-1;s++)
. i  R" l" a4 u9 a5 S; v9 I. ^# K        for(int d=j-n_m[1];d<j;d++)
5 S) B, k1 L5 A            if(re[d][0]==temp&&re[d][2]==temp[s+1])
) j8 ]0 S9 ~" W8 O4 T            {
+ w% J$ Q5 r- I7 {                count++;
2 Y- g5 M7 }  l) X" X: e                break;
$ f9 F) b4 L0 a6 `! F1 v! v            }
3 T+ \5 n. g0 k2 T7 U! I* T/ h            if(count==n_m[0]-1)
$ [+ `8 g  ~+ T( K5 T            {
                printf("Sorted sequence determined after %d relations:",n_m[1]);
5 O7 V: c4 n- N  r0 z* \                for(int f=0;f<n_m[0];f++)
                  printf("%c",temp[f]);
9 F  p; P$ W% ^0 H" L) ~8 O5 {/ i$ V                 printf("\n");
            }
            else
               printf("Sorted sequence cannot be determined.\n");
        }
0 {  s6 b/ n$ G/ k* z  S    }
- E- O) T4 w) J* S/ J' g: S" m6 R    }
}



* {1 I6 N$ L5 W$ I( q+ |

: q2 Y% D& L/ S) n! X
& U( ~/ P4 D% p/ v. s

6 w, B2 z" L! {

来源：编程爱好者acm题库