3629. Oblivion
喜欢 ZR 的计数题么?
题解 1
O(nlogn) 做法。
方案数有两种影响因素:
- 好人还是坏人
- 给出的是 L 还是 R。
观察一下,容易发现坏人能够决定好人的选择,也就是说相邻两个坏人间的好人给出的字符是唯一的 。
具体的讲,如果相邻两个坏人是 i,j,那么中间点就是 k=⌊2i+j⌋,也就是说在 (i,k] 之间必须给出 L,在 (k,j) 之间只能给出 R。
考虑根据这个设计状态:f[i] 表示前 i 个字符不出现矛盾,并且 i 是坏人的方案数。
把转移形式化一下,我们需要找到所有 j 满足 (j,k] 都是 L,(k,i) 都是 R,令 preL[x] 表示 x 前第一个固定为 L 的位置,nxtR[x] 表示 x 后第一个固定为 R 的位置。(由于 ? 可以随便改,只需要考虑对转移有影响的字符即可)
对于这两个数组,我们可以写出约束形式:
j≥2⋅preL[i]−i
这个告诉了我们 i 对可用的 j 的左边界。
i≤2⋅nxtR[j]−j−1
这个告诉了我们 j 对于 i 的使用右边界。
接下来写出转移:
f[i]=2[s[i]=?][preL[i]=0]+j<i且j→i合法∑f[j]
其中当 s[i]=? 时答案要乘二;当 i 前没有固定 L 时 i 可以当第一个坏人。
转移主要复杂度在求和上,由于每个 i 所能用到的 j 有左边界,每个 j 对 i 也有要求,不难想到用树状数组进行维护,每个 f[j] 仅修改两次,总复杂度 O(nlogn)。
至于统计答案,只要找到所有 (i,n] 之间没有固定 R 的 f[i] 累加即可。
题解 2
O(n) 做法。
我们需要利用刚才的转移。
对于所有 1≤i<j≤n,我们将 (i,j) 视为一个转移点,并将其标在坐标系上。
现在对于每个固定的 s[k] 转化约束:
- 若 s[k]=L,则将 k>2i+j 即 i<k<j,i+j<2k 的所有转移点删除。
- 若 s[k]=R,则将所有 i<k<j,i+j>2k 的转移点删除。
观察一下剩余合法点的形状,由于初始时 i<j,也就是说所有合法转移点一定在直线 i=j 下面,所以经过所有 s[k] 的斜率为 −1 的切割,最终产生贡献的一定是两条直线,他们围成无限长的矩形或者等腰三角形。
此时我们 j 单调递增,与矩形或三角形的交为一段区间,容易发现,总共有 O(n) 个区间。
直接对所有区间做前缀和,直接进行转移,复杂度 O(n)。
