编程竞赛题目（一）

厚积薄发

' ^6 L' _* O, P8 F$ w+ M7 r3 i
Sorting It All OutDescription
8 D' O3 W5 ~1 k' D0 p
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.
$ s: N0 i! x) l4 A% wInput

9 ]6 M- T# W* L  d- n, }' ~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.
6 U* u0 I+ c. {2 LOutput

; i0 x* A/ [9 Z3 vFor each problem instance, output consists of one line. This line should be one of the following three:
, T/ g% s: `. m: A9 _/ ?8 B  d
Sorted sequence determined after ** relations: yyy...y.
5 ^% W6 I0 x8 S. a& xSorted sequence cannot be determined.
Inconsistency found after ** relations.
7 P  G: ~# z* m
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.
' m# e+ n+ U/ G% j. {4 G
输入样例

4 6
A<B
A<C
8 b+ n1 T. Y3 S# zB<C
C<D
B<D
A<B
3 2
A<B
B<A
2 @( t- C5 b6 P8 D0 l- s26 1
, J8 ]9 y1 b* @2 vA<Z
/ j  X: n  Z- j) q; {. d0 0
1 A8 K- v5 W: H. l3 K- S

0 G( H4 h$ ^* K" v% ]& c) \% P; R1 i输出样例

. X. r5 B9 J1 N( \( s: HSorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.

Source
9 K1 w+ |5 ?9 [" h: I# E/ F
* Q: u" F& `5 Z; Y' JEast Central North America 2001

程序解题1：

1 H3 V/ G  X' l: u//By Jackie Cheung
6 X+ O6 C- ?2 g" C#include <iostream>
8 q, V. ~1 X4 G. s) F* e" }#include <string>
! m2 m1 B% a8 w2 O+ v; T#include <cassert>
typedef  struct tagNODE
{
2 R) G7 _2 T; K2 p/ D) c    char val;
    struct tagNODE* link;
}NODE;
using namespace std;
# @' h$ A9 n6 Z. o6 o: cvoid Marshall(bool** arrary,int n)
{
    for(int i=0;i<n;i++)
& h+ J' Z$ Q7 F    {
        for (int j=0;j<n;j++)
- `2 T7 f8 i5 e+ T9 f3 q        {
            if(true==arrary[j])
! ]; D2 ?! x" V. [                for (int k=0;k<n;k++)
' c; i) Y( f3 H% m) Y; l$ w  p                {
                    arrary[j][k]=arrary[j][k] || arrary[k];
* k! z; e/ G8 @+ W. i) H1 J                }
        }
5 g/ M% U2 {9 \5 T" \: b' \$ ?    }
};
bool  SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)
; \9 ]. q. [4 x. Q* C1 ^{
    Seq[n-nLeft]=static_cast<char>('a'+nIndex);
* q+ m8 |' F) I# D5 @5 Z" q    bool bFlag=false;
7 [4 q: E! F, h* a    if(1==nLeft)
    {
! Z+ C6 `2 N2 V( K1 U        Seq[n]='\0';
        return true;
- s- x: G' a0 S8 S7 A    }
" h7 ~. g  F+ F: w9 V' \' ^* `' |    for (int i=0;i<n;i++)
    {
        if(true==array[nIndex])
% r9 V- y; Z8 ~& ^2 k        {
0 M) v7 y' m- t6 R* Y& H            
0 R5 P! M! B( E' e& P  j3 ]            bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);
' ^+ d8 [9 U) U9 ]8 B! E        }
0 ~6 P3 ~, F3 g0 d. F        if(true==bFlag)
# h5 l. |$ R1 S9 w2 h6 D8 K8 ~            return true;
    }
0 E$ c7 ?) s1 p( {8 o" ~' v    return false;
% W( C& Z8 x1 T# b% `};
$ l  y; V1 J6 o3 Mint main()
2 T8 Z, t& e4 Q) J9 @1 g{
. n6 f) @7 G, H    int nSeqLen;
; [1 h" V4 w0 E8 I, i$ R    int nRelNum;
    cout<<"Input the length of the sequence:"<<endl;
0 W1 r) [  @5 @3 H- g( u2 V- t+ A    cin>>nSeqLen;
- L$ I$ p! h, k( k0 L    cout<<"Input the number of relations between the elements:"<<endl;
$ }: v# }2 f  R0 l+ A5 E    cin>>nRelNum;
    //1:if nRelNum<nSeqLen-1,then the relation can not be determined!
1 T# X  U6 w" T  u$ G% S* }    if(nRelNum<nSeqLen-1)
    {
6 h; R7 z% k3 f3 k& \# Z        cout<<"The relation can not be determined!"<<endl;
        return 0;
, N" z0 h6 A$ @    }
0 s6 a* A0 W1 N( Z2 Z9 I    string* strRelations=new string[nRelNum];
( W9 Z  k% E$ ], J- i0 w5 H    char* Seq=new char[nSeqLen+1];
    bool** array=new bool*[nSeqLen];

    for(int i=0;i<nRelNum;i++)
- S. f0 _1 W' J7 ?! b( A% c    {
& b, e+ ~+ }3 x1 V  N5 q        cout<<"Input the "<<i+1<<"th relation:"<<endl;
$ d) X/ f' N: D; y+ T        cin>>strRelations;
    }
1 V! u* V6 @3 l   
    for (int i=0;i<nSeqLen;i++)
4 W; r6 f$ K' Y; O* Q    {
        array=new bool[nSeqLen];
7 P- }0 u- r, B! |$ D( ?        for (int j=0;j<nSeqLen;j++)
" ]  F; l; a2 F' b+ \+ V            array[j]=false;
# c2 \0 p3 D, w! J! J    }
% R: S/ j* B- C) v    //The main loop
; a9 z6 Z) P8 q4 O7 @  P    for (int i=0;i<nRelNum;i++)
+ I, O3 I2 Z# E/ K# P  L4 W    {
6 F2 W1 d' l+ j8 z+ D        char a=strRelations[0];
4 N" K. g( V! p! u+ U; p, D" H        char b=strRelations[2];
9 O( t3 `- O. Y        assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
        array[a-'a'][b-'a']=true;
: o: i8 r# u8 V0 e" }- @
4 ^6 e- v9 `( G        Marshall(array,nSeqLen);
5 r' M9 [/ L! f# D
$ V# J5 d5 M& E5 }9 D7 w9 ?/ b; g: {        //Check for Inconsistency after  every relation
  n; U" M! p3 m% O, b+ s        for (int m=0;m<nSeqLen;m++)
        {
/ y3 h' L( z' }$ w: R% p            if(true==array[m][m])
" Q. T5 P- ]1 Z0 ]( z* g2 ]  T            {
                cout<<"Inconsistency found after"<<i+1<<"th  relation!"<<endl;
0 U! o! ^+ W( [: d" `4 L4 k* N                    delete []strRelations;
                    for(int k=0;k<nSeqLen;k++)
                        delete []array[k];
                    delete []array;
                    delete []Seq;
6 J) j7 b2 t, z) o2 R                    return 0;

            }
        }

* [/ ?% ]. _1 ?/ e8 H4 }        //Check for the determined sequence after  every relation   
        for (int j=0;j<nSeqLen;j++)
        {
            if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))
6 F# h* m- S: J3 u# O            {
0 L) x5 O; \, ^' ]8 ^' S                cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;
- v! F. m' m5 m* `# r                delete []strRelations;
% x1 R/ ^8 u. o. B! U- a                for(int m=0;m<nSeqLen;m++)
1 a& a* D% `5 \- u7 f1 E                    delete []array[m];
                delete []array;
" |$ ~. h+ t7 F2 w1 k0 {. B) J                delete []Seq;
- j. J' E, j# J( `/ I                return 0;
            }
        }
