ZOJ 3713 In 7-bit

Very often, especially in programming contests, we treat a sequence of non-whitespace characters as a string. But sometimes, a string may contain whitespace characters or even be empty. We can have such strings quoted and escaped to handle these cases. However, a different approach is putting the length of the string before it. As most strings are short in practice, it would be a waste of space to encode the length as a 64-bit unsigned integer or add a extra separator between the length and the string. That's why a 7-bit encoded integer is introduced here.

To store the string length by 7-bit encoding, we should regard the length as a binary integer. It should be written out by seven bits at a time, starting with the seven least-significant (i.e. 7 rightmost) bits. The highest (i.e. leftmost) bit of a byte indicates whether there are more bytes to be written after this one. If the integer fits in seven bits, it takes only one byte of space. If the integer does not fit in seven bits, the highest bit is set to 1 on the first byte and written out. The integer is then shifted by seven bits and the next byte is written. This process is repeated until the entire integer has been written.

With the help of 7-bit encoded integer, we can store each string as a length-prefixed string by concatenating its 7-bit encoded length and its raw content (i.e. the original string).

Input

There are multiple test cases. The first line of input is an integer T indicating the number of test cases.

Each test case is simply a string in a single line with at most 3000000 characters.

Output

For each test case, output the corresponding length-prefixed string in uppercase hexadecimal. See sample for more details.

Sample Input

3
42
yukkuri shiteitte ne!!!
https://en.wikipedia.org/wiki/Answer_to_Life,_the_Universe,_and_Everything#Answer_to_the_Ultimate_Question_of_Life.2C_the_Universe_and_Everything_.2842.29

Sample Output

023432
1779756B6B75726920736869746569747465206E65212121
9A0168747470733A2F2F656E2E77696B6970656469612E6F72672F77696B692F416E737765725F746F5F4C6966652C5F7468655F556E6976657273652C5F616E645F45766572797468696E6723416E737765725F74
题目都看不懂直接看别人博客,才看懂题意。
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <map>

using namespace std;
char a[3000005];
int main()
{
    int t;
    scanf("%d",&t);
    getchar();
    while(t--)
    {
        gets(a);
        int len=strlen(a);
        int l=len;
        if(l==0)
        {
            printf("00\n");
            continue;
        }
        while(l)
        {
            int t1=l%128;
            l/=128;
            if(l)
                t1+=128;
            printf("%02X",t1);
        }
        for(int i=0;i<len;i++)
            printf("%02X",a[i]);
        printf("\n");
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ml

poj------(3468)A Simple Problem with Integers(区间更新)

A Simple Problem with Integers Time Limit: 5000MS Memory Limit: 131072K ...

383100
来自专栏ml

HDUOJ-------2719The Seven Percent Solution

The Seven Percent Solution Time Limit: 2000/1000 MS (Java/Others)    Memory Limi...

30650
来自专栏函数式编程语言及工具

Akka(40): Http:Marshalling reviewed - 传输数据序列化重温

   上篇我们讨论了Akka-http的文件交换。由于文件内容编码和传输线上数据表达型式皆为bytes,所以可以直接把文件内容存进HttpEntity中进行传递...

25280
来自专栏ml

hdu-----(1507)Uncle Tom's Inherited Land*(二分匹配)

Uncle Tom's Inherited Land* Time Limit: 2000/1000 MS (Java/Others)    Memory Lim...

26540
来自专栏ml

hdu 1805Expressions(二叉树构造的后缀表达式)

Expressions Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 ...

35660
来自专栏ml

uva-----11292 The Dragon of Loowater

Problem C: The Dragon of Loowater Once upon a time, in the Kingdom of Loowater, ...

32850
来自专栏xingoo, 一个梦想做发明家的程序员

HDOJ 1013

Digital Roots Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/327...

20980
来自专栏算法修养

POJ-1959 Darts

Darts Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 1286 ...

382100
来自专栏前端儿

1000. A-B

Time Limit: 1 secs, Memory Limit: 32 MB                                         ...

13210
来自专栏吾真本

CYBER-DOJO.ORG上的编程操练题目100 doorsAnagramsBalanced ParenthesesBowling GameCalc StatsCombined NumberCoun

Cyber-dojo.org是编程操练者的乐园。下面是这个网站上的43个编程操练题目,供编程操练爱好者参考。

47720

扫码关注云+社区

领取腾讯云代金券