数学建模社区-数学中国

标题: acm编程竞赛题目2(Run Length Encoding） [打印本页]
作者: 厚积薄发    时间: 2010-5-6 18:38
标题: acm编程竞赛题目2(Run Length Encoding）
Run Length EncodingDescription
! V4 t0 b$ q8 v* W* d4 f: ^. ~7 `) z/ `  r- D9 g# p
Your task is to write a program that performs a ** form of run-length encoding, as described by the rules below. , J1 r) J1 f3 {9 ]

, E) i7 c: @7 V# WAny 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. 3 u9 k# Q3 R1 D2 R

2 Q' O6 ]$ q+ o- Z8 j0 eAny 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
$ E3 n: ]; O( z" I. i+ {$ }2 T" J6 {& rsequence, it is escaped with a 1, thus two 1 characters are output. 1 z$ o0 H$ J) R( m
: Q: k" t0 x0 c- [
Input
& R8 w  o% Y4 d" d% b2 v* Z* R, Y3 \6 t' X4 t/ ?
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. / c0 Q9 h$ u1 X8 t7 Z

6 t# m' V) w7 y3 l- C6 BOutput
5 ^' e. C; U7 P1 J2 h, v1 v1 m
! `& [$ i" m7 vEach 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.
: O5 |: J8 H+ B$ Z, r" s
7 E: {! r  a% g$ N; N输入样例

2 }; ]& Y9 M1 c: [0 ~# R; n% A
AAAAAABCCCC3 A/ ]# `+ E( C) }' U
12344
: c% S& Q4 j# ]5 Q. `

8 B& k; z$ c* J3 H9 L0 W

! f, c9 F+ o* ]输出样例

3 Y' ?$ S' s& z$ m- p
6A1B14C9 U; p; L/ Q7 \0 F5 w. K  C' U
11123124
' q- L9 e2 O1 x


( r( h& l- I8 R6 }, v$ X: p
+ d* X2 S8 t# X1 M$ b1 XSource
* ]! B! S" @9 }# }( U
: t/ o% I4 y7 ?2 ?+ D8 KUlm Local 2004
4 J: Y" a/ h, ]# g! i* Y4 A! T2 S
4 g2 h: j0 E4 |5 ~; dexample1:5 u# @, y: t: X% W+ k
#include<stdio.h>
# E( U: H: Q* l) g7 \: Y8 N. `#include<string.h>0 i5 _3 M2 ~0 M# m. W
void main()' b$ p& N0 ]7 d
{  int i,j,k,n;
0 Q  Z, @6 @$ k2 y   char a[50];% c; W+ f6 C  P5 N1 S* m6 ~0 e
   gets(a);
+ C+ [& X; J3 L+ \   n=strlen(a);
5 `4 c3 ~: I3 [% _* A& t6 W) a
9 |- Z& i: {/ _2 m   for(i=0;i<n-1; )
+ \+ X" k4 w( \+ Z: f      if(a==a[i+1])
2 `- d# F) d7 ?7 I      {  for(j=i+1;a[j]==a[j+1];j++);& h' ?7 i" s5 C- {
          printf("%d%c",j-i+1,a);4 o  N6 Z! T+ Q; ~* F$ {
          i=j+1;
9 R! x+ g9 J, y3 ?      }
. D/ E) Z4 d- v0 ?      else
& {4 M5 D' A( s3 }& C  ?      {  if(a==1)
$ u2 X$ S& n/ c% L            { printf("11");
" v: e, ^0 H" ]4 E" i9 l% `2 u2 j                 i++;3 M) _  H& z0 h5 o. C( Y6 O% F
            }
: g0 ?7 y1 |6 ?0 I: Z% m; ]          else) n/ m5 k' \0 {" ]
          {  for(j=i+1;a[j]!=a[j+1];j++);3 G% N3 D# {3 H. S5 V/ ^! N' M8 P/ d
              printf("1");
- R' D- X# _- a: M0 K3 n& r              if(j==n+1)
6 s; F, f1 k- L9 @                  j--;
% K" f7 s' Q$ C! Y0 ^              for(k=i;k<j;k++)7 w6 N( p# X# K7 }
                  printf("%c",a[k]);
& A# r' E# }( Z. U+ R: W2 f              printf("1");1 l% j  `, P+ F! n( T
              i=j;
2 `) j8 r9 T* r' r2 h          }
% x7 D- |( D9 S9 `      }1 F7 m% T) O% Z4 V) U4 c/ s
      if(n==1)" p: x" z6 l7 r
          if(a[0]=='1')
