网站首页
编程语言
数据库
系统相关
其他分享
编程问答
隐身术
2024-11-08
P5479 [BJOI2015] 隐身术 题解
题目传送门前置知识后缀数组简介|字符串哈希|二分解法考虑分别计算出编辑距离恰好等于\(k_{0}\in[0,k]\)的答案。观察在编辑距离的存在下,长度差至多为\(k\)。考虑设\(f_{i,j}\)表示最大的\(x\)使得\(s_{1\simx}\)和\(t_{1\simx+j}\)可以在\(i\)次编
2024-11-08
#473. 编辑 & P5479 [BJOI2015] 隐身术
模拟赛出到加强版了,一点不会所以记录下。枚举每个后缀。设\(f_{i,j}\)为操作\(i\)次,长度增加\(j\),即插入的次数减删除的次数,所能匹配到的最大位置。也就是\(A\)的前\(f_{i,j}\)位匹配\(B\)的前\(f_{i,j}+j\)位。考虑转移。假如已经操作完了,那显然有\(f_{i,j}\ge