Summary - ber 中周赛 Round 24

倒数第一我最强，worth reflecting，故记之。

T1

一开始读错题了，浪费了不知道多久。

然后后面实在不会了打了一个很丑的 \(O(n \log n)\)。

中途提示说学了双指针，但是认为那是 T3 用的，，，总之就没想到。

但是为什么呀？固定好了右端点逐渐变大，左端点也变大，那么中间的最优决策点也逐渐变大。对左端点和最优决策点维护两个指针 \(l, j\) 就好了，因为单调所以是 \(O(n)\) 的。

for (; i <= n; i++) {
		if (s[i] == '0') {
			l++;
			while (s[l] == '1') l++;
			while (j < l || (nxt[j] && nxt[j] <= i && max(i - nxt[j], nxt[j] - l) < max(i - j, j - l))) j = nxt[j];
			ans = min(ans, max(i - j, j - l));
//			cout << l << " " << i << " " << j << endl;
		}
	}

T2

这个呢，我一开始又把题读错了，然后又浪费了很久。

最后当然是得到了题解上的结论，但是不知道为什么属于是脑抽了，写了一个要把 \(a_i\) 和 \(b_i\) 分解质因数然后比一堆 \(\min\) 和 \(\max\) 的玩意（本质是一样的），而且因为细节原因挂掉了，得了 \(0\) 分。

T3

积累这个 trick：第 \(k\) 小 / 大转化成二分判断 \(\leq mid\) 或 \(\geq mid\) 的个数与 \(k\) 的大小关系。当然早就应该知道，退化了只会看到中位数二分了，，，

二分完 check 的话也是有单调性的，维护一下就好了。注意精度问题，可以直接循环二分 \(100\) 次。

T4

唯一一道 A 了的题。也浪费了挺多时间，原因是维护 Hash 应该是：

hash -= p[n - 1] * (b[i - 1] - 'a' + 1);
hash = hash * P + b[i + n - 1] - 'a' + 1;

写成了：

hash -= p[n] * (b[i - 1] - 'a' + 1);
hash = hash * P + b[i + n - 1] - 'a' + 1;