* s! j4 i: X: g

/ l0 n; Z% f7 ~6 n+ C7 E    }
    //If the program has come to here ,then the relationship hasn't been determined!!!
, |+ _0 T, }8 i& A    cout<<"The relation can not be determined!"<<endl;
# }" B1 J& k/ z7 k    delete []strRelations;
    for(int m=0;m<nSeqLen;m++)
+ T8 f4 y9 m, R7 c* o+ e. w        delete []array[m];
' w8 X+ ]* j* r/ O! x    delete []array;
    delete []Seq;
- l1 p/ g! m$ E' Y: W& P, y   
    return 0;
5 j3 M! Q6 k& Z# v}
" o: C" C' c& L  z) `8 _
7 I* V# t3 Z) @, }! T  U6 \4 U, a程序解题二：#include"stdio.h"
void main()
{
; ]  \) w$ W( H/ j    int n_m[100][2];
0 }. V' N& x" g9 P" c  c    char re[1000][3],
! h9 p5 W; u4 F! J+ t  T) l    temp[26];
# w' v, T; z$ U  b5 ^# S    int i=0,j=0;
    scanf("%d%d",&n_m[0],&n_m[1]);
) l3 G% T: u) w: \: k    for( ;j<n_m[1];j++)
+ L2 I% s; M5 [+ \, z; s    scanf("%s",&re[j]);
0 H/ E) |+ r7 ?, C% ]    while(n_m[0]!=0&&n_m[1]!=0)
    {
    i++;
    scanf("%d%d",&n_m[0],&n_m[1]);
    for( int f=0;f<n_m[1];f++,j++)
    scanf("%s",&re[j]);
    }
