编程竞赛题目（一）

厚积薄发

% i1 \: J* u. `1 e6 V! N8 S
Sorting It All OutDescription
2 m4 l& r! w* @& O; m
# a  u- K6 m; F5 [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.
. P" Z; r: z/ ^$ v. \. uInput

& f" B( m! a1 W* X* U" F: |1 J: CInput 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.
3 I) W7 f7 _, {( u2 q2 `  s3 WOutput
# t2 D; g2 A3 I6 n  d& t6 g
For each problem instance, output consists of one line. This line should be one of the following three:
9 X9 t: P- @2 `# F. }( U
' w1 z) @3 ~9 U) I: K9 v$ Z% N$ uSorted sequence determined after ** relations: yyy...y.
Sorted sequence cannot be determined.
5 k5 d( e7 ^) P/ _Inconsistency found after ** relations.
4 Z* {1 o  _7 n/ j. R
4 U; ~4 i% g; Y- a0 d/ e% A5 S, Q2 S1 pwhere ** 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.
* O2 M$ e6 T, C& z6 u
4 z+ e, l+ a0 @% W: \输入样例

7 t4 i: M; S9 L2 c- a4 6
$ S4 Z! F' q" TA<B
A<C
# ^/ J  }" E# p# ~1 ?7 L8 A  W3 c2 tB<C
7 F; z/ x; m! J* [" y6 }5 iC<D
B<D
A<B
" {4 c, e+ k* j! l7 V/ K3 2
2 E+ H) C& K: u. y4 V& w: ^A<B
! R+ j; G9 f5 y, i5 @, Q: yB<A
26 1
2 d, N- \1 @$ aA<Z
1 f& B: d+ f1 B5 l* p( O% Y0 0

3 m% C  Y7 k' d5 \输出样例

Sorted sequence determined after 4 relations: ABCD.
9 |7 v5 C/ o) L9 W! oInconsistency found after 2 relations.
Sorted sequence cannot be determined.

Source

4 s& a& C+ K8 Z; L! K: ?& l* YEast Central North America 2001

程序解题1：

//By Jackie Cheung
, a0 z; j9 y6 P# o0 h#include <iostream>
: P8 O( d9 L5 _#include <string>
#include <cassert>
typedef  struct tagNODE
{
    char val;
, ~# l* H! m. l. a* b% X+ Z    struct tagNODE* link;
/ I& b; m" s7 |1 \8 K}NODE;
using namespace std;
9 k6 ?% k7 ~" C9 ?( M+ I9 f6 uvoid Marshall(bool** arrary,int n)
/ g, n6 X) `2 S1 H1 J{
    for(int i=0;i<n;i++)
    {
        for (int j=0;j<n;j++)
. a$ ]' C$ L. T5 \. O( a        {
            if(true==arrary[j])
1 q* o( B6 w) d" K, C# D# B. c                for (int k=0;k<n;k++)
                {
                    arrary[j][k]=arrary[j][k] || arrary[k];
* n' v1 [+ k+ \$ X5 C                }
        }
    }
};
% m+ r" q! ?. h9 a) qbool  SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)
/ K  n( J+ W6 G$ w( ~{
9 i6 t5 e/ ]/ V2 s% `& ]& d  n& X    Seq[n-nLeft]=static_cast<char>('a'+nIndex);
    bool bFlag=false;
. f- U7 e" z% y& g& G, Y+ w    if(1==nLeft)
- h, T- G+ S$ O- D+ L4 s: M/ K/ r    {
        Seq[n]='\0';
% \! o- L" c) h4 e( {* r# n        return true;
    }
5 Q& N9 t9 E' [* o; p! P    for (int i=0;i<n;i++)
: B3 z+ r8 C1 z    {
        if(true==array[nIndex])
        {
            
            bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);
( t$ N5 j% `, ]7 T2 U5 Q        }
        if(true==bFlag)
            return true;
* C. |' O, E" _: b9 @    }
    return false;
( v9 [8 e" f/ O, e2 |, w};
int main()
4 ^. X8 \3 ^3 V9 O% s/ E/ A7 r{
    int nSeqLen;
    int nRelNum;
    cout<<"Input the length of the sequence:"<<endl;
    cin>>nSeqLen;
: @4 \1 X- n2 U8 O6 x, a8 Y- Y    cout<<"Input the number of relations between the elements:"<<endl;
  B) q# i% P9 X+ h    cin>>nRelNum;
    //1:if nRelNum<nSeqLen-1,then the relation can not be determined!
' }" N) s( }* i9 S) i. n7 _( |    if(nRelNum<nSeqLen-1)
1 n1 |/ |2 G9 {, p    {
2 b' ~7 N2 W+ b5 b% Q' S        cout<<"The relation can not be determined!"<<endl;
        return 0;
    }
    string* strRelations=new string[nRelNum];
, |5 N" U' k0 V8 x% r0 B    char* Seq=new char[nSeqLen+1];
    bool** array=new bool*[nSeqLen];

    for(int i=0;i<nRelNum;i++)
% F$ I; a0 B; _2 V- [5 w    {
% M7 S# u( s6 I  q8 M6 B        cout<<"Input the "<<i+1<<"th relation:"<<endl;
! }" L" ]5 l. {: _        cin>>strRelations;
    }
   
8 o' R3 I3 U: e) E" O$ [1 ~; Z    for (int i=0;i<nSeqLen;i++)
    {
) ]  m1 g9 O6 q) I1 k        array=new bool[nSeqLen];
  l+ e# {9 w/ g        for (int j=0;j<nSeqLen;j++)
            array[j]=false;
) _' Y: x) L5 \9 y) M    }
    //The main loop
    for (int i=0;i<nRelNum;i++)
