编程竞赛题目（一）

厚积薄发

Sorting It All OutDescription
& H/ ?( |1 b& K7 d9 ]6 _
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

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.
; l* ?: t( X4 a$ d8 ^5 H- cOutput

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.

& X6 F3 _$ g' Q9 l! D' ~& Mwhere ** 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.

/ |, E4 l6 D/ a* o9 z输入样例

' H! o. W/ y3 x1 O5 n) i1 I" R0 c4 6
& X0 @9 Z) @# F% q+ q! c+ sA<B
A<C
+ L  k1 T7 Z, E. i0 EB<C
C<D
2 K5 v& q+ D6 ^! @2 YB<D
A<B
3 2
. c7 |" k1 D4 f+ Y9 f& L* PA<B
B<A
26 1
/ X( {. G0 _8 Z" o, D' hA<Z
3 n, @( G1 w  g$ c0 0

7 I9 K) W' J) O- a9 E2 R输出样例

7 J" y' K0 E) {$ r) S. zSorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
9 P. J7 i1 k, N/ @- jSorted sequence cannot be determined.

Source
- t7 S. }+ V) O3 z; E
East Central North America 2001

! J) b* ^8 n- _. c

程序解题1：

//By Jackie Cheung
#include <iostream>
#include <string>
+ w3 T: y+ J. e2 k#include <cassert>
0 S% Q3 Z  W  x# gtypedef  struct tagNODE
{
    char val;
, Z  `- e7 a: s    struct tagNODE* link;
# l* p3 i- [6 U1 _, X+ R4 r, w. d}NODE;
using namespace std;
% W; D0 l: {. l$ E, l/ Hvoid Marshall(bool** arrary,int n)
  N3 i3 J# Y* w0 o$ g5 H{
8 J; E  y# ?; j/ q    for(int i=0;i<n;i++)
    {
+ X; o; [# |. o        for (int j=0;j<n;j++)
; t7 z5 [$ i: s7 g9 J! U+ O        {
            if(true==arrary[j])
                for (int k=0;k<n;k++)
                {
) J) m% b; q1 T2 |                    arrary[j][k]=arrary[j][k] || arrary[k];
& c8 U, u& Y+ S5 H3 I7 U1 |( i/ C                }
        }
    }
0 l4 i. D1 o  x3 S; z+ u};
, }+ w$ z, u  vbool  SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)
% B. a$ r/ c& D$ D{
    Seq[n-nLeft]=static_cast<char>('a'+nIndex);
% Y1 ]2 ^" g6 x' ]: y    bool bFlag=false;
+ `( ?$ f3 j8 F3 X    if(1==nLeft)
    {
' X2 N- N# e( h  X4 ?6 c/ j* o        Seq[n]='\0';
        return true;
" a+ V- q; T- x5 D' b  @7 h4 v    }
3 F% @# y4 I9 G4 |8 I# X( i3 k    for (int i=0;i<n;i++)
4 ?4 z4 @5 i( f9 }4 e+ e" @    {
8 V1 p; f8 j9 T7 n( k% ]        if(true==array[nIndex])
        {
: l3 a5 W; c* H/ z; U6 Q4 }: a            
# b- Q+ Y2 x! q6 D- [            bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);
( x6 M* p# L* o        }
  O$ d$ G) T" e% I+ f        if(true==bFlag)
            return true;
    }
    return false;
};
! F7 r* \! K9 [9 }! cint main()
{
1 m# A1 ]/ P+ c0 C! q, [    int nSeqLen;
" R9 g4 V6 {4 k8 ]% I- k    int nRelNum;
    cout<<"Input the length of the sequence:"<<endl;
+ t4 A0 l& Z( U. K$ ^    cin>>nSeqLen;
. O* }3 k- S7 v) \    cout<<"Input the number of relations between the elements:"<<endl;
    cin>>nRelNum;
    //1:if nRelNum<nSeqLen-1,then the relation can not be determined!
8 H; V4 i7 J- g* y    if(nRelNum<nSeqLen-1)
    {
# k5 R9 L) ~- J1 x7 r        cout<<"The relation can not be determined!"<<endl;
        return 0;
    }
    string* strRelations=new string[nRelNum];
    char* Seq=new char[nSeqLen+1];
    bool** array=new bool*[nSeqLen];

    for(int i=0;i<nRelNum;i++)
    {
        cout<<"Input the "<<i+1<<"th relation:"<<endl;
$ L  L: R8 ^; F& ^" J- I        cin>>strRelations;
    }
& z7 T6 w2 d; p5 {% j. e   
    for (int i=0;i<nSeqLen;i++)
7 f- F7 Z6 H3 b% g% [5 n% F# k$ X    {
        array=new bool[nSeqLen];
+ N4 }* C0 L3 c! t        for (int j=0;j<nSeqLen;j++)
% w! U4 E8 [  a' Y! M; `            array[j]=false;
    }
" _7 L4 k; W* w9 v; z* I    //The main loop
3 h/ {/ k! ^" a" m    for (int i=0;i<nRelNum;i++)
    {
        char a=strRelations[0];
        char b=strRelations[2];
        assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
5 \2 p3 c. [0 A) ?- \        array[a-'a'][b-'a']=true;

        Marshall(array,nSeqLen);

% O7 V" }7 p5 f% q) k. w5 k        //Check for Inconsistency after  every relation
+ @7 |/ J; z, O% a7 \- G% O        for (int m=0;m<nSeqLen;m++)
        {
            if(true==array[m][m])
& N# B* o* A, G) v1 ~            {
+ h8 ^/ j3 Y8 E                cout<<"Inconsistency found after"<<i+1<<"th  relation!"<<endl;
$ ~- ]0 r5 n4 l; d" B                    delete []strRelations;
" t1 M/ k! M/ A4 e; B" a( Q                    for(int k=0;k<nSeqLen;k++)
                        delete []array[k];
+ x/ s2 s4 h) R8 d( R* {                    delete []array;
                    delete []Seq;
( V- l& A5 _/ u; h' B                    return 0;

$ b; p6 w3 A9 S            }
        }

        //Check for the determined sequence after  every relation   
        for (int j=0;j<nSeqLen;j++)
        {
' m1 Z! @4 m9 S. {9 c9 @            if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))
* r9 E, P" V% o# w& W            {
. n1 h; a" R0 X( ?3 y1 t                cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;
                delete []strRelations;
                for(int m=0;m<nSeqLen;m++)
# H# S/ n. }3 c4 ]- |" N                    delete []array[m];
                delete []array;
                delete []Seq;
; r) d8 N* E! w' ^4 w! ?                return 0;
            }
; z" Z$ w1 |7 \0 `. t# ?% K        }


    }
    //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++)
) `- X! G# J, c4 x        delete []array[m];
    delete []array;
* F( D: P! U1 M* q$ C8 Q6 i    delete []Seq;
; ~3 j4 P1 o4 h; ?: b/ r$ f/ [   
    return 0;
5 R  H. }. S9 \1 c+ Y& O}
' S2 x$ D6 a, _. \! ?
' {/ C0 I7 f" d4 _" p程序解题二：#include"stdio.h"
void main()
+ q1 M3 Z+ x# s{
5 u4 o9 B. w" e+ C    int n_m[100][2];
' n# }3 [% h! ~/ H- ^    char re[1000][3],
2 i* W# a% X. Z/ Y+ G0 |    temp[26];
! O- r2 l, C) J- |( b    int i=0,j=0;
    scanf("%d%d",&n_m[0],&n_m[1]);
; i7 [8 I. W" c' S( _5 f    for( ;j<n_m[1];j++)
    scanf("%s",&re[j]);
4 _/ E; D1 M; k    while(n_m[0]!=0&&n_m[1]!=0)
    {
    i++;
    scanf("%d%d",&n_m[0],&n_m[1]);
, d6 e) ?8 e" v5 O    for( int f=0;f<n_m[1];f++,j++)
    scanf("%s",&re[j]);
    }
    i=0;
" O  `! Y& K3 g- G: x! [    j=0;
   for( ;n_m[0]!=0&&n_m[1]!=0;i++)
    {
       int a=0,b=0,l=1;
$ |2 V+ }5 n$ J; Q) W' e( }       for(a=j;a<j+n_m[1]-1;a++)
0 w0 U7 Y5 h7 q: ?% ^) p         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])
            {
8 ~& |. N, @$ T2 }* {7 {1 Q            l=0;
            printf("Inconsistency found after %d relations.\n",n_m[1]);
            break;
            }
         }
      if(l==0)
