数学建模社区-数学中国

标题: acm编程竞赛题目2(Run Length Encoding） [打印本页]
作者: 厚积薄发    时间: 2010-5-6 18:38
标题: acm编程竞赛题目2(Run Length Encoding）
Run Length EncodingDescription
8 b* x' u0 v  o/ F. m- J+ S) r& t* V% }* x1 U# b. |, H
Your task is to write a program that performs a ** form of run-length encoding, as described by the rules below.
5 W) A: K  |2 i* D. o! N
! ]  U5 w4 l: V! rAny 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. " ~. g, B( Y3 q, q; e( X

- r8 l8 h; ?4 RAny 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 3 v. W! |- g" a  X
sequence, it is escaped with a 1, thus two 1 characters are output. $ R, w( L: n+ l6 |0 z, |7 ^& _
) ?( M0 c+ ?3 v  w5 L
Input
5 Z& w/ q, S/ A1 c
1 V* k, k( Y( {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. & I8 l2 r8 ]: c$ E2 O5 V4 z, t8 w
! e9 ~* L* k8 o. }9 M
Output
8 J; c7 V/ Q6 s" @' _( G7 r- `/ j* G  v
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.
  {; j2 e: M6 }, \
: w. Y1 I; ~( _& M- j9 P输入样例

7 V1 M8 F) J7 N* H
AAAAAABCCCC" L0 ]0 G6 r( D3 k. S
12344
: h. ?2 |# m3 i9 [. r6 h


1 Q7 t- b9 r4 T; Y; E1 }" }+ y0 y" e0 }( j  N
输出样例


) B% C& C$ Y: ~: B0 z4 _6A1B14C/ }/ r5 z) x" n. l- R
11123124
; }" [1 s& c' n$ V

: J3 _9 S( s7 H' p

1 ^4 D2 c5 C% J' X- s1 pSource5 X; B. O& y+ [3 P. a; J6 C' v
$ F0 B$ n1 j& B7 J
Ulm Local 20045 o0 H4 |+ U" Y" N

5 A8 C$ N1 R/ q# nexample1:4 O1 n1 h! ^# u$ ^. z9 b2 N
#include<stdio.h>' |4 N8 R6 a7 K1 x1 ^& i5 M
#include<string.h>/ e4 \$ ]; N' m* x- M( `, @5 B
void main()
7 U! v# v) ]2 C4 K5 \; W: b4 N{  int i,j,k,n;
) O, _. G: h% x& N' u* g   char a[50];( a/ S5 t2 F* E. I/ d/ Q/ f! p) |
   gets(a);
, h) ^1 D$ Y# P7 a" C) D   n=strlen(a);" Y4 u0 Q: w6 n/ }% Y& I; T
! V/ _, k, z- Y
   for(i=0;i<n-1; )
3 o) L; a2 q/ d0 a5 k& j$ l; X      if(a==a[i+1]), m) h' K; F# B2 [
      {  for(j=i+1;a[j]==a[j+1];j++);. g1 @; l+ n% _) Q  |
          printf("%d%c",j-i+1,a);4 I) ~5 k' N) @: m; B4 T
          i=j+1;; b. n. P) L' y: M
      }7 E  M) u# b% U% @
      else
