数学建模社区-数学中国

标题: acm编程竞赛题目2(Run Length Encoding） [打印本页]
作者: 厚积薄发    时间: 2010-5-6 18:38
标题: acm编程竞赛题目2(Run Length Encoding）
Run Length EncodingDescription
! g" L, ]6 i% ~9 P( z- l# A* q  k3 m# z8 C( K
Your task is to write a program that performs a ** form of run-length encoding, as described by the rules below. 0 b( ^7 k" u6 a$ k1 \/ i& x

) p+ D+ V$ E! M" Z  J0 A7 y7 G6 T+ ?  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. & D" Y- U( h* ^+ ~6 u1 q* H8 E* Q

  l& E0 \4 O: ], ]1 U8 [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
+ m- H* G6 C, i# v" K  m, R9 L% Osequence, it is escaped with a 1, thus two 1 characters are output.
7 H1 B3 x7 f4 k5 [
( \% _8 Q; Q3 c" ~. a# WInput
' S* H/ B' w: I& `2 w7 a" U3 d
1 a# E  d# ?+ c) \, k1 u2 [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. ' C; F. y+ g6 b# z. E

" M) y, ]) a0 @" x. P: y$ ~Output
( u& q* H, u$ V; P/ U: K/ r9 @2 _6 G1 \+ |( ^( t
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. 7 a+ |/ H" r6 Z( p& {

# l% q9 x4 j; F输入样例


$ X% {! k# T2 i4 i( ^! O$ ^AAAAAABCCCC: ?: X8 y* Q  X* s2 k9 i
123448 u5 F0 j) W& X+ [- E


1 E6 b) Q. M2 M8 e1 w; p4 z' A. Q% z' e3 I! J8 ~
输出样例

) B5 G  ?# h( t/ A6 S- T
6A1B14C2 E. b: z, m# e* h
11123124
8 G3 h5 ^, w$ U


) G+ D  n" ~- y% e- P1 E* Z" \" k
" Y5 J& |5 H/ T" lSource
1 x' M4 L3 Q9 C2 G0 g$ _  U; A1 K) ]$ V' l/ P& `
Ulm Local 2004( K& h% ^4 I( l$ |# p

/ j: r, B% o- r, [example1:
% W9 ]$ z* n7 H$ p- ?3 l& z#include<stdio.h>; ]% W: V5 ~" k2 i. i
#include<string.h>2 k5 |: G* Q; `7 r% n( X" K  }
void main()
2 s& `: U( ?+ h, v; s  w" {/ N{  int i,j,k,n;0 w0 O8 N$ A! p& ]
   char a[50];
9 P- S3 Q  l. k$ E   gets(a);
: i4 X3 Q- W2 @, \& s   n=strlen(a);
* w, p4 u) f( P8 H8 N* H
5 g6 h4 Q' n/ O  G! T2 C   for(i=0;i<n-1; )1 w1 T* z; B9 k
      if(a==a[i+1])7 Y4 u' h& X7 N( l% d- B' y# c* z
      {  for(j=i+1;a[j]==a[j+1];j++);
8 y; c2 T- a; b5 v* M          printf("%d%c",j-i+1,a);
7 I' w8 ~7 d$ u" ]2 ~7 ]( z, @8 o          i=j+1;
' x/ j1 d" o) a7 r5 g      }
) J: U+ c4 J' M- E1 F; V8 |# z; [      else0 Z! c, |8 r! y! O) q+ j/ u
      {  if(a==1)) B2 [8 ?. |* l
            { printf("11");7 u& w" N/ R/ ~" u/ C) c& K
                 i++;
/ @/ W2 {/ x- T+ m5 ^. h8 _$ i            }3 p( |9 F9 B; a" w+ m
          else
. B# U2 Y* g( ?2 F          {  for(j=i+1;a[j]!=a[j+1];j++);, E8 q1 O. d; ^# _# v* r& j
              printf("1");
. z% U# O! ~0 x6 X$ Y- A; X" r7 _# F              if(j==n+1)$ y7 f7 W% b4 T; \+ _: Q
                  j--;
6 s8 W, ?1 f6 ]- E              for(k=i;k<j;k++)) O4 v& W  V9 b3 \* }
                  printf("%c",a[k]);5 I; Q  Z6 @! \# g5 M
              printf("1");
/ [7 H+ o. w* z              i=j;
& m: a% j' d. k. [          }, }7 b0 G# n/ b. D
      }
8 z; J, {) l# f  |      if(n==1)# v# x7 r) R5 q) d9 G( b  W& A
          if(a[0]=='1')
* }' c! J, u2 m; e- Z% Q+ J              printf("11");
- m9 b9 C$ n  F8 m, f1 M          else/ T- ~/ o! U3 {
              printf("1%c1",a[0]);
! o8 K+ R% z* P, i   printf("\n");
6 P: c2 ~% G3 N }0 c1 e5 _+ m' K' Y% q9 u5 j+ F5 c
评论人: Colby  发布时间: 2010-3-2 12:04:06 #include<stdio.h>
4 t; m0 J( M6 I#include<string.h>7 T. Y: {: S$ a6 X: d' Q% E$ v
void main()& ]; i& E3 j1 l6 M& O
{  int i,j,k,n;6 X. @" H3 K' Z  x
   char a[50];
2 H! E  V2 O4 a. ^. S: g% ]1 T   gets(a);
: K" V5 p( T* W; H   n=strlen(a);
, w7 g( t# c$ K" `8 v
! H/ W) k1 x; u- u4 t. _/ ?   for(i=0;i<n-1; )
( V8 ^4 s) N$ n$ u6 {1 P      if(a==a[i+1])
$ d' N5 a: L7 L0 v+ ?      {  for(j=i+1;a[j]==a[j+1];j++);" o' u+ E: Y+ u% h5 t% k
          printf("%d%c",j-i+1,a);' G# O6 |# p5 I. x4 {
          i=j+1;
1 W) V0 i, p$ D0 b- `      }  M' U) {! a! o9 r8 ?/ c
      else% ?* n$ w& ~5 Q1 ?7 q
      {  if(a==1)' _( l- Y) \( M* z
            { printf("11");
- f, C1 w" F1 `! f; {4 \+ ]                 i++;
  ^. w$ n8 I1 P' M/ y1 n            }& c! A. m+ |8 W
          else0 |1 X* U0 f" x8 ?- V- t9 W
          {  for(j=i+1;a[j]!=a[j+1];j++);
5 p0 I, Y+ \, N: M9 d' _- S              printf("1");
# y' _! K( y& b6 J0 u2 j              if(j==n+1)( {+ b5 Q8 O; O0 S
                  j--;
0 c8 q' t. P* \+ ?% [              for(k=i;k<j;k++)" s7 A0 M* p$ m% M: o# `# f* |7 E3 X
                  printf("%c",a[k]);, U6 \/ I: t! k0 Z# ^
              printf("1");1 q  ?; i; a% Q6 Q
              i=j;
+ E( n: ~2 T' u7 c7 Q          }: Y) \3 A* r' C1 h) k" @
      }5 V. _3 |+ h4 K8 E# ~& z  G
      if(n==1)
9 X* y" z4 A- W+ b- b; x) g          if(a[0]=='1')- o0 n" G- X  \. }/ ~
              printf("11");
5 M0 j( u2 C* L/ g% P: |          else
4 b# i+ w( A, i0 a% w/ L4 D; O              printf("1%c1",a[0]);
+ W! Q8 W# [0 k" s   printf("\n");
& S! I) x/ n+ S9 F$ x8 C$ M }    example2:#include<stdio.h>& H$ ~) _/ W9 l% q& w
#include<string.h>
) I$ ~. D2 R1 H: D+ t( Wvoid main()
3 s: S5 j& D& O$ B# N{  int i,j,k,n;
3 r. }; _4 r2 |& D' Q   char a[50];* f2 J" C9 N: W6 A0 C6 h
   gets(a);7 q- I  j& B  q5 b
   n=strlen(a);( t  p5 R% Q: `" M

: j; Z/ _) \1 T) Y- B) R   for(i=0;i<n-1; )
7 x: L- X/ O& [7 f      if(a==a[i+1])9 [4 r! w! R8 y3 c9 R( o# E  M
      {  for(j=i+1;a[j]==a[j+1];j++);! c$ P0 I: c' B3 M# T8 D8 ^  @" {
          printf("%d%c",j-i+1,a);! W6 q4 |( z: Y* h! x/ A
          i=j+1;
* I) z! b) S: v! o      }/ {9 Y; x# w& E& H( g7 I
      else
# U! T6 L9 ~, W! |0 {1 k4 m# T6 g# Y: x      {  if(a==1)7 ?5 r  n, t% T
            { printf("11");
' F% p3 S6 Y7 Q$ h3 k, w                 i++;
7 P% k0 Y: |4 m# \            }
! C. c* a2 p1 v4 I+ j          else" K" F  L+ f6 W
          {  for(j=i+1;a[j]!=a[j+1];j++);3 T9 K0 ?: T4 a  p+ f' e- q+ z2 g
              printf("1");
$ S3 E2 I* h. j/ X+ H7 e* Z* O' {8 p              if(j==n+1)
% B9 h6 J  R1 P* l                  j--;
' L$ q3 A0 ~, |; v" g$ C* a              for(k=i;k<j;k++)0 ~* w9 x  q) P9 R
                  printf("%c",a[k]);; M/ r9 C) N% r' k& M( L- J$ g# q
              printf("1");
. l- v/ e# ]' z, t& R1 d6 o% u              i=j;4 m% I+ W" ?; W6 g% ]
          }9 H5 v' }& Q: X0 ?; F  r
      }% {8 ]4 k0 |! r, D1 y( M8 h
      if(n==1)( Y: o1 |4 d# c% o; o
          if(a[0]=='1')) o( i, |8 P' [* W
              printf("11");
" r, Y- p3 u2 K1 L3 L  \1 }# {3 e          else
9 y2 N! F( S# A8 Q# C2 v              printf("1%c1",a[0]);
/ q# _; I3 ~1 K: g   printf("\n");
' K. Z9 f5 C. R$ ~- } }* o) r" k+ `, `  T5 ~& [
   example3:#include<stdio.h>9 _( [* ^: L8 k4 `5 m
#include<string.h>% K$ s$ x! X- O$ X
void main()3 p# V( _* k9 o* t) G
{  int i,j,k,n;+ M$ v- j9 R9 b( ]7 ^
   char a[50];! N# i# ?5 v2 ?; O8 G3 q2 \
   gets(a);
9 J3 M  n( U% V: F8 K   n=strlen(a);6 G' j4 c7 n) s5 d& ?  Y
; @, b. o5 d6 a6 z9 |8 q% Z
   for(i=0;i<n-1; )! G) |3 I) T+ P! r- r* n2 c4 }: y
      if(a==a[i+1])
# ^% L5 U. E- ]. u4 v. ]- v      {  for(j=i+1;a[j]==a[j+1];j++);
4 ]5 a* |' o+ z          printf("%d%c",j-i+1,a);5 E8 y- @( P4 X/ N3 {" @* V7 ]
          i=j+1;
# d8 v6 d# q  Y* x" [: }& g      }
$ y& |2 F% C9 B8 a- Y( c      else, }7 b7 C+ ?1 I: v0 U8 r
      {  if(a==1); g! }6 y: a- l4 c4 M+ s9 d
            { printf("11");
5 Z; g% J, z; l% e1 z                 i++;
$ ?, O( `7 a: q: Q            }" y% {% D5 t- a) i* [0 t. t, a
          else  b3 m) h4 K2 x/ |. h% v5 p
          {  for(j=i+1;a[j]!=a[j+1];j++);' L9 Q6 Z* j+ x( J5 ]. \# S
              printf("1");$ A. K2 U9 F8 a6 @4 I/ N6 q
              if(j==n+1)
# I' k& L1 q3 E5 d1 T                  j--;
  U  `) ?0 j$ Z* _: B              for(k=i;k<j;k++)
* j( g3 m  c; J3 J                  printf("%c",a[k]);2 c* i2 X6 y; e& o$ N0 S
              printf("1");& G# ~, d# g  u" s6 H- H4 i3 j
              i=j;
* Y, O$ R/ `7 _! M. T( j          }+ B$ R; D7 [& ^& S! o; B% e
      }- T- E7 u' C- g4 _* n0 p; C4 S
      if(n==1)! S+ K' |$ E9 [- n0 O
          if(a[0]=='1')2 i$ Z, Z* M& `$ Z
              printf("11");  M3 x( N8 J% A
          else( H" c) `) k3 l1 O' ~, b) Z4 \
              printf("1%c1",a[0]);+ Z) m' ?% k% r7 u; T- O8 N
   printf("\n");# d+ g" M" C, D3 V& @. K
}
/ D' Z+ ~+ k4 H1 e, {      来源：编程爱好者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