做题记录

2024-07-03 Views 做题记录830字4 min read繁

Abstract Ynoi.

不难想到可以先使用树剖维护这个东西。

由于每一个二进制位是互相独立的，所以可以记录当前位是 0/1 在当前区间从左到右或从右到左后能否成为 1。可以开 k 棵线段树维护，复杂度 $O(n\times \log_2^2n\times k)$ 。

仔细观察 pushup，可以将 k 棵压成一颗，记录当前区间从左往右或从右往左后的。

证明题？

将 a -> 1，b -> 2，则 $\bmod 3$ 结果不变。 $p(s)=\sum (s_i-a+1) \bmod 3$ 。

结论（不会证明）：s 变成字符 c 的 充要条件 是 $p(s)=p(c)$ 且 s 有相邻FDSA

相同（即不为 ababa... 或 babab..）。

前面贪心匹配，注意最后剩下的 p 值为 $0$ 。

dp 即可。使用刷表发， $dp_i$ 表示前 $i$ 个数的答案，每次在当前序列末尾加上一个 a 或 b，注意加答案时要保证剩下的 p 值为 0。 $a_i=p(s[1,i])$ 。

dp_{nxt_{i+1,(a_i+1/2) \bmod 3}} +=dp_i

CF3200

《面对做法构造题目》

奇妙构造+奇妙证明？

考虑这件事情有一个明显的必要条件是：任何时刻相邻两个亮着的灯必须颜色不同。

对于时间到这枚举，可以使用 set 维护前驱和后继，当 $i = col$ 时， $lst_i \not=col$ ， $nxt_i \not= col$ 。

~~cyz说~~ 可以归纳证明这也是充要条件。

也可以证明， $col$ 的范围是 $\log_{\frac{3}{2}}N$ 。

然后就做完了。。。

码量虚树，为何不改？

$\sum m \le 3 \times 10^5$ 套路建虚树，暴力是好做的，思考如何在虚树上做。

答案 = 为在虚树上的点的贡献 + 不在虚树上的点的贡献。

设距离节点 $i$ 最近的关键节点为 $p(i)$ 。

复杂度是 $O(\sum m\times \log_2n)$ 。

又是证明题？

自行模拟或证明：只可能有两种操作，取 $1$ 个石子或取 $1$ 堆石子。

$f_{l,r}$ 为 $[l+1,r]$ 没动，让 Firstleft 赢， $a_l$ 的最小值。 $g_{l,r}$ 为 $[l,r-1]$ 没动，让 Secondrigtht 赢， $a_r$ 的最小值。

若 $a_1<f_{1,n}$ ，则 Secondright 赢，否则 Firstleft 赢。