数学建模社区-数学中国

标题: acm编程竞赛题目2(Run Length Encoding） [打印本页]
作者: 厚积薄发    时间: 2010-5-6 18:38
标题: acm编程竞赛题目2(Run Length Encoding）
Run Length EncodingDescription & P- Q# ]6 l5 r2 Y  I; D
4 X: L# g; {9 z* c1 B+ a3 _: }
Your task is to write a program that performs a ** form of run-length encoding, as described by the rules below. : Y/ u* R" c) v# ]3 H7 I2 ]
  C5 ^2 m8 h/ C5 _0 @( ]
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 q7 g' N9 T( i1 T5 U: x+ T

& X5 D3 j, A+ k3 m4 L; ?+ ~/ }+ _9 {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
) v6 d" Y" A. P# F# xsequence, it is escaped with a 1, thus two 1 characters are output. 5 }3 W! A; y7 W$ \9 _0 T
% H' U" m  {' U% m5 O8 N8 d" y
Input
/ \- h* N" q2 T. t: |( K1 `+ R6 e: m1 L5 V% {: D4 u, I8 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. - a  T8 K: s% P& C6 S

9 P3 o$ Q$ _# {" E3 H; L9 L8 tOutput
" O: `3 H: Z6 y. q9 e, w
+ ~' m, @" ^* X2 ]2 i6 {" zEach 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 }; [; a, z1 @3 i- ]& Q5 ~) s* F& O' ^8 X: T% j0 A
输入样例

& p$ w8 s# F) ~# x5 f) \+ }* n
AAAAAABCCCC( V% n- g5 H* \  H
12344
( t( o+ U6 X# L$ A


' O8 u! _, x6 I
& {+ A8 @: m  s输出样例


9 _4 h7 ^/ ?% ?6A1B14C
$ M% r/ p' J; i11123124" T* u; v, G6 q4 Y

) G0 U& w% O, }, Y* e# |! o' \9 H  L

, }+ l  J2 M- g( G7 O$ V/ k- RSource
7 A' |" \$ Z0 T7 F6 R9 u5 `
5 X6 C- @% w2 ?! C3 D! |) y4 kUlm Local 20043 T1 Z+ i7 Q7 S0 d1 s/ [7 m2 N
, ~- }1 Q/ n* T# f' [# I* T
example1:' t9 t- W8 {% \& b" X; \
#include<stdio.h>8 U+ @" R9 t) y' y6 }# a
#include<string.h>
7 t, l/ I/ L/ G7 Gvoid main()* |. I* r8 t# g  I5 p' ~
{  int i,j,k,n;
' p+ i+ [2 w# p: L   char a[50];
+ n- \8 c- j  K' e# R   gets(a);4 H) W1 X! i- W6 k
   n=strlen(a);
) i8 h) i: B8 P  B/ m) U' ^  n& Q) e$ l  x
   for(i=0;i<n-1; )