0 Y* J0 D( `5 Q. z! c8 S. i" D* W              printf("11");
& E' i2 ^4 F( ?2 f: Q' A. r          else
5 {6 m# M! g# K$ k              printf("1%c1",a[0]);
. `5 ~) \- F7 a3 M2 c! Y   printf("\n");' [& E* I2 t3 y7 i1 u. t4 V& }
}% r  e8 d9 X8 X* k; ~/ d6 P& Q; \
评论人: Colby  发布时间: 2010-3-2 12:04:06 #include<stdio.h>
3 J! P$ C1 V9 y1 x9 j" b#include<string.h>1 V/ B! X( @6 J: `/ f( z
void main()& @+ f. N: A' g1 I
{  int i,j,k,n;
7 m. T6 \* `; @% {" N   char a[50];
9 h& t2 ~$ `% e9 H2 G   gets(a);+ A& m* K9 M; m9 o* W# n
   n=strlen(a);* z2 p0 K5 [/ F2 S8 N

  i' G+ i0 O1 s# U   for(i=0;i<n-1; )
7 _$ j6 Y5 N4 v& s4 l4 Y* y      if(a==a[i+1]), V/ O' k2 I0 Y  T: S! \5 t: o# A
      {  for(j=i+1;a[j]==a[j+1];j++);
% E) |1 x  q$ O( _          printf("%d%c",j-i+1,a);6 x( m$ w  L0 D! ^$ Z
          i=j+1;
) t/ `& o- ^, h5 v$ F+ T      }
. P& P; A1 I5 F% g! N. T      else
; D3 c$ d( F( A5 Z; e+ V2 k& z      {  if(a==1)
, c3 w7 U$ X9 r5 n            { printf("11");' I* E# J2 p/ V) j& L. Q
                 i++;
8 A& v) L. L8 `/ h            }, @: l& ~3 Y* |% B
          else0 y; [6 X% q) K' D, K) X, T9 X( t$ M  S% l
          {  for(j=i+1;a[j]!=a[j+1];j++);. F$ [( S8 t+ p% M( g7 H
              printf("1");
  p! B, I& D7 z# B7 e& I( l! H' D              if(j==n+1)
+ X0 J- M" d# w7 m% w                  j--;! @0 z( z; U6 p5 G$ Q% K
              for(k=i;k<j;k++)- i( u. f, ~" Y: P# i" p$ ?
                  printf("%c",a[k]);4 Y% }9 T9 ]# ]
              printf("1");
# _9 w; E8 i# Q, x  o              i=j;
3 z& C# O) K, @2 N( t. V          }
: J2 k6 C, `& ~' `& u) d      }, @% e8 c/ H. c% z+ D/ J
      if(n==1)! |/ V1 J4 T& N' h( t- _
          if(a[0]=='1')
' h0 d1 ]' E& z$ b3 G" ]5 `* r              printf("11");7 J% O4 [$ l" B" ~; b
          else
) ^4 |& `' S8 }6 q9 S6 v              printf("1%c1",a[0]);0 X* Z+ |1 g2 a& _
   printf("\n");
' C+ e" S) H* B3 D9 o) k' F }    example2:#include<stdio.h>
1 _3 A0 @3 J- C: d, x$ T#include<string.h>3 D2 |) ]$ X9 S
void main()
( ^5 J( x: B, W- V$ _) X3 c{  int i,j,k,n;
* k7 L, U/ `9 ~! K1 S, o   char a[50];
+ q) r* T- d& e& K( u( u' J   gets(a);
: ?# c7 {: ]0 d# @  T/ a+ W   n=strlen(a);
+ S3 J$ `5 y, `% x7 E- v9 d' |4 Q, Q3 G
   for(i=0;i<n-1; )6 S" q& {( v" d, B9 b) U
      if(a==a[i+1])
  D- n0 N; v) k5 y" F9 [& k* p( v4 q      {  for(j=i+1;a[j]==a[j+1];j++);
" w, Z9 ~8 W8 t" |' B1 _          printf("%d%c",j-i+1,a);) Z+ ]7 B4 D3 l( a7 M1 w! }( O
          i=j+1;9 p, P4 h  ?5 v& ^" V
      }
