总结

今天是正月十一了，天气挺暖和，听说要降温了，最近山火频发，大家注意安全。

前面的话就少说一点，总结一下就是，考场上可以试图改变思路，可以从最开始思考的地方开始。重新看待问题，清空自己的脑子。

题解

本来不是很想写太多的，但是感觉写不少啊。

A. 相似序列

就是给你一个序列，然后每次询问两个等长的区间，问你这两个区间排好序之后是否至多只有一个同一个位置的数不同。

直接主席树 + hash 在树上二分即可。可以做到一个。

B. zzzyyds

就是有一个圆环上面有个位置编号，然后每次随机选择一个位置涂黑，这个时候如果有空格子两边相邻的都是黑的那么把它也涂黑。如果此时剩下的白色格子，那么游戏结束，否则权值加上此时黑色格子数目的次方。求最后权值的期望。

有两种做法，第一种码量小，看了让人有恍然大悟的感觉，第二种感觉如果我考场上做出来这道题可能会想到的方法，思考量可能会更大。

法一就是我们只考虑主动涂黑的格子，枚举个数，然后显然所有选法是等概率的，由于可以选择自己，所以最后乘一个就行。然后去白色的相当于插空，枚举一下额外的格子数，然后剩下的插进去个数要么是要么是的个数，可以 dp 前缀和优化解决。然后最后乘以一个就恢复到原来状态就可以啦。

法一我自认为我最开始没有这样想，这个更接近我的思路。首先打完暴力发现黑色个数相同的转移乘上的系数是一样滴，然后考虑合并一下等价类。发现一维没法转移，画一下转移的方式会想到加一个段数进去。容易发现段数和黑色个数的可重集相同的话的概率是一样的，因为在这之前相互之间是独立的。那么把这些缩了点之后所有情况概率分布是一样的，所以可以转移。就把一段当成一个点插进白色缝隙里面。由于这样子没有编号，因此我们可以钦定一个黑色点插在一个缝隙里面作为 1 号点，然后剩下的插进去。这就是小学奥数啦！几个位置选择几个位置不相邻！这就不细说了。然后考虑转移，手搓一下很容易发现几种，然后枚举方案数就行了。余下的新增一段的用总的去减其它的就行。然后几个占总的的比例就是转移的概率，然后就 OK 啦！

法一方法很简单，但是也需要掌握法二，毕竟法二对于我来说是更自然的方法，不过也需要掌握法一的思考技巧，在一个地方没走出来尝试重新读一遍题目。

P.S. 这道题读了之后由于有自环所以我好久没有想出状态是什么，所以后来想到用有向图来表示，所以自然会觉得法二更容易一些。然而如果我一开始就是想按照选的的集合来看，估计就能想出法一了。

C. 科技题

很牛魔的科技。此题暴力需要掌握使用 bitset 优化 LCS 的方法，需要学习。原题：PA2020 Tekstówka ，洛谷上评级黑。

简要题意就是两个小写字母字符串长度不超过，然后次询问两个字符串的两个子串的 LCS。首先想到猫树分治，这是很好的思路，就是将第一个串从中间劈开，然后枚举第二个的从哪里分，这样的话容易想到在分治树（猫树）或者说整体二分之类的。很好的小技巧！继上次含有时间的在上面二分之后新的小技巧！猫树！然后这样查询的话就变成的了。然后这个时候我们就只需要维护一个东西，什么呢，就是，表示两个字符串，表示与的 LCS，在猫树上每个节点都弄一个这个，容易理解。但这样复杂度不还是爆炸吗？甚至更高，因此我们有了妙妙小性质：

可以考虑网格图上的转移，由于有交点，容易证明，这里省略。

那么表明假设将放到一起，的变化前一个加以会加一个后缀，后一个加一会加一个前缀。（变化量肯定都小于），然后计一个和分别表示从转移过来前后缀的位置，手画一下的关系就容易发现规律，查询用一个前缀和就可以了。最后复杂度。实现起来如果用一下现代 C++ 的小技巧会更容易 doge。如 vector，string 之类的。

后记

时光如梭呀，哈哈。没有什么过不去的坎。今天小区里面见到一只可爱的猫猫，喵。