Run Length EncodingDescription # {0 P. m: H# N# U0 b, I + z% V8 S7 K; M' zYour task is to write a program that performs a ** form of run-length encoding, as described by the rules below. % S9 R& H6 r+ E! y4 z1 o3 U% A
, K' H4 D3 k" T/ P# Q& V' z$ I0 x8 Z
Any sequence of between 2 to 9 identical characters is encoded by two characters. The first character is the length of the sequence, represented by one of the characters 2 through 9. The second character is the value of the repeated character. A sequence of more than 9 identical characters is dealt with by first encoding 9 characters, then the remaining ones. 9 C% b5 v# o" P/ m B0 k, h+ ~* \/ c5 y& ^7 zAny sequence of characters that does not contain consecutive repetitions of any characters is represented by a 1 character followed by the sequence of characters, terminated with another 1. If a 1 appears as part of the ' N5 S: R) q9 e6 {& xsequence, it is escaped with a 1, thus two 1 characters are output. % y. d5 K0 O" f, c! }& h' \; {" b7 b0 \2 g
Input - F* R) { M3 H+ m1 l& R
& ^# Z* U# a- p8 c! v- V
The input consists of letters (both upper- and lower-case), digits, spaces, and punctuation. Every line is terminated with a newline character and no other characters appear in the input. & E) D; Q+ c. S0 ^0 h, X8 s2 o- ^! Q/ o* `
Output m- I3 O. ~6 n3 T, N/ I# u8 a3 d- x3 `( c+ ?0 J; x; M i
Each line in the input is encoded separately as described above. The newline at the end of each line is not encoded, but is passed directly to the output. 2 X m( O5 h6 S, M( _8 `' @" z! ?; h- W 输入样例
: u8 ?4 ?: X2 l# H9 I0 e( yAAAAAABCCCC6 p/ f8 d% H& v0 D+ e
123446 ?- `1 ^* B3 c. w; c
# n3 Y1 {+ O$ ^# X0 Z7 W; N6 m$ I / ?' z. h* I) B输出样例
# ^# N. S* C* ]7 F
6A1B14C 0 Q/ k8 _7 L' ^4 i& R3 r$ I) E- z2 `111231247 Z% T4 y; }$ f' i* G t' j1 K1 l4 b7 q
1 s2 I) S/ y9 X% ?
) B( d7 @$ w+ K; K- U1 K+ CSource / Q* E* g- W# D$ h9 j& \' v' s/ z! c6 G/ c- \6 s6 @. C. z
Ulm Local 20044 V5 l: @$ E6 K: e5 {+ f! i9 h: g
" M& D5 N! G) T% O8 k( S* s
example1:" f. I2 u7 R* ]! Q
#include<stdio.h> / p; n1 k! n( y9 ]. W$ O#include<string.h> : c% B3 Z5 j0 P9 M& O! n8 }void main()$ t* | a% a* W7 v' d
{ int i,j,k,n;; n9 _# X E' M2 t
char a[50];: `. X" T" C+ K$ F. B& T
gets(a);# S8 v' r5 m3 b' {$ b8 Y
n=strlen(a); * `8 {* l# c% t6 C5 D; B; S) c2 n, d8 m: x
for(i=0;i<n-1; ) l1 d6 Q! Z8 Q3 } \
if(a==a[i+1]) ' A$ c0 ]0 Y5 e+ ^ { for(j=i+1;a[j]==a[j+1];j++); 9 T1 ^0 P. q$ m' y% G5 M2 W+ {3 R% U printf("%d%c",j-i+1,a);- d; G3 U8 `/ [' G- w% w
i=j+1; & n1 [$ `9 w" Z: G' w& j }2 q. F' T' m2 W @
else3 E& @% H: H3 F
{ if(a==1) ; A% ?- o( I/ u/ A' |+ Y# { { printf("11");; g8 M# ~$ s7 M
i++;- p" }5 k4 \, @! D4 E( s
}4 ~4 O; D+ P! y0 x5 j9 O
else0 R: m6 b% C$ | a+ y5 }
{ for(j=i+1;a[j]!=a[j+1];j++);% z2 k8 x: G! F: m. ^
printf("1"); , ?# F3 U: |2 N; R if(j==n+1) 7 u% e5 l) D* K7 j- K/ a j--;% p0 @7 h9 y$ w- p4 P
for(k=i;k<j;k++)( `7 r/ v9 W7 u1 c7 z! D& ]+ S9 t
printf("%c",a[k]);$ @: i G0 s* a
printf("1"); $ k0 E: P, K, V! w& C' ^3 C i=j;2 ?; m' L% G7 G" V6 @+ B
}! y/ O: X Y9 s6 M+ Q
}9 Z* x; z. ^* H7 r
if(n==1) # v" v/ j0 T4 G if(a[0]=='1')! H# a' O+ K6 I0 g; M
printf("11"); + n2 ~% ^4 n* v3 u6 @4 n else 6 l. m- k8 @0 N" Z5 v printf("1%c1",a[0]);6 b1 E0 O. T8 i5 n; `& P5 l
printf("\n");4 H! R- t% ^0 i. t& m6 a! f& |6 j
} 2 i0 j# E( t0 A评论人: Colby 发布时间: 2010-3-2 12:04:06 #include<stdio.h>: j. d# n1 W ?' p: B4 k; w
#include<string.h> + }2 B+ N7 {, ~void main() 4 f, w! \" \( F1 c, G5 Z$ {{ int i,j,k,n;! V$ I3 z6 g9 u# ]9 O
char a[50];/ s' P6 O' \( y& W2 I' V
gets(a);) }: }1 r, E F ?, u
n=strlen(a); % H5 M7 ?* u% i$ g! P" ]5 C4 o( ]" |# M1 K" L9 C! T3 r
for(i=0;i<n-1; )& a) [ B! F: F9 \$ z. M8 E) t. P
if(a==a[i+1])) N/ J- g( P% T! Y; d
{ for(j=i+1;a[j]==a[j+1];j++); # n, U7 c, p- u, K' d. O printf("%d%c",j-i+1,a);1 Q" r2 h) n' b
i=j+1;0 a& l0 w9 c! \# v+ K, K" h: U( y
} % i' B, ~3 k4 T+ { {! r! P else ; U" p9 j% o3 n$ m ` { if(a==1) 5 w* P" c/ J3 r' ~" p { printf("11"); 1 S, V) d/ a: }6 f3 z- | i++;2 K: x |, q! L9 B7 Z
}6 A- m" K6 {5 n) |) d
else ( o: x/ [; b3 p/ [& y { for(j=i+1;a[j]!=a[j+1];j++); $ C: P K$ B3 v printf("1"); 7 u. n: l! v0 |3 C6 P if(j==n+1) 3 I9 b, g$ h1 p; J1 _3 [ j--;) F2 ~ D0 e% i) _ K
for(k=i;k<j;k++) + T& \, x/ J' ]6 g0 W6 N printf("%c",a[k]);7 v7 y2 Q U: E2 J- y% a
printf("1"); , |6 i0 K3 G E' N3 Y$ V i=j; 7 X' X& d8 t; N" {3 |9 y) T6 P }/ J, g8 ~ }$ K: F: F) }( J
} . o# _; a* J: F, Z$ c if(n==1) s* d4 w6 _2 U
if(a[0]=='1'); ?4 w; ^! T, ^1 ?/ x( g
printf("11"); 8 _$ g3 C `1 Y else0 J& p6 H0 J9 J* V
printf("1%c1",a[0]);$ X/ H0 T" \2 C3 p1 p- }2 e
printf("\n");( e4 V/ w# g. h* z) U( i1 I, y, ?
} example2:#include<stdio.h> / `) C0 f5 {/ T: X* h# n+ x. U#include<string.h>8 P2 W5 G* [; y' _+ I
void main() ; `& [8 M8 J% X3 ?, F a2 `{ int i,j,k,n; * _4 Z# t2 \$ k+ J char a[50];$ V% n# o2 `; d: N) Z/ x
gets(a);2 x. d) D5 Y4 h8 U/ }, d9 `
n=strlen(a);& e+ v5 M( H6 C' {! r0 e/ s
6 D( ]: j; C; G7 k6 H
for(i=0;i<n-1; ) * G# E$ ] R3 C3 Y% y; h if(a==a[i+1]) . u% t4 T8 \4 _+ F { for(j=i+1;a[j]==a[j+1];j++);4 z7 b6 U9 Q% i6 C9 o2 m0 J9 w
printf("%d%c",j-i+1,a); & |% }* S$ P, @ i=j+1; , a* @7 K! g2 x& v3 N' Z }5 [8 _, Y2 ? Z6 ~1 j* S0 z
else 7 A3 ~9 a# t7 @) M A3 k { if(a==1)3 Y |1 x) l$ ?4 E$ H4 v
{ printf("11"); + U, Q; N" p/ ?. V) R, E [ i++;# ?2 X+ w C2 Z4 u5 w& h+ k
}5 B9 C6 H( G( }; V9 U/ b M% m
else 8 i* {& s. s6 ]7 f; N* J1 Z$ R% { { for(j=i+1;a[j]!=a[j+1];j++);) H2 D) r7 K0 q2 t3 e ?
printf("1");5 _, O0 }: [. R, s
if(j==n+1)( S( v) b2 x0 N
j--;' Y7 i+ k. f9 O+ V$ Z9 ?0 X
for(k=i;k<j;k++). L1 @! q1 J6 E1 A
printf("%c",a[k]); ) }* h2 ^! i. K printf("1"); + f' E/ k2 A( K$ j i=j;" X6 O+ Z- ~% c4 u9 J& v' @. ^" K
}$ e. S6 |. i/ v- Q! V, Z
} + L0 Q% [- I: l- a/ G9 x if(n==1)0 B3 y, x0 X' V( {
if(a[0]=='1') - ^; R5 V& h5 t( l printf("11"); & m" d" H7 o7 O% d0 k else P2 R/ _& _) C! H# [
printf("1%c1",a[0]); $ P0 q; H, y% v) _9 B& r9 U printf("\n"); 5 a. @6 r- o* A8 U, P2 T4 h/ ] } & U; q. X8 H( ^) b4 F1 w4 k0 c6 C example3:#include<stdio.h> " A% @; ?5 H8 r1 X2 s#include<string.h>6 l5 c2 p9 u9 V$ s
void main()' K5 v* f3 ~5 v$ c6 w* l& Y
{ int i,j,k,n; `7 u& A. {' q
char a[50]; 5 Y9 t* q6 ]1 g0 x! S gets(a); ' K$ Z+ P* E: ~/ L# W1 N& h; X2 ? n=strlen(a); ( |6 k: S+ T' F4 T g3 j& T5 x8 [$ {( W
for(i=0;i<n-1; ) . c' Y( [ G- I5 Z if(a==a[i+1]) S: }5 c4 D! B/ O/ ~
{ for(j=i+1;a[j]==a[j+1];j++);' m1 ~, l, s4 _; I6 ~( C
printf("%d%c",j-i+1,a); / b/ X8 K& F% m! h+ K, E i=j+1; $ w7 d7 E* c6 i# A } , r. c# Z1 V2 G3 r7 \ else4 R! k( _# H& E. V
{ if(a==1) - Z3 J7 v: x1 G) A h- W { printf("11");, I0 \" a+ [, _
i++;4 m5 s' Q: ^3 j! `, ?
} , U+ Q0 f( b+ p/ N) m* f3 h else9 b8 |6 }8 o" F% O" {1 b2 F4 S5 N
{ for(j=i+1;a[j]!=a[j+1];j++); + L& k- d3 F# S% w' d2 ?7 h1 U printf("1");( a6 t4 G/ T7 v3 P: z9 C2 E
if(j==n+1) " R: d: k3 J, E! w j--; # {$ p" H1 \3 n5 w1 S& I. z6 n8 i! q for(k=i;k<j;k++)) z/ s7 U& ]" d9 T! J' Q
printf("%c",a[k]); . y7 }; z. V8 d2 ?8 Z7 L printf("1");/ d+ ^% y/ P8 D& s t7 O( Q
i=j; }4 x$ S X2 Q5 j
}3 s: w) A6 K$ u0 @8 `! X
} v1 o) T# o/ @. _( V M/ K if(n==1) ' X! ^4 s4 P% S& k ~' q if(a[0]=='1')" c( ?. F! y8 o/ f- f: t0 n3 [
printf("11");) \. T+ f; f7 x
else5 ]) c0 C! h+ j& j. X5 m
printf("1%c1",a[0]);8 h) @* D* E+ G3 N4 \5 i* T
printf("\n");# m+ Q8 k3 N# `- w
} $ C; _; \1 W! I( c* Q5 M h3 m 来源：编程爱好者acm题库
IP卡
狗仔卡
发表于 2010-5-6 18:38
转播
淘帖
分享
收藏
支持
反对
微信
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
显身卡
发表于 2010-5-15 17:58
