Run Length EncodingDescription P0 X6 L, l& |, X4 o
3 @ J- b, R0 `( E: ^4 [
Your task is to write a program that performs a ** form of run-length encoding, as described by the rules below. ) ^: y# T- S9 z8 P" O i+ e ' a/ w! I# U! E4 t2 B5 f. a) hAny 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. v6 ^% o8 B2 c$ b+ g, ]
8 f1 n2 C3 N/ [# f3 c5 B) x
Any 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 - u, o2 }# g8 b1 E* J9 C
sequence, it is escaped with a 1, thus two 1 characters are output. ; U( E: T5 B! Q" @- i+ H1 M
5 s8 T& |4 C9 f) T
Input 7 _! M% O; b1 j+ S P7 o3 U
! }8 j( D+ p7 g: R8 [( e$ k
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. $ s% I+ W' h% S1 c% [) _
G4 E" a! S' v7 }% [! t0 `7 n
Output . D" [! s1 V- _% n+ u9 _+ i: s* w/ y2 G+ `
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. * c4 r! E5 ^- m# g7 S+ n2 O( w: M$ [
* Y0 A( A! g0 D% o( l4 a! O输入样例
: m3 p+ J* B. c4 E2 ^
AAAAAABCCCC' a5 d' _7 a8 y( q+ s* r
12344 * R( T9 x- N0 ]0 H! {
A( z; Z; y; P : q$ [# t5 A0 k0 |9 u& |, N输出样例
0 H4 ~; y* O0 M: A3 J
6A1B14C6 V- R* a' T" d7 S" W9 Y O; o
11123124+ K/ j Z+ ]. k" R$ K$ {
4 q( S7 }6 Z' x. q/ h" g( X$ K! f9 G8 ~
1 |4 q/ B0 q8 ]* U% N5 xSource ! J, @7 y' S8 c5 e- q& ?8 V' h' y# ~! L2 y- a7 y
Ulm Local 2004 ! h- L' v9 K& R6 q( K1 L* K; k) r) }& h4 F" V2 Q
example1:, n/ `$ X3 a* n2 T
#include<stdio.h> ' g, E' y7 |4 V; i8 F! w#include<string.h> 8 R) H+ z2 t0 a9 ~- ], rvoid main() * d, y- O! f1 Z# ^{ int i,j,k,n;1 I4 y9 I, `! u& z/ p2 r
char a[50]; y$ X$ c+ a* L gets(a);+ T' D, S/ A. t$ k1 y0 r
n=strlen(a); ! K3 s) h) I7 t3 r* I2 y0 P& j' Y7 B: d
for(i=0;i<n-1; ) 4 _) s# c; y( {/ Y if(a==a[i+1])9 E1 ^) M* j! E" A4 s+ C5 o5 T+ E
{ for(j=i+1;a[j]==a[j+1];j++);1 ^1 [' U! M, t% C! P
printf("%d%c",j-i+1,a); 6 k3 g) k B$ t4 L i=j+1;, R) L; l& e c
}# `' t0 d3 Y- K# O% |) Y8 |
else2 M! [( K$ F( h" S6 }
{ if(a==1) 6 [+ M" O0 ~. s: R8 y6 K, Y1 w3 E { printf("11"); 4 t N. ^( F5 i- J O i++;/ q5 o3 l& K; p" k: \: F7 `: }
} / u0 G$ P/ j# V6 M- R$ l$ K6 ] else- C% k: r9 q8 L$ q+ p# H
{ for(j=i+1;a[j]!=a[j+1];j++);# r: H' T1 E8 v* d1 u4 M6 j J
printf("1"); 6 J3 @& D1 H1 i1 y! h if(j==n+1) * e+ }3 a- @3 |" j j--;+ u8 j% b0 ]2 |8 B
for(k=i;k<j;k++)! w6 r n8 M i2 u- P4 I" t6 ?/ S
printf("%c",a[k]);1 s- a: b. p6 x1 G* P" }5 T) T0 a
printf("1");+ c3 h" [' n- P7 m ~ p
i=j;. W4 f q2 ]( e! w0 E u
} 6 b1 |& G9 }1 o1 x } 2 l. |/ i1 U8 c) L7 C# e if(n==1) 9 u' w z- l3 a+ @1 w- n/ ?% l% ? if(a[0]=='1')* U/ J% b; X! `; w0 ?2 _
printf("11");. H1 {, v, I+ s
else % Z; z0 X" ?/ f5 ?2 x5 t) O4 H printf("1%c1",a[0]); 3 s% {3 w' B2 `; F; c) l printf("\n"); ' x: N% [. y# e } 0 p1 u; X+ q6 ]评论人: Colby 发布时间: 2010-3-2 12:04:06 #include<stdio.h>% k; Q; X6 {+ W/ n- t
#include<string.h> 0 | a$ `6 l P, e0 `% F% Z0 kvoid main()9 i1 a3 e0 W4 m* l o4 j7 h! P
{ int i,j,k,n; 9 P% l9 L4 k9 q8 v+ z8 X, R7 ~ char a[50];, n" Y1 @$ }5 m+ M5 O3 E0 G% B
gets(a);' b& T* z$ E" g3 p0 w9 D+ F6 [7 `5 G
n=strlen(a);0 v3 s, R( j) i4 {; t6 E# s/ j0 A
4 o% ~+ c8 _3 j$ r y for(i=0;i<n-1; ) 0 L" h+ T8 H* L% {2 k2 p5 s/ l$ t if(a==a[i+1]) $ W1 {8 |/ {8 ]" S { for(j=i+1;a[j]==a[j+1];j++); , |& u8 V- u' c/ ^1 [7 n3 O- ~ printf("%d%c",j-i+1,a);0 Y* S5 a; O: v9 G3 _- O
i=j+1; + A+ i- [" U' m) y }: U9 F" E. A& `8 c
else 0 h5 }8 P9 x; {; g. r { if(a==1) p: z8 Z8 S; k; D2 p { printf("11"); : T( v+ q9 ?: |/ ]# H5 Z i++; 3 \" F. i( i% u. e; L, k } * S& r! Z/ b! {; D9 `0 X7 F else + j4 z6 _0 p! @6 n; V6 g' c { for(j=i+1;a[j]!=a[j+1];j++); 8 a& ^& U% @6 |( @ printf("1"); # A! `3 K. o, k& f2 h if(j==n+1) & @5 d) K7 v0 W* t j--; + [# E" t% n7 L1 p* N+ u for(k=i;k<j;k++) $ v( f; F. I- g/ i. z% r printf("%c",a[k]); ' x' v) I, H t+ ?9 Y* ^1 O printf("1"); 6 c8 E7 B- z8 b2 L8 U( c i=j;9 d2 c0 Z# c: e* k. t5 a+ F
} 6 u# O, h9 Z9 q. { }# q3 f8 d+ [3 Y1 l
if(n==1)* \3 H8 e! N. i( J6 d2 y' n
if(a[0]=='1') e8 ~+ b; m4 z/ g, V
printf("11");3 R5 W4 a1 s: F/ G
else * p8 h) N6 Q9 X& K printf("1%c1",a[0]); ' Y3 [( b0 Y1 ~4 A# G printf("\n");/ b1 J2 P" t# e! t
} example2:#include<stdio.h>2 y7 j8 X/ z" h
#include<string.h>. \" m! U9 q0 ]2 \) g$ T, ~1 r1 t3 p3 x
void main() 6 Y# p5 B/ _5 Z{ int i,j,k,n;- s0 q! \# ], }* T6 Y# L
char a[50]; + l) ^* l6 x/ g0 q; E5 k gets(a);3 g% k: T" o t+ q# V& e+ r/ R
n=strlen(a);! c: C, @* G3 V8 D; x: s3 C! b
4 n7 Q H# ~ r9 Y) K
for(i=0;i<n-1; )% [) h. r0 \* n
if(a==a[i+1]) 2 w: N; G8 l0 s2 w0 K9 Y! s { for(j=i+1;a[j]==a[j+1];j++); : m+ t G# q7 f" T# w printf("%d%c",j-i+1,a);& Z" m7 d! s; E3 a$ \3 \
i=j+1; , q! }6 d* T9 e9 l4 M: E }9 _' ~! ~* d+ C6 R: c
else/ C4 n2 L( g7 b, F1 p8 C) K- W
{ if(a==1)# W2 u& A6 V5 C4 V5 N/ j
{ printf("11"); 5 c m6 c2 H% z7 R3 n1 x" A$ M4 H i++;1 h0 r. K+ i) K& t. V
} ! D, X$ u2 l: z4 T+ ~: @ else ' |- h1 a! {. m' z6 m" L" ] { for(j=i+1;a[j]!=a[j+1];j++); , V, H, X v8 Q9 X, S printf("1"); / v; _, b2 h. U9 Q6 C4 l if(j==n+1) & }4 l2 N. J! l0 Z! _9 J% \3 I: c) Z j--; : K u: [+ G4 J6 k( i for(k=i;k<j;k++)$ l) L4 y* S9 c* S4 c3 B7 ^2 p6 P
printf("%c",a[k]);& \$ ~0 l. w/ J) A# e! f
printf("1");8 ^# q* X3 D' T# U* [# p% v* M0 S
i=j;# x0 j4 j! n/ v& j- H2 v% v
} 2 K% H' `7 o; ` }; x+ O- d& z$ Y
if(n==1) * Z6 H. |7 \! c1 U if(a[0]=='1')& r4 @2 Y% _# U2 Z: c: J
printf("11"); * \$ ?, L& c& Q' u5 i f7 x$ S else0 }/ K m% ^2 Y6 }4 D- x
printf("1%c1",a[0]);; Z+ T6 d/ C0 k9 C$ D7 p
printf("\n"); G' O$ F+ L$ L0 ~9 M1 l } 7 P+ _, v' F2 |. y example3:#include<stdio.h> ~1 c: [1 B# K1 y' j( b#include<string.h> / K* z9 L% `+ G. M; c, d4 r& z3 M0 Vvoid main() / _+ b7 {# M$ }{ int i,j,k,n; ! O* T' c/ I% b# X f, p A8 B" d char a[50];8 Q# R% `1 g. `- x5 r
gets(a);! _; a+ s: [( U
n=strlen(a); ! d% o+ \) i7 [- ?0 ^1 Z6 ^8 I# W& z6 W* v x5 j" S! V5 w2 s1 G
for(i=0;i<n-1; )% n2 D, \) I5 g' J; m [
if(a==a[i+1]) * X" y+ x7 i2 ~8 e { for(j=i+1;a[j]==a[j+1];j++);+ R# H5 @. g8 m7 X8 f0 A: j1 b7 }
printf("%d%c",j-i+1,a); ) n( w- h/ w/ D) Z, J7 @ a, I& M i=j+1;; N) y+ y; j/ g/ Y2 c+ Q
}# @ D# Y O6 I! B
else ) `- b U/ t X- n+ @" u0 { { if(a==1) ! P$ s$ h& o! i7 N { printf("11"); . T5 ?( o* L% O% L' x7 p1 T( Q i++;) I' E$ `8 v- A+ m5 W1 n# B- b
}2 S* F+ `6 q" |% r
else 0 {( R6 J: u, M) \ { for(j=i+1;a[j]!=a[j+1];j++); 5 Q4 v1 B- c, q. u+ Q! l7 |: x printf("1"); ( @+ L) \( g/ e" C7 J( ~; A if(j==n+1) 0 _, _0 ?7 z, n0 v9 F j--; 2 N( o4 d8 D# @! ^3 I for(k=i;k<j;k++) 0 Q& T8 |6 ]3 X5 A% U printf("%c",a[k]);: Z7 B& E6 u$ {( A1 I8 @
printf("1"); 3 X; t0 X0 ~! E: [) | i=j; : e, ~* ] C( y" p; _ } 0 q; V+ E, |/ I' B$ v } t% n9 T( f) C1 x8 _3 @ if(n==1) b5 i e6 k9 M# l! q
if(a[0]=='1') 5 }3 U2 E7 v6 x# w printf("11");; \+ j! ~9 W/ v/ K1 V
else. f) E3 Y# E3 o; L* [' _
printf("1%c1",a[0]);. J- W0 b5 o6 m1 q$ M5 D, s; S
printf("\n"); F I- Y% S G, w% F) t
} 1 o" p+ |2 Y4 l7 z) Q 来源：编程爱好者acm题库
IP卡
狗仔卡
发表于 2010-5-6 18:38
转播
淘帖
分享
收藏
支持
反对
微信
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
显身卡
发表于 2010-5-15 17:58
