编程竞赛题目（一）

厚积薄发

Sorting It All OutDescription

: G5 a4 t; @& dAn 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 s' S8 }- a0 [5 R, T- A% y8 fInput
! r4 g* a& J4 R3 m1 X" r
# R+ s# _5 m" D! d  AInput 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:
. L7 Y+ E# z+ c7 M- i% g
' K. C- b" w% m6 Y) k$ JSorted sequence determined after ** relations: yyy...y.
5 F7 [& _* i0 S9 y# A' VSorted sequence cannot be determined.
Inconsistency found after ** relations.

9 S. x; J. j( 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.
3 m; e: {$ [9 u' k: W4 g
输入样例

4 ]8 N) a! m$ W4 Q( C* J2 }4 q4 6
8 O2 G/ P, t/ BA<B
A<C
B<C
6 G+ T0 g# M1 W6 R% KC<D
3 u5 S2 Y  u  O2 r; ~) k8 p. H7 ~B<D
A<B
3 2
A<B
$ Q7 G* o/ r; N' I5 EB<A
( @6 k. `5 T0 c2 {( {26 1
8 T- {; g2 Z( M# g. M5 h/ V4 C5 yA<Z
0 0

( |. H' p  p0 j  z/ `+ x1 y输出样例

Sorted sequence determined after 4 relations: ABCD.
+ \, a+ ]( S; A# i2 X0 KInconsistency found after 2 relations.
7 ^: J) P* k. I) ?0 V- a# r# uSorted sequence cannot be determined.

Source
7 R4 Z3 t, T; f# d% W, I- U0 y
East Central North America 2001

7 Z# e! E, L) L4 s2 Q$ Q+ o* Q0 a- C- c

程序解题1：

