编程竞赛题目（一）

厚积薄发

$ W. N3 R# y+ p1 P" _  l/ zSorting It All OutDescription
9 O1 l, g# a1 v6 V0 z
( V/ y3 [" Z5 E/ L' O0 A. ]! NAn 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
$ O0 U) r$ A) V# a9 s( F6 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.
( K& s! O7 V2 POutput
) p+ q' y0 T8 i6 {8 F6 n& L" Q
For each problem instance, output consists of one line. This line should be one of the following three:
, w! c$ c' t+ k( a4 Z( B) y
Sorted sequence determined after ** relations: yyy...y.
& I, I# D# k: Z0 E" vSorted sequence cannot be determined.
Inconsistency found after ** relations.

+ x4 D/ f' l( _8 e/ h4 ~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.
" f  A+ }0 ]$ h6 h
输入样例

# F; }' p- S4 j, ^& c4 6
A<B
8 W/ q6 I9 o+ i' kA<C
B<C
C<D
, m2 c4 @0 @* \" S' oB<D
A<B
( l4 E' N$ R( s- ]$ g0 o3 2
A<B
" r, ]  J0 u+ H- rB<A
& @, o) x. V. O- i26 1
A<Z
0 0
1 J5 X' [1 B8 H: _

. m' S9 |. I8 ]- }+ T( ]输出样例

Sorted sequence determined after 4 relations: ABCD.
9 j& c5 Y$ X( n8 HInconsistency found after 2 relations.
Sorted sequence cannot be determined.

Source
/ @; T" i9 [% @8 ~1 M% U
1 t+ n' B* W3 h" w8 E  hEast Central North America 2001

" d  H! W! O" t  [4 ]

程序解题1：

//By Jackie Cheung
#include <iostream>
3 T- K2 _3 |5 R# _#include <string>
8 ]+ a) ~  M, c) @8 I# d#include <cassert>
typedef  struct tagNODE
5 |$ z9 i4 E: _8 T; W- i2 q{
& H% f4 a0 Y9 Z7 T% s' H6 l    char val;
    struct tagNODE* link;
/ C6 x8 o" P! W5 w}NODE;
4 p" `4 ~% ]9 C1 v9 N* G, rusing namespace std;
* ]5 L4 k# `: }: W. k; ^" wvoid Marshall(bool** arrary,int n)
{
5 ?5 y; E' |8 l+ H    for(int i=0;i<n;i++)
( }; k% i# L1 V. f! o5 I    {
5 b2 A3 f0 {! n. d2 U        for (int j=0;j<n;j++)
8 h2 U9 y' h0 s% ?  n        {
            if(true==arrary[j])
                for (int k=0;k<n;k++)
                {
# N0 g" t; e. ~/ m/ s                    arrary[j][k]=arrary[j][k] || arrary[k];
                }
        }
( g3 ~+ C+ h# j3 k/ x" G    }
};
bool  SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)
; k8 i: {5 }5 X* {/ q4 W{
% _: {/ R+ K/ e6 i$ u    Seq[n-nLeft]=static_cast<char>('a'+nIndex);
% T- N3 w- f* m  J5 ~    bool bFlag=false;
    if(1==nLeft)
  X8 b' q6 w  i    {
        Seq[n]='\0';
        return true;
9 ~$ K* ]3 D+ |6 q3 ]9 o- I, J- Z0 \    }
    for (int i=0;i<n;i++)
    {
        if(true==array[nIndex])
- R4 ?$ I% t( e/ N        {
, e" N4 T1 w' p2 u$ B            
  a: c3 e8 o1 r/ F  u; w% {; F            bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);
        }
        if(true==bFlag)
            return true;
    }
    return false;
};
* l1 L' E" ]+ Z# `- Rint main()
{
    int nSeqLen;
! J3 H: }) K% Y- r& K    int nRelNum;
3 H* b7 Y4 v. S1 A% f    cout<<"Input the length of the sequence:"<<endl;
    cin>>nSeqLen;
    cout<<"Input the number of relations between the elements:"<<endl;
