编程竞赛题目（一）

厚积薄发

6 e. k6 |. `. X  F3 ^Sorting It All OutDescription
( F! }5 _' M$ b9 E- A7 L; w
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.
9 p# ^. [0 [# `& S3 I4 F. ~  w# sInput
3 c7 j5 i2 t/ R+ Y/ y( M
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.
) Z+ r% r! E; o1 \: N4 O8 SOutput

# q. h# x; t: B" a7 cFor 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.

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.

输入样例

, t% S. c3 L" Y2 g# j+ i4 6
A<B
A<C
2 V1 l8 w2 w1 |5 qB<C
- N5 P. v, B; ^C<D
B<D
A<B
1 z7 T  ?- I5 T! \0 B- X1 \3 2
: X8 M1 T! C- X9 k1 BA<B
B<A
26 1
A<Z
0 0
+ v2 W/ @) E; p: o) q) U; ~6 n

输出样例

* o+ Y' O- X2 I# sSorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.

+ R7 @0 h0 ]6 {! G) t

Source
4 A7 ^1 K6 [, @9 }' ^+ F
East Central North America 2001

+ I) h8 n* [( F0 ?6 ]4 _3 b

程序解题1：

//By Jackie Cheung
  Y6 p: m$ [" o: e! L  ^#include <iostream>
6 q5 I6 d/ _6 R#include <string>
* }3 ]( S% K6 d; m( D#include <cassert>
typedef  struct tagNODE
{
6 b/ n( J# _% a& K* B& D    char val;
    struct tagNODE* link;
}NODE;
, h3 O. j  l1 {* U: d% iusing namespace std;
void Marshall(bool** arrary,int n)
$ a" h' O* L$ k4 A! i0 B{
    for(int i=0;i<n;i++)
6 R, J  h( y9 l# K9 s8 L    {
        for (int j=0;j<n;j++)
7 a  u3 ~0 K* e        {
0 R. Q' r8 u+ L; z            if(true==arrary[j])
+ x0 f3 W. u. j) i7 P                for (int k=0;k<n;k++)
7 N7 m5 O6 Q- Q( W1 [4 G                {
& }) M- R) W, o8 p2 N                    arrary[j][k]=arrary[j][k] || arrary[k];
                }
$ a5 ^) F6 y; Q. Q9 Z) J        }
% \8 G( K; U* ]: Z, j$ o    }
};
' i! p2 O$ d8 o3 {& Ebool  SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)
{
/ A1 [' U: W- \1 P; w2 O. l" c    Seq[n-nLeft]=static_cast<char>('a'+nIndex);
    bool bFlag=false;
, r1 V( z3 U5 C) y9 N7 }/ ~4 z    if(1==nLeft)
    {
        Seq[n]='\0';
        return true;
% j8 J0 b2 g5 x$ s' v( @' o    }
    for (int i=0;i<n;i++)
8 J- w4 Z1 ~& o    {
        if(true==array[nIndex])
        {
. R3 c, L# C9 h' Q& X& B            
            bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);
( V7 ~0 E5 a+ d) W. s+ d! }: t2 w# C: d0 F        }
. L+ _4 O# M4 D* w5 s        if(true==bFlag)
9 H: ?4 B3 y* c+ m, h" L/ t            return true;
    }