; D& \& X0 \1 l    {
        char a=strRelations[0];
+ K- [& O& z) x5 X: p) l& ^        char b=strRelations[2];
' ~" d4 O$ f& I' M        assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
' a: S8 K0 i% V+ ]- f+ t4 S        array[a-'a'][b-'a']=true;
( }3 g. O7 R* b( f' t  m
        Marshall(array,nSeqLen);
3 ^) T/ d, C9 Y" [
$ H  h6 }" K+ D! M        //Check for Inconsistency after  every relation
7 Q5 S# @7 \8 Y  f5 |  q' G9 W        for (int m=0;m<nSeqLen;m++)
% s% ?0 v5 O$ I2 s& X' E7 K        {
" U1 L5 d# p& b) Z2 Q+ I            if(true==array[m][m])
* ~, u4 V1 B  n/ C& {            {
                cout<<"Inconsistency found after"<<i+1<<"th  relation!"<<endl;
                    delete []strRelations;
                    for(int k=0;k<nSeqLen;k++)
                        delete []array[k];
; }! s0 A& ?4 f0 L# N/ _8 o3 Q0 ]6 W# L                    delete []array;
                    delete []Seq;
9 ^8 s/ f( i7 M/ @& D                    return 0;

            }
        }
, G! f# `$ @2 Y- ^) I8 ]
; j3 V, g1 p* d# I' H        //Check for the determined sequence after  every relation   
        for (int j=0;j<nSeqLen;j++)
