编程竞赛题目（一）

厚积薄发

8 f  o# R& c; c9 CSorting It All OutDescription

% U+ \; V! a5 L  {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.
$ c0 a  u5 \  L  nInput

8 U% F3 z$ m" e! ZInput 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.
! c2 Q% X. D: X% g% o' h. xOutput

# z0 I6 t( Q% }% r6 U1 p' CFor each problem instance, output consists of one line. This line should be one of the following three:
% n$ T; X* e3 ]1 c0 F2 b5 i9 I
Sorted sequence determined after ** relations: yyy...y.
Sorted sequence cannot be determined.
Inconsistency found after ** relations.

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.

输入样例

$ N7 `$ g+ Z3 v" G$ n4 6
( ?, g6 ]) m5 XA<B
A<C
! b2 V. Z5 @0 b9 U/ xB<C
C<D
B<D
1 o) o9 o" `. K. y% X3 DA<B
  ^( i6 d0 w4 ]( v5 ^3 2
3 p' w1 c& b* o" L6 aA<B
$ X' ]5 g) }7 V# H! }; w+ ^9 TB<A
& W0 ?4 x: \; j0 Q& l' g$ T26 1
A<Z
4 p& @% \' s0 e3 U0 R0 0
6 u. S' ~2 {: s9 j$ V5 B+ ]& O

4 G4 M2 g( i. [+ l+ K+ ]1 G" @/ w# i输出样例

Sorted sequence determined after 4 relations: ABCD.
2 `4 i3 M' G+ u/ jInconsistency found after 2 relations.
Sorted sequence cannot be determined.

Source

: R) b& @  W4 L9 R$ D& OEast Central North America 2001

程序解题1：

//By Jackie Cheung
: T. M# l4 A% c3 Y#include <iostream>
#include <string>
$ ?1 x- N; {- R- a#include <cassert>
typedef  struct tagNODE
{
( P0 W& L: r! r    char val;
/ e3 |6 A/ Y: B; R    struct tagNODE* link;
}NODE;
using namespace std;
/ L1 \) K2 W& D: x6 w& J6 ^void Marshall(bool** arrary,int n)
{
% I# Z2 ^0 c7 N& b/ H/ F    for(int i=0;i<n;i++)
# L; u& ?# M/ j) {    {
        for (int j=0;j<n;j++)
        {
( c* h8 p) f  d' t2 q" z: h& }$ M            if(true==arrary[j])
+ V& H4 W' C* r6 z' a                for (int k=0;k<n;k++)
% x9 Y0 b- S( {- _) o                {
                    arrary[j][k]=arrary[j][k] || arrary[k];
                }
        }
    }
};
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)
) ?& H1 s! N& r7 `    {
& U! H- K3 N- p2 M5 J4 Q# l/ ^        Seq[n]='\0';
- a3 H! N+ G2 u( Q        return true;
    }
    for (int i=0;i<n;i++)
4 ?7 o& i% ?( ~! F! ?    {
        if(true==array[nIndex])
        {
6 g, l/ E% W* e1 a            
4 f8 u  Z  E) \# r7 k/ ?4 W            bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);
        }
        if(true==bFlag)
            return true;
& l; P; |. I( ~+ T( h    }
  T3 T- u- m, J& i3 I& q) H9 M    return false;
};
1 \/ C/ M; n, Nint main()
! }% m0 t$ y7 v! @+ v! w/ Q( j{
) U6 W5 F0 b8 C$ ]    int nSeqLen;
    int nRelNum;
8 W3 n. V( N4 j; y    cout<<"Input the length of the sequence:"<<endl;
- G* Y7 f0 @8 y1 e, M9 x4 D1 \    cin>>nSeqLen;
/ T7 d* y, L+ q; a8 Y    cout<<"Input the number of relations between the elements:"<<endl;
' Z2 `, L, `3 j$ Q" c    cin>>nRelNum;
; j) u( ]8 I: E/ {9 m+ l0 Q5 J    //1:if nRelNum<nSeqLen-1,then the relation can not be determined!
    if(nRelNum<nSeqLen-1)
    {
4 ^$ k/ Z0 [- M  K0 h5 A; k        cout<<"The relation can not be determined!"<<endl;
& ^2 w% q7 z/ N- w: I, r" W* h% o        return 0;
    }
5 n1 W7 S( s, m! ^    string* strRelations=new string[nRelNum];
5 k$ b% t! B- _& Z% ?3 s6 t$ |9 b6 W    char* Seq=new char[nSeqLen+1];
6 y" j+ w$ J; X, t7 Y# S, Q9 j    bool** array=new bool*[nSeqLen];
8 s/ M! p! C; T6 Q# @6 X7 h
$ ~% ~# x4 Y; i$ Q9 t$ J0 r4 W    for(int i=0;i<nRelNum;i++)
    {
        cout<<"Input the "<<i+1<<"th relation:"<<endl;
+ }4 M6 b6 C1 Q! r% z' i' f        cin>>strRelations;
    }
   
    for (int i=0;i<nSeqLen;i++)
    {
. v/ S& Y/ v9 }0 `        array=new bool[nSeqLen];
, G" z% `% O, d" Y; S) V        for (int j=0;j<nSeqLen;j++)
+ X  c' D5 |" z- X8 j3 e8 T            array[j]=false;
- H  H3 |$ S& }& w    }
8 `4 \) C+ C% K9 I" \% Y- ^1 `    //The main loop
    for (int i=0;i<nRelNum;i++)
    {
        char a=strRelations[0];
4 \1 @  E/ }; Z% K        char b=strRelations[2];
        assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
        array[a-'a'][b-'a']=true;

9 |7 C' v+ a2 O' q2 O" B        Marshall(array,nSeqLen);

& B' e" c, a; ]5 Q        //Check for Inconsistency after  every relation
$ R, N) v( w5 d& j        for (int m=0;m<nSeqLen;m++)
        {
4 N$ d+ c# f& p$ K! a% W+ h! f3 u            if(true==array[m][m])
; d( v0 o" [2 P2 A            {
                cout<<"Inconsistency found after"<<i+1<<"th  relation!"<<endl;
                    delete []strRelations;
                    for(int k=0;k<nSeqLen;k++)
                        delete []array[k];
                    delete []array;
# @3 G) h6 P- o: S% e- N7 G: e; B                    delete []Seq;
                    return 0;
2 R+ F1 x! K7 O. _. ^" F
( K' w# l+ G  k: P  }            }
- K# W3 ]/ h3 M7 O6 j        }
$ ?% B7 P/ B  B
        //Check for the determined sequence after  every relation   
        for (int j=0;j<nSeqLen;j++)
; d% a5 a7 e+ }$ W- n5 R        {
2 o, C% a- T' _8 N% ~0 Y: v: _            if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))
            {
( U3 U/ a7 r0 ?6 O                cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;
                delete []strRelations;
6 Y& f% r8 y. [                for(int m=0;m<nSeqLen;m++)
" W* D# `/ e/ b0 e: s4 n' P                    delete []array[m];
$ s, Q. x5 }7 o/ E* O0 ]1 Z7 }                delete []array;
" n  b, P6 p& n; w* x                delete []Seq;
: [8 J4 M7 u4 d7 [& w9 l5 W                return 0;
            }
        }
7 G: j( D/ r4 I
& k) c$ o% d; N  T
, P) D+ U0 K6 B. {: E/ F    }
0 A( g5 X9 `# Q" ~1 C; T    //If the program has come to here ,then the relationship hasn't been determined!!!
    cout<<"The relation can not be determined!"<<endl;
! m. M! r9 e4 h/ |8 v1 q  `0 _5 `    delete []strRelations;
5 H1 r' |' t# o  b* d    for(int m=0;m<nSeqLen;m++)
        delete []array[m];
    delete []array;
    delete []Seq;
   
    return 0;
; F2 \$ e* Y7 B+ |% t}

! w; s  c4 Y2 Y, h程序解题二：#include"stdio.h"
% [# M  x2 v  E: fvoid main()
{
    int n_m[100][2];
    char re[1000][3],
    temp[26];
9 D$ x; z5 i: s/ V    int i=0,j=0;
    scanf("%d%d",&n_m[0],&n_m[1]);
+ V, V- v$ B1 t: ]9 w    for( ;j<n_m[1];j++)
7 w8 j# o/ a& z" Q. M    scanf("%s",&re[j]);
- c. t0 D, I8 f" e+ z. q    while(n_m[0]!=0&&n_m[1]!=0)
. |3 G( M! F& W5 Y( |( f! ?    {
    i++;
3 U! G- r+ t) F& _$ C* H    scanf("%d%d",&n_m[0],&n_m[1]);
( [, `8 r. N# d* o. u+ R8 j    for( int f=0;f<n_m[1];f++,j++)
    scanf("%s",&re[j]);
    }
    i=0;
! j8 f7 [8 I# ~0 v" `    j=0;
   for( ;n_m[0]!=0&&n_m[1]!=0;i++)
2 a0 y  ~. n5 C4 b2 y  c  B5 s. d    {
: n/ j. [0 A: v8 [       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])
) f) ~( k# n+ y) V            {
  V& K  F9 B' s0 m/ p7 L            l=0;
            printf("Inconsistency found after %d relations.\n",n_m[1]);
            break;
! v$ q0 j% C& @; o3 A% d3 H5 [            }
         }
      if(l==0)
          continue;//Inconsistency found after x relations.
    else{
           if(n_m[1]<n_m[0]-1)
        {
            printf("Sorted sequence cannot be determined.\n");
            l=0;
        }
        else
* O0 c) t# I" \; o. w1 v0 H        {
          if(n_m[1]==n_m[0]-1)
          {   
              int k=0,p=0;
* @3 x2 I* ?) n              for( ;k<n_m[1]-1;k++)
3 v; @9 O4 x/ f8 a" n                  for(p=k+1;p<n_m[1];p++)
% }3 A6 p6 }4 P! K  S/ X                      if(re[0]==re[0]||re[2]==re[2])
* ?7 a. z  I& K                      {
* T, p' T. z- u( L$ A                      printf("Sorted sequence cannot be determined.\n");
                      break;
                      l=0;
$ B3 o4 p* D# i% M+ }" ^4 o, l$ z                      }
% L* ?2 g+ ?1 ]# h/ C          }
  v% G4 d$ _& c1 f2 @* B* d# J        }
        if(l==0)
4 V+ S/ m  C* }9 D4 m0 f        continue;//Sorted sequence cannot be determined.

        else
         {
5 p* a* h# x3 M, R$ l- M           
            for(int k=0;k<n_m[0];k++)
             temp[k]=k+65;
0 [% Q$ ]. N! `            for(k=0;k<n_m[1];k++,j++)
; G/ L6 [! [- j( \, y            {
8 N! S9 D; J( y; ]                int t1=0,t2=0;
              for(int s=0;s<n_m[0];s++)
7 F! B2 h- r2 q+ k( Q6 R              {
               if(temp==re[0])
! N: |3 H& w  f, w) \0 r$ Q( g4 `/ n                   t1=s;
                      if(temp==re[2])
                   t2=s;
4 Q" I; {) g) }/ V              }
0 T( f9 T8 K' e7 w. U2 T! i              if((t1>t2)&&re[1]=='<')
; J- X9 B  Q8 z: t2 C              {
                char t3=temp[t1];
                temp[t1]=temp[t2];
5 r0 Z3 }7 i/ T                temp[t2]=t3;
1 l5 }; W3 p7 F! n; C# ?              }
            }
        int count=0;
        for(int s=0;s<n_m[0]-1;s++)
        for(int d=j-n_m[1];d<j;d++)
  J* [0 T! b$ x" C, x, e            if(re[d][0]==temp&&re[d][2]==temp[s+1])
+ s8 F6 {3 W% D3 U7 L) l- b            {
                count++;
                break;
            }
            if(count==n_m[0]-1)
- F* R! V- E  E/ r2 L: r            {
& N' N5 g4 v8 F' z1 F+ A0 T6 e9 S                printf("Sorted sequence determined after %d relations:",n_m[1]);
; M2 [; c# u! z# n8 C$ d& B; `                for(int f=0;f<n_m[0];f++)
" ^9 J: Y9 |- T4 F- O                  printf("%c",temp[f]);
( o# ^. W: [5 e& y+ L% r- g3 t                 printf("\n");
/ R& T, i& v: g) r  q/ o            }
: |! e4 h. g  }            else
               printf("Sorted sequence cannot be determined.\n");
: B9 @! U3 }9 ]1 K        }
    }
" i! X" `0 z6 P5 d5 A- `    }
}
5 o/ |5 Q) d3 K% M  }  E

& D& r3 J& ^/ l: @/ A$ n* m
9 a3 Y! v+ W) `( [
: w1 \2 q7 O0 u6 h5 o% p



4 w  q) l0 T& y% e

来源：编程爱好者acm题库