5 v/ \" D: T4 E* \  s/ |& a+ A    return false;
) T  ~- A9 Q$ g% s6 y6 a};
int main()
{
7 E' [" P4 {6 O+ q# r- R    int nSeqLen;
3 \& x+ f/ B5 u( g/ w" e$ s5 e    int nRelNum;
" n5 h" I- J% X, }- \    cout<<"Input the length of the sequence:"<<endl;
1 n6 W6 ?6 x/ s    cin>>nSeqLen;
) U5 p. E0 x! ~% j  {    cout<<"Input the number of relations between the elements:"<<endl;
+ ?% Z" }( |- z    cin>>nRelNum;
. q, z& I, K5 N7 O& |    //1:if nRelNum<nSeqLen-1,then the relation can not be determined!
% _! R$ r  {. e( e    if(nRelNum<nSeqLen-1)
    {
        cout<<"The relation can not be determined!"<<endl;
        return 0;
3 `5 ?5 d3 l0 |  D4 |' K2 J    }
    string* strRelations=new string[nRelNum];
$ g9 M' r* U$ F1 a    char* Seq=new char[nSeqLen+1];
    bool** array=new bool*[nSeqLen];
' W, X6 q" v, b" @4 k  Y1 G
    for(int i=0;i<nRelNum;i++)
    {
        cout<<"Input the "<<i+1<<"th relation:"<<endl;
        cin>>strRelations;
$ {  K: P% ^: F! p( L' S    }
1 S7 C  {0 e5 b; B   
    for (int i=0;i<nSeqLen;i++)
    {
        array=new bool[nSeqLen];
$ z" L4 S, N- Z        for (int j=0;j<nSeqLen;j++)
3 v/ G/ g( k# U6 G0 e            array[j]=false;
    }
0 x! P( }, L" F" O& J8 |. W6 x" V  W9 a    //The main loop
# `- K( I" p9 e4 h% M    for (int i=0;i<nRelNum;i++)
    {
( H" `2 f  t! J2 s! D        char a=strRelations[0];
# J/ b; Z7 A* S        char b=strRelations[2];
        assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
        array[a-'a'][b-'a']=true;
" V  x* d) n5 S  P
% X0 z9 [, m/ a9 u- [- j        Marshall(array,nSeqLen);

        //Check for Inconsistency after  every relation
        for (int m=0;m<nSeqLen;m++)
, |" t4 q) H) E8 P- V5 j        {
4 q1 o% E4 ~  F* s3 U! K  g            if(true==array[m][m])
            {
1 m& R3 ]1 Z; X                cout<<"Inconsistency found after"<<i+1<<"th  relation!"<<endl;
& ~, x8 d* y8 b) ]                    delete []strRelations;
                    for(int k=0;k<nSeqLen;k++)
                        delete []array[k];
5 }8 J* ~' d+ h5 J* V5 a9 T                    delete []array;
                    delete []Seq;
                    return 0;
. V' t6 K! ?7 p2 Z# b# G0 f
            }
" ~2 l, |$ I# b2 ]- K; ^& i; ^        }
5 K5 [! V1 k( V0 k$ Z% f  Y
* \$ i% A) |, p9 x        //Check for the determined sequence after  every relation   
        for (int j=0;j<nSeqLen;j++)
, m- A; j+ F  e8 x1 U) ]2 y2 P        {
            if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))
1 b0 e7 h. K8 O- A2 l4 c7 l5 [2 v1 C            {
+ H" j% R, J' B! c- D                cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;
; n- q7 N6 ?' @: i                delete []strRelations;
                for(int m=0;m<nSeqLen;m++)
                    delete []array[m];
                delete []array;
                delete []Seq;
- `  K8 {6 W; k4 X2 ]  {% O% `                return 0;
            }
        }
: B! h1 t# n2 Q- l3 ]! M

5 d& A7 y& b/ _) M5 K3 T4 l& n6 q    }
    //If the program has come to here ,then the relationship hasn't been determined!!!
4 k# c- i/ Q8 b- q9 T0 f: u9 Z" O0 t/ f    cout<<"The relation can not be determined!"<<endl;
* Q( d2 ^: |! f, `7 x    delete []strRelations;
* Y6 V! R/ m) X) Y    for(int m=0;m<nSeqLen;m++)
        delete []array[m];
    delete []array;
: c& m1 P* t! ]' L    delete []Seq;
/ u8 s& T% [/ r7 @  O# F) c+ t   
- w" o6 }" e  k  Q5 C    return 0;
) K  `; _5 ]& L! j}
6 z' B0 c5 i6 V
程序解题二：#include"stdio.h"
void main()
! N. X  ~0 `' ^9 I{
, S/ N/ y$ a! ?, C6 I3 w: |& t# f    int n_m[100][2];
    char re[1000][3],
    temp[26];
  ?5 o0 X4 l  L    int i=0,j=0;
( g/ v: W9 d: D  v; }    scanf("%d%d",&n_m[0],&n_m[1]);
% _& \; I( J- d+ H3 N  k! y6 a: R    for( ;j<n_m[1];j++)
$ _, n) V( l  [- s/ O    scanf("%s",&re[j]);
6 U+ G1 i0 f% L    while(n_m[0]!=0&&n_m[1]!=0)
+ H' V& \* P1 G5 }    {
+ c& r5 ~. }9 e( ~* w! y! |4 c    i++;
    scanf("%d%d",&n_m[0],&n_m[1]);
* N5 P* N3 {. s$ A! o    for( int f=0;f<n_m[1];f++,j++)
7 Y" d6 |, R3 o    scanf("%s",&re[j]);
    }
4 Y" [- m; r4 J3 |    i=0;
    j=0;
   for( ;n_m[0]!=0&&n_m[1]!=0;i++)
! I8 L; Q% V4 w6 u! s    {
       int a=0,b=0,l=1;
: F+ \  X( R4 K5 V/ K       for(a=j;a<j+n_m[1]-1;a++)
         for(b=a+1;b<j+n_m[1];b++)
# d7 i1 x6 Q' G: J. v2 @, |8 T         {
              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])
( E- y" s# B7 B: [9 u: D            {
7 ~. a" m7 t/ U9 s3 E: R            l=0;
$ ~0 \5 ^! Z/ q) ~            printf("Inconsistency found after %d relations.\n",n_m[1]);
            break;
            }
         }
      if(l==0)
6 Y4 @- y; ?8 q0 }( C          continue;//Inconsistency found after x relations.
  n: V$ ]4 R6 E% j    else{
/ {/ p/ W: C4 s5 B% S           if(n_m[1]<n_m[0]-1)
8 Y* b5 C' H8 {. \# K1 e5 J5 h2 F        {
; Q1 E+ n+ n  u7 R            printf("Sorted sequence cannot be determined.\n");
% N( C6 X0 d% F1 i' {            l=0;
0 M2 V; d' A. W# {        }
7 Y' H* m. w/ x* C        else
: T* u; o8 k/ I; g# A6 G. ~        {
7 t* V+ K6 F4 C+ K8 [7 Y* h          if(n_m[1]==n_m[0]-1)
          {   
( r8 g$ a: n% e8 z( `+ n7 f7 A' `              int k=0,p=0;
5 r5 ], ?% j8 H0 i% ]$ x              for( ;k<n_m[1]-1;k++)
. \0 Y9 |3 j$ A" @' G& U                  for(p=k+1;p<n_m[1];p++)
                      if(re[0]==re[0]||re[2]==re[2])
) X: e5 }: A" g1 L$ W+ J4 U0 F                      {
                      printf("Sorted sequence cannot be determined.\n");
                      break;