0 [" O# t- w3 e      {  if(a==1)$ J; X/ n$ T$ Y/ z
            { printf("11");$ }7 p2 s8 q% D6 R5 C0 }- Z+ |
                 i++;% A3 U9 K. p( I, j; x! _7 k
            }) i( d! |( h8 y0 d: ]; P
          else
7 f! m  R# N& M0 u          {  for(j=i+1;a[j]!=a[j+1];j++);8 h  I; ~2 W. t! u5 `1 v
              printf("1");
) F" Z( L9 p( S              if(j==n+1)
; g( z0 `# Y+ w                  j--;: _  g6 e! [) z8 Y
              for(k=i;k<j;k++)
- X7 V* i" D. o                  printf("%c",a[k]);
* @& ^; t# ~) O  W+ ^              printf("1");
7 M" |2 C6 x* x, _  }) e              i=j;
; K# N/ k+ I& V) a& Y6 `( v8 b          }7 _0 |* E& `( e# \
      }! k" C! ?* g  a, C2 j, T# l: j2 B
      if(n==1)
7 H3 W4 F" |3 z% U# I7 m2 |! g* _          if(a[0]=='1')0 ]0 A7 S0 g8 ~$ d' T
              printf("11");
" P/ K1 w! L, \" r          else
8 ]6 f1 h* `4 Z4 s+ G' G, Y              printf("1%c1",a[0]);' {  o6 j1 M6 b0 n% e* M; E. O2 O" \% }
   printf("\n");% T* E- Y& M% I0 i0 m* _
}
; X* X/ o5 |( E1 [  r* k$ m评论人: Colby  发布时间: 2010-3-2 12:04:06 #include<stdio.h>
- H- N$ u& _$ y; r#include<string.h>5 o) ]! P3 l2 `( r
void main()) ~3 ~" k0 J2 F: ~: d
{  int i,j,k,n;) Z( [$ J& W; P/ |: m! L
   char a[50];
( s7 {8 s9 V2 w$ t. ~, h$ F   gets(a);
: _  I$ ?* j' B, a+ P% d% |- w7 r' R   n=strlen(a);9 |. c# U5 C. k
4 G) g! X" k% w2 g. s
   for(i=0;i<n-1; )4 \9 }9 T% [6 t: S* w9 F
      if(a==a[i+1])
/ g) q( X0 D: j& i8 H      {  for(j=i+1;a[j]==a[j+1];j++);
/ U9 F7 g1 R& x. U% r" l          printf("%d%c",j-i+1,a);6 B& I" y, l. E$ ~& K7 p5 D+ _
          i=j+1;
, g, `7 b9 P5 z/ D  }2 ~! c2 S      }3 i$ c" X. p7 B4 d
      else
" U+ A/ l$ w7 q* o( T; C6 j/ h1 r$ i      {  if(a==1)
* n) J* @& V. i0 }            { printf("11");
, i# i7 i. o/ |& @( z0 ]) b                 i++;
% E# A: \  b/ P7 t3 o            }' _9 N* J2 ?6 Z) x
          else
2 G/ u, U0 v3 W  T2 [# Y          {  for(j=i+1;a[j]!=a[j+1];j++);" k2 \  ^4 H& x& @
              printf("1");, p  y1 d# ]5 M# e- D! M8 T
              if(j==n+1)
3 d6 M# L; d) P* K                  j--;
( M/ I( q+ L" _( ~# g" J( r  I              for(k=i;k<j;k++)
7 F# w& f3 l! v8 S7 L                  printf("%c",a[k]);
3 K0 o5 P4 n3 k, a. ?0 L              printf("1");
! J, N) f1 Q; Y! ]9 ?6 y+ Q              i=j;
. O, g# s! E, U4 I4 f5 B          }
- S& G/ d; w" ?      }
7 q8 Q7 M( o( b) `( [. N      if(n==1)
+ g3 }+ B( J9 y! U! |          if(a[0]=='1')- M8 H4 f/ X) j8 _3 x
              printf("11");
1 `$ m: S1 [  q6 @- L          else, H2 Z4 g: `9 _7 }" r  v
              printf("1%c1",a[0]);
; x0 D& R: M% O! N5 V; s   printf("\n");
# o9 L0 s+ K6 C' n: j6 O }    example2:#include<stdio.h>
7 R& ~3 ^* |( H; n9 N- Y+ i' h#include<string.h>+ z) T: a0 ~( [  e2 n' ]
void main()
# Q5 P/ n/ b0 d+ V! R6 \{  int i,j,k,n;/ \. h; b: }3 O* E1 K
   char a[50];2 o8 K- i8 p( E) |
   gets(a);
, L6 R& {, t0 m- d) r   n=strlen(a);2 G( ~/ u$ v2 g1 B9 F- ~

3 L2 _3 C5 D/ g/ `/ \   for(i=0;i<n-1; )) V+ N: W4 x& T2 ]7 H
      if(a==a[i+1])5 G, q; E  g: V( [+ @  t
      {  for(j=i+1;a[j]==a[j+1];j++);
/ Z5 k% k* H1 N* T& K3 x          printf("%d%c",j-i+1,a);3 ?; Q7 s4 q7 O% l; t
          i=j+1;
3 A4 }5 I7 @6 m+ ~3 y# l      }
0 s' v6 {4 \2 v: X' ?8 O      else8 N  _* A# s# h" t% Q! t# [
      {  if(a==1)
9 t# U, s2 }$ v- E            { printf("11");
* U7 Q$ a! w! h7 h8 ~  J+ M( t                 i++;
/ K8 z$ A) Y8 W& V1 V            }* \9 `$ q# E' j% c4 j. T3 S" \
          else
, u1 p$ k9 R8 C2 d$ n          {  for(j=i+1;a[j]!=a[j+1];j++);% C  Z' i$ _# M! }5 h
              printf("1");
+ \0 L  w$ B/ o              if(j==n+1)
7 c: s( h) l+ y: c                  j--;
( T5 n" }/ x: p- h. F. I0 B              for(k=i;k<j;k++)
5 }( W) d, {% ~1 M                  printf("%c",a[k]);$ f& a' }! v; @! v* T+ B$ |7 _
              printf("1");4 @! x& o. K6 ^' o. `3 ?! v; a& y
              i=j;
' c8 h; b) j# r  m0 S. J          }
1 P& ]( }% o9 ~9 _" p      }
5 H# e+ l& U$ v  O( g( I& Y      if(n==1): }8 I( x3 i6 S/ @6 x# O
          if(a[0]=='1')
+ F& m  [4 Q% e4 N% |* ]* P              printf("11");1 [( M5 v5 G( s# P6 l; c
          else
: f, Q6 n/ `8 L: j* Y# t! |              printf("1%c1",a[0]);
: ~& f' }  l' H! K! {: u3 M8 i   printf("\n");
1 G( ~% l/ k2 K }$ P5 i1 j0 P2 A2 [% Y  A
   example3:#include<stdio.h>
- n4 z. m$ X* g  X  M! M* r#include<string.h>
8 W, G/ o( c2 B/ Vvoid main()( u" u% m  h: Z2 \. z: V+ e
{  int i,j,k,n;
1 t0 @- w$ W- X: r   char a[50];7 c: W8 w) n% U) V
   gets(a);
' {" G2 U' O  O. o0 ^   n=strlen(a);# J4 `+ M7 y- Y) G* j0 _4 B
7 M7 G' d5 m* |: ?: \
   for(i=0;i<n-1; )
) e6 d6 C5 ^2 M% n, G      if(a==a[i+1])
: |% Y2 l- G7 m6 [      {  for(j=i+1;a[j]==a[j+1];j++);$ |! U" E- u- R- r
          printf("%d%c",j-i+1,a);
+ P4 q% ?4 E' _6 q( u6 t          i=j+1;
' ]$ C" |; A; K, U# G1 C1 d      }
! \9 M, Q; r! f, B' E" u1 d1 P2 S7 A0 o      else
. b/ h+ L4 \+ P" H+ \4 J6 t      {  if(a==1)
# @$ K7 l* K" p; U            { printf("11");
, z1 w1 u: s0 n                 i++;) }$ ?. F$ V9 h/ m
            }6 c$ e* Y3 Y4 e
          else  m( C, Y4 t' B+ C8 p! \3 Z$ q3 D9 n
          {  for(j=i+1;a[j]!=a[j+1];j++);, K9 q5 x+ b5 G  M" ~( ~# W- `% C9 d
              printf("1");. [8 U3 p, Z$ O& {- n$ C% n- z  I# W
              if(j==n+1)0 m/ F( u! x& }2 n' G
                  j--;+ F( R4 f9 B& I6 l. E. w6 [" D: x  \9 o
              for(k=i;k<j;k++)5 p& G! x; S9 W4 q' G
                  printf("%c",a[k]);
5 a9 |- M6 b6 H9 V& o) F              printf("1");3 t+ B: L" d. G1 W
              i=j;
4 _$ I0 y. z& v* X0 w& [          }
7 o6 ?* i( L  c; x, b. G/ Y* w      }
. I6 b: a4 e) Z( O      if(n==1)
- R8 y3 Q) v2 ^! ?          if(a[0]=='1')
; K' y- P5 j( t: y+ A              printf("11");7 m2 o6 \5 w  {0 Z, Q9 }  U
          else  T0 {* R' a- s& Z; v; v5 X
              printf("1%c1",a[0]);
6 ]$ Y! p3 d* U. l; r& f: u   printf("\n");
' Z( x% L1 h# a3 Y8 P! b: S9 a) | }: M9 B0 ?" z9 U1 l$ C* y( Y
      来源：编程爱好者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