题目链接TUOJhttps://sim.csp.thusaac.com/contest/39/problem/2反思第39次认证其实是有点可惜的可以说是有史以来离300最近的一次。为了拿200分花了一个半小时左右的时间本来不需要这么久的写出了bug只留了两个多小时做第三题思路分析正确可惜没做完没发现资料包里有题目给出的代码手敲浪费了不少时间实在是大冤种了9-21考完出成绩那周一个下午就顺着思路把代码重新写了出来要想留下考试时候只写了一半的代码可以注释掉再提交当时直接交编译失败后面下载源代码才发现这题的代码没存下来难绷但到11月才找到可以测试的地方确实本可以拿下第三题。当时就想着写一个题解但想着只有20天就期中了结果拖到现在昨天才考完咱就是说能不能别这么拖沓啊喂思路1. 数据结构与初始化数据存储jtable静态词条表大小为S初始化后固定不变dtable动态词条表大小为D可头部插入更新每条词条是键值对pairstring, string编码准备初始化十六进制字符到4位二进制串的映射mp读取哈夫曼树的前序遍历编码重建哈夫曼树用于后续解码2. 核心功能模块哈夫曼树重建(rebuildHuffmanTree)输入0表示内部节点1字符表示叶节点递归重建哈夫曼树用于二进制串到原文的解码解码函数(decode)根据重建的哈夫曼树将二进制串逐位走树0→ 左子树1→ 右子树到达叶节点时输出字符重置到根节点输入预处理(chuli)处理三种输入格式普通字符串非H开头直接返回双H开头去掉第一个H返回单H开头执行哈夫曼解码流程去掉开头的H将每个十六进制字符转为4位二进制去掉末尾指定位数由最后一位数字指定调用decode哈夫曼解码3. 三种操作模式(solve)操作1查询输入编号n若n ≤ S从jtable取静态词条否则从dtable取动态词条操作2查询并插入到动态表头部类似操作1但会将查询到的词条插入dtable头部LRU更新若n0则输入新键值对插入头部操作3仅查询类似操作1但不更新动态表代码#includebits/stdc.h using namespace std; #define endl \n #define pss pairstring,string vectorpss jtable,dtable; int S,D; mapchar,stringmp; struct Node { char data; shared_ptrNode left; shared_ptrNode right; Node(char d) : data(d), left(nullptr), right(nullptr) {} Node() : data(\0), left(nullptr), right(nullptr) {} }; shared_ptrNode root; shared_ptrNode rebuildHuffmanTree(const string s, int index) { if (index s.length()) return nullptr; if (s[index] 1) { index; // 跳过1 char ch s[index]; // 读取字符 return make_sharedNode(ch); } else if (s[index] 0) { index; // 跳过0 auto node make_sharedNode(); node-left rebuildHuffmanTree(s, index); node-right rebuildHuffmanTree(s, index); return node; } return nullptr; } string decode(string s) { string ans; shared_ptrNode troot; //temp for(int i0;is.size();i) { if(s[i]0) tt-left; else tt-right; if(t-data!\0) //根不是叶子得在转移动之后判断 { anst-data; troot; } } return ans; } string chuli(string s) { string ans; if(s[0]!H) anss; else if(s[0]Hs[1]H) anss.substr(1); else{ ss.substr(1); string str; for(int i0;is.size()-2-1;i) strmp[s[i]]; int ns[s.size()-1]-0; str.erase(str.size()-n); ansdecode(str); } return ans; } void solve() { int op; cinop; if(op1) { int n; cinn; if(nS) coutjtable[n-1].first: jtable[n-1].secondendl; //1, ...S else coutdtable[n-S-1].first: dtable[n-S-1].secondendl; //S1, ...SD } else if(op2) { int n; cinn; if(n!0){ string v; cinv; vchuli(v); if(nS) { coutjtable[n-1].first: vendl; //1, ...S dtable.insert(dtable.begin(),{jtable[n-1].first,v}); } else { coutdtable[n-S-1].first: vendl; dtable.insert(dtable.begin(),{dtable[n-S-1].first,v}); } } else{ string k,v; cinkv; kchuli(k), vchuli(v); coutk: vendl; dtable.insert(dtable.begin(),{k,v}); } } else if(op3) { int n; cinn; if(n!0){ string v; cinv; vchuli(v); if(nS) coutjtable[n-1].first: vendl; //1, ...S else coutdtable[n-S-1].first: vendl; } else{ string k,v; cinkv; kchuli(k), vchuli(v); coutk: vendl; } } } string transfer(int n) { string ans; while(n0) { ansto_string(n%2); //warn:先取到的是最后一位 n/2; //warn: / 2 } reverse(ans.begin(),ans.end()); if(ans.size()4) ans.insert(0,4-ans.size(),0); return ans; } int main() { ios::sync_with_stdio(0),cin.tie(0); for(int i0;i15;i) { char c; if(i10) ci0; else ci-10a; //WARN:i-10 mp[c]transfer(i); // coutcendl; // coutmp[c]endl; } // mp[0]0000,mp[1]0001,mp[2]0010,mp[3]0011; // mp[4]0100,mp[5]0101,mp[6]0110,mp[7]0111; // mp[8]1000,mp[9]1001,mp[a]1010,mp[b]1011; // mp[c]1100,mp[d]1101,mp[e]1110,mp[f]1111; cinSD; for(int i0;iS;i) { string s1,s2; cins1s2; jtable.push_back({s1,s2}); // coutjtable[i].firstendl; } string encodedTree ; cinencodedTree ; //WARN输入顺序错了 int idx 0; root rebuildHuffmanTree(encodedTree, idx); int n; cinn; while(n--) solve(); return 0; } /* 4 5 3 4 -5 5 0 0 3 4 */