数学建模社区-数学中国

标题: acm编程竞赛题目2(Run Length Encoding） [打印本页]
作者: 厚积薄发    时间: 2010-5-6 18:38
标题: acm编程竞赛题目2(Run Length Encoding）
Run Length EncodingDescription : {; l: [' v' ?8 Z5 E
  x8 r4 y# M  j) y5 q: Y$ X
Your task is to write a program that performs a ** form of run-length encoding, as described by the rules below. 3 q2 i# D2 A, p( l
8 i7 F; W! b; K7 B$ Q; t$ L: T
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.
2 h/ L: j; R% K
7 d; v6 O6 [/ z  z: N: WAny 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
8 z; K+ H! T; i. m) Nsequence, it is escaped with a 1, thus two 1 characters are output. + T/ I4 k  {. [# B1 f+ S5 Y7 F
4 w' R3 c# k) E
Input
3 E2 l6 A# o8 \1 B" ?8 I1 F. F! Q% L. j$ u2 X
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. 2 Q' S6 {" |# ^; o3 f0 d
/ }+ x0 E, y( Q: ~* E& T+ A, B
Output
9 a! D- D9 M. Y1 Q* i6 j; p2 o
/ m4 }$ I* O4 t$ T, B1 N7 [3 xEach 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.
) Q; M: W  d1 o2 l. c. G: p5 l- n  D! l/ e/ p
输入样例


' W: ]/ w, i% L( B6 cAAAAAABCCCC! \6 Y3 H$ d1 X6 e% t$ z; s/ @' h
12344$ F8 i0 U' O" A! K/ J


9 @( ~4 }( m! B% N- I
. I% l# Y) @- m$ _9 L; \% B输出样例

- E5 W( f1 f7 W( O8 ?* q* t
6A1B14C: ~" e  w7 G8 @! x) D( Y+ Z  N8 I
11123124& k$ c' O; T6 \7 Z# e+ w; \' f


8 U8 l& l+ S+ e$ L# ^  Q, }+ `) J/ O2 g7 S$ _% A6 f: D
Source# d" g+ |' a% K! F$ ?1 y
3 M: c7 Q5 H% ]  H2 ~6 y( K% h
Ulm Local 20041 I/ a/ x) q6 {4 A; @, E* W
" s0 |6 l: M7 X. S
example1:: g. p2 R7 ?( [
#include<stdio.h>
. c+ X! g9 s2 J+ M) f* l' c#include<string.h>
& c3 _0 K% j) Y& ^! ^  svoid main()3 @" T) ?. ~  _* `
{  int i,j,k,n;
2 T. u& n7 ]  |+ B* p% ]5 @8 U   char a[50];
" {" s8 U: X4 ]1 X5 s  \0 R+ h   gets(a);
9 W# T, k3 M* d$ D. v0 k4 ~   n=strlen(a);
0 ]# A% Y0 I* r6 Q' ?
4 G( `' V( A; N, p' O8 F; P2 b   for(i=0;i<n-1; )' K) g  _* ?  e# c/ S. v
      if(a==a[i+1])
) Z& }% M: H% n( A$ z( F9 N      {  for(j=i+1;a[j]==a[j+1];j++);* h) c( _: ^7 ~) D6 X
          printf("%d%c",j-i+1,a);
# t& H& d7 H# k, U7 T+ G9 D          i=j+1;
. P0 y& V4 T8 K4 q- n      }
4 I4 W/ t' D5 w3 d( |9 B      else5 ^4 j9 K0 }( E! r! r+ R) N$ ?
      {  if(a==1)2 {( x$ g8 p7 V* q9 R
            { printf("11");
8 a# V' i$ j+ j* T2 i, t0 M. ^5 D                 i++;
9 e! o+ C0 v% z- |# C' [6 U            }4 j" @5 Q1 U3 Q
          else
# m- a" l0 p; f( V          {  for(j=i+1;a[j]!=a[j+1];j++);* T* A  \) Z, J( _/ K6 Z9 ^- f
              printf("1");+ [( Y$ ^; X, R
              if(j==n+1)/ v# A. ^8 ^5 B, |" B& x- v! U
                  j--;1 t; a6 N* x; j2 _& \  @8 [
              for(k=i;k<j;k++)1 g5 t- Y* U; Y$ C; H
                  printf("%c",a[k]);
5 ]  _" Y4 m) k0 [2 @0 _              printf("1");, F) a1 P. C; t" i4 N
              i=j;
4 n! z7 }0 p: c$ D$ d          }! F* A- c5 k$ N9 Z' v
      }7 A5 e2 R" ~/ a# L5 A
      if(n==1)
. K/ P# Q; X, C/ f          if(a[0]=='1')/ ~' i$ T+ N# I' B
              printf("11");
  v2 x3 j/ _3 s" U$ ]2 c          else
2 F6 c5 L% z- O9 g/ ~" u              printf("1%c1",a[0]);
6 \# k3 v8 b: G. w% Q# h   printf("\n");
" J1 K$ z7 A1 K; O8 {7 F* d }9 j' b* x9 D- S6 t( d
评论人: Colby  发布时间: 2010-3-2 12:04:06 #include<stdio.h>
( N7 o8 c% f$ @: L6 ]#include<string.h>3 Y' t& m5 Q9 G3 Y& ^: l
void main()6 b' s& _6 W' Q8 E, A
{  int i,j,k,n;
) a6 p2 p* l* q) `6 S   char a[50];8 q6 D7 G: ?  t2 N8 V# X
   gets(a);6 H$ b4 l, c, W$ Q5 U
   n=strlen(a);' [- S, n- c# ]  Y
* Q5 I! g5 @! i8 z6 V: z( }
   for(i=0;i<n-1; )
2 |: \' b4 W" a+ x* S9 v% m1 y      if(a==a[i+1])2 @/ D: I3 Z8 D+ M8 y0 F
      {  for(j=i+1;a[j]==a[j+1];j++);% ^% e: l* v! O  T) N3 ~
          printf("%d%c",j-i+1,a);
, K7 x, ]% c/ r          i=j+1;
# ]9 D& K+ h) E' ]' m! H      }
% _6 X, x6 z- L/ m! ]6 _' E      else4 M+ [! b! j% Y) |* t" b. B
      {  if(a==1)- P0 Y' `+ d% ^" O" \4 ~+ O
            { printf("11");
' e& c9 S4 K) v, |, \                 i++;. ]3 M  H7 g' d# T" ~5 E5 m
            }; T) x4 e$ U/ O0 T
          else6 d9 a5 R1 ^& @6 R2 N
          {  for(j=i+1;a[j]!=a[j+1];j++);
  |# w& N7 ~2 D- T% M* e              printf("1");/ i4 u* g, |' i3 X2 U
              if(j==n+1)
, M1 f- V4 j& Q; [6 f                  j--;6 ~4 Z5 ^" H; K9 I' y
              for(k=i;k<j;k++)
  P7 V& P- q+ v$ c5 Q" J: N                  printf("%c",a[k]);7 u" k/ b2 M" v" X0 A( {9 Z2 Y# O. `
              printf("1");# u! ~  `. e  J( Q4 E2 _
              i=j;5 {0 W$ f, H! [- U, e$ R+ A7 v2 L4 o
          }
( M% F+ Q6 r% N+ V/ r      }
+ L8 ~  ^( t* }: b; ~      if(n==1)" |* @$ t  f  O8 U
          if(a[0]=='1')8 [6 U3 q5 C" q. E/ }
              printf("11");
$ U) x. t6 A1 |; i: J          else% {+ e0 ]/ k+ |4 B
              printf("1%c1",a[0]);
1 l; S8 L  p; C0 k# t. a) M. ~   printf("\n");! n: N/ f" t. B
}    example2:#include<stdio.h>
  f8 n* I& G  ?#include<string.h>
" C1 M3 s" o4 B0 z1 z, K* ]void main()
. B, E" }% u5 x+ ~{  int i,j,k,n;# A( N& U6 @  a
   char a[50];
" Z2 E- U' `9 U: d: B0 }- R- D) T   gets(a);
2 D( i5 g2 j4 Z1 @, Y4 G   n=strlen(a);& V$ K, B% }9 t; T) \
/ I& }9 ], L+ s+ ^) v1 i, `
   for(i=0;i<n-1; )
7 ~* ^. h/ `- d1 _; S! W0 p' {! @      if(a==a[i+1])
: {  k' N+ X7 E1 ?/ U      {  for(j=i+1;a[j]==a[j+1];j++);. b+ n4 I  W6 U& Y9 @
          printf("%d%c",j-i+1,a);' K0 T8 h, X+ z
          i=j+1;
* q! R- N; C: D. X      }
. m3 \0 f. a3 z$ q& Z9 T      else6 o8 Z9 T  Q+ v8 f
      {  if(a==1)
- N6 d& Y) I5 O7 I  Q6 L0 ~            { printf("11");% a8 y2 O0 ?- I* i3 u8 y6 U
                 i++;- i& h- Q( w2 G$ }: m( f0 ^
            }, f7 ?* i8 Q; i$ f' M/ g; a( Y- p
          else, P( E# ]: C9 Q9 Y
          {  for(j=i+1;a[j]!=a[j+1];j++);
6 v2 m/ h! v! [$ _  |& g, p$ ]& f              printf("1");0 `5 I4 G& D& r. E# f) I
              if(j==n+1)
! a( T) @! F- [6 }' a                  j--;
/ \+ H( m. i9 O; a              for(k=i;k<j;k++)% V2 B) I0 C  q5 D! ^, O  e/ i
                  printf("%c",a[k]);$ h' V: m8 t" M; F1 H" b2 B
              printf("1");
& ?% c. f& K, p              i=j;
) x1 P$ M- S& C          }7 o! [# g, x* e# I6 t
      }
2 J' P  Y* Q& J( n' z' c3 W      if(n==1)3 l5 K2 \. c% s' W. g% v! b
          if(a[0]=='1')2 y9 v% u. Y2 x! T: M+ d
              printf("11");
/ P/ i; Q% ]% P          else
0 l4 H5 Y2 O/ G& ]2 ~! I              printf("1%c1",a[0]);& U7 {9 m; F5 |( E2 [; c/ r7 e
   printf("\n");. {' O; B" ?, u& y1 i
}9 Q; c4 c+ _+ t: ~! J
   example3:#include<stdio.h>! D: v# I" L! f7 d1 w9 S
#include<string.h>1 S# K8 n0 `5 ~0 r- [
void main()8 L; k3 P9 ~5 W
{  int i,j,k,n;
& A8 H+ [$ N- n. M$ N   char a[50];
, R9 V3 X7 O6 V   gets(a);
" p: I, h# \5 [, f+ G# X! K6 L1 a) o; U   n=strlen(a);) D& A5 n3 G9 ~
, Y: d2 v8 c- d
   for(i=0;i<n-1; )4 {3 P$ z& x4 Y/ K2 S' H( t- Q
      if(a==a[i+1])8 M4 M, n: H2 j
      {  for(j=i+1;a[j]==a[j+1];j++);
% j! v6 Y0 q" Z          printf("%d%c",j-i+1,a);! a; C& n2 t$ u. m% R6 T% r
          i=j+1;
5 ?) S9 U, X, z% n8 N      }- n& z; ~0 ?5 C) y' C% \
      else
; T: J. {: r+ I6 H) b      {  if(a==1)
! D9 D: h& G5 }5 e( P            { printf("11");; A2 v. \' ?$ D% c' [; N: z5 o
                 i++;
# ]6 f% h9 R- P+ d: c6 {' K            }
6 j- ^  c1 z% t          else! D7 Y" F! y1 N; A" G2 _
          {  for(j=i+1;a[j]!=a[j+1];j++);4 x( Y+ U9 e4 J2 B9 B8 x5 A/ t' P
              printf("1");/ Y5 ~; s0 T9 G! i5 o" b
              if(j==n+1)- ]% L, g* K! t5 j4 J' ~/ j
                  j--;
' B1 t" E. c6 c/ _8 E3 E3 j              for(k=i;k<j;k++)
& e) [- S7 I6 P$ y# |' ^$ F                  printf("%c",a[k]);) o& z1 M" v6 _7 S: y- |
              printf("1");
' s$ M) V# ^3 m$ j              i=j;6 r6 m- Z( ^- Y& w
          }* v/ d6 `( Z% `' a
      }$ K; Y  O9 S: A5 X( b: P8 c) n7 m
      if(n==1)9 Z# f) d) `4 {+ Q
          if(a[0]=='1')
1 u2 [. p! O& f0 W" x0 Z9 Y              printf("11");( l9 L8 P& n) z& Q
          else8 p6 D# Z8 S" ]. [
              printf("1%c1",a[0]);) G% N9 [6 O" b2 `
   printf("\n");# h. E# V" w6 H: }: R' |
}
$ G# u; @  y, S8 J3 S2 M      来源：编程爱好者acm题库
作者: qnbs1    时间: 2010-5-15 17:58
最好附上中文翻译嘛....很不起  难看
作者: Jackge    时间: 2011-11-20 21:48
顶楼上……
作者: dahai1990    时间: 2012-2-5 15:38
虽然没看懂,,,,
作者: qazwer168    时间: 2012-2-6 10:23
关注中！感兴趣的朋友都来说说



欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5