5 |3 W9 P5 W  Z( p* J$ u//By Jackie Cheung
#include <iostream>
, J3 a+ Y! {- P$ y" e4 _* N. d) b#include <string>
#include <cassert>
  U6 o8 w3 }% }3 o8 R, @' [# ntypedef  struct tagNODE
{
    char val;
    struct tagNODE* link;
! v5 p: w0 r' `9 N/ u. M* _4 l2 U}NODE;
using namespace std;
% B# y$ z; W! x% r7 Gvoid Marshall(bool** arrary,int n)
/ z9 \2 C7 Z, T) j+ W( J{
' u6 I  R; C% F/ s1 M$ V# [    for(int i=0;i<n;i++)
    {
4 U4 p5 V9 ?9 J. S: g9 t9 q        for (int j=0;j<n;j++)
8 a7 M# Z. F; t        {
9 q( l5 Z* w  G+ G4 m! d( R            if(true==arrary[j])
                for (int k=0;k<n;k++)
                {
                    arrary[j][k]=arrary[j][k] || arrary[k];
; _8 S3 A# \% o  b3 ~                }
7 x2 Q; d) i; U- q6 U+ ?1 q* S        }
" V3 x* y3 o6 k* R7 |% O    }
};
% t  g; A5 k7 Hbool  SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)
, l0 M/ K  A3 {. G8 e{
9 n( W: @8 f' L7 {9 @* {    Seq[n-nLeft]=static_cast<char>('a'+nIndex);
    bool bFlag=false;
    if(1==nLeft)
    {
        Seq[n]='\0';
        return true;
$ Z- s# z7 y+ J, J, g    }
5 r! b4 L% u3 b    for (int i=0;i<n;i++)
) J$ A: R* R; _4 U& {( x" ~  f5 Z    {
- a/ y5 `8 [% X$ a) [        if(true==array[nIndex])
4 s3 ]3 r" T& v2 |        {
            
            bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);
        }
        if(true==bFlag)
6 {  B. }- N. J: v            return true;
9 Q6 }  X' c3 c; @    }
    return false;
};
int main()
{
    int nSeqLen;
& _+ {  k. I8 a8 O( r: v, j( [    int nRelNum;
3 I* M- @+ \: r- C2 |! z9 L3 m& e" N4 r    cout<<"Input the length of the sequence:"<<endl;
6 l% p" g  E& H) v3 P% V    cin>>nSeqLen;
4 c0 t6 |& s+ P% ?$ z+ A# s" r    cout<<"Input the number of relations between the elements:"<<endl;
    cin>>nRelNum;
    //1:if nRelNum<nSeqLen-1,then the relation can not be determined!
0 H; v6 B$ h! O0 E( `; L8 E    if(nRelNum<nSeqLen-1)
, D' J8 {& N7 X1 O2 E' e5 u    {
* l/ y, F- B0 O2 E7 K        cout<<"The relation can not be determined!"<<endl;
& T% J; g! Z8 M7 k* K9 m; I  P6 e        return 0;
    }
    string* strRelations=new string[nRelNum];
" \2 \( z  b4 e  Q  j; x6 `    char* Seq=new char[nSeqLen+1];
    bool** array=new bool*[nSeqLen];

5 h8 }2 ]+ n' i7 O" Q* I    for(int i=0;i<nRelNum;i++)
    {
* ?+ H  D+ L/ g2 S. k) ]        cout<<"Input the "<<i+1<<"th relation:"<<endl;
- o/ }0 O! ^1 Y! z' [6 L6 v        cin>>strRelations;
    }
& M0 W  x) x0 i! c   
    for (int i=0;i<nSeqLen;i++)
+ Z8 E' F1 D+ I3 r    {
        array=new bool[nSeqLen];
        for (int j=0;j<nSeqLen;j++)
  N! U; ~4 y( c            array[j]=false;
    }
+ i7 Y. u+ A, ~6 X( X) G$ [    //The main loop
    for (int i=0;i<nRelNum;i++)
, E; s  E- ^; m3 w  ~$ @* I& U! H    {
        char a=strRelations[0];
        char b=strRelations[2];
0 Y  X: T# d; `$ `        assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
% t2 n. w4 O! A5 F, i        array[a-'a'][b-'a']=true;
! d2 w/ D- o: _' y* W! H6 w* T: \
        Marshall(array,nSeqLen);
3 m7 F& I; i3 _; y% r
( l# L4 j# P6 J4 k* P7 ]" _- d$ }        //Check for Inconsistency after  every relation
        for (int m=0;m<nSeqLen;m++)
        {
% Q) u7 u3 A& W2 F5 r: ?            if(true==array[m][m])
            {
                cout<<"Inconsistency found after"<<i+1<<"th  relation!"<<endl;
                    delete []strRelations;
, _0 B0 q, |( F" D' p6 x% F) S4 O& V                    for(int k=0;k<nSeqLen;k++)
                        delete []array[k];
                    delete []array;
                    delete []Seq;
, E) s( ~6 R% B+ z                    return 0;

            }
6 M! A2 Q9 m6 s5 ~1 \3 Z/ G- L        }
2 W2 v$ G8 B6 v, Y; n0 G5 L
+ ~" i. ?3 `% U2 x: j- Z3 Y        //Check for the determined sequence after  every relation   
: }( P1 T; n8 h7 C) B        for (int j=0;j<nSeqLen;j++)
9 I5 g4 N6 e1 H' r: W( ]        {
" D9 k& `, x  ]9 V            if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))
/ e  y' q5 c  z; a            {
- ~; ^, O/ E1 g! ]( y                cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;
& @9 R  P8 C, C) C- k                delete []strRelations;
                for(int m=0;m<nSeqLen;m++)
; s3 O* g3 l; w  p                    delete []array[m];
+ E9 E. Q$ l  u/ l3 z                delete []array;
                delete []Seq;
3 z, ^5 p+ r$ V- U1 s8 S: f" p                return 0;
3 C; ?' \+ F, ]6 t! T            }
        }

: B/ u; @; s# f' m6 `/ X
    }
    //If the program has come to here ,then the relationship hasn't been determined!!!
    cout<<"The relation can not be determined!"<<endl;
7 a% u2 b  h5 h2 l& r    delete []strRelations;
    for(int m=0;m<nSeqLen;m++)
        delete []array[m];
    delete []array;
    delete []Seq;
$ b$ t; E5 R4 _5 y1 T2 b8 D- m  d$ C   
4 u% X& i% ^- d. a6 ?) r% k    return 0;
}

