数学建模社区-数学中国

标题: acm编程竞赛题目2(Run Length Encoding） [打印本页]
作者: 厚积薄发    时间: 2010-5-6 18:38
标题: acm编程竞赛题目2(Run Length Encoding）
Run Length EncodingDescription
* F5 A' k$ C; D7 o" b
* i! [! }* J4 ^5 uYour task is to write a program that performs a ** form of run-length encoding, as described by the rules below.
1 G3 S  j8 Y% u! Q- |0 N+ _& M( W( H. b* X/ s
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.
  Q' G8 v; x) i, [& W6 w  H1 s% f/ o& p. Z+ {: {
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 . q' d2 [, G) e5 L& J& L% f* w
sequence, it is escaped with a 1, thus two 1 characters are output.
8 M0 d1 n; |4 ^: H1 ^9 {! I1 z- ^% }6 Z: W, X$ g3 J7 `
Input
" M/ c* M% A. q  M  v1 u0 z4 A4 Z' Z3 o: W1 j. ^2 v+ v2 {# A+ g
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.
/ H% F: _/ l1 v" w
4 f1 E7 S! O/ u  F: pOutput
* k. Q, w( W4 }0 J+ p, _# J
5 G; I! M' ~# |7 Q$ UEach 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. 3 H2 @+ V& R) Z  ?* u. _* ~9 n
% I) E" j1 b- M; l- P
输入样例


/ m" u" I2 T7 z, {% mAAAAAABCCCC$ w, l( [; Z. B. s  _- O
12344( h! e% P/ O) C  l9 Z1 P

. t( R$ o  Y! S! F0 F* s5 l) ~

" G9 Q- A. s: C& G4 [8 N8 \输出样例


9 @: x5 V6 F& c- j6A1B14C
( x# R, @' e- y% w6 L11123124
8 T  H8 v5 q, I  h8 R

1 g8 {" [  I5 h  u4 S0 k; C
' I7 B7 `$ J( ~5 Q6 m: a
Source: \  B5 o6 N# t
0 ]! l7 ]/ X5 X; _+ s! s9 B
Ulm Local 20047 i' U+ F7 W1 `# a+ _6 H0 N

0 F) y2 j9 f, |8 D- eexample1:! l1 h* D% H7 u' _" W2 Y' i! P3 v
#include<stdio.h>" ?) n. ?/ V8 p; h' P5 U) P
#include<string.h>
" @$ f, d/ [5 P( T% Avoid main()
0 C* \/ _# V( Y1 H9 w{  int i,j,k,n;
( |2 `: l7 e) F' \   char a[50];: n. t. _! V$ H" ^
   gets(a);
8 l/ y6 Q5 f4 a, Y- e   n=strlen(a);' m; g6 g6 A/ m( d% ]
0 `* {% l- p( \# O9 A0 D, c
   for(i=0;i<n-1; )
3 B+ z. d: `  u# W# A8 o      if(a==a[i+1])" `0 k6 F" a$ {! {
      {  for(j=i+1;a[j]==a[j+1];j++);
# }6 F/ m, i6 H- h          printf("%d%c",j-i+1,a);9 b) @+ r+ s  }0 f/ s
          i=j+1;) r2 G" O* O* r, N! [6 g3 L9 a
      }
6 _. Z6 w4 h# @3 L. R      else" N) d1 i4 ]/ [8 Z1 @6 a
      {  if(a==1)
5 G" G5 @9 y" Y5 h            { printf("11");/ K4 j) c8 O! l
                 i++;0 O) U  e  Z" |9 H% a1 P
            }
. E8 ^- x4 T/ \: N1 T          else
9 p; p/ s3 G+ c5 \8 n( z# Y: Y          {  for(j=i+1;a[j]!=a[j+1];j++);
1 J" ~: e7 j4 e) v7 o              printf("1");
% p7 l9 n3 O( ^$ U6 J3 z$ k              if(j==n+1)& h; T3 I3 k- x- q, `1 S4 C5 i
                  j--;
: {& `% Q" N/ J" A7 U1 Z              for(k=i;k<j;k++)
1 ]1 i3 }( G* z1 C                  printf("%c",a[k]);) Q: w4 T/ x" Z  v: v4 f2 D8 _  [
              printf("1");* {0 h9 f5 r, A- V3 D, q
              i=j;( I# ~, V0 @' _& d+ q2 g
          }
3 G1 X1 J7 I2 ~$ ], ^& z      }
% D1 h) r/ e3 D4 E9 P4 V      if(n==1). @) O* Q1 q+ |! |, O( y
          if(a[0]=='1')
7 V3 [2 J3 [# t3 A5 u              printf("11");
: t! b* F; N4 z8 W6 G- ~          else
4 \4 R- @; U8 K$ t: j: l              printf("1%c1",a[0]);
2 j8 ]- o% `- b2 e   printf("\n");% K% L6 p$ j4 @0 X3 @/ Z
}2 X& k; Y: @: Y. W
评论人: Colby  发布时间: 2010-3-2 12:04:06 #include<stdio.h>
% @* ?+ y/ N; s, q+ i% d% ]: V#include<string.h>" L. N; X- d( }, F: u) H
void main()
8 u# }6 S% t( f& A5 t! X{  int i,j,k,n;, v" J% r( J7 V3 i' u/ R! M! E
   char a[50];& @, c6 x) ^; G3 p6 }( P: E, q
   gets(a);5 Y+ e  s9 n  t, e
   n=strlen(a);9 t' w& {) H5 y: P5 m* y
! B6 H8 p9 K9 C% E+ {# L+ R
   for(i=0;i<n-1; )
4 j# b* k' [& [5 t5 d4 y      if(a==a[i+1])
8 L) `- g! r. x& Q  S      {  for(j=i+1;a[j]==a[j+1];j++);
7 ]+ U2 x% I6 Y$ w7 P          printf("%d%c",j-i+1,a);
' M2 R$ N. V, m' ?3 ]* D0 i0 D          i=j+1;8 T+ ]6 E: T: B* s; n
      }