( r" Q9 k/ \) E9 d, _    i=0;
! [8 i+ [% k9 |' E# A    j=0;
9 Z$ _$ M/ K. T( }7 U   for( ;n_m[0]!=0&&n_m[1]!=0;i++)
3 p9 y# Z  A& {- s- V, o5 ~    {
3 {7 U" u# J3 B, b       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++)
         {
              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])
            {
0 @1 \1 E% Y" S5 ?            l=0;
9 M9 Y3 p* _+ ]+ @/ d            printf("Inconsistency found after %d relations.\n",n_m[1]);
            break;
$ |0 t7 C! X) t8 v! D  I' r            }
         }
5 G( J% S" G2 Z7 I/ h3 C      if(l==0)
8 q* x+ n* U0 F$ T0 `+ I. k          continue;//Inconsistency found after x relations.
" q. a2 @+ s) n4 d: G  B8 j    else{
; e' x0 _3 P( |+ ?( o: u, C/ c           if(n_m[1]<n_m[0]-1)
6 H$ b! q- W$ v        {
# h4 X, _. X4 R+ N            printf("Sorted sequence cannot be determined.\n");
            l=0;
        }
        else
        {
$ C, U1 R9 p/ ], X) t5 h8 C/ r3 w# I8 Y6 G          if(n_m[1]==n_m[0]-1)
! q4 H7 h& H9 w          {   
              int k=0,p=0;
              for( ;k<n_m[1]-1;k++)
) l7 y- Y  V1 U. Z                  for(p=k+1;p<n_m[1];p++)
- c- f+ c8 {4 p& K7 T                      if(re[0]==re[0]||re[2]==re[2])
' x% D2 |5 Y& ~& S                      {
0 W! R" w$ i4 Q' l7 M9 O                      printf("Sorted sequence cannot be determined.\n");
                      break;
7 y9 N3 S( a3 h/ o* Y                      l=0;
                      }
          }
5 Q0 Q' p3 H- d  f2 o( @% Q/ @        }
        if(l==0)
        continue;//Sorted sequence cannot be determined.

5 W0 @. D+ t  ?3 L        else
         {
. {7 x+ }# a7 C: A5 {8 s7 e7 r% `1 r           
9 y1 @4 C- ], H9 q: ~: M1 l            for(int k=0;k<n_m[0];k++)
4 h/ `, h- ]0 I             temp[k]=k+65;
* N5 R0 G4 a+ u3 u, \9 S3 f: I) j            for(k=0;k<n_m[1];k++,j++)
            {
                int t1=0,t2=0;
              for(int s=0;s<n_m[0];s++)
              {
! d# U& f- x( x5 O4 K& ?               if(temp==re[0])
                   t1=s;
8 q+ I# k1 h+ M2 Q. p" s  J                      if(temp==re[2])
                   t2=s;
              }
- ^3 P3 o  m' m              if((t1>t2)&&re[1]=='<')
' T* P$ N$ I' s1 J              {
- e& q' I7 i4 g/ ~" ^+ }& D- `                char t3=temp[t1];
: H: G% J8 T, f+ ^* P* ]                temp[t1]=temp[t2];
1 d" `" E  S7 R' {, J                temp[t2]=t3;
+ _" r4 ?1 V6 l. b' L              }
            }
. e/ F4 `2 ]! [        int count=0;
8 i; S( T! p5 A- I. [        for(int s=0;s<n_m[0]-1;s++)
        for(int d=j-n_m[1];d<j;d++)
            if(re[d][0]==temp&&re[d][2]==temp[s+1])
2 t1 y5 G2 ]9 i# ~, \! ?            {
                count++;
                break;
; m8 l1 j! p1 b            }
$ Z5 k' K. ^6 Z2 @* [6 s            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++)
2 F/ I* w- \/ A0 \/ ?# k, I7 r                  printf("%c",temp[f]);
. @# a. A' |- v' G                 printf("\n");
& L$ j5 h9 g; p. }! m! h$ \            }
: w1 o' c+ A8 |) F- y* w' t            else
               printf("Sorted sequence cannot be determined.\n");
4 V4 R2 B; q" M' ]$ a& ?+ ~5 L4 V# r: B        }
    }
( f$ ?1 M6 o$ ?    }
, }$ Q& k* L) Q# |5 r3 D! P}

7 P0 D" Q4 B+ ~
& }0 ]+ V5 f5 z5 g



2 m/ M3 G# j7 O. \. f
, [) o9 F) R& w& G! N' @

来源：编程爱好者acm题库