瞎做记录 2
瞎做记录 2
看了题解的会打了 *
[模板]线段树分治
二分图 /【模板】线段树分治
神犇有一个 \(n\) 个节点的图。
因为神犇是神犇，所以在 \(k\) 时间内有 \(m\) 条边会出现后消失。
神犇要求出每一时间段内这个图是否是二分图。
这么简单的问题神犇当然会做了，于是他想考考你。
\[\text{Data Range:}1 \leq n,k \leq 10^5，m = 2\times 10^5。1 \le x,y \le n，0 \le l \le r \le k \]建立时间轴的线段树，将包含边所在范围的边加入线段树上节点，使用扩展域并查集 dfs 着判断是否为二分图，遍历完子树之后撤销然后继续即可。
注意到，其实随机键值的并查集合并 \(n\) 次期望的复杂度仍然为 \(n \log n\)，于是可以简短代码难度。
存在 lct 解法，很平凡的维护图上奇环，可以很轻松完成。
[COCI2019-2020#5] Zapina
有 \(n\) 个不同的人和 \(n\) 道不同的题。
第 \(i\) 个人开心当且仅当他被分配到 \(i\) 道题。
求让至少一个人开心的分配方案数。
\[\text{Data Range : } 1 \leq n \leq 350 \]这道题的 \(n\) 过于小，立方算法很有前途，但是仍然不会。
正难则反，反过来思考，总方案数为 \(n^n\)，考虑不合法的方案数，记 \(dp_{i,j}\) 为前 \(i\) 个人分配 \(j\) 道题目的不合法方案数。
\[dp_{i,j}=\sum_{k=0}^{j} dp_{i-1,k} \times \binom{n - k}{j - k} \]注意 \(j- k\) 不能为 \(i\)，容斥即可。
[SHOI2014] 概率充电器
\(n\) 个点构成树形关系，每条边有 \(p\%\) 的充电概率，每个点有 \(q\%\) 的直接充电改了吧，求进入充电状态的元件个数的期望，四舍五入到 \(6\) 位小数。
\[\text{Data Range:} n \leq 5 \times 10^5 \]设立 \(dp_x\) 表示 \(x\) 的子树内进入重点元件个数的期望，考虑叶子，\(dp_{x} = 0 \times (1 - q_x) + 1 \times q_x = q_x\)。
发现贡献为 \(1\)，于是只用算概率就好了，问题变成了 \(\sum_{i=1}^n P(i)\)，\(P(i)\) 表示 \(i\) 节点通电概率。
发现父亲会给自己产生贡献，每次枚举儿子作为根的暴力没问题，于是换根进行 dp。
分类讨论，根据概率定义容斥一下就好了。
CF1624G MinOr Tree
给定 \(n\) 个点 ， \(m\) 条边 \((3 \le n \le 2 \times 10^5,n - 1 \le m \ \le 2 \times 10^5)\) , 求在或运算下的最小生成树，保证图联通。
按位从大往小的贪，能取 \(0\) 就取 \(0\)，每次得到一个答案 ans，然后每次整体遍历 check，复杂度 \(n \log^2 n\)。
[CSP-S 2021] 括号序列
小 w 在赛场上遇到了这样一个题：一个长度为 \(n\) 且符合规范的括号序列，其有些位置已经确定了，有些位置尚未确定，求这样的括号序列一共有多少个。
身经百战的小 w 当然一眼就秒了这题，不仅如此，他还觉得一场正式比赛出这么简单的模板题也太小儿科了，于是他把这题进行了加强之后顺手扔给了小 c。
具体而言，小 w 定义“超级括号序列”是由字符 (、)、* 组成的字符串，并且对于某个给定的常数 \(k\)，给出了“符合规范的超级括号序列”的定义如下：
()、(S)均是符合规范的超级括号序列，其中S表示任意一个仅由不超过 \(\text{k}\) 个字符*组成的非空字符串（以下两条规则中的S均为此含义）；- 如果字符串
A和B均为符合规范的超级括号序列，那么字符串AB、ASB均为符合规范的超级括号序列，其中AB表示把字符串A和字符串B拼接在一起形成的字符串； - 如果字符串
A为符合规范的超级括号序列，那么字符串(A)、(SA)、(AS)均为符合规范的超级括号序列。 - 所有符合规范的超级括号序列均可通过上述 3 条规则得到。
例如，若 \(k = 3\)，则字符串 ((**()*(*))*)(***) 是符合规范的超级括号序列，但字符串 *()、(*()*)、((**))*)、(****(*)) 均不是。特别地，空字符串也不被视为符合规范的超级括号序列。
现在给出一个长度为 \(n\) 的超级括号序列，其中有一些位置的字符已经确定，另外一些位置的字符尚未确定（用 ? 表示）。小 w 希望能计算出：有多少种将所有尚未确定的字符一一确定的方法，使得得到的字符串是一个符合规范的超级括号序列？
可怜的小 c 并不会做这道题，于是只好请求你来帮忙。
\[\text{Data Range:} 1 \leq n \leq 500 \]这个范围，加上这个括号，考虑区间 dp。
\(dp_{l,r,op}\) 表示 \(l \sim r\) 区间内，\(op\) 类型的括号序列的个数，考虑分别计数，然后对于每种类型，依次拿其他类型的括号序列来拼凑即可，这么做不用处理算重。