+ A9 w; a7 d) V0 H: {1 m& x, P      else
2 u, i( `- z2 s      {  if(a==1)9 [. e; i) t' p9 S; C% r: T& L
            { printf("11");$ Z4 }# [  p! I# g- d. Z
                 i++;& a* l; l% e2 C! [$ {
            }
/ S% N4 E) D+ c$ G- |          else9 Q, u! h2 c5 _0 Q
          {  for(j=i+1;a[j]!=a[j+1];j++);
0 j2 |1 I4 l# }7 l: ?1 f              printf("1");  |9 w3 @: ^* {3 S
              if(j==n+1)
, S) [4 z% Z. x8 \' A$ a4 V3 R                  j--;
% A. P3 p' v) i9 [$ @              for(k=i;k<j;k++)
3 Z- c. s3 i8 q# a- e                  printf("%c",a[k]);
: ^8 ?% g. }/ r% P/ M              printf("1");
1 ^- F' R7 m6 I  s5 G6 N; s7 h              i=j;
! g9 h( h! G. m! x* G* A- f          }% P- z3 o% g! Y' Z( K) b# R
      }
6 T0 R. k. |: f( r: D8 _      if(n==1)% d8 H0 n5 l( l2 R
          if(a[0]=='1')
( ]3 u) J) D- I. b6 A, D              printf("11");. j, P$ H7 y3 d5 Y, g: t9 I# s
          else
% P8 L) k8 G. C0 L9 R! P7 g              printf("1%c1",a[0]);& i4 `! W7 x3 `2 H; M; @; {& T5 a7 `
   printf("\n");
) A: _6 W7 K, e0 C: t" }# {( B }    example2:#include<stdio.h>3 f- O% `* O3 y; d+ l7 \; C
#include<string.h>
/ `8 P2 n8 ~" |* ?4 Bvoid main()+ H; q! w; l) s( ?
{  int i,j,k,n;5 U+ f6 R! Q+ d( T
   char a[50];
! D9 e$ p8 ~5 c; B0 ?+ ?$ a1 Q   gets(a);/ ?, d4 G/ L( q# \2 J" r, r
   n=strlen(a);% b: D( e- R! e+ e" s0 F2 G. }7 V3 S
& n/ e# O' d* ]5 u
   for(i=0;i<n-1; )1 e3 m, S7 A# Z  S% k) o
      if(a==a[i+1])
, D9 ~( R5 Y' D; r5 J3 o      {  for(j=i+1;a[j]==a[j+1];j++);! \' {( R6 E; ?: Q9 o- }1 s
          printf("%d%c",j-i+1,a);
( k: C$ K7 }! s: l3 ]& o          i=j+1;
2 N8 b. E4 l& Z( U3 r* d      }
5 D0 c) F" L- m4 X" r      else. U/ P' m, l3 J& N1 G3 m: K% N
      {  if(a==1). S% L  ?  r; K1 D4 ]
            { printf("11");
( Y" |: z) l/ a  ^3 c                 i++;
, `: e9 |5 m- f6 u            }1 [: A: m9 G; h1 S
          else
5 a9 l' ]" f- x6 ^" P! t1 t. j9 ]          {  for(j=i+1;a[j]!=a[j+1];j++);1 }# [+ c1 R5 K+ p. P4 ]0 O
              printf("1");2 t6 Q& G3 J. h0 h
              if(j==n+1)# w8 c7 n3 F; S  R4 _1 w/ M
                  j--;
# i+ g& S" E+ Z- g              for(k=i;k<j;k++)
: @5 S% P8 A, s' S: [                  printf("%c",a[k]);  z8 S: o( g- A  @
              printf("1");
# P* k- B( F8 K0 w2 T9 d              i=j;
7 L& \0 @" K7 I- `. @          }$ Y* h' G( t# [0 [- }  t. ?
      }
