编程竞赛题目（一）

厚积薄发

Sorting It All OutDescription
4 g. r, J" E5 o3 A
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.
" \$ R+ _& {$ qInput
, A) s# x( M8 p' Z+ Z  L
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.
  o! P, Q; @/ I- d1 TOutput

For each problem instance, output consists of one line. This line should be one of the following three:

8 c$ x. H" d8 u; e" Y8 |! \Sorted sequence determined after ** relations: yyy...y.
8 z$ n, C; n; i5 s' I* u; }0 uSorted sequence cannot be determined.
Inconsistency found after ** relations.

7 Q3 i- D% P/ ~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.

8 P1 B4 t  W: C输入样例

4 6
A<B
A<C
5 z  ?+ s/ H. u+ W  \6 `9 Z6 Z) l  A8 IB<C
" R2 f4 @/ h  O- z( t5 KC<D
" l0 }5 s+ u( eB<D
( g7 \" |# c6 R/ o" Y. s4 o$ F8 d9 }A<B
3 2
+ b, s& {! J8 c4 n0 cA<B
+ N% W) ]9 r( G3 x6 A; }  NB<A
26 1
A<Z
0 0

# B% Y% u$ n4 P输出样例

# N4 Y' ^' e7 p/ ESorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.

9 B2 }+ R$ {! Y0 q* ~; Z

Source

East Central North America 2001

0 F- z7 W" p6 |9 ?" J* p5 V$ ^

程序解题1：

//By Jackie Cheung
2 Z, ~3 m0 g# B1 {  L#include <iostream>
8 V! f: h) n$ N  ^4 S, F  E3 q( q6 g#include <string>
#include <cassert>
typedef  struct tagNODE
{
    char val;
& u/ d+ a$ i! S+ `* Y    struct tagNODE* link;
* i' L. O1 ?. }0 V}NODE;
using namespace std;
void Marshall(bool** arrary,int n)
{
/ T5 q) s* e6 S& l2 O    for(int i=0;i<n;i++)
    {
4 s4 x5 L+ @+ B  C7 K        for (int j=0;j<n;j++)
        {
            if(true==arrary[j])
4 N/ k/ q" U6 [6 M: ]1 {' ]2 u/ b                for (int k=0;k<n;k++)
+ t- ?+ G) u" D& S* K) y# R0 ]! v                {
( _/ k" Q4 B  ]* {2 m4 `' b( l2 u                    arrary[j][k]=arrary[j][k] || arrary[k];
+ N- l: C5 `$ H/ C                }
        }
0 p# g6 g9 h6 w9 ^    }
};
/ U3 v! T! ~; v3 U: obool  SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)
{
/ ]' J  _  G+ e/ f    Seq[n-nLeft]=static_cast<char>('a'+nIndex);
    bool bFlag=false;
    if(1==nLeft)
    {
- s) @- t. L% T  T+ N: @        Seq[n]='\0';
* U7 p( s! u# A( R* C+ u/ R: D        return true;
0 |0 b: z4 ~' a# M0 X" q    }
    for (int i=0;i<n;i++)
    {
2 q0 z5 T9 d0 z9 B  P! b. s0 ^        if(true==array[nIndex])
        {
: D  F$ B: H* G0 k4 Y! z% [            
% ^! o- P0 v6 k. V/ a  V+ }            bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);
        }
        if(true==bFlag)
            return true;
    }
    return false;
( T) r7 m, k5 _! J};
int main()
+ e& |  h/ W( r; y* N1 n9 k{
* Y" I. t. Q3 e! }9 p    int nSeqLen;
    int nRelNum;
    cout<<"Input the length of the sequence:"<<endl;
$ |, g, t( Q/ n& v( {7 |    cin>>nSeqLen;
* }  b# T  J, V9 Q; S2 Y    cout<<"Input the number of relations between the elements:"<<endl;
    cin>>nRelNum;
, A3 h. t- E! X- T4 i/ D    //1:if nRelNum<nSeqLen-1,then the relation can not be determined!
3 i$ q' Q  _$ H    if(nRelNum<nSeqLen-1)
    {
' q7 T' d8 j& Q2 ]8 T# b4 Y        cout<<"The relation can not be determined!"<<endl;
        return 0;
    }
    string* strRelations=new string[nRelNum];
    char* Seq=new char[nSeqLen+1];
    bool** array=new bool*[nSeqLen];

% f9 x9 y" k% C7 d) j9 ^    for(int i=0;i<nRelNum;i++)
    {
4 K+ M1 V. g" i6 a0 r        cout<<"Input the "<<i+1<<"th relation:"<<endl;
        cin>>strRelations;
    }
   
    for (int i=0;i<nSeqLen;i++)
    {
        array=new bool[nSeqLen];
        for (int j=0;j<nSeqLen;j++)
6 o, ?& J" h' S* @6 _  z- T            array[j]=false;
    }
    //The main loop
, r+ j3 E, r$ P" v/ Q0 V( W. e% i    for (int i=0;i<nRelNum;i++)
, z+ u. X8 i. u    {
( v/ \. r! n+ b2 b# }  [        char a=strRelations[0];
9 `3 J  u! _. J; {        char b=strRelations[2];
        assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
        array[a-'a'][b-'a']=true;

        Marshall(array,nSeqLen);
. }% Y3 n+ a' a+ X- @  y; K, Q8 M
        //Check for Inconsistency after  every relation
        for (int m=0;m<nSeqLen;m++)
5 j6 z/ U9 u$ ^! C        {
            if(true==array[m][m])
            {
' {) ~  [' n8 i% r- o                cout<<"Inconsistency found after"<<i+1<<"th  relation!"<<endl;
0 ^( n: P) f5 O% M' M7 O: f                    delete []strRelations;
. z: D: K9 M. C4 l                    for(int k=0;k<nSeqLen;k++)
                        delete []array[k];
# a/ A5 R! T. u* s                    delete []array;
  v$ g) g) U4 m! o# i                    delete []Seq;
                    return 0;
: f2 {) j0 D; h5 `- }( C+ i0 v
            }
: J1 U4 K0 E- p; \        }
% _  m8 z# X+ q8 u* `& h5 M
5 G/ @  A; d, g        //Check for the determined sequence after  every relation   
        for (int j=0;j<nSeqLen;j++)
        {
            if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))
2 {" Y! O2 J& l- i8 u( v. z. n            {
2 v, a& j! {* T                cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;
2 ]3 i1 S/ N( P                delete []strRelations;
* n7 h0 r! t+ @" \7 O                for(int m=0;m<nSeqLen;m++)
                    delete []array[m];
                delete []array;
* d0 A9 ^+ _2 \9 ~  o" f& L                delete []Seq;
                return 0;
            }
        }
  F5 N8 H2 o% w7 k- ?* {2 n8 b
- _- |8 t% S1 x  i4 K1 v
7 t" H* l: _) O! d, o% Z+ @    }
5 `6 t8 K; M, d# T# u0 A( @    //If the program has come to here ,then the relationship hasn't been determined!!!
    cout<<"The relation can not be determined!"<<endl;
& M. a* V8 f3 F5 c, B    delete []strRelations;
6 |! D8 _* P, j    for(int m=0;m<nSeqLen;m++)
( O1 `, `$ L. @3 ]        delete []array[m];
    delete []array;
$ R7 W! u2 l! w7 Z2 M! y5 i' n    delete []Seq;
   
    return 0;
}

( [& j" ]0 `  N& i+ y0 C程序解题二：#include"stdio.h"
, F9 ]  N9 f. rvoid main()
{
- K( U% f3 V- X6 J    int n_m[100][2];
6 X: ?' d- r, G' ^9 B7 J5 h    char re[1000][3],
' i$ l* @) H0 r: A$ u    temp[26];
; x8 f3 O, j! L: {    int i=0,j=0;
/ I5 o: X' ^* \4 r    scanf("%d%d",&n_m[0],&n_m[1]);
% d0 @3 E8 R8 `7 V8 T+ g$ V- a    for( ;j<n_m[1];j++)
3 L. n" h5 t" I/ n( m& p    scanf("%s",&re[j]);
2 O9 A8 j) [  ?" e0 T    while(n_m[0]!=0&&n_m[1]!=0)
  N, D, j/ ~/ a. m) `    {
    i++;
    scanf("%d%d",&n_m[0],&n_m[1]);
7 D' V" C; I. q3 R8 d; H6 R" `2 @' X    for( int f=0;f<n_m[1];f++,j++)
    scanf("%s",&re[j]);
    }
    i=0;
    j=0;
   for( ;n_m[0]!=0&&n_m[1]!=0;i++)
    {
- n# x4 ~" @6 \3 Y. H. k       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])
: Y5 o5 ]2 a- }* |) Q! ]            {
- C1 \: G  n6 W/ B* j            l=0;
            printf("Inconsistency found after %d relations.\n",n_m[1]);
5 V: }. T: u* I3 _6 K8 {            break;
            }
         }
      if(l==0)
          continue;//Inconsistency found after x relations.
