考场上思考量不可减少
否则分数秒变弟弟，考后秒变弱智
T1
二分答案。打的稍恶心
T2
线段树维护“如果我在这个点开枪，前方点的贡献有多大”
想明白了就很好理解了
另外已经飞过去八千里的鸟还输入进来干吗？
T3
暴搜：在有意义的范围内，已知(i,j)可行
若a[i+1]==b[j+1]，则(i+1,j+1)可行
若a[i+1]!=b[j+1]，则(i+1,j)(i,j+1)可行
在暴搜的基础上打表考虑
还考虑个毛线啊然后两位AK王就打了个表猜了个规律就AC了这道题啊
以A串上的点为基准考虑
如果操作序列和A串完全匹配，那么将取到A串上位置在B串能取到的最左位置
如果和B完全匹配，则取到最右位置
那么把左右端点之间的长度的$\sum$就是答案了，秒过样例，AC！
然后完全过不去对拍
仔细观察（打表）发现，可行区间中间有零星的不可行位置
再观察，发现这些位置两侧的字母在A，B两串中恰好逆序（考场上没打表没能说服自己，学习skyh大神做法）
不可行==逆序？
充分性：假设两个字母逆序（AB BA）而且存在使两个指针分别指向这两个位置的方案
考虑最后一次操作，是A呢？还是B呢？
是A，那BA的指针就向后移动了，是B，AB的指针就跑了
所以字母逆序充分不可行。
必要性：从暴力的过程考虑。把（i，j）看成一个01矩阵，0表示不可行，1表示可行
（i，j）不可行，也即从未有（i-1，j）（i，j-1）（i-1，j-1）向它转移过来。
那么两种情况，要么（i-1，j）（i，j-1）（i-1，j-1）本来就不可行，
要么转移条件不符合，a[i-1]!=b[j-1]&&a[i]==b[j-1]&&a[i-1]==b[j]
考虑到“字母逆序”可表示为：a[i-1]!=b[j-1]&&a[i]==b[j-1]&&a[i-1]==b[j]
形式相同，那么只需充分说明转移条件不符合就可以了
尝试证明状态原本一定全部可行，即可证明转移条件不符合。
由于a[i-1]!=b[j-1]，则（i-1，j-1）可以转移到（i，j-1）（i-1，j）
只要（i-1，j-1）可行即可，不可行怎么办，反正一定存在k使（i-k,j-k）可行
这是由于不可行状态是位于可行状态之间（因为讨论的是可行状态间零星的不可行状态）
（可以理解成那个01矩阵中，一条长长的0把左下角和源点(0,0)或(1,1)阻隔开，左下的状态全都无法被转移到，全是0，不在讨论范围内）
所以考虑从左上到右下这串0的 左上角的0，显然满足a[i-1]!=b[j-1]&&a[i]==b[j-1]&&a[i-1]==b[j]
从而a[i]!=b[j]
从而满足a[i]!=b[j]&&a[i+1]==b[j]&&a[i]==b[j+1]
从而a[i+1]!=b[j+1]
从而链式递推下去，所有0全部满足a[i-1]!=b[j-1]&&a[i]==b[j-1]&&a[i-1]==b[j]
所以0的产生原因都是因为转移条件不符合，也即必须满足字母逆序的要求。
所以直接处理6种字母逆序的数量就行了
为什么不是9种
因为在可到达的范围内有相同的字母相邻的话，你可以在A串上还未进入此串相同字符前不断操作此字符，让B指针跳到期望位置的前一个，此时再让A指针移动即可达到目的。
感谢skyh教我做人。
原文：https://www.cnblogs.com/yxsplayxs/p/11740949.html