本帖最后由 厚积薄发 于 2010-5-6 18:40 编辑
$ \8 Y$ o+ e+ g2 z6 K4 a4 _' z/ i+ e- r
Sorting It All OutDescription' i- F: R5 p: t0 G7 z
$ A- s# i3 w# z# ?9 \+ qAn 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.
9 ]. @" d8 } u' R4 K' [( _6 t/ U; d0 bInput" s! G2 b, m: m6 G/ B8 g& }
5 F) w+ @& x I' _ w1 D3 d& S
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.
+ r8 b' }1 \3 R% K; `4 hOutput# Y- Q5 o2 c5 \* }
$ t4 S8 Y8 Q( w7 r( {For each problem instance, output consists of one line. This line should be one of the following three:
* U$ g5 x' W& v3 n1 l5 ?& i, U4 e9 v3 {7 H: D
Sorted sequence determined after ** relations: yyy...y.
! `4 I) o: `* mSorted sequence cannot be determined. ) _. j C' X) e& U+ l5 l, L) K$ X
Inconsistency found after ** relations. 8 @) |% x: v' q
0 M8 g+ H/ H$ E. v8 B
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.
. s j2 ]) A. g6 I8 J- b
7 i5 Q, x& c+ O1 }3 ?- ]: r2 t5 T2 `输入样例
6 E5 e% [8 {" B3 @% n4 6- C5 v6 g3 |0 M
A<B
4 u- ]; E5 Z9 AA<C; ~ V3 O* a7 t4 Z0 f v
B<C
7 g! {9 g7 j8 U9 v; j7 \$ t7 b7 XC<D
, k5 F" W( j: w, ]- J" o' B7 rB<D) |7 h+ O3 m; ~; `; ]
A<B F" F( |1 s G* g2 b1 y
3 2' x2 N1 |, H5 [$ m/ |: `: y- Q
A<B" r. G1 E; V% }7 [# l" u# N7 r
B<A3 X0 M# v6 M. r9 W7 l* Z! E% \% d1 f
26 19 {* x' h3 B: X3 ?* m: X
A<Z
! c+ o' U& o1 `7 c% ~) p( f% Q0 05 V! q0 E5 X: Y K1 j1 _5 n1 ^
0 I! A. g% `9 Y2 q0 S& s/ [, h" |输出样例 3 {( r! {9 H& f- h
Sorted sequence determined after 4 relations: ABCD.
" J0 X- X: J! cInconsistency found after 2 relations.
6 @4 Q. H9 @7 H% _Sorted sequence cannot be determined. 5 M# `" O+ E( g+ }& ?* E4 Y% |
Source
+ E5 `7 R3 R" R( t2 `0 Y- g: F- ^) i0 B
East Central North America 2001
O9 \4 F# O; d" G! \: M程序解题1：
7 y7 |/ J& Q% a//By Jackie Cheung w5 F, ]& V2 G; h
#include <iostream>
* [8 t) a) U, _% B1 b0 u; T# C' C. W#include <string>
7 H; p1 X9 F s% G+ p$ Q#include <cassert>4 t9 F' D- x/ s/ U1 }
typedef struct tagNODE
- M6 }" M3 m2 q: Y{& u5 }! W* d) W7 j7 S
char val;/ m* m' p! V/ g% \" _
struct tagNODE* link;8 G: ]: e! q' X" B Z& R2 \( n/ z
}NODE;
7 Z& d+ z3 u+ c" x' ~" K8 dusing namespace std;
' E/ b% }& u2 Ivoid Marshall(bool** arrary,int n)
% Q2 M" [, v! k% K( g9 d6 v/ j- z{6 k' P% c! G6 W+ s
for(int i=0;i<n;i++)
( Y# ]0 X( H" V$ g8 L {0 D/ |4 ~( J( R, Y' j: f
for (int j=0;j<n;j++)% m7 U+ [$ X$ i- A
{' \ ^& \8 C9 q" u$ x# L) y7 c
if(true==arrary[j])
3 J; ~% {; i5 {# } for (int k=0;k<n;k++)
+ e: b' n; s, o% S {
7 ]0 ~: l% x2 X$ f9 y8 r' N arrary[j][k]=arrary[j][k] || arrary[k];
& Z! ^6 |3 H2 D: n }
# i) ]. f4 a6 E% E# ~2 I }, h& H& Z, T' H' `6 z, M
}1 C/ v" J5 o) Z% N5 F
};. b2 g& o' C( Q, e8 ^ b' G6 i
bool SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)1 }% S8 q% i8 X9 ]# }" Y2 ~, }
{$ V( o4 b/ V% p2 I d
Seq[n-nLeft]=static_cast<char>('a'+nIndex);. q7 h# x) X# d
bool bFlag=false;
3 y5 Z* u% D9 n- r if(1==nLeft)& h- ?, |( O m( u
{" o7 n2 [/ c. X$ `- M
Seq[n]='\0';8 M- u2 Y1 F4 Z9 X
return true;
2 {" Z8 O7 t- }7 y }
7 W/ c2 P! r- J1 o for (int i=0;i<n;i++)
. N6 K3 u) C! T" |- r2 ? {' \6 x4 ?$ r2 D: B( c! M7 \0 \8 v2 o
if(true==array[nIndex])
: Z( Z; K* e# ]+ u- n {* w+ m6 a4 x/ d- y& F. F: I+ P
/ K% @; u/ S s, M. _
bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);
3 H+ ^8 t) N8 b' ~2 Z }
* g P) r; B3 r* s8 O7 Y- ~ if(true==bFlag)
V+ g+ e K5 V8 | return true;
! [9 }/ k( I/ P! [$ `+ [* M }
; d* }' B" B6 t* u9 e; }8 U9 ~ return false;+ n" |4 \4 s- b( ]8 [' p, K4 C+ S4 H
}; f+ b# m$ c) B( v$ @ ~
int main()
# x7 c3 k% n* l+ _- }6 u9 T{! K4 s$ }) E6 h, k1 c
int nSeqLen;2 l0 ]* _ X G$ h3 V
int nRelNum;$ ^; ]- m/ y; ?, z3 z" h7 h
cout<<"Input the length of the sequence:"<<endl;0 Q0 O2 U; \. T4 j! y
cin>>nSeqLen;, R& X! f! K c; g% g3 Z4 p
cout<<"Input the number of relations between the elements:"<<endl;( i$ {' Q' o7 i- c7 h* T9 A
cin>>nRelNum;
4 u7 L# p# Y; }0 O9 H: t# b8 Z6 N% ? //1:if nRelNum<nSeqLen-1,then the relation can not be determined!% m9 ~4 u* G% X- s; x; ^% B
if(nRelNum<nSeqLen-1)( b: |$ ]* M* p. h% Q" p& s
{) G( k6 J4 g( W! B: C
cout<<"The relation can not be determined!"<<endl;0 T/ w! t/ f0 }0 j+ C
return 0;4 h$ o% d7 \* [4 ]- H; y9 C. `
}1 H. t1 v( I0 s" E$ q9 Z' ~" I
string* strRelations=new string[nRelNum];, l0 q4 A) ^$ Z! \+ z O7 j A
char* Seq=new char[nSeqLen+1];
5 W9 l& ?# \* C& l bool** array=new bool*[nSeqLen];
7 E2 B* d2 j% u0 Z( [4 l, x
% X5 E# z6 y, F6 a, M6 K2 N for(int i=0;i<nRelNum;i++)$ o+ w5 A+ H+ \. A
{. K' E# \" X2 b# S2 }+ V
cout<<"Input the "<<i+1<<"th relation:"<<endl;2 d5 O8 H5 S7 y5 l' A: A
cin>>strRelations;
2 G. G: e0 w9 m6 |3 O7 n8 ] }
# B; S7 m! n1 i+ A% H, B # j; U1 C& m5 B S
for (int i=0;i<nSeqLen;i++)
2 h1 H! K/ x/ Q2 R0 U4 O) W0 h {" s! k8 z) o7 o9 q) K1 m
array=new bool[nSeqLen];; b0 X3 O; L$ g6 H- D. H
for (int j=0;j<nSeqLen;j++)1 Y* |$ h6 z- a: s( i ~
array[j]=false;+ v+ ~; @ J0 E$ i" F8 ~
}
# H) ^' i1 \, S" I0 P# n7 b //The main loop/ E) U: X6 P$ g+ w# k' D
for (int i=0;i<nRelNum;i++). T) U) S- ^& ~& o9 m- z
{
& @) m! H1 Y: W6 r# D. \# T char a=strRelations[0];$ y5 S6 X; ], [
char b=strRelations[2];
$ \! y% u: k( a8 J& x) W3 w assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);0 C: ~6 O# e8 O7 G% ]9 F
array[a-'a'][b-'a']=true;
9 ?' g! t( T$ I* c9 Q! \& R' [3 D) o! |3 K' I3 Y* X" u
Marshall(array,nSeqLen);
% X, L7 _$ y; X. w% j5 C) g: f, F9 p& U0 W8 R
//Check for Inconsistency after every relation
. z) ?& u z& O& M for (int m=0;m<nSeqLen;m++)
' Z" u5 W( v" i; i% z4 O {
6 a. ^. l: c6 n( ~0 M if(true==array[m][m])
# r" h: O) {8 s; T: }& } {
; w( V1 X) \9 [9 c: o; u cout<<"Inconsistency found after"<<i+1<<"th relation!"<<endl;5 Z. W$ w0 B6 ?$ B" r/ C# N
delete []strRelations;
' f1 p& T5 u1 @3 Y _, ^- L8 Z7 r o% t for(int k=0;k<nSeqLen;k++)8 h0 I& X- K6 q) S* O1 ^2 O/ C5 v
delete []array[k];
# g1 X+ C. n% T1 k6 A5 Y delete []array;# c& x F6 u4 U! O6 R
delete []Seq;
* S9 y5 [2 J1 \1 y) i3 b% e return 0;) s2 D* @6 O3 ]* A4 V# V
! Z, _8 u9 p2 Q) e: H' ^ \2 s+ i }
% C- |3 z! Y* I4 O- j( a }- m& r6 G2 [4 @ I
- _( v$ i% T9 Y) t: F% F
//Check for the determined sequence after every relation - n! d1 a8 j2 f$ w) y7 N) c" V! t
for (int j=0;j<nSeqLen;j++)! O4 k7 f! f/ a# k4 R9 O& \
{
0 x* w: ?- O. p7 O if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))
8 m" J4 V. b5 K* I1 e& e {) ^) w* y+ p. B6 ?' U v2 H
cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;# B8 `4 F K2 w5 ~7 W5 a3 _- Z
delete []strRelations;
. i0 s. ^4 ]) H( ]" l6 n for(int m=0;m<nSeqLen;m++)1 H9 L" {" {- O
delete []array[m];; t- k: i: b9 x; Q& d0 a
delete []array; }$ U& A% b2 ?1 _1 s
delete []Seq;8 f" x5 [# }6 w }" D
return 0;
j3 k3 h3 q/ M( ~# ^ }3 f4 O$ h$ @9 D; c" a
}
; ^5 p# T& S; p* W, {/ _# q& ]
& Q! }8 k5 H1 X5 P1 }: S) i, f& u% x' p o, D. t% Z
}* T; I5 {- `4 Y( Y+ }
//If the program has come to here ,then the relationship hasn't been determined!!!
# X5 p' x1 t) j+ u cout<<"The relation can not be determined!"<<endl;7 [) a; a/ ?0 f; }3 b# L# G
delete []strRelations;
, Y' ?, R/ J6 H3 x for(int m=0;m<nSeqLen;m++)9 Z8 V7 o$ X( C* \# ~
delete []array[m];
2 v8 m0 |, F" y delete []array; X; C8 i4 z+ L6 f9 T
delete []Seq;
$ B3 @. ^( K( T/ r# n3 G * g' Y* S% Z, i0 k, X9 _ R
return 0;
9 T6 J& d3 k- n9 g5 P- K}
. U+ {7 M Q1 m3 h$ [* N6 l* ?3 r/ e, P4 c$ A! i
程序解题二：#include"stdio.h"" B$ Y$ U5 T& ^. G9 e, l: {+ t
void main(): a* F9 G5 w) R0 @" k
{
8 }; n3 f$ Q, k. ` J* q7 T) l int n_m[100][2];/ D. p: c9 G( k+ d) z
char re[1000][3],
$ ^- V/ s9 u% _3 S: s7 o0 I temp[26];
8 }% n b5 ~1 r& ~ int i=0,j=0;
: K' f/ x( W) ?0 j scanf("%d%d",&n_m[0],&n_m[1]);
$ ]! b" R( f, ^ for( ;j<n_m[1];j++)
0 A5 \3 _ ^% P* S# B9 L scanf("%s",&re[j]);9 h; q" U* R8 n8 a) u5 ~- u9 ~5 q
while(n_m[0]!=0&&n_m[1]!=0)1 N8 N6 ~) u* ^: J
{
2 {, n/ i# }4 V9 [5 m4 N0 ~ i++;
2 i/ n0 f* j) t4 G3 n6 ]! h scanf("%d%d",&n_m[0],&n_m[1]);
- g# J- a% O+ [+ m6 S, e2 z for( int f=0;f<n_m[1];f++,j++)1 a) Z+ p$ t) e! e! t/ _2 k
scanf("%s",&re[j]);
4 j9 c1 D. i* ~ }3 [7 |0 C, l) ~! i O: t& v: f7 R
i=0;* `( N$ ~! |( t/ _. d
j=0;
5 g' f$ o/ @6 T& ^, A6 A for( ;n_m[0]!=0&&n_m[1]!=0;i++)1 _2 ?/ L" {5 R2 k; i! ~0 \
{3 n( n7 A7 W# N3 l
int a=0,b=0,l=1;
+ ?; q3 o% Z/ f6 x l for(a=j;a<j+n_m[1]-1;a++)
0 a9 O3 j0 T" v- k4 R; Y for(b=a+1;b<j+n_m[1];b++)
! b6 f& t; g2 M7 y, ^* M# ^ {0 b' O; ]( y+ j4 d! ~& ^. @) K
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])
2 F4 _/ @: j, @, @" U" ?. K {* _; D9 R! x8 X1 ?" v
l=0;: Q6 w& y9 W J9 x3 R% @+ B8 F- U
printf("Inconsistency found after %d relations.\n",n_m[1]);
2 U9 a" q, w6 ^& B) y! {9 ] break;& J, _6 t- A& u/ V% j7 z
}9 D" l& C' k$ T" G/ {
}: ^! s v1 w* d! e; u4 W
if(l==0) % d( S$ k% U1 a3 T
continue;//Inconsistency found after x relations.
5 \: o. {1 I( r0 W4 h' | else{
$ i+ @; N0 ^& w' g2 C if(n_m[1]<n_m[0]-1)
( _) B+ l( G8 o; s {) T% `2 D& }- C8 P2 J5 }* E7 g
printf("Sorted sequence cannot be determined.\n");
/ R, N5 Y {. j6 D. Q+ _$ P l=0;
9 b T, @2 B6 |$ ^ }
/ s! ~# P1 p% s6 B4 r$ ] else
' ?" N, q2 B1 M {8 ]4 Q6 a1 o* y5 a- s( Z j5 j
if(n_m[1]==n_m[0]-1)( s- B* {6 t/ K- w( C+ P
{
/ p, t" m# i. |0 v8 Z3 E int k=0,p=0;7 F d. [) K/ r% g L# c
for( ;k<n_m[1]-1;k++)
" l4 |# V6 Z. @. K for(p=k+1;p<n_m[1];p++)5 K6 w7 _4 v4 R+ M l6 L
if(re[0]==re[0]||re[2]==re[2])
1 t" X; G( [9 o: H* M P/ _ {5 B$ a. ]3 T4 |
printf("Sorted sequence cannot be determined.\n");) `9 y& c% s4 Y, }) z3 k) ` J
break;, r; N" j7 S* h' E3 ~6 s% m
l=0;+ M1 n, ~& |, `
}( e7 o5 q6 |& v4 \
}
' F( k y9 \" m% x }/ {% e# {8 Z# `% b
if(l==0)
8 S' w; I' V: }% n0 W- ~3 s continue;//Sorted sequence cannot be determined.
1 d$ r" k6 ~: q) z; K B
) m* B4 I# Z+ S1 w7 q2 n else4 l! I4 B$ Y8 i2 s; W _
{/ e7 A; X& U: N) {" C ?
" o( c: \+ L9 `2 n& q% l for(int k=0;k<n_m[0];k++)
, ~; R" V# r* Q1 H- D) Y temp[k]=k+65;
6 V9 l0 g, i. c for(k=0;k<n_m[1];k++,j++)
% u1 q4 s/ B) X8 q/ m9 a) Z4 S {
7 I$ @. h, O0 i' |1 x int t1=0,t2=0;
# n: `) o7 m; G+ N+ ?) m5 { for(int s=0;s<n_m[0];s++)! L& I1 Q( ?! x, O+ U) S
{2 v6 O' r( u7 p% z- C; E7 i
if(temp==re[0])) W. l4 U7 `( f. z& ?* _, M- C
t1=s;
2 }: M: r+ Y/ A9 { if(temp==re[2])( \: z! I; }" e0 B
t2=s;
" F+ Z; R/ |' X( u+ J }
5 c h3 p- I& r; L/ L/ m4 e i% w if((t1>t2)&&re[1]=='<')) p' H/ {) H2 v8 T1 ~
{2 J$ A1 k* a; ?; Q; z$ I4 w
char t3=temp[t1];
( w: h, S8 n( x+ \1 j9 F/ u9 U temp[t1]=temp[t2]; J4 C4 v8 f: Q, L1 p/ Y; [. u
temp[t2]=t3;
8 s0 F$ J8 }4 Q, t% v: _ }8 {" X4 b# t5 W8 V" J. P# q9 ] y
}( |8 A* I0 Y9 \$ r5 [( W3 |3 i
int count=0;, ^+ f8 T b' l- h6 H7 Y
for(int s=0;s<n_m[0]-1;s++)
/ w: Q4 O }+ [; |5 f# d* t2 S for(int d=j-n_m[1];d<j;d++)
* [0 B6 v# i9 I' o if(re[d][0]==temp&&re[d][2]==temp[s+1])4 L/ b# y) y- p
{
0 E1 H0 ]$ T9 W4 I7 Y" L3 `& E6 r; v2 d count++;/ Q, f8 T1 ^" U5 z# g- C
break;$ @( T7 k( c! `/ h9 I4 p: o5 ?
}( x8 D, _' A" H' g; a, V
if(count==n_m[0]-1)
# \) V5 @. f! O& v9 }6 E {/ F4 W1 k, m _5 b( W
printf("Sorted sequence determined after %d relations:",n_m[1]);6 a# U* y; M! W0 M' G
for(int f=0;f<n_m[0];f++)7 V$ n* }% x1 u7 H" W7 G
printf("%c",temp[f]);' Q; @/ N& O" \/ [, a
printf("\n");: Q3 I. ] ~, D* T
}
6 \! Y& K- z$ ]+ { else; t. r) g f; g* M, m: a" f5 I9 n
printf("Sorted sequence cannot be determined.\n");
! e. M0 |5 J- S8 M8 O4 d+ G) P }
8 w7 b1 }7 o5 U/ \ }6 p+ X1 Z* q& s, z! g% U! a
}
3 e3 ^7 P$ X. B1 N/ J}( ^" S! H! i2 K8 L+ r
6 B1 R: J% A b9 H# I% s) l
: @9 H! ?$ U( D7 K& Q) b, f
, o/ d* y7 [* m m
$ Z- B8 I; q- o) }4 }
. n) [; X. ?1 R9 W7 j8 G" F1 L% X8 O- B; M
1 _6 c) e& e& f. M- ]+ c% W0 m
N% v, u; n- a1 ]% R& l来源：编程爱好者acm题库 |
IP卡
狗仔卡
发表于 2010-5-6 18:35
转播
淘帖
分享
收藏
支持
反对
微信
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
显身卡
