UVa 520 Append

题目描述

题目要求计算给定的编码序列CwC_wCw​可以分解为CuCvC_u C_vCu​Cv​的方式数，其中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;}