NOIP2024集训Day57 哈希
NOIP2024集训Day57 哈希
A. [CF213E] Two Permutations
考虑到都是排列，值域连续，于是 \(a\) 都加 \(x\) 之后相当于在值域上平移了一段，也是连续的。由于要进行比较，个很容易想到哈希。\(a\) 的哈希值很好维护，每次平移一位加上 \(\sum base^i\) 即可。
考虑如何快速取出 \(b\) 中在这段值域内的数的哈希值。
不妨设 \(id_i\) 表示数 \(i\) 在 \(b\) 中出现的位置。值域类似一个滑动窗口，当 \(i\) 进入的时候就在 \(id_i\) 插入 \(i\)，删除同理，用线段树可以简单维护处哈希值。
然后注意一下，该开 ull 的变量就要开 ull，要么就写 #define int unsigned long long。本人因为这个调了 30 min。
B. [CF961F] k-substrings
从 \(T\) 串的中心开始向两边扩展。首先处理串中心的 \(k\) 子串：如果 \(T\) 串长度为奇数，则 \(ans=-1\)；如果长度为偶数，则 \(ans=1\) 或 \(-1\)。
接着开始向两边扩展。下一个的最长前后缀长度最多是上一个的长度 \(+2\)，最小是 \(-1\)。枚举每一种情况，用哈希来判断是否能成立。