编程竞赛题目（一）

厚积薄发

; R3 X  S- B9 j7 M& T6 JSorting It All OutDescription

& w5 A5 e, C% i  S' U3 R1 O0 OAn 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.
6 K& m; g) p$ q# l7 }* X9 `8 p4 RInput

  x2 e; l/ 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.
. a7 e/ M8 l/ j& k3 h8 [Output

For each problem instance, output consists of one line. This line should be one of the following three:
; N! [- [; g5 y0 y1 u/ W0 V
Sorted sequence determined after ** relations: yyy...y.
Sorted sequence cannot be determined.
" t% Y( v' B  [7 r0 nInconsistency found after ** relations.
9 M% i1 R. h7 w
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.

输入样例

) M3 T% s" t' a. u3 y4 6
1 ^! y+ V6 B. o+ PA<B
. I9 a: t' g, ~9 d' N! d0 Z$ pA<C
5 t5 J! w. }% f9 g, ~6 b; HB<C
C<D
B<D
9 e' w5 n4 R0 o# p5 K4 m( _7 g' J! CA<B
3 2
; }9 h# \4 N6 T8 c3 TA<B
B<A
4 I, u2 t" k% j- U) @9 Q26 1
5 t$ M' ~. k( G, R, @A<Z
0 0
2 R% j' A, @& j5 P; |, w

输出样例

0 i( M+ r" f' _. ^: F1 \) YSorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
$ A6 ^7 u7 ?. q4 z* \( iSorted sequence cannot be determined.

Source

) T" G: J/ R" }7 e& AEast Central North America 2001

程序解题1：

: d6 J' O6 y- G5 W2 }0 ]8 J//By Jackie Cheung
#include <iostream>
4 r- b5 d. U6 T# ]% Z4 ~2 J#include <string>
" l" X/ j' v+ R#include <cassert>
  F9 x" ~# B$ R* b/ ]8 Ltypedef  struct tagNODE
{
  o6 ]7 }& i* y3 h4 z9 O% z; g    char val;
. I6 z+ w; y2 F! Y/ q- Y5 z5 r    struct tagNODE* link;
) B$ Z! E) O5 @3 W2 s  n8 W}NODE;
8 l. y; w6 A0 D8 _using namespace std;
void Marshall(bool** arrary,int n)
{
% P2 Y: e# c4 I& c; W0 o( t    for(int i=0;i<n;i++)
# P  b. I7 b1 }1 E2 U! s& K    {
        for (int j=0;j<n;j++)
        {
            if(true==arrary[j])
+ U8 M: W1 |+ K# K% P                for (int k=0;k<n;k++)
                {
& Z) f& j2 k9 ?: W. z  N                    arrary[j][k]=arrary[j][k] || arrary[k];
                }
/ x* j% w; S! d) ^7 n# j, B        }
    }
};
bool  SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)
{
    Seq[n-nLeft]=static_cast<char>('a'+nIndex);
2 n- V/ y0 Y, E% L/ T+ b# L* a    bool bFlag=false;
    if(1==nLeft)
    {
) g! K0 t" e2 L. ~0 c8 h6 s        Seq[n]='\0';
        return true;
    }
  Y" Z2 z0 ~7 f: c' w    for (int i=0;i<n;i++)
