题目描述题目要求计算给定的编码序列CwC_wCw​可以分解为CuCvC_u C_vCu​Cv​的方式数其中uuu和vvv均为非空字符串且wuvw uvwuv。编码规则如下每个编码对(pi,ri)(p_i, r_i)(pi​,ri​)要么是0 c表示添加字符ccc要么是p r表示从当前位置往前ppp个位置开始复制rrr个字符添加到末尾。解码过程按顺序处理每个编码对最终得到字符串www。需要统计将编码序列CwC_wCw​拆分成两个非空前缀和后缀编码对序列的方式数使得解码后的字符串恰好对应www的前缀和后缀。输入格式输入包含多个数据块。每个数据块由若干行组成每行一个编码对若pi0p_i 0pi​0格式为0 c其中ccc为小写字母。若pi0p_i 0pi​0格式为p r其中1≤r≤p10001 \le r \le p 10001≤r≤p1000。每个数据块后有一个空行。输入以文件结束符EOF\texttt{EOF}EOF终止。输出格式对于每个数据块输出一行一个整数表示分解方式的数目。样例输入0 a 1 1 0 b 3 3 3 3 3 2 0 c输出1题目分析本题的核心是模拟解码过程并确定所有可能的拆分点。解码模拟维护一个列表或双端队列记录每次添加操作后新字符的起始位置。每次解码时若遇到0 c则新字符的位置为当前字符串长度。若遇到p r则新添加的字符是从当前位置往前ppp个位置开始的连续rrr个字符。这些字符对应的原始位置可以通过回溯得到。拆分点计数解码完成后我们得到了整个字符串www的构建历史。每个字符都有一个“来源”位置即它是由哪个编码对添加的。CuC_uCu​对应www的前缀部分CvC_vCv​对应后缀部分。CuC_uCu​必须是某个前缀且对应的编码对序列是CwC_wCw​的某个前缀。关键是要找出所有位置kkk使得前kkk个编码对解码出的字符串恰好是www的前缀且后∣Cw∣−k|C_w| - k∣Cw​∣−k个编码对解码出的字符串是www的后缀。实际上参考代码使用了一个队列cache来记录每次添加操作后新字符的索引。当遇到0 c时将当前长度加入队列当遇到p r时通过回溯找到复制源的起始位置。最终队列中的元素个数减111即为分解方式数因为最后一个元素对应整个字符串而前面的每个元素都对应一个有效的拆分点。复杂度分析每个编码对处理O(1)O(1)O(1)或O(p)O(p)O(p)总复杂度可接受。代码实现// Append// UVa ID: 520// Verdict: Accepted// Submission Date: 2017-05-03// UVa Run Time: 0.000s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intpi,ri;string line;while(getline(cin,line)){intcurrent0;listintcache;do{piri0;intidx0;while(!isblank(line[idx])){pipi*10(line[idx]-0);idx;}if(pi0)ri1;else{idx;while(idxline.length()){riri*10(line[idx]-0);idx;}}if(pi0)cache.push_back(current);else{while(current-cache.back()pi)cache.pop_back();currentri;}}while(getline(cin,line),line.length()0);cout(cache.size()-1)\n;}return0;}