* w! f3 B0 S2 e8 c+ H      if(a==a[i+1])& [& {  b3 y, F
      {  for(j=i+1;a[j]==a[j+1];j++);' |( }  f, o8 U" ?( I, r( q
          printf("%d%c",j-i+1,a);6 q; Y! A8 E" b+ T
          i=j+1;6 L' `/ x; p; q, E& o$ @& D" w
      }
6 [6 F( W. j- z      else  Q' A2 n0 Q+ ]7 u* G
      {  if(a==1)4 W- i" T: j7 L5 d0 t1 \- n
            { printf("11");
2 T$ U$ e1 |$ O/ ^' l" u  p/ V                 i++;
: q. @$ T9 n  K8 J5 Q            }
5 d2 d: U. J, e          else
$ f# |$ h; j4 ~2 P  K9 z; P  t  |          {  for(j=i+1;a[j]!=a[j+1];j++);
) `+ z, U$ B) a9 L/ o              printf("1");* l- w9 x0 c! ~
              if(j==n+1)
8 B) l( u9 n( l+ Z6 x                  j--;
7 N5 ^* o) |% ]- X) o5 E1 R              for(k=i;k<j;k++)7 k, w0 S3 j' ?: [
                  printf("%c",a[k]);+ K3 }0 ~2 s1 m2 ], r1 E
              printf("1");
& I- U5 H* g  D' D6 I3 S# ]  I              i=j;
( }/ o: }. A1 C# U/ j% G- f$ O' G          }! g8 ?6 Z$ |4 E+ B. K  B# J
      }
# `" g* q3 t- a& e) `5 r$ ~9 m      if(n==1), ^$ J: L% R# b1 P3 u- Z
          if(a[0]=='1')
4 r6 g  T8 f; o+ C2 E% t: [$ ~              printf("11");
% E" L( q. {% _  }. G2 }          else
$ H, j6 ^, C* K. q              printf("1%c1",a[0]);- p) S1 @+ E; N( U
   printf("\n");
) s7 |* t$ F/ _1 o, C4 y: o }
6 O. J4 P8 ~$ z) T评论人: Colby  发布时间: 2010-3-2 12:04:06 #include<stdio.h>% `, a, n5 c6 I
#include<string.h>
' `; M1 T" d- e) I9 [; |0 h7 Lvoid main()
7 s) l$ u+ h" C' Q" @{  int i,j,k,n;8 k' J! {4 i) i3 p, G: a
   char a[50];  E8 A( v% _* t0 T
   gets(a);
) X3 C5 t/ d+ m2 O) G   n=strlen(a);& C, Z' o8 [' \! m+ c& ~9 g' g
. x( f) i4 z! O' _! d1 p6 `  m0 j) b
   for(i=0;i<n-1; )
0 _/ M, _7 ~! }0 |. ?1 c      if(a==a[i+1])
/ ^  B% G. v3 n      {  for(j=i+1;a[j]==a[j+1];j++);2 y  g) w" L& y9 ], S9 R% Z# b
          printf("%d%c",j-i+1,a);5 ?0 U2 w" R4 i9 w
          i=j+1;
