编程竞赛题目（一）

厚积薄发

Sorting It All OutDescription
, W: C) y/ [4 D+ O3 F
, w3 i0 [3 N# @( A5 M8 ]0 `  \) n$ ]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.
Input
) X4 p* v( d' i( y
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

/ k4 @2 Q/ J4 N# `& K9 h0 e& g9 }1 p  PFor 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.
3 ?! M  q+ B( D! f- e# G
4 c  W) l+ ]6 V% ?) D+ j+ M1 \# awhere ** 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.
) i6 n8 J& }; s, [0 Q
输入样例

4 6
A<B
" b# q! B" c/ Y% @( G6 @3 {A<C
' _* {- i  F5 L  MB<C
C<D
B<D
A<B
3 2
( i8 \" r7 w. ]1 Z6 E- AA<B
: ~! Z, U5 F( F8 L0 e2 }B<A
! T- z4 ?; b& g4 ?26 1
A<Z
0 M' }$ p7 x6 _8 \9 p0 0
1 j2 j  f: v8 l0 W% L9 @  f- U6 q

输出样例

/ B: B% `3 d% k9 w6 fSorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.

Source

East Central North America 2001

程序解题1：

//By Jackie Cheung
#include <iostream>
( ~0 A6 f" f( @; J- w  F#include <string>
#include <cassert>
typedef  struct tagNODE
# y! I* `8 {7 z5 d' c, b: w0 Y{
    char val;
0 b5 D7 l! t* _% [    struct tagNODE* link;
}NODE;
using namespace std;
void Marshall(bool** arrary,int n)
{
" O4 e# S( C9 G4 ~2 S: w0 f    for(int i=0;i<n;i++)
    {
: L. S$ p2 Y( `5 H6 ~! F$ ~        for (int j=0;j<n;j++)
0 p/ P) Z: B. [( [9 ?3 C/ C        {
2 E0 i0 ~/ r+ M- Z* _            if(true==arrary[j])
                for (int k=0;k<n;k++)
                {
% e" v' _( v% k# S0 M1 U: V                    arrary[j][k]=arrary[j][k] || arrary[k];
1 \( p1 p! m3 B                }
        }
    }
6 v$ i# v8 U+ e/ z$ |& O5 J0 U};
& _5 Z& j$ g. Z! {bool  SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)
{
    Seq[n-nLeft]=static_cast<char>('a'+nIndex);
    bool bFlag=false;
    if(1==nLeft)
    {
        Seq[n]='\0';
: ]/ B" ^- P) T        return true;
5 y/ Z4 |$ k/ m- k    }
7 i8 ^% V9 Z3 c0 R3 H. v1 P    for (int i=0;i<n;i++)
# N8 ^# z) i* ^! d% ~    {
        if(true==array[nIndex])
+ r& `5 R8 r* g2 t( K        {
) L3 R, z- ?& k2 B/ z% S! R( n            
+ U4 n/ z/ K% g$ w+ s/ }9 {+ ~            bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);
        }
        if(true==bFlag)
            return true;
    }
8 m8 \7 o- P3 g" R- Z0 G    return false;
6 i5 X+ H0 Q9 o8 X! T};
; a5 ~1 N7 a& ]1 z, _int main()
2 L! _* d$ a0 ?, o/ j( k{
6 e, ?: h$ q& R! m8 C    int nSeqLen;
    int nRelNum;
    cout<<"Input the length of the sequence:"<<endl;
2 U4 O3 D6 V& F* s2 e    cin>>nSeqLen;
- |4 ^3 S; x  G3 l    cout<<"Input the number of relations between the elements:"<<endl;
    cin>>nRelNum;
    //1:if nRelNum<nSeqLen-1,then the relation can not be determined!
  Q7 k! U9 g. l% I: {$ Y    if(nRelNum<nSeqLen-1)
    {
        cout<<"The relation can not be determined!"<<endl;
        return 0;
    }
: n7 K- l  ?, o0 ]% W" w    string* strRelations=new string[nRelNum];
4 t" o2 ?4 M/ j+ v9 }    char* Seq=new char[nSeqLen+1];
    bool** array=new bool*[nSeqLen];

    for(int i=0;i<nRelNum;i++)
  a" j+ ]# V" ?8 O& C$ E$ [- Z: Y    {
% I- P  o) R8 F8 h& @6 ~        cout<<"Input the "<<i+1<<"th relation:"<<endl;
        cin>>strRelations;
. u1 q/ n. [) B! U. g6 ^& Q* m5 f8 j2 c    }
! k7 o" B# T, m; N/ W   
- h- a) F* t2 J3 ]" ]; v; E; P    for (int i=0;i<nSeqLen;i++)
    {
- ^; E8 p7 G9 y        array=new bool[nSeqLen];
        for (int j=0;j<nSeqLen;j++)
            array[j]=false;
7 m/ g& X2 n2 P9 D, ~# c    }
    //The main loop
    for (int i=0;i<nRelNum;i++)
    {
1 f# {* q7 A  V4 S& t        char a=strRelations[0];
( _' [$ f$ _5 s3 O: I. v0 N) H        char b=strRelations[2];
+ l# m8 {6 \; f0 H7 a) g7 I$ G        assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
        array[a-'a'][b-'a']=true;

) v& c+ V- |( W' K        Marshall(array,nSeqLen);
' `* L3 u& ^/ y+ S  J
1 t3 P# Q# |- J% k, M5 U! v( i        //Check for Inconsistency after  every relation
        for (int m=0;m<nSeqLen;m++)
; J' b2 N" }7 o6 q6 s) y& J- m        {
            if(true==array[m][m])
' W7 E5 B: g  v/ o0 E( Z& \            {
                cout<<"Inconsistency found after"<<i+1<<"th  relation!"<<endl;
                    delete []strRelations;
& }& c2 k1 {, g0 U+ {% t. p8 g                    for(int k=0;k<nSeqLen;k++)
/ |+ m0 i9 b& b# d& B' e                        delete []array[k];
* U, ^0 ^! I7 U3 z) F* P) H/ v                    delete []array;
: X2 O% g1 m6 k) T                    delete []Seq;
% A3 K) P9 L! x4 \) Y1 f/ t- T- ?                    return 0;
" Y+ i7 |3 m, w! w! x- U
            }
        }
% [8 c2 ^0 X9 X; }4 ^1 P1 G
        //Check for the determined sequence after  every relation   
        for (int j=0;j<nSeqLen;j++)
( p) I9 A6 V; v" c        {
            if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))
            {
( w/ r. d- Z, H                cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;
# b' z& _! a4 ?6 Z                delete []strRelations;
0 H3 j0 c- V( t                for(int m=0;m<nSeqLen;m++)
                    delete []array[m];
' p( d" T7 E* Y1 I: y                delete []array;
                delete []Seq;
: v# W/ ^: d# O/ x( ~+ S                return 0;
            }
. d% q( Y2 L+ x        }
7 N- n) J, ^7 \$ a) p

