2023.8.7 模拟赛

A

有一个 01 串，只有一位是 \(1\)，你每次可以翻转一个长为 \(k\) 的串，求出使得每个位置为 \(1\) 最少翻转多少次。
其中有一些位是存在 \(1\) 的。 \(n 10^5\)

考虑求出一个点能翻转一次到哪些点，只要不碰到边界即可。
考虑线段树优化建图，建立奇偶两颗线段树。
然后 deque 优化 BFS 即可。
也可以用 set 优化，并查集等。

B

有一个括号序列，其中有通配符，问有多少个子串可变为一个括号序列。\(n 10^6\).
考虑一个子串是合法的条件。

1.长度偶数
2.若把左括号和通配符看成 \(1\)，右括号为 \(-1\)，任意前缀和非负，记这个前缀和为 \(s_1\)
3.若把右括号和通配符看成 \(1\)，左括号为 \(-1\)，任意后缀和非负，记这个后缀和为 \(s_2\)

设 \(p_i\) 为右边第一个 \(j\)，满足 \(s_1(j)-s_1(i-1)<0\)。
\(q_i\) 为左边第一个 \(j\)，满足 \(s_2(j)-s_2(i+1)<0\).
单调栈求出。

那么若区间 \([l,r]\) 合法，满足 \(r<p_l\)，且满足 \(q_r<l\).
显然是一个二维数点，即计算区间 \((l,p_l)\) 内多少个 \(q_r\in[1,l)\).
排序后树状数组即可。

C P8908

D P9379

累了。