( A# y9 s% P: X8 `2 T( m: O    {
        if(true==array[nIndex])
; ?; a7 C7 p+ v' ~# I        {
$ t# K) R5 S: |9 y, G, K            
$ h1 `9 c6 h9 }9 k" C8 U            bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);
- [) I& k7 G5 |        }
: h* \, n) v1 C3 Q+ }1 \" e7 q3 T        if(true==bFlag)
            return true;
    }
    return false;
" O6 j( y+ Y- x/ N3 K* _* G4 h};
7 n+ r* a) }' L6 }int main()
{
    int nSeqLen;
' }2 e! b7 ?" [- z- T# @/ x) {4 j    int nRelNum;
    cout<<"Input the length of the sequence:"<<endl;
    cin>>nSeqLen;
    cout<<"Input the number of relations between the elements:"<<endl;
    cin>>nRelNum;
2 e) _4 |: c4 k1 Z# E3 b    //1:if nRelNum<nSeqLen-1,then the relation can not be determined!
    if(nRelNum<nSeqLen-1)
8 {+ b4 @$ t3 y7 U5 h6 q    {
        cout<<"The relation can not be determined!"<<endl;
! X+ C5 D( r$ I2 p        return 0;
    }
9 C/ y/ G8 L  X1 a    string* strRelations=new string[nRelNum];
    char* Seq=new char[nSeqLen+1];
    bool** array=new bool*[nSeqLen];
6 k0 K. F! y7 V3 B: L1 c
, W: a# l1 Y7 g9 ?) N    for(int i=0;i<nRelNum;i++)
! _( R) p8 s+ E+ I7 i: `    {
        cout<<"Input the "<<i+1<<"th relation:"<<endl;
        cin>>strRelations;
    }
   
+ n5 {1 C  h  x    for (int i=0;i<nSeqLen;i++)
7 D/ U5 k+ p  l7 Q2 F    {
        array=new bool[nSeqLen];
& E$ a* ]/ o2 G$ n/ |        for (int j=0;j<nSeqLen;j++)
            array[j]=false;
2 D; X, \. f2 |8 p6 a0 i    }
    //The main loop
; J8 J1 z% b8 |- L1 |' Y- R, w0 J    for (int i=0;i<nRelNum;i++)
$ {# `/ l; {" ~6 X, h    {
        char a=strRelations[0];
, z8 Z# o3 a* T4 c4 v) N        char b=strRelations[2];
& ?2 O! {* j: B! \        assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
        array[a-'a'][b-'a']=true;
8 R( K) a/ Q1 z' S
+ w: `4 K2 t/ J2 x        Marshall(array,nSeqLen);

        //Check for Inconsistency after  every relation
        for (int m=0;m<nSeqLen;m++)
) N( L, Q. m2 O: ]        {
2 A. V; k: p$ u" w' ^( _3 T. d            if(true==array[m][m])
, _9 n5 N( j4 i9 c4 u            {
                cout<<"Inconsistency found after"<<i+1<<"th  relation!"<<endl;
! M4 m* f( V3 u# W# p5 K                    delete []strRelations;
. K' Y7 V' H, h  Y* }! [* `' k                    for(int k=0;k<nSeqLen;k++)
( [; H4 L. B; ]3 P( y) Y9 D$ a                        delete []array[k];
' Y5 |7 T8 A% F) Q% Y* h                    delete []array;
                    delete []Seq;
                    return 0;

            }
+ {7 F  ~- Q, h5 V( L6 v+ ~0 d, ^        }

9 D" o) }; X6 {. }4 ]! B        //Check for the determined sequence after  every relation   
) H8 h; q2 n& c, g        for (int j=0;j<nSeqLen;j++)
        {
            if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))
3 V- v7 h8 }6 r( {% u9 J            {
& ]; I, m6 P; w* ~' H                cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;
! y) l1 f% \" M2 ~5 \) |* S* A                delete []strRelations;
                for(int m=0;m<nSeqLen;m++)
                    delete []array[m];
                delete []array;
) ]) Z* _3 n8 S, Q                delete []Seq;
                return 0;
            }
        }
; V. D2 G" B7 b$ a5 b

    }
    //If the program has come to here ,then the relationship hasn't been determined!!!
    cout<<"The relation can not be determined!"<<endl;
) N% S: ?6 j, u$ _; M    delete []strRelations;
    for(int m=0;m<nSeqLen;m++)
. P+ R6 x. F7 k" a7 C/ T% B& G        delete []array[m];
4 w2 V, D6 R' U6 ^( ]* [* r) t$ V    delete []array;
    delete []Seq;
   
7 g0 ~7 o1 o& _& p: ]    return 0;
}
+ p6 u  E4 Z% B1 l  r" S
程序解题二：#include"stdio.h"
! M1 d. C1 [1 hvoid main()
) M" u- ]  _4 V9 [+ C( {{
    int n_m[100][2];
    char re[1000][3],
    temp[26];
