编程竞赛题目（一）

厚积薄发

- T' s1 w9 o) ], e: Z+ y( a. W0 z$ BSorting It All OutDescription
" T: j; G. t9 A0 _
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.
" @# {( m7 g1 Q- j5 H. J2 JInput
9 }& ^% N2 q" I! g
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:
, i+ @1 P6 W* q6 F% Y' P( n8 a/ t5 P
Sorted sequence determined after ** relations: yyy...y.
* y6 A5 Y& I$ c9 e1 M* vSorted sequence cannot be determined.
Inconsistency found after ** relations.
! f; L- n$ X# f7 l! a7 \
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.

  Q0 b8 l. i+ E. O, F: t输入样例

+ A3 \: B7 Y* E% X4 6
A<B
. E. \" C3 {2 `A<C
/ [1 I* m6 d* r/ ?8 m5 WB<C
( C2 N4 l5 }, ?- i" JC<D
B<D
A<B
; p& x% A0 q' B. I3 2
) o5 [; B& Z! C% T4 N8 O7 OA<B
* \! w/ d( @" ?  f# ^  Z9 cB<A
' W2 O4 K( B% Q26 1
' u& O% Q* R1 I5 U2 f/ l- \& pA<Z
8 H+ f/ d  F: s. C$ @- s  F; Q0 0

* d5 O2 X- |) e$ [输出样例

- p' @2 ~  Q8 e1 nSorted sequence determined after 4 relations: ABCD.
6 ?5 M' \6 a' EInconsistency found after 2 relations.
Sorted sequence cannot be determined.

  J! g7 x, U- W6 \4 M, p

Source
8 h# R6 }" i8 p! N7 z% C; z
East Central North America 2001

程序解题1：

//By Jackie Cheung
#include <iostream>
#include <string>
( R8 r3 f; t+ l0 d2 h9 y#include <cassert>
typedef  struct tagNODE
{
; a$ O% e$ R$ \; N4 R/ u# n) M9 J    char val;
    struct tagNODE* link;
& v$ i! F, Y% N+ T' `' a, e2 ^}NODE;
2 `% j0 m% }$ g: {9 A0 \using namespace std;
' c, A) x9 R: Gvoid Marshall(bool** arrary,int n)
{
    for(int i=0;i<n;i++)
& n8 Y& @* M4 N    {
        for (int j=0;j<n;j++)
        {
            if(true==arrary[j])
                for (int k=0;k<n;k++)
; R( S4 L' [" B0 a4 i                {
! c4 c0 Z/ j4 @& s7 j& X& L                    arrary[j][k]=arrary[j][k] || arrary[k];
" v* E( u) E( ~6 |( {                }
2 S8 |; Z! S% I9 }1 {        }
% Z! \' I: R8 k& K' Y5 G: X    }
0 `+ \" r0 \2 M};
. k- Z" s- r$ J5 s# g2 z6 l: U/ pbool  SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)
7 r. i) C% V, a" w) F{
    Seq[n-nLeft]=static_cast<char>('a'+nIndex);
    bool bFlag=false;
    if(1==nLeft)
    {
7 \* E: v' I* x) ~0 [! e4 q        Seq[n]='\0';
        return true;
    }
# {0 i" K: G7 W6 Z    for (int i=0;i<n;i++)
1 H4 y9 R& Z) h. l4 h/ [    {
        if(true==array[nIndex])
: d+ x3 U5 G/ ]. G& ?/ ~) i0 {, W; \        {
- G6 g( C$ t/ d, `& a8 u            
            bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);
        }
        if(true==bFlag)
            return true;
    }
2 y/ m, [% a( d" a, H& X' ~    return false;
. i2 i! |' G) Q+ i6 m};
! U+ m( M' y* n! ~0 S$ _4 ]int main()
; L$ P, X* g  `8 k( W2 L{
    int nSeqLen;
    int nRelNum;
    cout<<"Input the length of the sequence:"<<endl;
$ e+ r* k- y; S    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!
, }# s' }  X+ e3 Q* j9 S    if(nRelNum<nSeqLen-1)
    {
3 o# m/ u8 D; D        cout<<"The relation can not be determined!"<<endl;
        return 0;
* M2 ^6 M9 G2 r# D, e$ O3 K    }
1 x6 z& v& P8 k  Q# R& y3 w1 `4 J8 y    string* strRelations=new string[nRelNum];
) ~* p: Y' u& m  R1 g/ U4 o    char* Seq=new char[nSeqLen+1];
: b: {4 R3 f1 ?# u- E    bool** array=new bool*[nSeqLen];
% z/ q  ~' k) u+ H( s( b5 W
    for(int i=0;i<nRelNum;i++)
    {
        cout<<"Input the "<<i+1<<"th relation:"<<endl;
* s2 G# W, T; F) e* W/ @. H- o( g9 K        cin>>strRelations;
' x5 D4 a$ m8 Q6 A& k9 \    }
   
3 d, K/ w9 G% l3 X- [9 `2 |    for (int i=0;i<nSeqLen;i++)
( j/ P3 ^& Z8 W9 w3 ~+ k    {
        array=new bool[nSeqLen];
        for (int j=0;j<nSeqLen;j++)
- T$ q, D9 H6 i" B5 L6 d            array[j]=false;
    }
    //The main loop
    for (int i=0;i<nRelNum;i++)
+ U: u) t1 X6 ?/ @    {
        char a=strRelations[0];
9 ~0 i0 Q8 v& Y  u9 X0 @2 ~        char b=strRelations[2];
        assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
) [; R& X. W6 u        array[a-'a'][b-'a']=true;
$ F3 f4 A6 P- y) ]0 V& S3 ^
( C7 U: F3 \6 G% K+ u1 A& X7 l* m* _        Marshall(array,nSeqLen);
  W8 m5 ?9 b0 P/ ~
$ I6 R; [% x% ]2 k        //Check for Inconsistency after  every relation
/ a0 u) s& O% @2 _) Y" p        for (int m=0;m<nSeqLen;m++)
  I: i' O0 O7 F( v5 q        {
            if(true==array[m][m])
0 o" i+ v7 w$ P- B            {
! z; I$ }# {0 u                cout<<"Inconsistency found after"<<i+1<<"th  relation!"<<endl;
9 V5 T6 w1 C  q0 X+ o                    delete []strRelations;
6 l& }! u8 L. R6 |1 ]+ P0 V( c                    for(int k=0;k<nSeqLen;k++)
7 J9 l; _3 l( ?  g# o0 E. k                        delete []array[k];
                    delete []array;
                    delete []Seq;
; I  ?1 o* J* Y" {* j2 I# Y                    return 0;

2 L/ W' l6 f. Y/ J5 t. F1 k2 r            }
        }
; a$ c9 G+ o( q& I. }/ n7 H
3 W8 @' m/ R, w2 y& q! @9 |        //Check for the determined sequence after  every relation   
        for (int j=0;j<nSeqLen;j++)
1 P6 F% l9 ^6 g, _4 S        {
/ I  d5 X3 t, d+ y8 O            if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))
            {
                cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;
) R& z( h7 v6 l2 K9 ]0 P' D                delete []strRelations;
                for(int m=0;m<nSeqLen;m++)
                    delete []array[m];
                delete []array;
                delete []Seq;
$ C: s/ l8 z6 s1 `                return 0;
" [0 m  c, s1 o* O# L; e9 z            }
7 A2 g% T% r4 e; l' g, b$ O6 R        }
( K+ k! N9 q! p& k

4 R. R' o) e7 u    }
. d2 K  ]" z3 i/ w    //If the program has come to here ,then the relationship hasn't been determined!!!
% d$ e- f5 |  {# `4 ~6 d    cout<<"The relation can not be determined!"<<endl;
- m9 ]" E& k( K# R- u    delete []strRelations;
  X3 b0 W1 G" o8 t    for(int m=0;m<nSeqLen;m++)
! z; Q" m1 ~$ k" }        delete []array[m];
    delete []array;
) y1 K: r5 c" I: b% }2 p7 L" Q: r    delete []Seq;
   
    return 0;
}
& w# I+ i6 L* F% n
+ Y: J2 K2 r! V程序解题二：#include"stdio.h"
% H& e7 D: \: q! `" o$ B, w/ avoid main()
7 |* d- A0 f1 G* v{
    int n_m[100][2];
6 I, k4 z8 t0 W* l. P    char re[1000][3],
    temp[26];
    int i=0,j=0;
    scanf("%d%d",&n_m[0],&n_m[1]);
    for( ;j<n_m[1];j++)
1 C: {% a3 _( o! O6 }* n/ L    scanf("%s",&re[j]);
- D7 I4 }: R/ l4 ?' }# x: o2 K& Q    while(n_m[0]!=0&&n_m[1]!=0)
7 o9 c/ L/ W3 t8 s    {
    i++;
& L8 Q3 ?0 o4 A# V8 |9 v0 K    scanf("%d%d",&n_m[0],&n_m[1]);
    for( int f=0;f<n_m[1];f++,j++)
    scanf("%s",&re[j]);
' {( n; x2 r* |2 o% o  N( G    }
    i=0;
% r% a+ _: X. a    j=0;
   for( ;n_m[0]!=0&&n_m[1]!=0;i++)
    {
       int a=0,b=0,l=1;
0 i( B7 T: d" [# W# \8 P       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])
( w* v9 a: f/ q  w" j            {
            l=0;
            printf("Inconsistency found after %d relations.\n",n_m[1]);
            break;
            }
         }
      if(l==0)
; t/ ]7 I- Y# ~: S          continue;//Inconsistency found after x relations.
    else{
. v. B; R; J1 R$ B# F           if(n_m[1]<n_m[0]-1)
" V$ V; K3 J) p, z& I& L1 [        {
8 m/ Y- C9 _; |& j) s9 o! l" g            printf("Sorted sequence cannot be determined.\n");
            l=0;
        }
        else
3 |/ u+ ]  j# G3 c5 V, N        {
          if(n_m[1]==n_m[0]-1)
$ z" [' W. u) c! t  O          {   
              int k=0,p=0;
6 r, z9 V" m* |# {! I5 U              for( ;k<n_m[1]-1;k++)
; [8 B% ?8 g  T5 G6 j                  for(p=k+1;p<n_m[1];p++)
                      if(re[0]==re[0]||re[2]==re[2])
                      {
) m5 Y+ T' y6 i8 \  U8 Q0 ]                      printf("Sorted sequence cannot be determined.\n");
% l" S+ Q" l: H  {, L                      break;
3 g" ^$ d! }& B% d6 P                      l=0;
8 a3 r, r6 I* M. b                      }
( W4 S# A7 e6 I: m2 [+ X  W2 ?          }
* J! \& p* p. \% Z& _/ l8 c        }
2 j4 `! T" G1 H' D. V: x* M+ R# x: n) g        if(l==0)
5 Z; e; i& W4 P5 G" h        continue;//Sorted sequence cannot be determined.

& F' z* a, U8 o( c        else
8 g3 U2 E$ L4 s* t7 c. |; V3 i; H  U         {
           
            for(int k=0;k<n_m[0];k++)
             temp[k]=k+65;
: ^  R9 {$ T  S* A5 Q" J* g            for(k=0;k<n_m[1];k++,j++)
            {
                int t1=0,t2=0;
/ e" p! I3 j1 q              for(int s=0;s<n_m[0];s++)
& [- v4 Y3 u- n% c% A              {
/ q8 L3 k; E  l) |- l               if(temp==re[0])
                   t1=s;
# m/ w( S4 B- {$ p5 ~- Y2 A                      if(temp==re[2])
7 k( W! l3 F& {7 q, O3 @2 n" Z+ Q                   t2=s;
) _2 ~8 J9 y; b7 |, Q: q5 x- `              }
              if((t1>t2)&&re[1]=='<')
$ n6 r5 c0 t6 [              {
                char t3=temp[t1];
6 q- ^0 @' `, Z9 m2 d* N' _                temp[t1]=temp[t2];
                temp[t2]=t3;
7 q# Y  Z  N6 b8 O6 [              }
            }
        int count=0;
        for(int s=0;s<n_m[0]-1;s++)
        for(int d=j-n_m[1];d<j;d++)
6 m( R5 h8 e8 A/ v  l            if(re[d][0]==temp&&re[d][2]==temp[s+1])
            {
                count++;
                break;
            }
            if(count==n_m[0]-1)
            {
. F% ]; ]" i* Y& V                printf("Sorted sequence determined after %d relations:",n_m[1]);
4 Q' a8 \: }, A+ H, ?                for(int f=0;f<n_m[0];f++)
                  printf("%c",temp[f]);
                 printf("\n");
  J: ?1 g8 R% F; p7 |' x& B            }
: p( N( W' d$ M' s+ c6 j$ M7 l            else
8 t) _+ l7 ^: h               printf("Sorted sequence cannot be determined.\n");
        }
    }
    }
9 H5 {& D% T  v$ l0 e}
; p$ w- w2 u) W/ s



  @( H1 {6 h1 m+ Z

+ h' W5 ~' {$ R1 Q' @* Q

2 w& p8 b7 S. L' R$ D

来源：编程爱好者acm题库