ZOJ 3713：In 7 - 字符串編碼與長度壓縮

題目大意

給定字符串，先輸出其長度 len 的特殊編碼：將 len 轉二進制，每 7 位一組，低位在前；若有更高位，在該組最高位置 1（即加 128），最後一組最高位為 0。每組輸出兩位十六進制。隨後將原字符串每字符按 ASCII 碼輸出兩位十六進制。

編碼規則示例

• len = 0 → 00
• len = 100 (二進制 1100100) → 低 7 位 100100 = 0x64，無更高位 → 64
• len = 300 (二進制 100101100) → 低 7 位 0101100 = 0x2C，高位 10 = 2，加 128 → 130 = 0x82 → 輸出 82 2C

代碼實現

#include <cstdio>
#include <cstring>
using namespace std;

char str[5000010];

int main() {
    int T;
    while (scanf("%d", &T) == 1) {
        getchar(); // 吸收換行
        while (T--) {
            fgets(str, sizeof(str), stdin);
            int len = strlen(str);
            if (str[len-1] == '\n') str[--len] = 0; // 去除換行

            if (len == 0) {
                puts("00");
                continue;
            }

            // 編碼長度
            int x = len;
            while (x) {
                int low7 = x & 0x7F; // 取低 7 位
                x >>= 7;
                if (x) low7 |= 0x80; // 還有高位，置最高位為 1
                printf("%02X", low7);
            }

            // 輸出字符串內容
            for (int i = 0; i < len; ++i)
                printf("%02X", (unsigned char)str[i]);
            puts("");
        }
    }
    return 0;
}

關鍵點

• 長度編碼本質是 Base-128 變長整數（類似 Protocol Buffers 的 Varint）。
• 字符按 unsigned char 輸出，避免負值擴展。
• 輸入可能包含空格，需用 fgets 或 gets 讀整行。

總結

本題考察對變長整數編碼的理解與實現，代碼極短，核心是位運算循環提取 7 位並設置延續標誌位。