& C* z% @- _2 O% i* `) h, G& V    }
5 ]0 ~# N- b( C9 m    //If the program has come to here ,then the relationship hasn't been determined!!!
    cout<<"The relation can not be determined!"<<endl;
    delete []strRelations;
    for(int m=0;m<nSeqLen;m++)
        delete []array[m];
    delete []array;
1 H( i' e" t8 H! t  w6 I! V    delete []Seq;
# P; S. U. E2 `/ M1 g   
+ w7 o* E4 t: r: @    return 0;
8 m5 r# [8 U. e}
" U6 t5 |$ Z4 S% R  j6 e( `2 c) h
3 T3 N4 ~; f, r8 Q. K8 z程序解题二：#include"stdio.h"
void main()
  g+ O& Y' D2 Q! |/ E" o/ Z{
8 b3 C; `2 J5 q# m4 A$ O6 D    int n_m[100][2];
8 @2 Y" ?9 j7 c3 P5 Z    char re[1000][3],
    temp[26];
    int i=0,j=0;
* q; [2 }; I9 w+ Z7 p    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)
    {
  _: b1 Y( @6 ?9 ]  _' q    i++;
- y, I' Q1 z, u2 |# E    scanf("%d%d",&n_m[0],&n_m[1]);
    for( int f=0;f<n_m[1];f++,j++)
. n6 v3 I7 Z  @9 F    scanf("%s",&re[j]);
: C' q# H- z- W, x1 Z7 L    }
5 w: ?; U/ x1 i: l0 w3 `    i=0;
    j=0;
