首页 > ACM题库 > HDU-杭电 > hdu 4241 QR待解决[解题报告]C++
2015
05-23

hdu 4241 QR待解决[解题报告]C++

QR

问题描述 :

QR Codes (the smallest, which is 21 pixels by 21 pixels, is shown below) are square arrays of black or white pixels (modules) which include Position Detection Patterns (the square bull’s-eye patterns), Timing Patterns (the alternating black and white lines), Alignment Patterns in larger QR Codes , Format Information (the stippled pixels), Version information in larger QR Codes and Data and Error Correction Codewords (gray 8 pixel blocks).
Route Redundancy

The 21-by-21 QR Code has 26 data and error correction codewords. At the lowest error correction level for this code, 19 are data codewords and 7 are error correction codewords. Data may be encoded as numeric at 3 numbers per 10 bits, as alphanumeric at 2 characters per 11 bits, as 8 bit bytes or as Kanji at 13 bits per character. Data is encoded in groups of(mode,character count,character data bits).The mode can change within the data stream. The mode is specified by a 4 bit code and the character count by a varying number of bits depending on the mode and QR Code size. For the 21-by-21 code, the character count bits are:
Route Redundancy

The entire data stream ends in the termination code which may be truncated if there is not enough room. Any partially filled codeword after the termination code is filled with 0 bits. Any remaining codewords are set to 11101100 followed by 00010001 alternating.
Numeric strings are encoded 3 digits at a time. If there are remaining digits, 2 digits are encoded in 7 bits or 1 digit in 4 bits. For example:

12345678 -> 123 456 78 -> 0001111011 0111001000 1001110

Prefix with mode (0001) and count (8 -> 0000001000) is (4 + 10 + 10 + 10 +7) bits:

0001 0000001000 0001111011 0111001000 1001110

Alphanumeric strings encode the haracters (<SP> represents the space character):

0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ<SP>$%*+-./:

as numbers from 0 to 44, then two characters are encoded in 11 bits:

<first char code5> * 45 + <second char code>

if the number of characters is odd, the last character is encoded in 6 bits. For example:

AC-42 -> (10,12,41,4,2) -> 10*45+12=462, 41*45+4=1849, 2->00111001110 11100111001 000010

Prefix with mode and count is (4 + 9 + 11 + 11+ 6) bits:

0010 000000101 00111001110 11100111001 000010

The 8 bit binary and Kanji modes will be straightforward for the purposes of this problem. Kanji codes will just be opaque 13 bit codes; you need not decode the characters they represent, just the hexadecimal values. For example:

8 bit 0×45 0×92 0xa3 -> 01000101 10010010 10100011

Prefix with mode and count is (4 + 8 + 8 + 8 + 8) bits:

0100 00000011 01000101 10010010 10100011
Kanji 0x1ABC 07×0345 -> 1101010111100 0001101000101

Prefix with mode and count is (4 + 8 + 13 + 13) bits:

1000 00000010 1101010111100 0001101000101

To illustrate forming the 19 codeword content of a QR Code, combine the first 3 sequences above (for numeric, alphanumeric and bytes). Concatenate the bits, split into 8bit code words add the termination codeword, any fill bits and fill bytes (41 + 41 + 36 data bits + 4 bit termination code = 122 -> 6 fill bits are needed to get 16 bytes, and to fill out the 19 bytes, 3 fill bytes are needed):

0001 0000001000 0001111011 0111001000 1001110
0010 000000101 00111001110 11100111001 000010
0100 00000011 01000101 10010010 10100011
0000 000000 11101100 00010001 11101100

split into 8 bit codewords:

00010000 00100000 01111011 01110010 00100111 00010000 00010100 11100111
01110011 10010000 10010000 00001101 00010110 01001010 10001100 00000000
11101100 00010001 11101100 -> HEX 10207B72271014E77390900D164A8C0EC11EC

Write a program to read 19 codewords and print the orresponding data.

输入:

The first line of input contains a single integer P, (1 <= P <= 1000), which is the number of data sets that follow. Each data set is a single line of input consisting of the data set number, N, followed by a single space and 38 hexadecimal digits giving the 19 bytes of QR Code data. The valid hexadecimal digits are 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E and F.

输出:

The first line of input contains a single integer P, (1 <= P <= 1000), which is the number of data sets that follow. Each data set is a single line of input consisting of the data set number, N, followed by a single space and 38 hexadecimal digits giving the 19 bytes of QR Code data. The valid hexadecimal digits are 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E and F.

样例输入:

4 
1 10207B72271014E77390900D164A8C00EC11EC 
2 802D5E0D1400EC11EC11EC11EC11EC11EC11EC 
3 20BB1AA65F9FD7DC0ED88C973E15EF533EB0EC 
4 2010B110888D9428D937193B9CEA0D7F45DF68 

样例输出:

1 16 12345678AC-42E\92\A3
2 2 #1ABC#0345
3 23 HTTP://WWW.ACMGNYR.ORG/
4 36 3.1415926535897932384626433832795028


  1. 看到韩国棒子就可劲的砸钱!!八百万,能救治中国人多少个了?特么的,看到就生气!当初干嘛不直接专机遣送回去?装什么菩萨?!!

  2. 就是,比韩国还不要脸的,最不要脸最无耻的就是四大发明了,英国一个野鸡教授折腾出来的东西,变成了我国的金科玉律,拿来蒙骗无知群众,一骗就是几十年。智商低没救啊。

  3. 就是,比韩国还不要脸的,最不要脸最无耻的就是四大发明了,英国一个野鸡教授折腾出来的东西,变成了我国的金科玉律,拿来蒙骗无知群众,一骗就是几十年。智商低没救啊。

  4. 就是,比韩国还不要脸的,最不要脸最无耻的就是四大发明了,英国一个野鸡教授折腾出来的东西,变成了我国的金科玉律,拿来蒙骗无知群众,一骗就是几十年。智商低没救啊。

  5. 就是,比韩国还不要脸的,最不要脸最无耻的就是四大发明了,英国一个野鸡教授折腾出来的东西,变成了我国的金科玉律,拿来蒙骗无知群众,一骗就是几十年。智商低没救啊。

  6. 就是,比韩国还不要脸的,最不要脸最无耻的就是四大发明了,英国一个野鸡教授折腾出来的东西,变成了我国的金科玉律,拿来蒙骗无知群众,一骗就是几十年。智商低没救啊。

  7. 就是,比韩国还不要脸的,最不要脸最无耻的就是四大发明了,英国一个野鸡教授折腾出来的东西,变成了我国的金科玉律,拿来蒙骗无知群众,一骗就是几十年。智商低没救啊。

  8. 就是,比韩国还不要脸的,最不要脸最无耻的就是四大发明了,英国一个野鸡教授折腾出来的东西,变成了我国的金科玉律,拿来蒙骗无知群众,一骗就是几十年。智商低没救啊。

  9. 就是,比韩国还不要脸的,最不要脸最无耻的就是四大发明了,英国一个野鸡教授折腾出来的东西,变成了我国的金科玉律,拿来蒙骗无知群众,一骗就是几十年。智商低没救啊。

  10. 就是,比韩国还不要脸的,最不要脸最无耻的就是四大发明了,英国一个野鸡教授折腾出来的东西,变成了我国的金科玉律,拿来蒙骗无知群众,一骗就是几十年。智商低没救啊。

  11. 就是,比韩国还不要脸的,最不要脸最无耻的就是四大发明了,英国一个野鸡教授折腾出来的东西,变成了我国的金科玉律,拿来蒙骗无知群众,一骗就是几十年。智商低没救啊。