本帖最后由 厚积薄发 于 2010-5-6 18:40 编辑
4 x$ l! J9 k$ N$ h/ Q! t, @: ^; d) n
6 @: `' \! i0 USorting It All OutDescription
: N9 [" }) ]! Q ^& [4 V( X
3 b- @3 c# b; G6 Q. CAn 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. . F1 S& ^; r/ l
Input, |1 P$ C8 U: k: e
) w: U5 J; B8 E7 X B5 B0 CInput 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.
& `7 p- M4 `; f cOutput( p* Z$ `, ?, C8 e- j* g0 n
2 I; Z: R- T6 O! a
For each problem instance, output consists of one line. This line should be one of the following three:
3 f8 @* V, p" O: \
8 S; C, \& }0 p3 n, w7 Z5 c# sSorted sequence determined after ** relations: yyy...y. $ D' v3 J1 D* j
Sorted sequence cannot be determined. . u% |* y6 F; R {
Inconsistency found after ** relations. / v4 S M( i. |8 q( @
* e# L$ p+ H* D. w+ U* Kwhere ** 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.
6 b: r8 a" s, ^3 A# N( e2 G+ p
, ~. S) T2 S5 Y g6 e输入样例
. r1 J% l/ ^% m4 y. q T- g1 A4 U' `- D; r4 6
% i. E1 I: ]# m$ b1 `A<B) J, W0 n5 W! \9 s: p3 C
A<C
9 h. v$ C. o' ]. r9 j& b1 b1 l* CB<C
" n: ^- g' y2 y( G1 B5 \, MC<D
& ]& e# B# L# cB<D
3 g& P( ~% \& i- @3 ?% H v1 wA<B, [7 \- L; o _8 [% P) s
3 27 k+ V* T$ P0 m8 P+ K
A<B
$ ?) L5 z! V8 c0 WB<A- ^, S% r# J5 v3 S; m
26 1% T4 { a* p+ R4 j* `9 k* ?0 ^1 F
A<Z& w) C/ B, K; y7 c$ ~% X
0 0
6 ?$ t( y! u, j6 y7 {& v1 X _ 2 x; t9 o/ ^' C u) S. F0 _
输出样例
- L/ V' B; k" ]& @! [; K8 lSorted sequence determined after 4 relations: ABCD.
7 t6 J1 }, \. aInconsistency found after 2 relations.
$ c7 k: ]8 X! b2 o; {1 PSorted sequence cannot be determined.
4 E' n: l& Z d$ S# PSource
+ Y: l7 U8 U( e* o Z8 h3 }+ s$ `; H0 N& f
East Central North America 2001
3 K0 }8 o2 w6 V; o5 ^1 j程序解题1: ) d! X; \% c) Y6 }
//By Jackie Cheung/ b& Q6 U$ f3 V y
#include <iostream>* s* Z. o- [, J. b
#include <string>
% I- Z: j3 m2 n+ N#include <cassert>
, [1 ]: G* L0 T2 N( x0 }typedef struct tagNODE
+ g( [6 o1 A5 y/ T$ ^' r' ?+ j{
1 l) T+ Z' d! Q; s0 r* H( q$ A char val;
2 q. i$ }& _6 \1 N+ F struct tagNODE* link;
+ [- O u& H7 C% _) g* ^}NODE;+ g' f& h6 o% f# g- p
using namespace std; n8 [4 r: k6 w X
void Marshall(bool** arrary,int n)0 Y4 ?: b3 R, M9 n9 x
{
7 `2 r, q/ x; K! F, v6 o for(int i=0;i<n;i++)
4 W' n/ A+ X# e {
# W9 x+ |- s, P& p2 r7 A for (int j=0;j<n;j++)
- o' ]$ o: H l i {( |$ z4 @0 s4 F7 T; [
if(true==arrary[j])8 I6 e, T6 [/ F2 b1 N8 [
for (int k=0;k<n;k++)( n Y- `1 M* a4 U1 Y
{' K9 [6 r4 Z9 U9 k9 j
arrary[j][k]=arrary[j][k] || arrary[k];
% d3 K: c: e* H6 c' T }
' t$ d8 j# ~/ Z q% l8 B4 F: I }. G! C' R! i# S6 |
}- b4 g1 Z8 J8 m
};/ o& P2 U3 ^* s2 |& l. t0 Q" Q- o
bool SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)
! ~6 _9 h- O6 V# s/ Y1 w. ]4 y, ?{
/ d) v9 |+ e1 L2 S Seq[n-nLeft]=static_cast<char>('a'+nIndex);
& o2 V5 s% V! H. d/ } bool bFlag=false;7 s. F. g7 Z3 i) T* d- w
if(1==nLeft)( M" F; M0 H0 [/ B0 w+ x& Q
{
6 R- r+ l. f8 z# Y/ r; Y2 m Seq[n]='\0';" e8 V1 [; j v
return true;
. H6 ?9 U1 [5 y: ~1 H& [9 M }7 B0 ?2 b; O! g t9 }1 R# [
for (int i=0;i<n;i++)$ r: _3 O n5 [- j! x4 W
{8 Y8 }# a8 K, y8 k# G
if(true==array[nIndex])6 _/ [+ j8 H7 W
{
" B+ l8 E/ j- m: e# g ' F/ Y) v( r$ `- W# w1 W- {
bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);' {+ x. Y; b$ D7 a# B" X
}
; w5 x8 ?- {5 N* X if(true==bFlag)8 u) y {$ R9 s* I+ I2 N) j
return true;1 Z, K! g( _% u/ u4 H( X
}
' X7 `$ N b0 t0 f. m# L$ b6 r return false;; l7 M. p" P6 \) v+ ?, q2 N$ c
};
) W! l5 [9 o' f+ w7 Mint main()/ e: {: k2 w4 z* H
{( ~! t; ]% g8 b6 ^
int nSeqLen;0 S" W# `5 U m$ s- H
int nRelNum;! h6 x3 s, ], W' Z0 ]
cout<<"Input the length of the sequence:"<<endl;$ E, [8 G1 F8 D0 r/ [7 `% |
cin>>nSeqLen;, X! N6 q' \7 H: h- q' a# c
cout<<"Input the number of relations between the elements:"<<endl;3 d! l4 p, u7 ?4 e7 S- D- s
cin>>nRelNum;
, B* ~+ \5 v0 U: n- t1 d //1:if nRelNum<nSeqLen-1,then the relation can not be determined! \$ r2 S0 n5 O) H3 D0 F7 s
if(nRelNum<nSeqLen-1)
; l. ?" t a5 U7 L: G {$ m! Z% T# k! g/ I* ^0 a! X
cout<<"The relation can not be determined!"<<endl;
: j# T# l M z) j6 B5 F+ Q2 A return 0;
& q$ t$ C0 d" F3 i# K4 J: H+ j }+ ?; c6 O" F& j. G
string* strRelations=new string[nRelNum];) s- y5 z1 P* ?+ w7 D2 y. o
char* Seq=new char[nSeqLen+1];4 S {9 h$ g" `+ N/ v" H
bool** array=new bool*[nSeqLen];0 X2 C8 k* O8 u& z: f8 p
2 @+ ~' H+ L" K
for(int i=0;i<nRelNum;i++)
- B$ u( c, {; l {* g5 ]2 S. D+ z
cout<<"Input the "<<i+1<<"th relation:"<<endl;& @& h: m! H8 g. b& z5 N& M* _
cin>>strRelations;
4 [. z8 ~) d7 t% g' h }7 A2 N" o& M, z3 C+ @& D
6 ]4 F& l8 o: D( F* x i# X for (int i=0;i<nSeqLen;i++)% ]" ?" ]4 \9 ~0 h& H
{
9 o+ i4 N m# A array=new bool[nSeqLen];! a& w9 L6 O3 H! F) G( H
for (int j=0;j<nSeqLen;j++)
1 h# g) J2 ?1 P array[j]=false;
% W2 Y t/ H$ L# \4 {' W0 ] }1 L4 H8 u! {+ D! z( j- [
//The main loop
, |, Z3 g+ }8 n U" J for (int i=0;i<nRelNum;i++)
# N8 k9 y/ f2 A& w {* Q; W3 }5 K6 A: R/ Y% |7 v
char a=strRelations[0];8 Z& @/ ^) q, |" _
char b=strRelations[2];
- K5 N6 @8 _5 B/ X6 {+ A$ ?) ] assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
- ]3 _: O0 i Y1 _2 W array[a-'a'][b-'a']=true;0 N1 y" d. F' T4 Q0 L( C& u& T0 h
8 k# n: J( N8 _' }4 F& Z" a Marshall(array,nSeqLen);( F( H. Y2 [* X3 l) n3 c, T( P: J7 d
* s/ G% o0 l, c, I u* M
//Check for Inconsistency after every relation
$ ?( s% ]( ^: p$ N, H5 i for (int m=0;m<nSeqLen;m++)( e" G% O7 p* Y
{
2 t% I0 o" R1 p7 e6 z if(true==array[m][m])
/ B: { j3 Z4 L$ @+ g6 D. s {; u$ O5 X( o3 p/ @# {5 @) y6 P5 n
cout<<"Inconsistency found after"<<i+1<<"th relation!"<<endl;3 `& c1 u( u5 X
delete []strRelations;- E0 O- b* Y" t* D
for(int k=0;k<nSeqLen;k++)
7 q% g- l c" h6 `, l1 n$ U delete []array[k];( X( {9 ^9 B) h8 Y2 s4 ^4 h, t7 K
delete []array;
$ C1 R- N) x1 v0 x" ?1 [, ] delete []Seq;2 s# x0 `! }2 C
return 0;
4 f. o, G8 N' ~( U M7 h1 H' e4 J( @7 O* @
}1 }" Q0 ^( @5 E9 d1 r
}& ^6 v5 b: c5 a- s ?5 T8 c
0 t+ s8 y6 h( A3 \
//Check for the determined sequence after every relation
) |! Y! L9 P+ u3 x: C6 L for (int j=0;j<nSeqLen;j++)2 x+ |; l2 ~4 s1 E7 F p
{4 x* v& ]" ^& v) O+ D. I( r6 c" J
if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))
5 v1 K7 g& b8 s* U+ i1 A6 q {
( |% ]8 Z) O& X x cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;# K, r/ H! l- f* L, m U7 d
delete []strRelations;
2 x( |# Z7 y; l0 } for(int m=0;m<nSeqLen;m++)
) d7 E# p! {: s9 | delete []array[m];
5 O2 @( x0 I7 u delete []array;+ T& w/ m0 J9 c
delete []Seq; ^8 [3 a3 O% C. B( {
return 0;, }" p% V2 P9 g" H2 U! w F
}. J: Q6 u* x1 L
}
2 O) g! ~ V, {, ?) I# i2 b+ `/ @9 o. f; Q' |: F8 q% Y0 j) t% T
4 D! V6 p* K9 B0 s/ J+ f
}
3 N0 k. ~/ |9 L9 f //If the program has come to here ,then the relationship hasn't been determined!!!. U$ x) T& S7 F7 z! }% F- h* W
cout<<"The relation can not be determined!"<<endl;
( G6 M$ C9 f7 I- Z& H8 j3 [ delete []strRelations;
- K8 D* M- A9 N4 E# B t( a for(int m=0;m<nSeqLen;m++)
" Y) I. X, c2 U: {" Y7 H delete []array[m];
7 F: K$ d) u& r( _! w delete []array;2 Y; @$ G( t8 }& a w6 c
delete []Seq;& {8 M; m0 I$ r2 d0 a
: }& `' w2 }( i: J n5 `7 n6 ?
return 0;
" F! H) {; j9 `1 ^, G3 H5 u}1 |. G+ ^' L# S7 m
* o+ G2 g4 U" k; x3 A! L% y程序解题二:#include"stdio.h"
8 A& v+ c2 v1 f' c/ uvoid main(): Z9 k8 f# V. n0 }' Y, [3 I
{
# _, `( ^* S- b N4 W" W int n_m[100][2];. [! T, E; D1 y+ P" T, o
char re[1000][3],
# o [- P* j; u temp[26]; q; L6 Q# j, O h; a. d
int i=0,j=0;; g8 N; Y7 G* y
scanf("%d%d",&n_m[0],&n_m[1]);% T) ?; s6 C, S' Q# `0 v+ w
for( ;j<n_m[1];j++)
" a# t3 g5 H2 g' j scanf("%s",&re[j]);: }; ^+ n7 t8 u
while(n_m[0]!=0&&n_m[1]!=0)' ?1 B6 d9 Q. ]% Y" {9 p
{
, l6 C' u! Q ^! T* p/ d7 Q, J i++;
4 s3 R) \6 @" L3 k scanf("%d%d",&n_m[0],&n_m[1]);
3 B5 E7 j- M0 H for( int f=0;f<n_m[1];f++,j++)
! z) u C" |" T5 {5 M ?) T2 } scanf("%s",&re[j]);* b) o2 ^* A2 C M( A; z
}
9 w% P" \, a. b( {. Y1 v i=0;; f6 q# u( G6 K# }7 D& ~
j=0;
9 S+ }( Q& Q! \0 Z) A' w3 V2 G for( ;n_m[0]!=0&&n_m[1]!=0;i++)
. O" X; h) I. p& z( Z {
) b6 E4 n/ J! l& v int a=0,b=0,l=1;
5 {: j; j: L6 Y9 c) P) P3 I: `; Z for(a=j;a<j+n_m[1]-1;a++)
# R, f1 \5 t, i( {% y1 u7 W for(b=a+1;b<j+n_m[1];b++)
/ }7 g. d1 ]2 J ~' T {) W. \2 d5 _% I G3 U ~9 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])/ _: A k6 D* i; @/ M4 T: n3 G' B
{
' [, {7 y* r, P* G l=0;) `+ s- D; \9 i5 A
printf("Inconsistency found after %d relations.\n",n_m[1]);
1 O* t" C% p( L! t break;7 J. h7 e9 _- ~5 z
}
]% u# C5 k) n3 S }: J! B! N1 X6 q9 q' j1 e+ B+ o
if(l==0)
, Y1 }/ I& W# a5 m9 i continue;//Inconsistency found after x relations.
0 L8 t, @, K9 E. T) S else{8 P+ d+ T7 u' L" ^0 ^ N
if(n_m[1]<n_m[0]-1)
/ L \( |) Z0 K0 f; o& A {% V+ R3 A& e4 {; Q& R* m6 i
printf("Sorted sequence cannot be determined.\n");' @; r# n# ~% b# s( O! C% O
l=0;: N4 c6 V! T: C, Y$ T6 O+ J
}
) Q4 M3 w0 @- s4 m: ~5 l p! P4 i else2 ]- N6 r% o q$ v# X4 c8 {7 X
{
$ U3 T! ^ `" L7 s- m% l& F6 Q' w if(n_m[1]==n_m[0]-1)
I: i( s) O+ N& r { 6 Z# g6 G4 j/ _# W+ S! Y
int k=0,p=0; f% T2 z# e5 L. Z7 r7 A7 d! t+ V
for( ;k<n_m[1]-1;k++): N. C$ R% q6 ^4 U# F ?
for(p=k+1;p<n_m[1];p++)
5 }1 {1 L7 ~& ]) U if(re[0]==re[0]||re[2]==re[2])! F/ F+ l& o4 Y1 ~# J" v* s
{9 f9 |/ q' C6 B# H: z
printf("Sorted sequence cannot be determined.\n");
; v' ^. I$ w, a g% I& a break;3 M! r4 T9 W a8 ?$ o& Y# C( l/ P
l=0;+ m) V9 c. x7 G( P- G4 \/ h! \+ H- l
}
Q+ |- s4 p; {( | }2 P2 S3 u- C$ K, o) u- k
}- a0 X6 D7 A9 _+ N
if(l==0) 3 C1 @' R0 T$ e a3 Y# ?
continue;//Sorted sequence cannot be determined.; S0 i8 Z* i m/ V
% ?& y$ d8 h8 A else
$ x( `" ?1 Z' X8 G4 ` {
1 D' ]0 q/ E( h) ^& c
2 Q s( V: O' M5 | B for(int k=0;k<n_m[0];k++): h7 |( Y" @: ?% `$ b' g
temp[k]=k+65;
" j$ F% f6 {% T0 _4 h d2 j8 Q for(k=0;k<n_m[1];k++,j++)
# x( i8 B( ~/ _' M/ s n- r: {; p {, \# B6 v0 e8 ^: G
int t1=0,t2=0;
4 E7 a: I: H$ @" A% y& v6 f for(int s=0;s<n_m[0];s++)! L( r. `9 D4 q
{1 ]8 x6 m4 }( l' U) ^
if(temp==re[0])9 ?( B5 D/ K" R
t1=s;3 [) Z/ p: W& ~3 u' ~" _
if(temp==re[2])
9 N- |' w$ L$ [. |( f& L t2=s;: D% g7 r1 e5 G8 \2 y8 m
}
+ T8 E% m4 V: l2 q# ~8 h if((t1>t2)&&re[1]=='<')
! O5 V! k2 x1 @3 [5 ~ {
. C$ h. L) |0 x( S- m% z) G$ W. f R7 \ char t3=temp[t1];* N, s8 B% X4 n. W) d7 ?- O9 _
temp[t1]=temp[t2];
9 s3 m0 H. r1 C, b, ~1 q temp[t2]=t3;
1 r" \2 n. A3 [ }6 a0 {! S* _# d- H3 q( e
}# f n( G+ ]6 a% N& R
int count=0;
! a i: R5 T# f1 _( e for(int s=0;s<n_m[0]-1;s++)
9 }0 C2 [6 t$ z9 v/ F3 D for(int d=j-n_m[1];d<j;d++)7 ~# J# h4 s# x" U( i' B" v
if(re[d][0]==temp&&re[d][2]==temp[s+1])
u8 a, ~5 w; ^5 n9 f0 d( p* P {
' g4 u" E, O3 n: A, N count++;$ {; K- ~5 M" M" T s- m5 p/ _' c. w
break;
3 J* Y& Q. n6 P3 p7 N }
& S! q; f7 c T3 d) p, O9 J2 f+ m1 @: w if(count==n_m[0]-1)
3 [/ H s* E& H2 V0 G0 i4 Z4 | {
C) f! m4 o }. C0 C6 p9 W. Z9 _6 t printf("Sorted sequence determined after %d relations:",n_m[1]);; { d1 _& n v9 b% Z O3 }) |
for(int f=0;f<n_m[0];f++)
t) {) {% r- w8 a) Z7 j printf("%c",temp[f]);
1 [6 j& A% N# ~& i' Z printf("\n");
) V9 R3 _2 W. V5 E+ C6 A }
0 @ S2 I' Q) M9 v else9 l, I; |' ]! m. D0 x* _' C
printf("Sorted sequence cannot be determined.\n");
0 e* _$ {1 i9 R: Z* S }8 T# @, r" ~; q+ h. j$ x. }/ u. u
}3 p( ^3 K0 k9 e# a# ~% t
}7 B, m6 ~: \6 ^: v; e+ J D1 o+ V
}
" ?, s; I" E6 _: g9 X. E1 h* O
) k' n4 a% E, ^9 x
& [$ M( @' J' B" i, l( X( K F" _
1 A' ]0 F4 p0 T8 C
/ z$ L2 j. J5 R. Y* t. x* _8 x. s
1 E4 D3 p: Q4 ~
) l- R x+ D/ W* u9 Z4 n/ R; ?. O' K; r( n
来源:编程爱好者acm题库 |