7 V/ M; I) h* [6 i        {
            if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))
            {
# L/ w% b" }6 W$ U5 h                cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;
; O1 M1 t& w9 w( n                delete []strRelations;
                for(int m=0;m<nSeqLen;m++)
, _0 F: \4 z" a* {% ^6 G- ]1 P                    delete []array[m];
) j* U! Z+ m) }- B8 v                delete []array;
. u. {: A! t  R( b8 x1 m8 Y                delete []Seq;
: @  N/ t* U6 G  D  ~                return 0;
3 s) R5 w+ F$ f; o            }
! |4 i: R7 C3 o: w8 P& n0 z        }
$ K, X; o0 Y1 ~/ r0 m/ I( {& ?/ H

$ ~; {, h8 K* `3 r% a0 F+ o    }
* X- `$ V! U5 h/ }1 v- W    //If the program has come to here ,then the relationship hasn't been determined!!!
    cout<<"The relation can not be determined!"<<endl;
% d1 r1 _+ d& d, f2 [    delete []strRelations;
9 X- j7 z5 Q0 x( n  i" j3 P    for(int m=0;m<nSeqLen;m++)
$ @) _1 R: m6 G) X- l/ B        delete []array[m];
    delete []array;
" ?; o% M/ R6 x4 \* {    delete []Seq;
5 w  x& f  ^7 s9 c; E% G- p   
    return 0;
' q# l. D0 k& U: i2 N. {}

' B; O! E* @7 |4 ~6 M程序解题二：#include"stdio.h"
. M2 o* ^, |2 \! e1 Y' J) ^void main()
{
" [) `7 J) C. B6 U& g8 ]. ^$ e    int n_m[100][2];
    char re[1000][3],
, s8 |  @( T. r2 l1 k. w7 ^    temp[26];
+ M) C2 }( C8 [) V$ X    int i=0,j=0;
8 `, B# R& l4 E- Z3 M    scanf("%d%d",&n_m[0],&n_m[1]);
    for( ;j<n_m[1];j++)
8 m3 R5 J4 P- j6 o8 a0 v! u    scanf("%s",&re[j]);
    while(n_m[0]!=0&&n_m[1]!=0)
    {
    i++;
' \, ]! l0 J5 d; \& }( e    scanf("%d%d",&n_m[0],&n_m[1]);
- c. o4 _& t( n1 F4 r" J% N7 ^    for( int f=0;f<n_m[1];f++,j++)
    scanf("%s",&re[j]);
    }
) ?1 ~+ F4 N6 w# Y; z% a    i=0;
  n9 V; B  v9 k9 L2 K/ ^; X2 _; L    j=0;
   for( ;n_m[0]!=0&&n_m[1]!=0;i++)
3 d& C9 G5 d$ v$ B: V4 R0 f5 Z% s    {
! X4 W3 _. P, C! w+ b       int a=0,b=0,l=1;
       for(a=j;a<j+n_m[1]-1;a++)
1 q; a& g& [) e/ W3 R  X! R         for(b=a+1;b<j+n_m[1];b++)
( \4 j0 Z2 y6 i; D  s9 l         {
& K7 Q6 J" ?, R* H9 z8 _* u5 G4 R              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])
            {
1 m4 G+ |3 ?* X+ }( O( D* i3 O1 S            l=0;
6 a# O/ w. w2 z5 v! R1 p9 \' b            printf("Inconsistency found after %d relations.\n",n_m[1]);
, S5 U1 p5 ]# Q4 j4 x" J            break;
5 g$ H/ G4 T/ P4 D' X( f            }
" l, e5 [1 P9 \# f4 g         }
# \# P0 t0 Q: a( Z* O$ |      if(l==0)
          continue;//Inconsistency found after x relations.
    else{
$ z: P" O; l% p; {. z; J  w* T           if(n_m[1]<n_m[0]-1)
% B* D! n3 s  j8 ]        {
            printf("Sorted sequence cannot be determined.\n");
            l=0;
9 v/ K( |% \3 g) p        }
        else
, P8 g2 q( b$ N7 o" \+ M        {
          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++)
                      if(re[0]==re[0]||re[2]==re[2])
                      {
9 U) {5 X) [' `& {- C/ Q' Y                      printf("Sorted sequence cannot be determined.\n");
. w3 @, E/ h! |) [; ^  i                      break;
                      l=0;
( `" a' w$ w/ P8 r, M1 T! a                      }
# N6 \( ?* S2 D/ M          }
9 D- S# O* u% T        }
  o) S6 q% x7 U1 b8 \        if(l==0)
        continue;//Sorted sequence cannot be determined.
, i# `) X( _, Z9 L$ r8 Y+ o; l
        else
1 F+ r# Z0 N. I& a, Y! G7 X         {
9 z7 V/ v! z% s' ?4 q3 l9 Q; z           
2 K: |1 \  W- Z! b* F0 M            for(int k=0;k<n_m[0];k++)
* Q$ |$ ^( ?2 w/ _) k' c             temp[k]=k+65;
5 M4 N; I: w4 b  H; t1 F% f            for(k=0;k<n_m[1];k++,j++)
) F. z) s! f8 E# N, k  ]1 _            {
5 Y" V7 X. @7 u5 p, A3 ~                int t1=0,t2=0;
' b4 d( I+ L5 k; G0 @              for(int s=0;s<n_m[0];s++)
              {
               if(temp==re[0])
8 v+ q/ u( y0 d+ f' h1 c                   t1=s;
                      if(temp==re[2])
                   t2=s;
! F% M/ X+ K1 Y4 j, f3 q# E) W( d; p              }
& V# ]/ z( O$ d# A              if((t1>t2)&&re[1]=='<')
% m9 ]& v4 ^) U. S& h              {
                char t3=temp[t1];
+ I/ {2 M* q6 n! Z4 S2 H8 I; ?) |7 Z                temp[t1]=temp[t2];
$ O' B, K! W/ g2 o3 V1 |                temp[t2]=t3;
1 l- e- K9 P- R) y! V# T  x3 c. s5 d              }
: o7 j: I3 F. f  I3 j; Y: ^# Q            }
% z% V& L- h* p: o4 o5 \& ~% A- D        int count=0;
1 a+ Y' \/ I4 N% P        for(int s=0;s<n_m[0]-1;s++)
/ F$ ?4 }4 X# Y1 H! f* n& U. D" F3 `        for(int d=j-n_m[1];d<j;d++)
            if(re[d][0]==temp&&re[d][2]==temp[s+1])
            {
5 I- R7 ?( f& @" f                count++;
                break;
2 }" C) c$ o) {            }
. P: u2 I9 @1 `  I% L; `/ q            if(count==n_m[0]-1)
            {
                printf("Sorted sequence determined after %d relations:",n_m[1]);
( y$ G$ ~& Q9 I& L% D  ?                for(int f=0;f<n_m[0];f++)
6 a* T. }) J1 V2 P7 E8 M                  printf("%c",temp[f]);
+ c) q1 T* v5 r- F: v                 printf("\n");
& b: T4 w4 t  M* D& u0 v6 L+ t            }
( A5 B# A% m8 z# ^& {  Y% w            else
               printf("Sorted sequence cannot be determined.\n");
        }
  k' x4 J5 {' I6 h0 k2 N* a/ d    }
* y; {& L1 s7 Y, O* r    }
}







6 u2 T, {# h5 `) ?% S2 f: f
+ @* n/ ]& Q* F1 ~; A9 z

来源：编程爱好者acm题库