+ p# u- J% t" [) A" z' H    else{
           if(n_m[1]<n_m[0]-1)
4 ^1 X# |9 G4 R. e6 R  D1 w        {
( N5 C/ H; P/ d  D* {( |3 V            printf("Sorted sequence cannot be determined.\n");
! s0 f  j6 z$ o1 M# l  ~* G            l=0;
        }
& a. `$ a, R) J5 b  e: B& t3 Y        else
0 K& N4 s1 ?1 o* Q# X6 L: I( W        {
          if(n_m[1]==n_m[0]-1)
# _4 z0 L+ U6 ~. q* e3 ~: R5 S5 O          {   
! b. L; K* i, H* T& b2 q1 \              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])
                      {
& M, p# F2 a6 N0 k- d, E& ~' {: w                      printf("Sorted sequence cannot be determined.\n");
                      break;
" n8 Z- a* r/ s5 f4 R6 d- j                      l=0;
                      }
) F7 Y, b4 D" N% M          }
        }
5 h5 d( b3 ]; b        if(l==0)
        continue;//Sorted sequence cannot be determined.

8 R- H0 ?  J7 A/ f: Z        else
         {
           
            for(int k=0;k<n_m[0];k++)
1 G7 y, X# {+ a+ h9 n/ t* [. \             temp[k]=k+65;
- W% [1 P6 P% l+ F0 Y0 F$ \% B            for(k=0;k<n_m[1];k++,j++)
            {
                int t1=0,t2=0;
; y0 D% d0 ~! o1 r. G7 \4 S              for(int s=0;s<n_m[0];s++)
              {
" f) j, i" n. y. l8 I) ?9 j               if(temp==re[0])
$ U, t8 Y$ I+ p5 r* O3 s                   t1=s;
/ {% Q# x0 q+ R: z$ J- c                      if(temp==re[2])
+ z7 }' {: C  K) D0 Z                   t2=s;
2 @% o3 y' w( B4 l& f              }
              if((t1>t2)&&re[1]=='<')
. y& q) ]- v7 ]2 H              {
                char t3=temp[t1];
                temp[t1]=temp[t2];
                temp[t2]=t3;
              }
, `% T8 X5 s3 C7 R5 v9 S+ b            }
2 _0 f% e# Q1 Q  H8 U- M        int count=0;
# C' e/ r& E' \) }        for(int s=0;s<n_m[0]-1;s++)
        for(int d=j-n_m[1];d<j;d++)
            if(re[d][0]==temp&&re[d][2]==temp[s+1])
            {
                count++;
- y8 ^9 L! \) E9 h& Q& j6 f                break;
            }
' h+ Z2 D6 {& Y+ C+ C            if(count==n_m[0]-1)
            {
                printf("Sorted sequence determined after %d relations:",n_m[1]);
                for(int f=0;f<n_m[0];f++)
, u2 G# R/ e% F& T/ x                  printf("%c",temp[f]);
                 printf("\n");
& E& c6 y) e/ s: i            }
7 y# c9 `! L) W+ n8 }1 s6 Z$ L            else
. o5 y1 ^; d, t' ]7 j               printf("Sorted sequence cannot be determined.\n");
0 V7 P1 N1 g" ~3 ], |        }
    }
" i# V8 \" a* S0 a2 h' @4 y    }
- B0 }7 [2 W4 n  ^9 Q}






+ T6 l, g) \9 q: l. O2 X
* \/ q$ Y) u" n% m: S# x7 q  w
6 |; I$ j9 L% z( x+ A# |

来源：编程爱好者acm题库