首页 > ACM题库 > HDU-杭电 > hdu 2707 Steganography-枚举-[解题报告]other
2014
02-14

hdu 2707 Steganography-枚举-[解题报告]other

Steganography

问题描述 :

In cryptography, the goal is to encrypt a message so that, even if the the message is intercepted, only the intended recipient can decrypt it. In steganography, which literally means "hidden writing", the goal is to hide
the fact that a message has even been sent. It has been in use since 440 BC. Historical methods of steganography include invisible inks and tatooing messages on messengers where they can’t easily be seen. A modern method is to encode a message using the least-significant bits of the RGB color values of pixels in a digital image.
For this problem you will uncover messages hidden in plain text. The spaces within the text encode bits; an odd number of consecutive spaces encodes a 0 and an even number of consecutive spaces encodes a 1. The
four texts in the example input below (terminated by asterisks) encode the following bit strings: 11111, 000010001101101, 01, and 000100010100010011111. Each group of five consecutive bits represents a
binary number in the range 0�31, which is converted to a character according to the table below. If the last group contains fewer than five bits, it is padded on the right with 0′s.
" " (space) 0
"A" � "Z" 1�26
"’" (apostrophe) 27
"," (comma) 28
"-" (hyphen) 29
"." (period) 30
"?" (question mark) 31
The first message is 111112 = 3110 = "?". The second message is (00001, 00011, 01101)2 = (1, 3, 13)10 =
"ACM". The third message is 010002 = 810 = "H", where the underlined 0′s are padding bits. The fourth message is (00010, 00101, 00010, 01111, 10000)2 = (2, 5, 2, 15, 16)10 = "BEBOP".

输入:

The input consists of one or more texts. Each text contains one or more lines, each of length at most 80 characters, followed by a line containing only "*" (an asterisk) that signals the end of the text. A line containing only "#" signals the end of the input. In addition to spaces, text lines may contain any ASCII letters, digits, or punctuation, except for "*" and "#", which are used only as sentinels.

输出:

The input consists of one or more texts. Each text contains one or more lines, each of length at most 80 characters, followed by a line containing only "*" (an asterisk) that signals the end of the text. A line containing only "#" signals the end of the input. In addition to spaces, text lines may contain any ASCII letters, digits, or punctuation, except for "*" and "#", which are used only as sentinels.

样例输入:

Programmer,
I  would  like  to  see
a  question
mark.
*
Behold, there is more to  me than you might
think  when  you read  me  the first  time.
*
Symbol for  hydrogen?
*
A B C D  E F G H  I J  K L M N  O P Q  R  S  T  U  V
*
#

样例输出:

?
ACM
H
BEBOP

地址:http://acm.hdu.edu.cn/showproblem.php?pid=2707

题意:在一篇文章中,每一段连续的空格代表一个0或一个1。偶数个代表1,奇数个则为0。把所有空格连起来得到一串0-1组成的二进制,再进行解密。每5个0-1二进制字符对应1个字母,末尾不足5个补零。二进制对应的十进制中,0代表空格,1代表A,2代表B……26代表Z,之后27到31分别代表’,-.?。按要求解密文章。

mark:暴力搞就好,题目说保证空格不出现在每行的行头和行尾,就简单多了。装逼没有好下场,1wa就wa在不想用memset,结果i+j>=cnt写成了i+j>cnt。。。

代码:

# include <stdio.h>
 # include <string.h>
 
 
 char str[110] ;
 char tab[] = " ABCDEFGHIJKLMNOPQRSTUVWXYZ',-.?" ;
 int cnt, label[1100] ;
 
 
 void gao()
 {
     int i, sp = 0 ;
     for (i = 0 ; str[i] ; i++)
     {
         if (str[i] != ' ' && sp != 0)
             label[cnt++] = ((sp&1)?0:1), 
             sp = 0 ;
         else if (str[i] == ' ') sp++ ;
     }
 }
 
 
 void Print()
 {
     int i, j, buff ;
     for (i = 0 ; i < cnt ; i+= 5)
     {
         buff = 0 ;
         for (j = 0 ;j < 5 ; j++)
         {
             if (i+j>=cnt) label[i+j] = 0 ;
             buff = buff * 2 + label[i+j] ;
         }
         putchar (tab[buff]) ;
     }
     printf("\n") ;
 }
 
 
 int main ()
 {
     gets (str) ;
     while (1)
     {
         cnt = 0 ;
         if (strcmp(str, "#") == 0) break ;
         while (1)
         {
             if (strcmp(str, "*") == 0) break ;
             gao() ;
             gets (str) ;
         }
         Print() ;
         gets (str) ;
     }
     return 0 ;
 }

解题转自:http://www.cnblogs.com/lzsz1212/archive/2012/05/21/2511885.html


  1. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