题目描述
题目要求计算给定的编码序列CwC_wCw可以分解为CuCvC_u C_vCuCv的方式数，其中uuu和vvv均为非空字符串，且w=uvw = uvw=uv。编码规则如下：
- 每个编码对(pi,ri)(p_i, r_i)(pi,ri)要么是
0 c（表示添加字符ccc），要么是p r（表示从当前位置往前ppp个位置开始，复制rrr个字符添加到末尾）。 - 解码过程按顺序处理每个编码对，最终得到字符串www。
需要统计将编码序列CwC_wCw拆分成两个非空前缀和后缀编码对序列的方式数，使得解码后的字符串恰好对应www的前缀和后缀。
输入格式
输入包含多个数据块。每个数据块由若干行组成，每行一个编码对：
- 若pi=0p_i = 0pi=0，格式为
0 c，其中ccc为小写字母。 - 若pi>0p_i > 0pi>0，格式为
p r，其中1≤r≤p<10001 \le r \le p < 10001≤r≤p<1000。
每个数据块后有一个空行。输入以文件结束符（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//// 版权所有（C）2017，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intpi,ri;string line;while(getline(cin,line)){intcurrent=0;list<int>cache;do{pi=ri=0;intidx=0;while(!isblank(line[idx])){pi=pi*10+(line[idx]-'0');idx++;}if(pi==0)ri=1;else{idx++;while(idx<line.length()){ri=ri*10+(line[idx]-'0');idx++;}}if(pi==0)cache.push_back(current++);else{while(current-cache.back()<pi)cache.pop_back();current+=ri;}}while(getline(cin,line),line.length()>0);cout<<(cache.size()-1)<<'\n';}return0;}