1 ?6 y1 j3 K$ N" ~3 q- c      }; t+ N$ W# P4 [5 O8 r% z
      else$ Z3 s' _: h9 A
      {  if(a==1)
+ ^& r$ l0 G: p3 w) t            { printf("11");2 o: u0 j- D4 F) ]% P+ O0 u8 p
                 i++;6 ^4 H! ]5 t; g, f$ a  M: S
            }* G/ w" e3 Q# w5 g# [- J3 p
          else5 ]8 V- z5 [+ C- E
          {  for(j=i+1;a[j]!=a[j+1];j++);
4 M, Q& f2 I7 X4 n              printf("1");2 q3 S: Q, a6 O3 i* ^  b. B
              if(j==n+1)! y1 ]' {- L0 {: P
                  j--;
6 D% _& H$ p1 \6 N$ _. _# x* v              for(k=i;k<j;k++)
6 |/ j: J0 F$ E                  printf("%c",a[k]);5 F( a" C6 C* K3 t: {4 @
              printf("1");
' K, b- \" ~& }: C              i=j;1 k! e$ E& c8 ?$ i9 p
          }
) `) \4 F6 O1 |( x      }! l$ }* V& K% n; i8 L. |, Y: R
      if(n==1)) m8 z# @$ b% V& U& x
          if(a[0]=='1')
$ ^/ M1 z$ C1 S( w              printf("11");
4 f! x* p+ ]& S% b/ ^5 B" W. k          else
. P5 y# u# k  i- c              printf("1%c1",a[0]);% S6 O/ B0 p& I' w( C
   printf("\n");& _- z: A, [5 m- w
}    example2:#include<stdio.h>9 h4 b9 X9 f9 a) s3 i$ r
#include<string.h>: ?# k' Q! h& E4 @; G2 ]; V: f  Q
void main()/ Q& z' I; ]7 I5 B0 q. g
{  int i,j,k,n;7 t+ X4 L% r. e4 T' ?) \. K1 \
   char a[50];
8 ~9 l$ D* G7 J# T2 z& \   gets(a);
! J1 S/ {+ `7 z* i   n=strlen(a);
+ L8 d  o0 B' ~9 q  r  }% s! R
$ o3 h* z% w0 c. T2 \5 m   for(i=0;i<n-1; )* Y( \4 L" c' u2 Q
      if(a==a[i+1]); Z- b' g' x- M8 A3 v2 R
      {  for(j=i+1;a[j]==a[j+1];j++);
; S2 K/ I8 D2 D5 ?1 E3 u9 R  j          printf("%d%c",j-i+1,a);( x5 C6 N4 Z1 v
          i=j+1;5 X! Q  u' N8 N9 ~* I
      }5 T4 F4 x5 g& H3 c7 `) b
      else
2 C# n( B! n( k2 @1 J5 R      {  if(a==1)
) v, j$ k- I4 Z. L% T% D            { printf("11");
! m8 c9 u0 i2 n- G2 Q5 d% W                 i++;
, G% t# t2 V- U" A1 u            }
; @# k( P. `& B2 q) N! W/ _$ u1 C, ]          else) F& Z$ P5 q# v. q( ~
          {  for(j=i+1;a[j]!=a[j+1];j++);5 D8 C4 [, E) ^
              printf("1");
$ e. {5 R* |' [+ U% i              if(j==n+1)
; M( o; u, r8 h                  j--;
, W1 g5 ?; k3 x# n( O5 Y5 I) n% s              for(k=i;k<j;k++)0 J+ E: b. ?+ ?( ]) A
                  printf("%c",a[k]);. ?- J+ k6 f! w. S# O- ^
              printf("1");
( v3 l- y6 \9 M              i=j;
8 J9 f/ Z3 f  k) X1 _          }
0 A1 v* t" t7 q: q      }
8 T- D( i& b* h8 R      if(n==1)6 b, D1 r& W/ e" l/ t
          if(a[0]=='1')+ [7 F( r; l  n( D$ g3 Y6 N
              printf("11");
4 X+ ~* ^* g5 D. |  Z" O& t" x! F; c          else% J& G2 j+ @$ P
              printf("1%c1",a[0]);/ N0 b5 L) W5 |  p8 c) Z, D
   printf("\n");
+ @4 L- B! Z, b/ @ }5 V9 V/ f, c) N' j0 O
   example3:#include<stdio.h>8 U, ]# C. {) Y- {8 H
#include<string.h>
. b8 W5 f, Q1 i3 n8 Fvoid main()
2 Y4 b5 S5 K  u' G) a$ j  h# N{  int i,j,k,n;
+ d" K. W1 b) V7 h6 A1 \2 |   char a[50];- ?; z0 e: p# X. Q( ^0 p6 y
   gets(a);; M, q2 |- q3 W% [0 L- Q
   n=strlen(a);
& B+ e2 U& K9 x- l: Z3 R) t
  O6 n0 W3 ]8 O$ J4 f   for(i=0;i<n-1; )
8 l/ U. f. y" z2 y: x0 M3 U: q9 Y$ A; |      if(a==a[i+1])
: |  Q- \, z' F* n. C1 B      {  for(j=i+1;a[j]==a[j+1];j++);
. p$ f+ z( W% m- v& O* v          printf("%d%c",j-i+1,a);
) S. h2 X) C- \$ n- [% ~+ @) P" o1 ~          i=j+1;7 n: r2 C: |) B" E0 @' r* o
      }* K: ^3 Q0 W. h+ @& \$ d
      else
9 s( w6 ]! D0 x( `+ |2 P      {  if(a==1)
- f7 D$ R9 j; u5 x2 x            { printf("11");3 I0 T9 Y# ?8 N
                 i++;
- i' R  l7 H/ Z            }7 g/ Z# i5 f) L8 e; T
          else
; |& w5 S; p% ^7 v          {  for(j=i+1;a[j]!=a[j+1];j++);  a: \$ U$ r& Q1 {
              printf("1");
" f- Q9 y- X6 U2 O& H( N' I) I: }              if(j==n+1)/ p6 P  d  f9 }
                  j--;
& M2 r2 Z5 Z* T+ U* j              for(k=i;k<j;k++)
5 f, I. Z- d3 |6 X5 }% r+ }" I                  printf("%c",a[k]);
. |0 Z5 `+ U. ^1 u  d              printf("1");
% F0 K/ h: n( E7 w' f& ]. W              i=j;4 m/ u% {. y- l# y4 X) @! K) m
          }, B3 [' h  o( B  O  w8 F: v
      }( A0 R2 @# \- D! @; }
      if(n==1)( V. ~( {$ C# B. ]; m3 \
          if(a[0]=='1')
( T, }  U# x3 [8 o/ e              printf("11");6 Z5 j8 P$ A. z
          else4 p2 O6 d2 N+ f+ t- C1 L& O  ^
              printf("1%c1",a[0]);
2 ?8 @- I7 I( a6 x- c  `   printf("\n");
7 q  M3 ?2 ^7 P: L  E+ N$ J }
# @' x  G0 k: B* y: K      来源：编程爱好者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