本帖最后由 厚积薄发 于 2010-5-6 18:40 编辑
+ o4 P) T/ V, S- K! Q0 W8 Z8 h( n' k
Sorting It All OutDescription2 j6 ]5 y8 u& N- T" H
4 l3 J5 W' w. {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. : v2 {4 a A4 v0 O) N! x) Z% i
Input
9 X+ I4 i4 P( r5 S& n2 _" v+ Y( ?8 g7 t9 D1 S! i
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.
9 I: x$ E3 _' _6 K0 b! L7 z: m: U ?, UOutput2 P4 a8 @7 ^' ~" Y/ r
* o3 l- e8 f4 |, UFor each problem instance, output consists of one line. This line should be one of the following three:
- a" g! Q: e) f6 h/ h# X
; P% N0 N) x8 V8 k7 u2 ISorted sequence determined after ** relations: yyy...y.
+ A* ?1 E+ V8 y2 x2 W- p! \( CSorted sequence cannot be determined.
2 O" M1 N# a% j$ T4 `& YInconsistency found after ** relations.
3 I6 |- T* U- u. M3 `
2 H) x6 \; k0 Q6 Swhere ** 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 t0 n, `3 ?: \& Q r6 k! K2 {6 p" E; t2 v, U6 [& v
输入样例
5 W. Y! i" R7 h1 |) `4 Y4 6
3 p: \" ^8 `* e! j0 U0 s# D+ CA<B9 U% k/ j" A I" h
A<C1 ?( S3 n& t! H% `0 B0 r k8 o
B<C
3 Q; l6 V- o9 E, J6 l& fC<D$ ~* R# d0 W2 J9 [8 |0 b0 u
B<D
1 |8 ]* X. w2 ?A<B' N, U4 y ]1 [+ N7 M3 W
3 2
8 J* H' o: p0 T/ c, QA<B
V5 m& T2 Q- ` R( e& L4 O8 cB<A
" _/ a- K! Q/ h) ]' V/ D26 18 ?/ N% \3 Z+ h( `' ?: R
A<Z
* \8 \* e6 J5 p" r0 f; y$ _( L0 0. O8 y# e8 b( z: K5 J
; ]% [% V8 Y @1 H" C/ X; R% e" J
输出样例 7 F& Y5 g" l) u1 u' @# m
Sorted sequence determined after 4 relations: ABCD.
) t( [" |: l* NInconsistency found after 2 relations./ W$ l7 ]& a$ |5 C7 @% P
Sorted sequence cannot be determined.
" X" j5 D! u% R8 _6 KSource* P, E; C6 d8 `# g
, z9 x9 Q* v, x# Z! o4 Z
East Central North America 2001 7 P0 E3 T. e( N: e1 J
程序解题1：
, }0 K1 X0 j; K9 o7 f$ K. O/ i//By Jackie Cheung
% n) O8 r. B( {3 d$ \: N#include <iostream>5 k3 K! D3 H- i D8 B3 ~) l$ w
#include <string>
+ M, l9 v6 B5 l% I: k/ {& |" S#include <cassert>
3 {) }- ]7 I Itypedef struct tagNODE ) Y7 [% d1 b2 C5 W" d8 c
{
1 T' [( `* y# R I1 ] char val;
; i9 Y* H4 l6 L1 z+ n; U( R struct tagNODE* link;- d6 q& }( k' |5 K! |2 t6 |' Y5 _
}NODE;# z% V: h% O) G- ^* T
using namespace std;
9 \% q: J. I# ~% Q+ l8 c9 I: _void Marshall(bool** arrary,int n)
7 J) i Z+ G& |! t0 }- V{
% z$ K. a3 V4 {" z$ Y for(int i=0;i<n;i++)7 Q- a0 L1 d* r# p
{+ ]$ O7 D, s% P+ y$ P
for (int j=0;j<n;j++)* `( h8 \2 d* o0 X3 A( a0 {
{1 L# ^* O8 T/ ^6 P
if(true==arrary[j])& i5 A. \6 m+ P) N0 z, K+ @
for (int k=0;k<n;k++)8 H m" @5 v! T7 r9 G: k
{
2 I7 M' E: \! y4 J' x. r arrary[j][k]=arrary[j][k] || arrary[k];
+ k- m9 K6 `9 h6 [+ F }
% n* Y8 r6 l- H5 ~% T0 S _ }7 L$ p) C4 |" }: X5 x! S7 W3 S
}
( |% V5 `% ~4 b8 Q* o Y% f};+ g# R6 b; e, y& L
bool SearchForRoute(bool** array,char Seq[],int nLeft,int nIndex,const int n)$ G6 o; K3 k4 M
{/ F8 ?5 p" J m: P( b3 O, D
Seq[n-nLeft]=static_cast<char>('a'+nIndex);9 D% ?* ]" T+ F& F
bool bFlag=false;/ E( W9 `- s: l- c
if(1==nLeft)% r/ t4 \' f# ?1 v) Y( ?
{
1 e) n1 b0 J& g% M4 d Seq[n]='\0';8 y1 Y# I# i1 V$ _8 z; K; `% v& M
return true;2 z( @+ S& ~ {( S4 }) ^8 C2 X7 ^* Z
}
( I, n- W8 n m2 f0 N; g for (int i=0;i<n;i++)& u, N" b6 w5 Z7 }+ K- k
{
7 V) I& _" q7 Q/ ^6 ]* X8 s9 u if(true==array[nIndex])% Y- }) h4 _! g2 K3 B% |9 A5 V
{
' m: L) e# W3 K0 N( U- L # l9 F4 \1 z/ x
bFlag=SearchForRoute(array,Seq,nLeft-1,i,n);& E6 o. A# g k9 E1 W
}
9 {2 m" v! F5 h$ A+ ? if(true==bFlag)
5 `0 D- j0 e. l+ \4 x+ b6 x return true;
, G) C- [3 \! k1 g+ G h- m% s }4 S. A5 ?! C: O; j) |, Q6 z
return false;5 v- c1 U M" f7 s
};& O: M. i/ @4 O% \7 a5 U, Z
int main()
4 [3 T$ a2 y9 n; {1 [, f{* c8 ^& c7 {! f# a4 m" C# F7 T
int nSeqLen;
` n* Q" z2 t, M1 v( x int nRelNum;
" X2 U' G8 X" H: D2 h+ |( x C7 t cout<<"Input the length of the sequence:"<<endl;
* H- f% B& o3 r( F% i8 S cin>>nSeqLen;
4 M* B0 W' `! P" A* n cout<<"Input the number of relations between the elements:"<<endl;0 C7 m) {! ]: y5 K$ J0 Z1 G; e
cin>>nRelNum;3 k. Z- d% {0 Q7 `# c# E( v
//1:if nRelNum<nSeqLen-1,then the relation can not be determined!" q2 O+ U" p. z1 \
if(nRelNum<nSeqLen-1)
3 j' T# |/ V8 G+ w# W( } {: J0 \7 R" P$ m# n( @: r
cout<<"The relation can not be determined!"<<endl;/ J c; g& ~) ^7 \+ m+ v
return 0;
5 X' p/ N! y. q; z8 \ }" Y) e/ ~3 g8 j8 i" {
string* strRelations=new string[nRelNum];: ~+ V6 i2 j, _ r$ ^
char* Seq=new char[nSeqLen+1];
- y# e) u7 H2 I1 P0 J bool** array=new bool*[nSeqLen];
( P) U5 J8 g- g$ h5 J3 U5 B8 o2 ~- a! u
for(int i=0;i<nRelNum;i++)
$ `2 j6 ~" d" N( ^. y/ ]8 u' B {- s/ e! E, C B+ ~. t5 q
cout<<"Input the "<<i+1<<"th relation:"<<endl;
V, x9 Z& ~' ?9 c* m cin>>strRelations;
' _7 _& H# P U4 N6 k2 i& `) G$ \ }
9 t3 J* Z* r j$ b; p; Y
# H9 B) @' ^ B' w. u5 E8 I for (int i=0;i<nSeqLen;i++)
" Y: P9 T7 V. l: e# ]8 \ {
, x" V0 p9 S, W, d# G) l5 ~+ \$ e array=new bool[nSeqLen];
0 u$ w9 e+ T; ^) D% p for (int j=0;j<nSeqLen;j++)
: m0 y$ h; U; q7 W3 G8 M array[j]=false;8 R% h2 x- W6 h# l: ?6 N# O K' @3 t
}1 c* A2 r$ T0 A. t1 X5 c0 [
//The main loop
4 Q8 L' K) W( l) _# y5 p6 [- D for (int i=0;i<nRelNum;i++)
5 ^0 l0 Z! \6 ?' G4 O1 s {
$ p6 x& y. l; i4 z* y" F char a=strRelations[0];
2 W2 i/ X, S2 G, i Y# F char b=strRelations[2];
& ^* e3 C+ b. A J- _" L; Q assert(a>='a' && a<'a'+nSeqLen && b>='a' && b<'a'+nSeqLen);
" U+ C) |1 @! d2 W" A! J0 B array[a-'a'][b-'a']=true;6 I6 i, @# l( L5 b" h
/ y9 ]# u9 e1 }: y& j Marshall(array,nSeqLen);- u9 |, i3 D: s3 d2 [$ T
I/ N5 ~5 N0 j, d
//Check for Inconsistency after every relation
+ C. z. {( O7 O" F2 ]0 q for (int m=0;m<nSeqLen;m++)( f9 t/ \7 y1 Z' F* J# d
{+ \* q2 t( _$ }7 {4 ^% }
if(true==array[m][m])
" b9 d( N* R' S. e, p {0 }3 M4 o, o/ s# A. }
cout<<"Inconsistency found after"<<i+1<<"th relation!"<<endl;, w' x- y1 C8 y& a
delete []strRelations;
. ?' S& O/ q/ R0 X) O/ d% S; V% ] for(int k=0;k<nSeqLen;k++)' x! P0 v0 j$ n5 u3 ?* S
delete []array[k];8 z# c3 I' f7 ~7 t9 A
delete []array;, Q( B: J. ?! i) {% w$ ?) u& V
delete []Seq;
. M( B# \% X8 ]% q" Y return 0;2 Q3 Q [: t' [1 ?: N6 P
! [7 y1 s0 \7 q% `. I
}+ C* e8 C; a6 P+ ~2 i% ?0 Q
}, Q) A2 h8 @& r, \1 F( O; s
7 m" D( B' ^& E0 w* Y8 R' l! p
//Check for the determined sequence after every relation 6 q& D. _7 r: r' ~4 d0 U5 B
for (int j=0;j<nSeqLen;j++)
4 c6 r3 O7 F6 D; l0 d$ z3 a {5 \4 V% `; G$ X( f" C
if(true==SearchForRoute(array,Seq,nSeqLen,j,nSeqLen))9 v; o# j+ j* T ^# `# a6 J
{) M0 i9 J# w# e$ H
cout<<"Sorted sequence determined after the"<<i+1<< "th relations:"<<Seq<<endl;! j+ J1 f9 R7 Y/ p% u3 `* `) M8 t
delete []strRelations;/ R) e9 J f8 @: Y+ f+ d, P* W1 o
for(int m=0;m<nSeqLen;m++)
; x7 d1 s% J" C delete []array[m];6 H* G6 z! J9 T# \* I; k
delete []array;
8 s5 H5 u1 d5 `& O delete []Seq;0 G( l9 [# I# \5 y4 C# h; v
return 0;
+ m2 p7 B7 s$ N2 Y; V }6 V) T S7 a' C3 \- T8 v' R
}
" w' |+ }: S4 \$ N. n. n3 u+ t/ S2 `% y& I$ }$ H
! e h& Z, }$ F8 Q }
! {7 x2 e, u) n* r; t; b //If the program has come to here ,then the relationship hasn't been determined!!!6 B8 y; O% \# M2 o) z: ]
cout<<"The relation can not be determined!"<<endl;
# k4 f4 ]; W7 f+ g: {0 V! | { delete []strRelations;4 A/ h1 R' j7 S8 `2 u( e% z, g
for(int m=0;m<nSeqLen;m++)! a9 j. _/ E4 s$ c6 p2 N" {
delete []array[m];
z5 I! P- U3 z( b delete []array;
% X) `$ f- S6 I delete []Seq;
7 j% _1 a, K% O" e8 n$ v
: G0 C1 P+ L8 J return 0;
0 Z4 @: z6 w! V K}
! e+ E4 Q7 i& D0 d1 H
/ L& f3 @9 ~- d5 x" v程序解题二：#include"stdio.h"
( K k7 k: I+ g k0 h. Ovoid main()
$ z4 F3 M3 {; p. A4 J1 ~; j{
$ j2 k3 T8 A p int n_m[100][2];, @( U$ f- P9 e5 x' T- v
char re[1000][3],9 q0 S$ D ^8 S
temp[26];* t/ F- l; E: N$ l( E% C% w
int i=0,j=0;
v$ K: M" d0 l4 g0 L2 D' b scanf("%d%d",&n_m[0],&n_m[1]);7 Z6 @5 |/ J# H
for( ;j<n_m[1];j++)
# M# ]: I( b6 k5 D scanf("%s",&re[j]);
; T$ x- Y. x5 h" B0 M8 y while(n_m[0]!=0&&n_m[1]!=0)
" d4 q, d2 o1 ^7 W+ P( N Q {
! X& Q: b, ?) F' H" e& T i++;
, U' j3 i) g, Q& I1 `) ?# m scanf("%d%d",&n_m[0],&n_m[1]);( u7 M% D+ g; f+ t
for( int f=0;f<n_m[1];f++,j++)
5 `6 |( z5 o9 D& _( `- Q& t scanf("%s",&re[j]);
C* R, D! x9 g# b* N4 c }, ?+ L/ w. D1 r5 R- U- S, W' ]
i=0;2 y* G+ D( l+ i) I4 j5 J/ J
j=0;
* o+ t P3 Z5 C+ [ for( ;n_m[0]!=0&&n_m[1]!=0;i++)- U& [# z1 @+ p1 m1 k
{3 r1 ], h& C: ]* {
int a=0,b=0,l=1;
) g! l+ k0 i9 @6 Y: \3 W7 R for(a=j;a<j+n_m[1]-1;a++), o1 ` K/ i5 j, t& g) Z
for(b=a+1;b<j+n_m[1];b++)% |, z- C( f9 ^# ~7 a; U/ s' H, l2 {
{7 N4 U, O/ K! ^" D6 P, i
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])
' X! {% l0 Y" A1 B4 } {
* c7 j% K6 n: N- N$ I% z l=0;
* J. w0 t: ^/ o: F' I: Z# P- O# L printf("Inconsistency found after %d relations.\n",n_m[1]);; C6 ~5 T0 R% H8 [: a; O
break;
1 G% Z. w0 P' H6 B4 g$ Q% d+ C+ e# j5 C! o }' h7 x, @- Q5 K @2 y! d% h
}) p9 g w. `8 S' Q* _
if(l==0) . g2 g7 N. x; a" j5 A* m3 I
continue;//Inconsistency found after x relations./ S7 j6 l5 b0 k+ c* u. T: H+ K
else{* m8 P$ r+ H) H- S5 Y1 H9 D
if(n_m[1]<n_m[0]-1)' X1 S! r' D9 G" l) M
{
! s$ q& ?/ M0 d printf("Sorted sequence cannot be determined.\n"); v6 a `! l" F) h# M9 F7 _
l=0;
$ v7 {: }: g5 E' Y* x6 w) ~ }
1 m+ l- i5 h; w7 i' B else
0 t% m0 Q) a+ C+ T- y8 {. a {/ a4 ]8 I/ o$ A! T9 ~ t2 b: w
if(n_m[1]==n_m[0]-1)
, M3 {( z1 x7 ^7 l! V; a3 D, M { . W% N% H- B+ _
int k=0,p=0;' ]: x" X! |# d3 z4 V) Z; {
for( ;k<n_m[1]-1;k++)7 n& ]1 i7 h# r$ E$ P4 K- [
for(p=k+1;p<n_m[1];p++)
4 H$ n! u, d7 l" j( `; o if(re[0]==re[0]||re[2]==re[2])
# b) e. z+ O3 x: x0 }9 ^( s {& r( O! ~: ^' S) m0 l( ]: E# N: v
printf("Sorted sequence cannot be determined.\n");
( {2 A1 r! M. b break;/ J4 s, v; d# L X9 W+ K9 z6 O
l=0;
, y# ^! ~: S' ?3 T! j }
0 V9 I0 j4 ~0 F! D# ^4 f$ w* P/ ? }
1 j& w% V& J, d; W W6 p }
/ W5 E/ S9 ~1 u8 I& R$ [ if(l==0)
- E4 ^! m1 Z1 i1 @' T0 G: U continue;//Sorted sequence cannot be determined.
* i' I. k& ~, p! U; J+ r. \8 ]6 t- ~: I+ D1 Q
else# F+ }+ h6 T6 Q1 B; V
{% }: R+ v0 P0 d9 G6 w' Y
7 V* i8 Z4 r3 l" m' Z# c7 ? for(int k=0;k<n_m[0];k++)
0 r7 |" G) v( k* N( [* ~ temp[k]=k+65;1 ^- G3 F1 w1 q" i1 G. w
for(k=0;k<n_m[1];k++,j++)
0 _6 F; Z! L1 W4 l {% U' n5 E1 D9 q, u2 C% K
int t1=0,t2=0;
& R" J8 u: h# ~& m: p, F8 d for(int s=0;s<n_m[0];s++)
( L9 F- Q8 @8 L4 {2 k {
7 D. H1 n4 d% t% t- ?) }2 J& ` if(temp==re[0])
. D/ M) X/ a! A t1=s;6 S0 V7 S; w1 [/ g9 Y# w) d. ~
if(temp==re[2])
+ l+ ^' K3 _4 e. n t2=s;; j+ U! S; t( Y& P$ D+ s
}
, r4 C1 y& T* q9 j if((t1>t2)&&re[1]=='<')3 ]8 [8 \2 ^, }, {- y1 r
{
2 j* f* S* f! }, w char t3=temp[t1];' _8 q. C; } q V4 w: P5 w
temp[t1]=temp[t2];) q3 a. P; ^4 E) `6 ]4 I4 O N
temp[t2]=t3;8 p8 E' l- A! R
}
$ ^" |2 M/ ~4 [8 `6 m$ M5 v8 N% ^- [ }
, c4 v. T# z8 T int count=0;: n5 W+ M0 \: F1 v4 B
for(int s=0;s<n_m[0]-1;s++)
7 |0 i/ X1 n- f; Q# w for(int d=j-n_m[1];d<j;d++)# G7 m; x% z2 Y( J0 N9 d8 U8 R* c
if(re[d][0]==temp&&re[d][2]==temp[s+1])0 r, E+ J- ~5 {5 O9 S" T
{0 E9 ]$ R) ~ [8 y
count++;% P3 p0 @7 E" b, k
break;
; T# ?2 |, Y! a; z/ y }
4 {9 C( k6 X7 q if(count==n_m[0]-1)
! R3 _" ]* B7 S0 ?, W* k" f {
# j A& ], M3 ` printf("Sorted sequence determined after %d relations:",n_m[1]);
y; p' g; J# d4 l9 i7 i* T for(int f=0;f<n_m[0];f++)* r9 G" Q4 p# D5 _+ b: P, d6 r
printf("%c",temp[f]);5 A1 F9 D& k7 u% e# q
printf("\n");
- i! g5 M0 E& O; I) P }
" \. r5 b/ e l; l7 v# x else' X& K3 S- R; E. E
printf("Sorted sequence cannot be determined.\n");
8 g8 S8 @% n P5 X+ b: A }5 u3 X9 J1 }5 Q s3 ~3 q: P; \
}2 a5 h5 }- R* L. S8 R6 ~. _4 {
}
4 T9 R8 [4 b3 |0 l}/ [/ O+ W5 ?+ Q0 g/ H
( H1 r. \- Y! r. f3 r
9 ~$ F. e$ F7 y
7 j. Q3 F5 b' Q" B. ~2 v6 L
( O g% Y. O" @; u" C, L7 x6 H2 b$ K6 C! H2 i6 {# M) @
) q0 D y# |8 z' `' L; W' e
' h" M1 a8 C- r. t3 K2 d* e# V7 ?* E6 _3 ~# g8 `
来源：编程爱好者acm题库 |
IP卡
狗仔卡
发表于 2010-5-6 18:35
转播
淘帖
分享
收藏
支持
反对
微信
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
显身卡