* o4 V6 }5 ^8 U9 K" Z( ~* W                      l=0;
# d2 ?2 W! L. [+ v                      }
          }
! k2 Y4 O$ J$ t$ @2 \  R0 h. L        }
6 J+ y" _0 {2 O0 _% S" R$ S' n+ D        if(l==0)
" J( {+ f+ B+ T8 V' k        continue;//Sorted sequence cannot be determined.

        else
; t; }' D7 Z0 j) \2 {, d3 U) B6 @2 n         {
           
            for(int k=0;k<n_m[0];k++)
- ?4 _4 ]; r% w+ K9 e* B             temp[k]=k+65;
            for(k=0;k<n_m[1];k++,j++)
            {
                int t1=0,t2=0;
              for(int s=0;s<n_m[0];s++)
* p- k$ [! J6 y3 `3 C- X              {
/ ~/ ]6 S4 Q+ x0 o( D2 N               if(temp==re[0])
                   t1=s;
3 q& ^! Z8 O) ~, Y8 n                      if(temp==re[2])
/ ^- U- b: B4 p* Y: Z, b3 u                   t2=s;
              }
              if((t1>t2)&&re[1]=='<')
) g2 Y) l2 t0 \2 v" q- t8 ]              {
                char t3=temp[t1];
: S8 u( @3 F- s- e! Y. t% R                temp[t1]=temp[t2];
                temp[t2]=t3;
8 Y2 x7 @$ U, j; P! p6 z5 |9 |              }
6 p/ J* o2 W3 j1 B$ A* ^            }
6 g2 [. t# h( |        int count=0;
        for(int s=0;s<n_m[0]-1;s++)
4 y# u) `  m2 {        for(int d=j-n_m[1];d<j;d++)
5 a( r4 o% j/ P0 g            if(re[d][0]==temp&&re[d][2]==temp[s+1])
            {
                count++;
                break;
, N9 q- y& }# u: E4 y" K" b+ s            }
            if(count==n_m[0]-1)
! _* j: b/ ]# ~% t/ g2 h            {
8 v" j0 E; F. W5 T& \                printf("Sorted sequence determined after %d relations:",n_m[1]);
7 G' z2 u- g; F: c& L+ R0 G, Y: L                for(int f=0;f<n_m[0];f++)
4 [' C, F7 P. g/ h; U& Q/ |3 n% v% l                  printf("%c",temp[f]);
$ e& k( @, m# q                 printf("\n");
            }
- c: ?( X0 d: E0 B) s8 y            else
               printf("Sorted sequence cannot be determined.\n");
, @* [1 b: ?. V1 W" U  q! ~        }
: u0 J1 |0 J4 r0 W* ~: Z; p    }
: i/ U5 v4 u! X1 M3 y    }
}
, h6 T+ y2 ~) g, s( M& @

2 X! `) k, s, ]2 H7 E4 @



. M9 C; U4 h% b+ q

来源：编程爱好者acm题库