6 u% C7 G/ F& Y7 b: J      else3 J9 X( x! h# z. @, t8 a3 P
      {  if(a==1)" F/ o4 n$ V) ?+ A  B8 @/ Y6 ?$ Z
            { printf("11");
3 P' }* e4 J! P7 O+ J4 b                 i++;# d, x& n5 S- i2 w) R/ q" }
            }
/ \. d" F* C! C+ m! w          else
# {+ [) U' y$ d8 |          {  for(j=i+1;a[j]!=a[j+1];j++);8 A$ k$ f; D9 O- \3 J9 }! C
              printf("1");' j5 A, o2 ^: K! r, Z
              if(j==n+1)
& o2 p& D; `2 Y2 H                  j--;
4 q- W- w6 |2 R1 ]; R) t$ M  b9 U              for(k=i;k<j;k++)
4 U% I2 C  C3 F8 g0 d) K                  printf("%c",a[k]);
% ]/ |8 L0 s0 i; c% Y              printf("1");- [9 N6 U$ j& P8 p$ ^2 g
              i=j;
: Y7 z! ~& X' ]) ~* R          }; V) D9 P# l. x5 n  M0 f+ m; S
      }  X8 k( I5 q  ~
      if(n==1)
5 v$ U; j0 y5 w          if(a[0]=='1'); E0 y! ^; z6 i# m1 I
              printf("11");7 x, }4 @1 G& l8 x7 o
          else
- X" Y# G  Z) U% a; N; V9 i              printf("1%c1",a[0]);' o8 D( r5 P9 l9 Z* A' [0 K1 B
   printf("\n");: c! G  C( R6 Q+ U1 V+ q0 p
}5 f4 L: @9 U, F* ?7 }4 I8 W3 e7 x
   example3:#include<stdio.h># l8 r8 {% o: C
#include<string.h>/ M5 G$ ^7 ]2 E: g# D5 h& n
void main()
1 D' e! Z" S* R{  int i,j,k,n;7 ~% K/ y  k1 w+ Z
   char a[50];* c% M6 M# s' [# v# u% [
   gets(a);
6 s6 m, E/ N' Q, a& ?   n=strlen(a);/ ~" B7 A2 n  f) t
6 e. l6 W7 P, Z4 K6 `2 Z$ f6 h$ T) Y
   for(i=0;i<n-1; )4 m2 S, `/ v) v. V
      if(a==a[i+1]); H8 M5 H( ~1 k' S
      {  for(j=i+1;a[j]==a[j+1];j++);
4 F  M! C! ~, P3 ]          printf("%d%c",j-i+1,a);& n4 |$ W* y2 A& ?4 Q$ b$ i
          i=j+1;
* Q5 C/ k: q( a& [1 ?5 |4 ?, S/ m- e0 j      }
) C) k7 M! e8 _, A9 ?1 B% j9 c      else; \3 H$ t8 t8 ~2 ?
      {  if(a==1)
/ p3 b' Q7 @# Q) }            { printf("11");' J7 ?$ P3 _3 n8 h) K& P. t
                 i++;$ V7 k; D/ |$ h& o4 {( @4 y( r
            }
% }( h9 a2 T3 p          else7 x: m. W2 Y+ l% C6 H
          {  for(j=i+1;a[j]!=a[j+1];j++);
( E, m6 |9 D: ]; A' L              printf("1");
- z: B3 d/ X" O5 [- O" I              if(j==n+1)
5 e) m- D4 X6 J" v# K" \( b                  j--;; \5 y( z! Y. ]# V$ I) [1 a
              for(k=i;k<j;k++): p; o* P7 R8 |3 P
                  printf("%c",a[k]);
" L5 c, B) ~. f! O2 @              printf("1");
9 d: X7 K2 D% H5 U              i=j;
/ Y1 }# D( O7 s9 Q% r' A          }
( _- b+ q2 h1 h3 E( P$ [2 o      }0 ^( a) Q  ]2 a! y- C, @
      if(n==1)
7 Q3 R4 d% ?8 T          if(a[0]=='1')2 P1 h- C' G! R2 Q9 g: n9 j2 U
              printf("11");
: {5 v1 R& H7 L5 H+ B& K) _$ Z# T          else. l. `- C& E3 Z5 [/ }& b$ C
              printf("1%c1",a[0]);
0 x% o; D( S) d* X2 h   printf("\n");( L' s, [6 E) u& g$ U6 G0 Y
}4 k& i! R' |5 b' e$ G7 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