在线时间 5024 小时 最后登录 2022-11-28 注册时间 2009-4-8 听众数 738 收听数 1 能力 23 分 体力 77429 点 威望 96 点 阅读权限 255 积分 27155 相册 1 日志 14 记录 36 帖子 4293 主题 1341 精华 15 分享 16 好友 1975
数学中国总编辑
TA的每日心情 衰 2016-11-18 10:46
签到天数: 206 天
[LV.7]常住居民III
超级版主
群组 : 2011年第一期数学建模
群组 : 第一期sas基础实训课堂
群组 : 第二届数模基础实训
群组 : 2012第二期MCM/ICM优秀
群组 : MCM优秀论文解析专题
Run Length EncodingDescription # t2 a+ }9 d/ v% |
5 s, G; ^/ \: n$ m1 [# a( t8 }
Your task is to write a program that performs a ** form of run-length encoding, as described by the rules below.
J/ Y. m! g1 d% c . C& ?+ O( f5 F# w4 K; b: U: b; L
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.
7 S. `7 e: _1 T8 ?0 W9 N% y" Z 6 @5 N6 M4 s) R! J- o1 l8 M
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
; T3 i B: O( m- r sequence, it is escaped with a 1, thus two 1 characters are output.
2 e, I* S* f( z9 |, h) ^( {( p/ L, H / J" ]6 @0 I% w" y
Input ' j$ s9 m3 K [' @
1 |" h7 T) Y! u1 S, ~3 ?
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. % L8 k2 H5 n+ v: @% R4 x
* f- N" v9 k9 b1 x! X
Output
$ V- H% J5 N' A7 T3 O" w+ c
+ n. I: b. @! a 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. " W/ z: h) E. d0 I
, m. n; K1 B! E( L: r* w 输入样例
" L) P+ { G0 m- L i6 L4 W% y AAAAAABCCCC# @! u. J+ X5 ?# R( R( ~
12344* G# L0 E' \3 d9 D( x5 c
5 y5 }/ I6 i- g2 w* H& D S
0 m" I, a/ g- c/ ` i) s* y/ o% g
输出样例 & r; O+ p( Q7 w
6A1B14C# E& h* o7 z1 X
111231248 t. m+ H/ v' P, _ p) ~
3 b+ m* N9 n: d+ [0 H8 W4 v
* S) n% Y; q" K0 {, C Source+ e7 b: s z+ E& R+ q9 B; [
4 a4 |% c$ T) Z2 Q* o Ulm Local 2004 ~- Z8 C0 \# G" k
N4 @* w$ x1 ]" f; V1 ` example1:
* u1 }* K# T0 z' h: N* L #include<stdio.h>
3 a$ [# ?" v4 K9 `* @- Z #include<string.h>
; z$ J G" q6 K# ^( u8 [ void main()
] u- ]+ P4 l: A; D% B" C! G { int i,j,k,n;
# ]% V l, o9 F" Y char a[50];
$ H f, q% i- c( Z, k$ [ gets(a);5 @; O9 I1 N: c
n=strlen(a);2 O# d2 h4 T) A; ?* _
5 B. }# T3 n2 x for(i=0;i<n-1; )% v& [) T/ |) N
if(a==a[i+1])
2 m- h( r2 _1 c+ L5 f* X! X { for(j=i+1;a[j]==a[j+1];j++);
( j3 U- s2 q9 O1 Y: c$ \: ~1 h+ n printf("%d%c",j-i+1,a);
; O$ f/ A& |. B/ h: s0 S* P+ i2 d% t i=j+1;
' Y* E/ M9 ^$ t& [ }
9 }. s4 U7 \: |% Y) }3 Q9 | else
0 B b- Q$ N3 F: r6 w6 e" ^ { if(a==1)
7 r0 e; {9 R! q/ f0 K { printf("11");
( ?" H% [4 ~* z0 k: N7 k i++;& P6 W$ C% H5 N+ r
}
* U' F! A) F- ?, ?: Q7 T7 ~ else
+ M& n$ y1 ?& _( p3 \ { for(j=i+1;a[j]!=a[j+1];j++);8 n0 \- u' |- ~9 z7 a
printf("1");
3 \% t( Q3 I. A3 O if(j==n+1)( b4 b/ k9 r; r9 x: h
j--;
7 _6 ]! T2 q8 _( f) j for(k=i;k<j;k++)
1 l+ e' K& `$ L+ N printf("%c",a[k]);2 Y9 n0 i- `6 B( I: n
printf("1");( P- @- j- d- [, J" x( K
i=j;
, G3 e1 A {$ V( }" l, e }$ a; N0 M9 A2 G: |+ q
}
; H+ {) ~. e4 ?: n: f r0 A3 ] c7 q if(n==1)- W: b' {, v; G. C/ S# W; a
if(a[0]=='1')* B9 u. w* r1 Y5 g( U
printf("11");! z2 y; \/ o5 [! r
else* D+ K1 x4 K3 V
printf("1%c1",a[0]);
. w V% N0 x: r. d" d6 r! W( U( Y7 ]3 l printf("\n");1 Y' p8 @9 I4 E. `
}
9 K! |. M9 S% r2 y# a 评论人: Colby 发布时间: 2010-3-2 12:04:06 #include<stdio.h>
\& M3 H5 h1 X+ c" d4 W# g #include<string.h>* ]8 F& K" V7 |
void main()
& d9 T1 X1 f) r& z: T { int i,j,k,n;2 Z6 H; p) ?4 q& ]3 G3 n, U
char a[50];
: E% m1 Z+ G; A; x! ` gets(a);
7 F; \; Y) D( M3 f$ [ n=strlen(a);
- U, M$ y) G6 Y( } # G0 M0 T) @' d+ I) E
for(i=0;i<n-1; )
: X/ @* r9 Y. ]) F$ m) V if(a==a[i+1])7 G- v7 z% e3 [% ]+ H. t! ^$ H
{ for(j=i+1;a[j]==a[j+1];j++);# t+ Y& D P9 N1 G! x8 ~
printf("%d%c",j-i+1,a);* {1 \) L9 g C# B% @' q9 P
i=j+1;# w* ?" W8 t* a$ F
}
/ V: y% {6 U6 \, s2 r8 F+ M9 K else( M0 C4 u7 h+ P- a" @
{ if(a==1)1 K5 v" R) `, n ?
{ printf("11");- z" |6 \$ J+ D5 u) `5 [' c5 M) n
i++;
1 d z& k1 n" D, n1 h5 E- Q } I5 O7 ^! t2 r% a, C. f
else
4 T, \% q+ F1 S+ D% |$ |( N* z { for(j=i+1;a[j]!=a[j+1];j++);0 p9 L% |) k. _1 p2 g4 m M
printf("1");- \8 |. F: z: _9 a+ g8 f+ I/ I
if(j==n+1)
2 V. r) x, M) ]8 g2 ], | j--;& \( e. R0 o: ]- i3 E
for(k=i;k<j;k++)
9 _7 u0 F3 q: i8 D5 q" f; H. ^# y printf("%c",a[k]);# j ^/ X/ {5 B
printf("1");
+ D6 m _' X, w' R! i9 C i=j;+ o2 V/ x! K# v1 y, M x9 J& U7 A1 B
}
/ e" o8 I6 {: j+ N }9 o3 |, r3 J3 ~% c( v9 `6 v& c
if(n==1)
4 q$ U- [2 E6 {: n- [ if(a[0]=='1')
6 e- x m. d) `0 Q8 ~ printf("11");
, p0 W5 E5 O, Y% D& g m else+ M. C; B% Y. }& k- n: b
printf("1%c1",a[0]);2 S" \4 C# P& n. P. D ` z. V, F
printf("\n");7 y2 U7 d. D; J) [0 c. S
} example2:#include<stdio.h>
M+ k2 l4 E& b# | #include<string.h>
; P% \1 c' Z1 R void main()
, @& w0 e0 W A2 i! m' l- ?2 | { int i,j,k,n;
0 \# i% I- d5 }$ A( [0 [- W char a[50];! N- @4 U1 V9 u/ ]
gets(a);
3 O# i8 P' h3 g* A4 C0 F$ S; J n=strlen(a);6 `* A8 R% t- h& B1 p5 D3 _! _2 N; i
& a- {$ _& m/ ?+ f- F( g. _ for(i=0;i<n-1; )
# ?; [0 d- o) B) H' n+ F if(a==a[i+1])
' w" c* x! Q* c { for(j=i+1;a[j]==a[j+1];j++);' B7 u; A: b# b! N- v" f! ~
printf("%d%c",j-i+1,a);. `% N6 }, S5 N& W8 o, k$ z
i=j+1;. f5 ]. [) E* o+ C
}
, U5 ~ P0 R6 Z4 Y: x# r# M$ ` else: K' O6 k+ |; C1 P: u5 V; D" K
{ if(a==1)
: M6 n1 @$ E$ L3 ]2 y- b: M5 O { printf("11");
! T" `- u: e5 k% `7 V, N6 T3 r i++;
2 g& F( E4 O8 z- N& d5 [ }
; Z3 z2 h" ?9 p1 S& r else e0 U) p% J; p6 }/ t7 y
{ for(j=i+1;a[j]!=a[j+1];j++);
, J. \. E1 V& o printf("1");
m- y# m9 J' P3 U% e- ^) U8 | if(j==n+1)
7 F. e; v# o' ?; `0 R$ q* ` j--;
# x0 z3 d4 V! {1 n for(k=i;k<j;k++)
; `0 p3 ~" q3 R' Q0 j, d+ L0 p7 a printf("%c",a[k]);
6 r4 H( a1 V9 T printf("1");
- Y( v. r/ D* ]! }, T F* h7 [ i=j;& b1 Y6 ?' L8 W
}% \( Y9 M' P- ~
}
% m7 a2 Y% v7 I `; R' C7 r: F4 V1 h, Y if(n==1). M. }! ^9 e/ {( Z
if(a[0]=='1')
9 Z/ ~! D! O0 F0 m printf("11");
; y- l. R7 m+ J0 | else
: h1 z g/ c7 U' Z4 f/ P- r8 @% {) P; s+ A printf("1%c1",a[0]);
2 r2 i+ F& N J0 v4 X( x, { printf("\n");0 J- I+ b! }- G$ \- l
}- d* N9 w% L1 I7 ` l7 k
example3:#include<stdio.h>
. y& p3 q5 t& y, B& R; q% a #include<string.h>
" I3 {, P' V3 e5 G2 A void main()4 ?3 T- C7 S1 r+ P" u% T
{ int i,j,k,n;+ j) Q0 G; b1 p2 q. Y
char a[50];
5 |6 r* ?. i8 _, J5 U) N1 z+ t Y gets(a);" X2 I! \1 A* f: t2 K% l
n=strlen(a);+ `* X* d! \, @+ U5 X1 X8 ~
- E8 [! K* W* t" J7 _8 r for(i=0;i<n-1; )
% `" c- J9 K( A4 {$ B; a if(a==a[i+1])
4 \3 \( d A5 f2 `8 r7 U$ o0 G3 b! q { for(j=i+1;a[j]==a[j+1];j++);. }( {. r. \, p% p2 _# g
printf("%d%c",j-i+1,a);9 n9 w0 m- a8 ?" b, S9 ~: D
i=j+1;, c1 k0 a! K- M- S I& X
}
; n8 H( l$ \0 u( A! k% O else
9 `& t5 q% [* d { if(a==1)$ ]- L8 U3 Q) _9 p4 q+ Q
{ printf("11");( { O& i: H' t) a
i++;
; N. z% S& ~: S8 X H }
) w8 k4 w% b* r! W# V/ i& E else
. K' t, a, ^8 b9 f: } { for(j=i+1;a[j]!=a[j+1];j++); s) ^) o6 E2 |5 w- k
printf("1");6 G0 h7 c# e4 X4 V3 O
if(j==n+1)5 k$ M$ J& k7 r* D& ~8 N: X% U
j--;; q/ X; d j& E9 `
for(k=i;k<j;k++)5 \1 S k% w# q/ B5 {7 |$ t
printf("%c",a[k]);7 Z5 `2 I/ \0 G
printf("1");
$ X% p5 C$ f: z$ H/ n' G2 l i=j;0 J& f$ z" R7 j2 p
}
) G$ \2 ?8 @ b( X0 J7 ?0 G" x }
1 L# U. x7 o$ U Y6 ?, W% k t if(n==1)$ v% h6 z! P9 n6 z8 S& t+ a
if(a[0]=='1')
+ C" x9 d$ t4 _; {0 E" P9 p. T! n# B" P printf("11");3 Q( k5 K. L$ @2 {
else
. {8 K* C! `# l1 ? printf("1%c1",a[0]);7 f2 r# f& t/ F# q: I
printf("\n");$ c+ w0 f3 c3 J. r% ?9 S) v
}! O5 j& r9 u4 f
来源:编程爱好者acm题库
zan