编程竞赛题目（一）

厚积薄发

# @, ^5 Q$ i  N$ H7 bSorting It All OutDescription
( {# ]3 L& e, u9 `& Q) p! Z9 i
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.
$ p8 _! W, w) t( M  l; q- F5 HInput
4 `7 Q( \: c3 ~; y; L5 F
& r+ A  j2 o1 Y5 c$ Q- eInput 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
+ ~9 r/ A  W1 Z' y- ?" J" I
2 O/ Z0 L0 }, V" n! E5 @For each problem instance, output consists of one line. This line should be one of the following three:
. f  y7 C/ o' {
Sorted sequence determined after ** relations: yyy...y.
Sorted sequence cannot be determined.
Inconsistency found after ** relations.

5 m' f! M) Z* _( U' _% X1 x0 Qwhere ** 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.

输入样例

4 6
1 Z5 l: \* h5 ]7 f. l' v' bA<B
; M) Q5 m* I; }7 R, pA<C
B<C
C<D
  U* t/ t. [7 TB<D
A<B
3 2
2 J. f/ s& L" ~2 B" I1 ?A<B
B<A
2 X* a# F6 J$ E* c26 1
A<Z
0 0

输出样例

' t6 z* P8 A9 R& Z) J. F# i$ W1 xSorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
2 w9 D! ^1 _: C) P4 QSorted sequence cannot be determined.

Source
; {" C' d; D8 x2 z# f% \( r
# f3 C/ M) M6 D# v- t1 REast Central North America 2001

程序解题1：

* q( n4 q6 v1 s# a% F$ u//By Jackie Cheung
#include <iostream>
+ s: U6 D. T4 E2 B+ U8 T#include <string>
" x' q6 q: G8 u+ J' t' c, V#include <cassert>
typedef  struct tagNODE
{
8 Z- a( Y  Y3 F& ?    char val;
    struct tagNODE* link;
/ O9 c1 @+ G* N- S}NODE;
using namespace std;
; n& q8 v. A  f2 u2 T( Zvoid Marshall(bool** arrary,int n)
{
4 D4 F9 j  |' p. T* i( D    for(int i=0;i<n;i++)
* l$ l& T. y5 N" l    {
        for (int j=0;j<n;j++)
8 l- Z  E) K$ ?        {
; t$ h8 K4 p! B# ~9 S4 J            if(true==arrary[j])
                for (int k=0;k<n;k++)
8 Q: Z; ^4 i' x8 c. B/ X  n                {
7 V8 F/ o% o9 u( P  L7 S4 {4 }; q9 D0 p                    arrary[j][k]=arrary[j][k] || arrary[k];
                }
2 c% `! g$ D+ g( {' L  D        }
5 U! w) B4 ^: x/ z( v+ W    }
};
, f! A9 [4 i1 r, Y  I7 rbool  SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)
: y: j  C6 f, z$ P( E9 K. [6 N{
7 q. N- S. C9 R* |7 p    Seq[n-nLeft]=static_cast<char>('a'+nIndex);
    bool bFlag=false;
    if(1==nLeft)
    {
        Seq[n]='\0';
        return true;
    }
    for (int i=0;i<n;i++)
    {
        if(true==array[nIndex])
$ Y, u8 W$ U& D8 j        {
            
9 g% I2 I2 ?2 t            bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);
        }
, u0 q  \% ?% j# d( f+ a        if(true==bFlag)
            return true;
    }
! [. ]' I0 D7 y0 r2 c2 k    return false;
3 t; ~7 a! y( X};
$ O; D$ a+ J1 m. N* nint main()
{
- W8 H7 v" u, a4 p  M    int nSeqLen;
, w7 \) c& a+ f    int nRelNum;
0 k: C  s: V, ]. y; J    cout<<"Input the length of the sequence:"<<endl;
* z7 m; ?( |. D4 I* \    cin>>nSeqLen;
/ b- n' y( M  A7 L    cout<<"Input the number of relations between the elements:"<<endl;
    cin>>nRelNum;
0 L# a( C! C: V" ^; @1 F    //1:if nRelNum<nSeqLen-1,then the relation can not be determined!
, h$ H" H1 K" `" E+ r, B- p1 n    if(nRelNum<nSeqLen-1)
' L; b9 A) I) E/ n; V- u8 O    {
* A; E( A! i$ p" D9 c        cout<<"The relation can not be determined!"<<endl;
        return 0;
6 [4 o1 w# S3 L0 Z# ~    }
    string* strRelations=new string[nRelNum];
5 A+ L4 h/ J8 s0 O    char* Seq=new char[nSeqLen+1];
2 J: c# L9 t+ q) n/ f8 E    bool** array=new bool*[nSeqLen];
# ~0 C% S9 b8 h# f# s# x
. Z2 U  |) ?# k1 k! C% ]    for(int i=0;i<nRelNum;i++)
    {
        cout<<"Input the "<<i+1<<"th relation:"<<endl;
        cin>>strRelations;
' q% M, Q, y2 b. P+ w    }
4 A& Y' h" Z# L6 E7 A7 S   
    for (int i=0;i<nSeqLen;i++)
7 w6 L0 ]! q& U! w    {
        array=new bool[nSeqLen];
  w0 n7 T2 q& @& \( _9 G        for (int j=0;j<nSeqLen;j++)
            array[j]=false;
# i0 j, V+ [4 @  G' a( n! p    }
  j2 ^- j" y; G$ Z/ S: O! I2 n, A; |    //The main loop
5 w2 g( s( V! n( x6 O6 R    for (int i=0;i<nRelNum;i++)
: l! ^8 ~; O$ R7 c    {
9 w. O, m2 C% n3 Y* q- f8 n        char a=strRelations[0];
        char b=strRelations[2];
        assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
        array[a-'a'][b-'a']=true;
  [* S: l+ c  }9 H% P8 [! [- V" L
        Marshall(array,nSeqLen);

* o# Q& W" \, a4 O/ W6 V* j2 f6 [- \        //Check for Inconsistency after  every relation
' q( k8 F# r8 T2 n1 k        for (int m=0;m<nSeqLen;m++)
1 D& c" Y9 g7 d        {
            if(true==array[m][m])
            {
                cout<<"Inconsistency found after"<<i+1<<"th  relation!"<<endl;
+ h6 q7 F5 w3 r8 S2 O9 Q                    delete []strRelations;
8 z2 p9 M) t( q0 C0 p                    for(int k=0;k<nSeqLen;k++)
                        delete []array[k];
: P9 N4 J( \4 D" I6 ^( g' i                    delete []array;
                    delete []Seq;
                    return 0;

4 w2 R1 z7 ~6 s1 ?8 l- ]            }
1 E2 U  f- w' L8 S/ Q5 t; q        }
8 x1 A, e  u( \8 {- E: q
$ o( `% ^; m1 G& x, K8 @, b        //Check for the determined sequence after  every relation   
! c/ D, H+ [8 K/ U1 e7 X        for (int j=0;j<nSeqLen;j++)
        {
            if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))
            {
                cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;
2 p2 T* n" }8 z# {% f                delete []strRelations;
- F: e# e' Z$ [4 a7 m% Q  ~3 M                for(int m=0;m<nSeqLen;m++)
                    delete []array[m];
" W8 D; V6 j) H7 n+ b6 X3 I1 ]& A                delete []array;
                delete []Seq;
                return 0;
/ e" v* m  Q+ K# M: V" ]            }
        }


  O: F: }! R" V; m$ i( I# ~    }
    //If the program has come to here ,then the relationship hasn't been determined!!!
    cout<<"The relation can not be determined!"<<endl;
) b" A* u% ^0 J! i& p1 s    delete []strRelations;
* `# `- Z0 Q! f% I) d, ^& w0 M    for(int m=0;m<nSeqLen;m++)
! U: V5 f5 s. g+ T; \* i: P        delete []array[m];
( r  G3 Z! B/ ^7 Q) ?0 y' p    delete []array;
    delete []Seq;
   
    return 0;
}
! k  B7 W0 y0 q, z, x9 ?# T
程序解题二：#include"stdio.h"
7 K. N$ z! o6 Q0 I9 T8 {/ c9 Nvoid main()
{
    int n_m[100][2];
! q  \3 D$ C7 s4 T- C    char re[1000][3],
    temp[26];
    int i=0,j=0;
    scanf("%d%d",&n_m[0],&n_m[1]);
3 T0 S9 j9 B/ Y' s0 c0 T    for( ;j<n_m[1];j++)
4 H" y0 S2 F4 o& [- |+ M% c    scanf("%s",&re[j]);
    while(n_m[0]!=0&&n_m[1]!=0)
    {
    i++;
    scanf("%d%d",&n_m[0],&n_m[1]);
    for( int f=0;f<n_m[1];f++,j++)
    scanf("%s",&re[j]);
    }
  p# {2 w- _7 K) Q    i=0;
2 M$ Z7 F: l2 @% ^0 Y' x+ [    j=0;
3 q/ G! E! C& i$ L   for( ;n_m[0]!=0&&n_m[1]!=0;i++)
    {
       int a=0,b=0,l=1;
( Q. j, Z: a4 k" X6 ?4 X       for(a=j;a<j+n_m[1]-1;a++)
         for(b=a+1;b<j+n_m[1];b++)
. p7 T6 \( c- u  H4 L         {
              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])
7 @1 A- d9 O5 l3 z7 Y            {
            l=0;
! V$ q% Q) _0 ?7 ]: _( ]$ K            printf("Inconsistency found after %d relations.\n",n_m[1]);
            break;
- U1 U5 M4 O( _( f, Q# q) a            }
         }
# |4 X& \8 Q. C# K# r" N" H      if(l==0)
          continue;//Inconsistency found after x relations.
    else{
4 D/ W8 `9 ?" e/ {. H3 |4 V% l           if(n_m[1]<n_m[0]-1)
% x9 A" |* X* v& X: I" O( I        {
            printf("Sorted sequence cannot be determined.\n");
' n4 K$ |- ^# p& L- S2 b" ~$ q  T            l=0;
        }
        else
3 Y$ E" S: Y* q! n1 i        {
          if(n_m[1]==n_m[0]-1)
( i- N0 r3 E5 M) |$ W  _          {   
              int k=0,p=0;
' M+ @1 j% `1 k  p              for( ;k<n_m[1]-1;k++)
' Q0 N7 m5 O% h2 ?! \) f! r8 {) o                  for(p=k+1;p<n_m[1];p++)
' q" i$ b, N6 `4 v6 u- i                      if(re[0]==re[0]||re[2]==re[2])
                      {
                      printf("Sorted sequence cannot be determined.\n");
" I% t% g7 c. t  v( s                      break;
  {% E5 S! B5 g$ f2 }                      l=0;
+ x4 ^" }+ F+ u% T& Y* m" \. i- m; L                      }
2 d; ~- w2 a9 r. ]8 m' p          }
0 @4 X5 q4 o/ {: d% e        }
        if(l==0)
4 Z+ R  E. N* |+ ?6 f1 R4 x0 D        continue;//Sorted sequence cannot be determined.
& \! e; R0 }! _& \! D8 k, f9 }
        else
6 z+ U3 E! D  k, `         {
           
            for(int k=0;k<n_m[0];k++)
             temp[k]=k+65;
            for(k=0;k<n_m[1];k++,j++)
6 P1 E! I. L$ Z4 K+ M% M! N            {
" A9 h' r$ E" f                int t1=0,t2=0;
              for(int s=0;s<n_m[0];s++)
              {
               if(temp==re[0])
8 }7 i9 a4 |7 L9 W                   t1=s;
+ r7 \4 X" u* v4 o                      if(temp==re[2])
+ n, H2 o3 }" N7 E5 l& c- D                   t2=s;
4 b3 @- ~/ u$ d: x7 Z              }
              if((t1>t2)&&re[1]=='<')
              {
/ n/ V5 o7 k* n+ i4 z                char t3=temp[t1];
1 k- W# P( N/ B8 ^# C& Z2 z% [                temp[t1]=temp[t2];
: a8 u  o; ?( U/ M  I: Y                temp[t2]=t3;
1 s) n  y+ l" ~; K- O  X- @              }
  l3 w: Y7 _8 U            }
        int count=0;
/ w- O6 z# Z# ^: F5 H        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])
+ z- V* g% W0 \9 o            {
                count++;
                break;
            }
            if(count==n_m[0]-1)
            {
                printf("Sorted sequence determined after %d relations:",n_m[1]);
  T- X0 Q3 ?% c0 y2 |  v1 j4 ?                for(int f=0;f<n_m[0];f++)
                  printf("%c",temp[f]);
7 R1 R9 G1 [! j+ ~6 R: x                 printf("\n");
3 z0 {0 s6 \6 o0 P5 M            }
1 v) |! f' y4 [' l            else
7 M% i6 F1 b  V9 `# l  {( i               printf("Sorted sequence cannot be determined.\n");
        }
    }
    }
- m. J& E8 d2 X; K+ y) K- T}
, [  X; P( m! R" r/ v





8 v% G2 y* w6 C

来源：编程爱好者acm题库