% z2 j; X( ^- W; s" I' Y5 z3 L0 U3 I          continue;//Inconsistency found after x relations.
, d% t; a6 k+ M    else{
           if(n_m[1]<n_m[0]-1)
        {
            printf("Sorted sequence cannot be determined.\n");
            l=0;
        }
        else
8 f' ~0 [! t4 A5 I$ r4 k        {
          if(n_m[1]==n_m[0]-1)
4 Q* O; K* J+ |0 c5 \  T: b( T. m          {   
6 F# H) H6 \9 B, F; p6 f( L              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])
                      {
% ^6 P+ h$ }6 {                      printf("Sorted sequence cannot be determined.\n");
                      break;
                      l=0;
                      }
: U8 k/ m4 j" b0 z) u# ~  P          }
        }
        if(l==0)
% R' D* @4 {9 b. Q        continue;//Sorted sequence cannot be determined.

. E5 H1 Z& C9 N- c: F8 A$ Y        else
         {
& o+ [# r1 h( L& M2 \6 u           
            for(int k=0;k<n_m[0];k++)
             temp[k]=k+65;
9 _1 h1 a2 g- s9 K- f            for(k=0;k<n_m[1];k++,j++)
" e( s0 f. m$ F; e9 y2 J! T2 F            {
1 {- D) S) ?; E" d                int t1=0,t2=0;
- g6 J7 }: p5 `3 v2 G; q1 B              for(int s=0;s<n_m[0];s++)
% ?; K# K$ G1 h1 |/ p8 m) w              {
" `8 F; I- y7 S/ V! D8 H# m( B               if(temp==re[0])
                   t1=s;
% ~+ U0 P  |  Z/ [& t                      if(temp==re[2])
" v$ R2 r+ c* O+ x, p! F                   t2=s;
* U- e, ?2 _; n3 L- `9 G, h' U              }
              if((t1>t2)&&re[1]=='<')
              {
4 o+ v' N! t1 w4 e                char t3=temp[t1];
/ g3 r; ^) l9 G+ p" w                temp[t1]=temp[t2];
                temp[t2]=t3;
              }
; A& T5 _& p0 G0 o  B  G            }
        int count=0;
" O' k7 F# s4 D0 y6 P' r        for(int s=0;s<n_m[0]-1;s++)
        for(int d=j-n_m[1];d<j;d++)
) O" I! Z3 F+ S0 j. `" \$ n' Y            if(re[d][0]==temp&&re[d][2]==temp[s+1])
            {
                count++;
                break;
8 G" n' O- l# q% E$ y3 P7 |0 A( Y$ ^            }
+ R7 Q& e* {# \            if(count==n_m[0]-1)
            {
8 u0 M5 S$ q' n. d0 b7 {4 s                printf("Sorted sequence determined after %d relations:",n_m[1]);
                for(int f=0;f<n_m[0];f++)
+ h7 l9 t  P, J0 b9 a                  printf("%c",temp[f]);
2 }3 |! g% ~) K& f2 V1 S                 printf("\n");
9 [" `* [) D) A# s' E5 }9 p            }
8 O. V3 f$ y, ]1 O! v2 t            else
1 d1 a1 |( t) P( N& U) ~! I               printf("Sorted sequence cannot be determined.\n");
# ^- w4 ?+ J5 |# a! a* ?5 N        }
    }
3 i; D; G. W; V  _) ^# W" w0 m2 t4 q    }
1 Z+ s: ?( d3 a4 A3 v  l) }}

3 O3 y- ^) F$ @






4 V  Q2 e, f  Y. T& J+ N# S

来源：编程爱好者acm题库