2 C: t! Q: L( q    int i=0,j=0;
5 U' ^0 `" p$ ^; Y4 Q3 h" X    scanf("%d%d",&n_m[0],&n_m[1]);
    for( ;j<n_m[1];j++)
  K0 P4 N2 v" c0 b2 {    scanf("%s",&re[j]);
    while(n_m[0]!=0&&n_m[1]!=0)
4 y& u8 O# x. Y+ S4 L    {
    i++;
    scanf("%d%d",&n_m[0],&n_m[1]);
    for( int f=0;f<n_m[1];f++,j++)
, F8 D, p* P" R; s9 Z    scanf("%s",&re[j]);
0 r- Z' Z# f4 K- _& N    }
/ v9 h  k: H2 C- c0 @/ s4 W4 v    i=0;
    j=0;
- D2 |7 ^! J" |" I   for( ;n_m[0]!=0&&n_m[1]!=0;i++)
+ N) ^9 R; b0 o" W  n! F( Q    {
' b- ?# A% c9 @9 r/ k  Y       int a=0,b=0,l=1;
6 q2 Q3 o3 k( ?       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])
- ~! r9 e& |- g            {
* T% S% }# _6 G; v- X9 }            l=0;
7 j* K) Z4 y  C( ?. y8 W. i" q            printf("Inconsistency found after %d relations.\n",n_m[1]);
            break;
4 C4 i* ]0 p( a  t* `            }
9 m0 Y" i& K. r$ z9 }, _) x         }
      if(l==0)
2 s5 r8 W) f, ?# M9 R          continue;//Inconsistency found after x relations.
    else{
           if(n_m[1]<n_m[0]-1)
        {
            printf("Sorted sequence cannot be determined.\n");
$ k9 o! m+ b/ g! H            l=0;
        }
. r; N5 I/ v# H) F! A. v        else
        {
          if(n_m[1]==n_m[0]-1)
          {   
9 ^7 K% q1 z9 U* l, B              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])
( D. N& r% r; ]+ U0 H0 S                      {
                      printf("Sorted sequence cannot be determined.\n");
! D4 _. e, l. P$ W                      break;
                      l=0;
/ E! B( O0 I# G                      }
( G+ Q* [/ V% |+ e" q          }
9 I; d$ \) v; Y2 ~        }
# j! h0 t. K' t3 e0 h- V        if(l==0)
9 @; R' D) C7 |        continue;//Sorted sequence cannot be determined.
. Y. j5 W+ |  W! W1 Z
        else
5 ?# |  d" k- U+ D' t         {
           
$ i6 J7 ?4 K4 D' o. a5 q            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;
              for(int s=0;s<n_m[0];s++)
              {
2 A5 P  l: z0 W6 Y3 b# V               if(temp==re[0])
- M* Q% C; n8 l1 `0 O: G' H/ {, R                   t1=s;
                      if(temp==re[2])
$ a6 [- r5 v* Q$ u2 G; A8 [                   t2=s;
              }
              if((t1>t2)&&re[1]=='<')
. F, n7 [; y# ]8 o4 z# y( d9 x. Y              {
                char t3=temp[t1];
% \# J: j3 {- T$ r$ c5 z                temp[t1]=temp[t2];
                temp[t2]=t3;
              }
            }
        int count=0;
        for(int s=0;s<n_m[0]-1;s++)
* A3 _$ I) ?8 n2 u' g8 M        for(int d=j-n_m[1];d<j;d++)
- `0 c+ F+ {+ c* N! _$ P            if(re[d][0]==temp&&re[d][2]==temp[s+1])
, |" G9 D* W& j            {
                count++;
5 N% A+ u; ^# _5 x                break;
            }
1 l  p/ H, r* m, d$ H# K            if(count==n_m[0]-1)
  V+ n& Y5 F4 U- |0 V            {
1 h) ~- x; s: ]& O                printf("Sorted sequence determined after %d relations:",n_m[1]);
                for(int f=0;f<n_m[0];f++)
: d, v2 |% C) x6 S                  printf("%c",temp[f]);
                 printf("\n");
! i: _! k7 h+ P. K4 d, m            }
            else
3 M# q$ `( T. W' @' r+ x               printf("Sorted sequence cannot be determined.\n");
        }
    }
    }
}
  W/ I( ^# f& L% O' H! C, F9 t5 y$ v
. y. g9 a6 ~* i7 z/ o8 D0 G0 y) G- e
3 O; n2 y* y9 _7 Z0 h: P# h8 W


5 s* N+ f/ M3 F7 u% X

1 m! ~  G, L% Q

来源：编程爱好者acm题库