& k; T/ |6 O# L* w1 Z程序解题二：#include"stdio.h"
, N3 r7 ?  A5 o# evoid main()
{
    int n_m[100][2];
    char re[1000][3],
# d) Y1 s2 k6 Y& D3 }    temp[26];
    int i=0,j=0;
& |/ B/ B' h! M+ `5 s! e    scanf("%d%d",&n_m[0],&n_m[1]);
    for( ;j<n_m[1];j++)
    scanf("%s",&re[j]);
    while(n_m[0]!=0&&n_m[1]!=0)
/ L( O/ y7 R0 @- _, t. Q' l    {
- _( R5 j6 I1 H. F2 U- x    i++;
/ z  B, z" y# J, O8 b    scanf("%d%d",&n_m[0],&n_m[1]);
% b( `* i" k. U% u" ]$ q$ [' H7 {    for( int f=0;f<n_m[1];f++,j++)
    scanf("%s",&re[j]);
# ~/ @1 B' q5 w, `- l6 E9 R( X6 x% p    }
    i=0;
    j=0;
8 w% c: S" Q: K, _4 {  a   for( ;n_m[0]!=0&&n_m[1]!=0;i++)
    {
       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++)
/ Q) D0 V" z6 V         {
, V! t2 x1 X# E- W  Y  s              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])
5 B$ Y( q) k; ~+ d5 b$ f            {
            l=0;
            printf("Inconsistency found after %d relations.\n",n_m[1]);
            break;
, t/ {5 G) }6 I            }
& i& E0 @' ^0 [         }
      if(l==0)
2 ^4 r3 j4 x) {3 e- @          continue;//Inconsistency found after x relations.
    else{
2 B% g7 r3 m7 O) _. H+ J           if(n_m[1]<n_m[0]-1)
* h8 c: }1 E* S& K% b        {
$ j8 y/ N, K9 D+ m8 \% a            printf("Sorted sequence cannot be determined.\n");
            l=0;
, s0 j* Q% _+ p! n        }
$ U# S: J0 s% a/ c        else
        {
7 _) M: O. w3 J/ j; {# B( h+ t          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++)
/ L6 P1 F, m2 X5 p                      if(re[0]==re[0]||re[2]==re[2])
6 N, e. q- o: g& P- i                      {
8 f8 U& q- Q! `1 T1 v9 _/ V: ?" }                      printf("Sorted sequence cannot be determined.\n");
6 ?& E) D3 @0 A# Z; R7 |0 i- }8 }                      break;
( j1 h/ O4 {( T3 I3 O* M/ z                      l=0;
                      }
6 D7 \, m: g; B2 T% Z          }
        }
        if(l==0)
        continue;//Sorted sequence cannot be determined.
+ Q7 b% O- m3 u) A5 f# `* O1 ~+ `2 n
        else
         {
; S5 @. R8 z/ N! |: [; e9 \           
            for(int k=0;k<n_m[0];k++)
             temp[k]=k+65;
            for(k=0;k<n_m[1];k++,j++)
            {
                int t1=0,t2=0;
; l% u1 q4 H- i4 `* I# Y              for(int s=0;s<n_m[0];s++)
0 |7 R5 E5 @0 F' q              {
$ D7 Q* ^8 ?4 R8 q  W2 t               if(temp==re[0])
1 W) G& L" |; w& m- |. w                   t1=s;
                      if(temp==re[2])
3 n# N' b- S* d3 o- d                   t2=s;
4 h. N! F0 ?0 u1 _  p6 I              }
              if((t1>t2)&&re[1]=='<')
0 \% i! S) z, @' h" D; t              {
  t3 O2 Z; ^2 }" O; N$ F( r# P4 a                char t3=temp[t1];
                temp[t1]=temp[t2];
                temp[t2]=t3;
8 l! k4 D; [( r! }              }
. V8 Z( v( x! k0 K. l! s, [' q            }
        int count=0;
% ^# e! _9 E3 e: T. j) e$ f        for(int s=0;s<n_m[0]-1;s++)
2 r/ ]- f& h/ j" R        for(int d=j-n_m[1];d<j;d++)
& E- Z8 N) m7 F6 w            if(re[d][0]==temp&&re[d][2]==temp[s+1])
& R" n0 }& }" ^" ?            {
                count++;
" r- ?/ D" e# z* [" R                break;
            }
            if(count==n_m[0]-1)
            {
$ {% C1 R/ ^( v, r$ D                printf("Sorted sequence determined after %d relations:",n_m[1]);
                for(int f=0;f<n_m[0];f++)
9 D) Y0 D8 a* P6 G$ i1 }" ~                  printf("%c",temp[f]);
                 printf("\n");
7 _% ^: l$ w& m6 z6 u! C' A1 _" L            }
            else
' T$ }+ P! B1 i8 l# N8 S               printf("Sorted sequence cannot be determined.\n");
6 c" B5 H* X% M9 c# t) _2 m        }
' r$ x1 w" V; y$ h7 y4 T    }
    }
}
1 W  m3 y) i  K  ?$ ~
# e  ]. V3 ~. G" H/ I

" x, @4 _% N/ B% `4 S% j: ]

5 K( E+ I5 v# e( M2 ?
6 F0 V# m% `* N7 ]( v! `
7 _6 J2 C, @% E8 D0 x
" V$ X3 U, N$ @$ ~+ B' G, K9 t$ t

来源：编程爱好者acm题库