1 条题解
-
0
文本拼接站:讲解
思路与 STL 接口
string 保存当前文字。APP 用 += 或 append;CUT 用 substr(l,r-l),第二参数是长度;INSERT 用 insert(p,s);FIND 用 find(s),显式判断 string::npos。空串输出 EMPTY。
复杂度
令 B 为初始串与全部字符串参数的长度总和,D 为所有修改后文档的长度总和。APP、INSERT 的复制或搬移字符数不超过该操作得到的文档长度,CUT 只复制保留片段,因此修改与文档输出的总工作量由 B+D 控制。一次 FIND 的朴素比较上界为 O((当前长度+1)·查询串长度);令全部 FIND 的该项总和为 W,查找总工作量为 O(W)。总体时间为 O(B+D+W+q),题目保证 B≤200000、D≤2000000、W≤20000000、q≤2000。存储当前文档需要 O(L),读入查询串另需 O(M),其中 L、M 分别为最大文档和查询串长度。
常见错误
把半开区间写成闭区间,导致 substr 的长度多 1;把 r 当作长度;把 npos 直接当作无符号数输出;不允许在串尾插入。
验证方法
Python oracle 独立读取操作并模拟或排序,不调用标准程序。正式数据含手算样例、边界、固定种子随机和两个最大规模用例;另做 200 次小规模差分,验证器拒绝非法状态、多余 token 及超预算的累计 FIND;正式数据另含恰达到 20000000 预算和接近预算的连续查询。common_wrong.cpp 保留上述一种常见逻辑错误,正式数据必须能够拒绝它。
C++17 参考实现
#include <bits/stdc++.h> using namespace std; int main(){ios::sync_with_stdio(false);cin.tie(nullptr);string s;int q;cin>>s>>q;if(s=="-")s.clear();while(q--){string op,t;cin>>op;if(op=="APP"){cin>>t;s+=t;}else if(op=="CUT"){size_t l,r;cin>>l>>r;s=s.substr(l,r-l);}else if(op=="INSERT"){size_t p;cin>>p>>t;s.insert(p,t);}else{cin>>t;size_t pos=s.find(t);if(pos==string::npos)cout<<-1<<'\n';else cout<<pos<<'\n';continue;}cout<<(s.empty()?"EMPTY":s)<<'\n';}}
- 1
信息
- ID
- 5255
- 时间
- 2000ms
- 内存
- 256MiB
- 难度
- 1
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者