( E# e6 r# {) T7 g   for( ;n_m[0]!=0&&n_m[1]!=0;i++)
    {
6 S; f% k( ^6 E8 Z/ c       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])
            {
- r; X/ _  J, [2 D5 ^7 a  V            l=0;
            printf("Inconsistency found after %d relations.\n",n_m[1]);
$ _) A- {0 ^, l; e9 F            break;
/ I! I/ }' f8 \! c6 g            }
         }
- K/ O1 c) A' a' ?" l8 F      if(l==0)
& R0 E; W+ X2 ~' G" O          continue;//Inconsistency found after x relations.
    else{
           if(n_m[1]<n_m[0]-1)
        {
            printf("Sorted sequence cannot be determined.\n");
            l=0;
        }
5 v! o, c: B. W( G7 Z        else
        {
          if(n_m[1]==n_m[0]-1)
          {   
, ]- y& J+ _3 f9 a8 d( h% r* f              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])
3 R4 K$ ?+ \1 G7 j& n                      {
                      printf("Sorted sequence cannot be determined.\n");
, I7 j- b* E/ f                      break;
                      l=0;
                      }
6 {8 M- f& L8 `7 D& D# t1 O+ q          }
/ @8 n: y; P# @9 S2 S        }
        if(l==0)
        continue;//Sorted sequence cannot be determined.
( `/ d; {# @& U6 O* U6 d
% ^3 I( Y; b, S) f/ s5 F  n) b7 z        else
         {
% l, S& e  `: f. H           
7 r% y# m# x5 s1 L            for(int k=0;k<n_m[0];k++)
; M6 y) s$ Q3 k' _- B             temp[k]=k+65;
, t+ L! V3 C4 c/ E( ]            for(k=0;k<n_m[1];k++,j++)
! j6 i; W3 u; u4 s: M0 C            {
                int t1=0,t2=0;
              for(int s=0;s<n_m[0];s++)
5 v1 v) e5 r" ]" [+ C: }  A  Y/ I              {
& u+ M' C6 }6 }" b* }               if(temp==re[0])
                   t1=s;
                      if(temp==re[2])
                   t2=s;
2 m# f1 U) `3 z! F' F4 X% ~              }
2 z' c# M  v. U! B; A  A              if((t1>t2)&&re[1]=='<')
+ G0 ^) `) B/ w# \, M              {
                char t3=temp[t1];
4 X$ ], [( E- V9 ~                temp[t1]=temp[t2];
( |" v/ U  p" @, Q6 \" ]) ]                temp[t2]=t3;
              }
            }
        int count=0;
        for(int s=0;s<n_m[0]-1;s++)
. _4 i" v7 Y1 H9 J7 ~0 P/ n        for(int d=j-n_m[1];d<j;d++)
            if(re[d][0]==temp&&re[d][2]==temp[s+1])
            {
                count++;
                break;
& d5 V" I( }+ f; R            }
0 ~0 E2 R" D+ S9 F# J& Y            if(count==n_m[0]-1)
            {
2 o  Z6 {; y4 ^7 g. \                printf("Sorted sequence determined after %d relations:",n_m[1]);
5 P3 \6 V$ P& m2 l- o                for(int f=0;f<n_m[0];f++)
; S4 y9 ~& W2 a7 C                  printf("%c",temp[f]);
4 y' q2 t$ |  f* G                 printf("\n");
# P' p7 M. W! g            }
            else
               printf("Sorted sequence cannot be determined.\n");
        }
    }
, y1 Z8 A/ X9 ^, F    }
}
' k* I, q8 {# R) _; Q; p

5 r( l8 u; y7 ]/ T, I- d
3 P+ z6 o5 J6 g, V. O4 |8 Q
- B: b9 w1 u- w/ `7 J  V! u
3 z3 T1 e- ~$ u4 I: n) B. q
7 z) m, L/ C+ }& X6 E' w' ~

来源：编程爱好者acm题库