CCF刷题计划——解压缩（stoi+bitset双管齐下）
解压缩
计算机软件能力认证考试系统
说实话，这道题有被打击到。
其实还好，看了半天题目，也算理解到这道题想要表达的内容了。辛辛苦苦写了好久，却发现只有40分。也就是，一遇到回溯引用部分就不行了。看了网上很多题解之后，我觉得我的代码还是大有可为的。取长补短，其他人的代码中的获取数据的方式就很nice，我首先可以在这方面优化一下，不要一口气把所有的数据都取出来。还有traceback函数也很深刻，我做到最后都没把回溯引用弄明白，直到看了其他人的代码，才知道，原来回溯引用就是引用之前出现过的，而且o、l 的两种情况的重复单元起始位置是一样的。这样就可以写成一个函数进行处理。
第二份AC代码中的bitset可以学习一下，当然，也可以自己写转二进制函数，但是别人家的总归是好用点，就当扩展知识面了。
那么就进入正题，本题可以学习到的：stoi任意进制字符串转10进制、小端转换、间断接收数据、bitset二进制处理神器
按照从前往后的顺序说，代码中，首先出现的是间断接收数据：题目到最后输入的数据量会很大，我们一个string压根存不过来，所以我们可以间断接收，要用多少就接收多少。所以我们最好封装一个函数，可以定量接收数据。
然后是 使用stoi将任意进制字符串转10进制：stoi真的是一个神器，都给我好好用他！我才知道，原来这个函数不仅可以将字符串转10进制，还可以将不同进制的字符串转10进制！如此一来，就不用像我那个40分的代码中傻乎乎编写转16进制的函数了。C++ stoi函数，字符串转整数-CSDN博客
bitset二进制处理神器：这个其实适用性不是很高，但是一旦用到那确实会方便很多。会初始化就行和转string就行：初始化bitset<n> b(s);这里的s可以是string，可以是无符号整型。bitset<n> b(s).to_string();OK，孩子，掌握到这里，就可以用bitset应付大部分的题目了。c++ bitset类用法_c++ bitset<64>-CSDN博客
最后是小端转换：实现这个的方法也很简单，你可以使用stack，当然，也可以像代码中一样从后往前遍历，i-=2。
给出我的丑陋代码和AC代码：
40分丑陋代码：
#include <iostream>
#include <string>
#include <stack>
#include <vector>
#include <cmath>
using namespace std;
#define ll long long
int s;
string d = "";
int dataLen = 0;
int r, l, p;
string ans = "";
//16进制转10进制
int To10(string x) //输入数据是16进制的
{
int temp = 0;
int e = 1;
int val = 0;
for (int i = x.size() - 1; i >= 0; i--)
{
if (x[i] >= '0' && x[i] <= '9')
val = x[i] - '0';
else val = x[i] - 'a' + 10;
temp += e * val;
e *= 16;
}
return temp;
}
//16进制转2进制
int getDataLen()
{
int p = 0; //设置指针
string byte;
vector<int>C;
while (d[p] >= '8') //比较第一字节最高位
{
byte = d.substr(p, 2);
C.push_back(To10(byte) - 128);
p += 2;
}
byte = d.substr(p, 2);
C.push_back(To10(byte)); //特殊情况特殊处理
int e = 1;
for (auto it : C)
{
dataLen += e * it;
e *= 128;
}
// cout<<dataLen;
return p + 2; //将当前的指针返回
}
bool isWord(string a) //当低两位为0的时候，也就是低位的值为 0 4 8 12的时候，说明是字面量
{
if (a[1] == '0' || a[1] == '4' || a[1] == '8' || a[1] == 'c') return true;
return false;
}
void ToSmallEnd(string& a)
{
stack<string>st;
for (int i = 0; i < a.size(); i += 2)
st.push(a.substr(i, 2));
string temp;
while (!st.empty())
{
temp += st.top();
st.pop();
}
a = temp;
}
int main()
{
cin >> s;
string str;
int n = s / 8;
n += s % 8 == 0 ? 0 : 1;
while (n--)
{
cin >> str;
d += str;
}
int pos = 0;
//先读入引导区，得到原始数据长度
pos = getDataLen(); //计算长度，返回指针
string byte;
while (pos < d.size())
{
byte = d.substr(pos, 2);
pos += 2;
if (isWord(byte)) //如果判断是字面量
{
ll len = To10(byte) / 4; //取高六位
if (len < 60) len++; //获得 l
else
{
ll cnt = len - 59; //计算后面存储字面量长度的字节个数 60对应1，61对应2
byte = d.substr(pos, 2 * cnt); //取这些字节
pos += 2 * cnt; //跟进pos
if (cnt > 1) //当需要转小端的时候再转吧，一个字节就不用了
ToSmallEnd(byte); //转化成小端的形式
len = To10(byte) + 1;
}
ans += d.substr(pos, 2 * len);
pos += 2 * len;
//cout << ans << endl;
}
else //是回溯引用
{
//低两位是01
if (byte[1] == '1' || byte[1] == '5' || byte[1] == '9' || byte[1] == 'd')
{
ll len = To10(byte) / 4 % 8 + 4;//取2-4位、加上4
int head = To10(byte) / 32;
string hb = to_string(head) + d.substr(pos, 2);
int o = To10(hb);
int startPos = ans.size() - o * 2;
ans += ans.substr(startPos, len * 2);
}
else //低两位是10
{
ll len = To10(byte) / 4 + 1; //取高六位、加上1
byte = d.substr(pos, 2 * 2); //此时后面两位存的o
pos += 2 * 2; //跟进
ToSmallEnd(byte); //将两个字节转小端
int o = To10(byte);
//cout << "l:" << len << "\to:" << o << endl;
//理解o、l:o看成是重复单元（下称单元）长度，l看成是实际重复输出的长度。
//当o<l的时候，实际输出的长度太多了，就将单元重复输出
//当o>=l的时候，实际输出不需要这么多，就输出一遍单元的内容，能输出多少就是多少
int repCnt = len / o; //计算实际输出次数
int restCnt = len % o; //计算余下的输出字节
string repByte=ans.substr(ans.size()-2*o); //将要重复输出的字节（单元的内容
//cout << "repByte: " << repByte << endl;
for (int i = 0; i < repCnt; i++) ans += repByte;
ans += repByte.substr(0, restCnt * 2); //从头开始，添加cnt个字节
//cout << "ans: "<<ans << endl;
}
}
}
int k = 0;
for (auto it:ans)
{
cout << it;
k++;
if (k == 16)
{
cout << endl;
k = 0;
}
}
return 0;
}
AC：
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
using namespace std;
using std::bitset;
#define ll long long
int pos=0; //记录位置
vector<int>vec;
string ans; //存放结果
//该函数类似于细嚼慢咽。一点点获取想要得到的数据
string readByte(int num)
{
string temp;//num表示需要获取的字节数量
char a;
for (int i = 0; i < 2 * num; i++)
{
cin >> a;
temp += a;
}
pos += 2 * num;
return temp;
}
void traceback(ll o, ll l)
{
int cursize = ans.size();
int start = ans.size() - 2 * o; //获取操作起始位置
//理解o、l : o看成是重复单元（下称单元）长度，l看成是实际重复输出的长度。
//当o<l的时候，实际输出的长度太多了，就将单元重复输出
//当o>=l的时候，实际输出不需要这么多，就输出一遍单元的内容，能输出多少就是多少
if (o >= l)
ans += ans.substr(start, l * 2);
else
{
string repstr = ans.substr(start, o * 2);
int repcnt = l / o; //计算重复次数
while (repcnt--) ans += repstr;
//剩下一点渣滓
ans += repstr.substr(0, 2 * (l % o));
}
}
int main()
{
int n;
cin >> n;
string lead, temp;
int vec_c;
while ((temp = readByte(1)) >= "80")
{
vec_c = stoi(temp, NULL, 16); //将字符串（16）进制转十进制
vec_c -= 128;
vec.push_back(vec_c);
}
//尾项弹出，特殊处理
vec_c = stoi(temp, NULL, 16);
vec.push_back(vec_c);
int length = 0; //数据原始长度
for (int i = 0; i < vec.size(); i++)
length += vec[i] * pow(128, i);
//开始接收数据
while (pos < 2 * n)
{
temp = readByte(1); //读一个字节，判断是什么数据类型
//这里直接使用高级的bitset来判断，当然，判断的方法有很多，我们其实也可以另外写函数转化，甚至可以直接比较16进制的值
//下面两个变量都是2进制
string low2b = bitset<8>(stoi(temp, NULL, 16)).to_string().substr(6, 2);
string high6b = bitset<8>(stoi(temp, NULL, 16)).to_string().substr(0, 6);
if (low2b == "00")
{
ll len= stoi(high6b, NULL, 2) + 1; //转10进制
if (len > 60) //后面用小端存数据真实长度
{
len -= 60; //存长度的字节个数
string str1 = readByte(len); //原顺序
string str2; //存储小端顺序
for (int i = str1.size() - 2; i >= 0; i -= 2) //转为小端
str2 += str1.substr(i, 2);
len = stoi(str2, NULL, 16) + 1; //数据实际字节长度
ans += readByte(len); //添加
}
else ans += readByte(len); //如果小于等于60.那就直接接收这么长的数据
}
else if (low2b == "10") //10,重复输出一段数据
{
ll l= stoi(high6b, NULL, 2) + 1;
string temp = readByte(2); //该情况需要取俩字节，o=这俩字节对应的十进制
ll o = stoi(temp.substr(2, 2) + temp.substr(0, 2), NULL, 16);
//因为只有两个字节，所以这里就直接手动转小端了。temp有4个元素，0123，23号是第二个字节
traceback(o,l);
}
else if(low2b == "01") //回溯引用
{
string high3b = high6b.substr(0, 3);
ll l = stoi(high6b.substr(3, 3), NULL, 2) + 4; //取2-4位+4
string temp = bitset<8>(stoi(readByte(1),NULL,16)).to_string();
ll o = stoi(high3b + temp, NULL, 2);
traceback(o, l);
}
}
for (int i = 0; i < ans.length(); i++)
{
cout << ans[i];
if ((i + 1) % 16 == 0)
cout << endl;
}
return 0;
}参考文献：CCF-CSP 202305-3 解压缩-CSDN博客