8 [0 W0 K/ K# p, k    cin>>nRelNum;
    //1:if nRelNum<nSeqLen-1,then the relation can not be determined!
( b% i3 h1 f! }8 g7 J' d    if(nRelNum<nSeqLen-1)
" e( H/ ?# |- d9 w' E    {
        cout<<"The relation can not be determined!"<<endl;
  E0 }0 Q( R: x8 J( s' \7 R9 p        return 0;
1 a  h2 R7 F2 ?1 ?0 ^% O    }
    string* strRelations=new string[nRelNum];
3 q4 E8 h* `, o% w7 ?/ k    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;
        cin>>strRelations;
7 [% k& j5 c$ `2 T8 Q' c    }
  u2 }' j, N: v3 o7 x: Y# b) n( y   
3 J' d) H" k6 H+ F, Z; t    for (int i=0;i<nSeqLen;i++)
5 m, c4 o4 G* E    {
& f3 K9 _9 z, E# q) }5 m, @        array=new bool[nSeqLen];
        for (int j=0;j<nSeqLen;j++)
            array[j]=false;
    }
    //The main loop
    for (int i=0;i<nRelNum;i++)
    {
+ m5 S' C4 Q  {1 g3 }7 a        char a=strRelations[0];
- s3 H# o7 @& Y, X        char b=strRelations[2];
        assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
8 h6 A7 R9 I7 z( d" k2 W        array[a-'a'][b-'a']=true;
) @- A3 s' \+ N; d0 |
        Marshall(array,nSeqLen);

        //Check for Inconsistency after  every relation
9 j# M# [% `3 C( z; R        for (int m=0;m<nSeqLen;m++)
7 L  Q5 V  P" F. Q& C        {
            if(true==array[m][m])
% F( g/ r0 ?; J; I            {
4 A  s: {- O: W: k7 ^                cout<<"Inconsistency found after"<<i+1<<"th  relation!"<<endl;
                    delete []strRelations;
. E8 k5 Z1 t% E8 E3 n+ J# @                    for(int k=0;k<nSeqLen;k++)
                        delete []array[k];
                    delete []array;
' p6 s3 B  Y) a! E                    delete []Seq;
: e6 K2 {. O0 ~( F- _                    return 0;

            }
        }
2 P: o' A$ g2 _, p/ v/ C! B& t) m, r
0 q" d( a% B2 T9 v" }# g$ o9 @8 C        //Check for the determined sequence after  every relation   
        for (int j=0;j<nSeqLen;j++)
        {
7 u3 u! J% J9 `            if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))
( l% j/ l4 a4 O  h* x9 s            {
                cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;
5 m/ u/ Y. x4 `5 e- D                delete []strRelations;
6 G' y" u' L# y                for(int m=0;m<nSeqLen;m++)
                    delete []array[m];
1 {( ^3 t! X- F; Y/ u                delete []array;
" B2 F' |2 P/ o7 |                delete []Seq;
                return 0;
            }
  {$ a. l5 ^" |        }

. R1 U8 n& C; V* x1 u) t
    }
. f+ y$ f6 O  M5 U: Y    //If the program has come to here ,then the relationship hasn't been determined!!!
$ w8 ?8 M$ j- h- o    cout<<"The relation can not be determined!"<<endl;
: a" D5 t8 \( P; D2 [6 U    delete []strRelations;
    for(int m=0;m<nSeqLen;m++)
" m4 a# o- S0 |* |, h9 ~        delete []array[m];
( P4 z6 O" J3 B3 ?    delete []array;
    delete []Seq;
   
+ @. J$ q  @# J% K' [" N; V& o    return 0;
}

程序解题二：#include"stdio.h"
" D" K' I' D. P) [+ Kvoid main()
{
    int n_m[100][2];
    char re[1000][3],
    temp[26];
8 G, J" q" e6 }! \  k  P    int i=0,j=0;
2 c% J3 d5 A9 O% h& M. k. Q- {/ B    scanf("%d%d",&n_m[0],&n_m[1]);
; [' o, ^* E, l0 ]% u$ q    for( ;j<n_m[1];j++)
9 v( m8 q% L) R8 v8 ^" ~    scanf("%s",&re[j]);
: s1 q- j1 Q% Q7 ]+ E1 O8 w    while(n_m[0]!=0&&n_m[1]!=0)
+ Q' a2 t) f& I7 e    {
4 X+ }( U* ]" C9 R) d; n    i++;
    scanf("%d%d",&n_m[0],&n_m[1]);
    for( int f=0;f<n_m[1];f++,j++)
    scanf("%s",&re[j]);
, x+ n$ F, C) R! c3 x3 `4 G! x    }
    i=0;
    j=0;
0 p2 _( p0 q" E( ^9 Y' r* R   for( ;n_m[0]!=0&&n_m[1]!=0;i++)
    {
) X; }9 Q, z1 ~# z$ J       int a=0,b=0,l=1;
5 ]) G1 Z$ [  l" [. N9 X       for(a=j;a<j+n_m[1]-1;a++)
         for(b=a+1;b<j+n_m[1];b++)
         {
, L& S' ~/ {1 K) C              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])
: D/ h1 U! M+ i2 E, g# I  @/ B            {
: @* i' e  }$ p            l=0;
( Q& c2 G, [3 ?7 V# l; k% H            printf("Inconsistency found after %d relations.\n",n_m[1]);
' `0 n4 M7 t' n/ {2 C- v6 e+ H            break;
            }
         }
      if(l==0)
5 N2 n+ R8 f3 O# s2 w! S8 z          continue;//Inconsistency found after x relations.
3 t9 n9 @7 ?6 N: }2 c. b    else{
           if(n_m[1]<n_m[0]-1)
        {
            printf("Sorted sequence cannot be determined.\n");
            l=0;
* ?) v5 P; B' `* J  z& G        }
        else
* U% C, N4 m+ v! v, q        {
          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++)
$ g3 k# F  ?4 S                      if(re[0]==re[0]||re[2]==re[2])
                      {
                      printf("Sorted sequence cannot be determined.\n");
8 M1 E' m- z7 I6 n& F                      break;
                      l=0;
% R0 j4 c) R) `' G6 N' M) W                      }
  m+ z5 t- r" _# T' W5 a8 @          }
        }
0 {5 `9 f3 \. p( R& `% }* ?% J        if(l==0)
! U8 U# S0 F) j" |# f% T/ u- p6 ?        continue;//Sorted sequence cannot be determined.

        else
         {
           
+ r9 j* Q. t: U$ E            for(int k=0;k<n_m[0];k++)
1 P7 S# o% Y  k7 u             temp[k]=k+65;
            for(k=0;k<n_m[1];k++,j++)
            {
" a- V) u" [2 A/ v! m                int t1=0,t2=0;
! N! r& }9 ^. S# i/ x              for(int s=0;s<n_m[0];s++)
) y1 n' y, w1 ?) X0 V' |. O              {
               if(temp==re[0])
                   t1=s;
                      if(temp==re[2])
                   t2=s;
; Z5 l) O; Q0 G              }
              if((t1>t2)&&re[1]=='<')
, g. e# N3 `2 J              {
3 a8 N8 E$ j9 p% [+ e8 {. G                char t3=temp[t1];
( x5 g3 r) H9 f9 v/ U                temp[t1]=temp[t2];
                temp[t2]=t3;
              }
            }
) n6 `4 Q  C5 a# ]' m* X        int count=0;
        for(int s=0;s<n_m[0]-1;s++)
. W2 _$ T9 c1 O' p/ S% a! q( v        for(int d=j-n_m[1];d<j;d++)
4 U4 ?. F; ]9 V5 [3 d/ @            if(re[d][0]==temp&&re[d][2]==temp[s+1])
            {
                count++;
& o1 ?* b9 J8 Z( T8 k6 |& k' _                break;
            }
            if(count==n_m[0]-1)
1 m( N# y$ y% `- n' N+ I& C5 V( b( u            {
                printf("Sorted sequence determined after %d relations:",n_m[1]);
) X' p% W0 V" E7 i: C3 y                for(int f=0;f<n_m[0];f++)
4 b- I& T( g2 ^- E& [4 a                  printf("%c",temp[f]);
1 M6 g9 {7 t( }& t2 U2 K: F1 _+ _0 N; L                 printf("\n");
            }
            else
               printf("Sorted sequence cannot be determined.\n");
        }
. j, A' F& {/ P. A+ T    }
: }' ]" s5 [8 u9 F8 W    }
6 n. a2 r" n; u5 _, v6 U5 g}
; ?( P" Y3 l' u- L) ]+ {$ B

: K6 B+ q" v# |' a% \- _/ j: _" s

) e% P8 b" i, i
3 C- A8 j6 E, l4 Z$ ~

7 |5 b, E$ ^; o" e# {

来源：编程爱好者acm题库