( i% D! e3 W: S$ @      if(n==1)
( z( A8 _5 Y& W; d2 r( r          if(a[0]=='1')+ a  O5 N6 k$ R& Q. A
              printf("11");
9 m) }/ e4 E9 X$ a          else
' Y4 u) v% w, \) K! M  T5 t              printf("1%c1",a[0]);
& Y) ?& `6 o* V( d/ N   printf("\n");
* P  m  C. ?4 U }" V  p. R2 _4 e+ L; b) D
   example3:#include<stdio.h>
. d& S2 b5 D9 s  g$ h: O* @#include<string.h>
# X# b' t( Z5 W1 |void main()4 k; h+ @% O1 Q
{  int i,j,k,n;
7 G; e# }' {9 p( M$ z6 G   char a[50];! w8 u1 L7 `( ~$ I0 E  g, U
   gets(a);
% }1 ~' t$ o  v' e, f% H6 |% a5 V, j   n=strlen(a);
  \' R* |* M& U8 H. q- d# ?1 z4 a; g3 T  u( j
   for(i=0;i<n-1; )
' ]3 n- T8 m7 q( G1 A$ X$ @. C: Z      if(a==a[i+1])" L/ i6 H; |$ I* [: U0 ?% \
      {  for(j=i+1;a[j]==a[j+1];j++);3 n; @% \/ o6 a
          printf("%d%c",j-i+1,a);
  j+ |1 a* u7 C2 j& Z          i=j+1;8 K  A6 b* @* K4 ]: _5 ~* _/ [
      }0 m5 A' P1 z+ D: s
      else
* T6 F3 i- j! j0 n' O9 z      {  if(a==1)
% I# n; i( y0 d6 ]3 v            { printf("11");/ \- i. l  S8 \4 H7 t5 `2 p2 q$ \
                 i++;
9 V4 M9 E& d$ y0 e3 }            }
5 i7 e7 Q7 c! b+ z          else6 C% _9 p& J5 {2 v0 c- b
          {  for(j=i+1;a[j]!=a[j+1];j++);
# S# H+ b. V$ a7 P( C) V; a              printf("1");
- o1 w) Q3 e2 v+ M2 V$ y( P              if(j==n+1): E( h, C  u. ^  S( ^
                  j--;
1 w" K* \7 k9 o. w& ^5 n' m              for(k=i;k<j;k++)
, w& |# G; X0 |7 Q+ ?- ?! i/ a                  printf("%c",a[k]);, Q5 T: D  y2 h; G/ O/ a; m: H; M. q
              printf("1");% [" `1 J1 X$ k. p9 h6 t- Y
              i=j;) B; K1 I" L1 Z
          }
0 `) A* b/ ]# h" {; a5 q      }# W$ ~" d* a* i3 o5 Q) u
      if(n==1)1 q, ^( |, Y9 G5 w4 c; G" l+ ?
          if(a[0]=='1')8 ~( [! g) }* F4 g8 S
              printf("11");& `" ]6 }3 ^+ V4 N: x' d% w
          else' K7 M/ X! W1 W2 C0 K& \
              printf("1%c1",a[0]);
0 t; X5 H) O+ f& T- ~4 W$ O   printf("\n");5 o# p* [9 f0 b* Q- X4 `
}8 J  ?( A+ n* z/ \
      来源：编程爱好者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