「CSP-S」做题记录
-
自己做出来了，开心捏。
先考虑对于一棵特定的树，如何计算答案（对应特殊性质 1）。
首先，根节点一定只能填 \(0\)。其次，可以发现各个子树不会互相影响，所以可以分别考虑如何填各个子树。
设填满以节点 \(u\) 为根的子树的方案数为 \(f(u)\)，\(u\) 的子节点数量为 \(m\)，子节点分别为 \(v_1, v_2, \dots, v_m\)。沿用”组合-顺序“的思考路径：设把 \((|T(u)|-1)\) 个节点（这里减去了根节点）分给 \(u\) 的各个子树的方案数为 \(cnt(u)\)，而在此基础上给各个子树安排顺序的方案数为 \(f(v_1) \times f(v_2) \times \cdots \times f(v_{m})\)，从而可以得到 \(f(u)\) 的表达式：
\[f(u) = cnt(u) \times \prod_{i=1}^{m} f(v_i) \]递归的边界条件是当 \(u\) 为叶子节点时，\(f(u) = 1\)。
下面只需考虑如何计算 \(cnt(u)\)。实际上这就是多重组合数问题：把 \((u-1)\) 个数分为 \(m\) 组，第 \(i\) 组有 \(|T(v_i)|\) 个，方案数为
\[cnt(u) = \dbinom{|T(u)| - 1}{|T(v_1)|, |T(v_2)|, \dots, |T(v_m)|} = \dfrac{(|T(u)|-1)!}{\prod_{i=1}^{m} |T(v_i)|!} \]dfs 一遍即可得到答案。这样可以拿到 35 分。
下面考虑带修的情况。注意到每次修改只是把一个子树的根节点 \(v\) 连向另一个子树的根节点 \(u\)，这只对 \(f(u)\) 有影响。我们只需快速更新 \(f(u)\) 的值。
考虑加入新的子树对 \(f(u)\) 的影响。分两部分讨论：
- \(cnt(u)\)：把式子展开，前缀积维护。
- 顺序（子节点的 \(f\) 的积）：再乘上 \(f(v)\) 即可。
于是这道题就做完了。（提交记录）
别解：
（下面把点的编号转为 1-indexed。）
把树的每一条边定向为从父节点指向子节点，得到一棵有向树。此时，合法的填数方案和树的拓扑序一一对应：按照节点在拓扑序中出现的位置填数，就可以保证合法。
下面计算树的拓扑序的数量。
澄清：一般 DAG 的拓扑序计数没有多项式解法，但某些特殊图（如树）是有的。
设 \(U\) 表示所有长度为 \(n\) 的排列构成的集合，显然 \(|U| = n!\)。
设 \(P_u\) 表示满足下列条件的排列的集合：\(u\) 出现在其子树内除它本身以外的所有点之前。设 \(size(u)\) 表示 \(u\) 的子树大小。对于任意一个排列，考察这个排列中 \(T(u)\) 中的所有点。对这些点重新排列，而其他点的位置不改变，总共可以得到 \(size(u)!\) 个排列，而其中恰有一个满足条件。也就是说，每 \(size(u)!\) 个排列中，就有 \(1\) 个符合要求的排列。因此 \(P_u = \dfrac{1}{size(u)!}|U| = \dfrac{n!}{size(u)!}\)。
设能作为拓扑序的排列的集合为 \(A\)，则 \(A = \bigcup_{i=1}^{n} P_{i}\)。
下面不会了。
总之，拓扑序的数量是
\[\prod_{i=1}^{n} \dfrac{1}{size(i)!} \times n! \] -
考虑枚举 \(l \in [1, n]\)，对于每个 \(l\)，计算它对答案的贡献 \(f(l) = \sum_{r=l}^{n} S(l, r)\)。
假设已知 \(f(l)\)，考虑如何更新到 \(f(l+1)\)。
拆式子：
\[\begin{aligned} f(l) &= \sum_{r=l}^{n} \operatorname{sum}(a_{l..r})\operatorname{sum}(b_{l..r}) \\ &= \sum_{r=l}^{n} (a_{l} + \operatorname{sum}(a_{l+1..r}))(b_{l}+\operatorname{sum}(b_{l+1..r})) \\ &= \sum_{r=l}^{n} (a_l b_l + a_l \operatorname{sum}(b_{l+1..r}) + b_l \operatorname{sum}(a_{l+1..r}) + \operatorname{sum}(a_{l+1..r})\operatorname{sum}(b_{l+1..r})) \\ &= (n-l+1) \cdot (a_l b_l + \operatorname{sum}(a_{l+1..r}) \operatorname{sum}(b_{l+1..r})) + a_{l}\sum_{r=l+1}^{n} \operatorname{sum}(b_{l+1..r}) + b_l \sum_{r=l+1}^{n} \operatorname{sum}(a_{l+1..r}) \end{aligned} \]算了还不会。
-
-
\(O(n^3)\) 35pts
区间 dp。
设 \(f(l, r)\) 表示子段 \([l, r]\) 能否被消除。
-
初始化：\(\forall 1 \le i < n\)，\(f(i, i+1) = [str_i = str_{i+1}]\)
-
转移：
可以发现，合法子串可以归为两种形式：
- \(AB\)，其中 \(A\) 和 \(B\) 代表合法子串。也就是说一个合法子串可以由两个合法子串拼接而来。
- \(cAc\)，其中 \(c\) 代表单个字符。即在一个合法子串的两端加上相同字符，得到的仍然是合法子串。
于是可以按这两种类别转移：
- 枚举 \(l < k < r\)，把 \([l, r]\) 拆成 \([l, k] \cup [k+1, r]\)，如果两段都可以被消除，则 \([l, r]\) 是合法子串。
- 如果 \(s_{l} = s_{r}\) 并且 \([l+1, r-1]\) 可被消除，则 \([l, r]\) 是合法子串。
-
答案统计：\(ans = \sum_{l, r} [f(l, r)]\)
-
-
\(O(n^2)\) 50pts
在此基础上优化。
转移第一种方案时，我们每次要枚举断点。考虑优化这个过程。
设 \(g(l)\) 表示最大的 \(r\)，使得 \([l, r]\) 可以被消除。这样，转移时就不用枚举断点，而只用 \(f(g(l)+1, r)\) 来更新。容易证明这是正确的。
-
\(O(n|\Sigma|)\) 100pts
（从这里开始是看题解想的。）
现在 dp 的状态数是 \(O(n^2)\)，这种状态设计决定了时间复杂度下界是 \(O(n^2)\)。要获得更优的做法，必须改变状态设计。
设 \(f(i)\) 表示以 \(i\) 结尾的合法子串数量，则 \(ans = \sum_{i=1}^{n} f(i)\)。
设 \(g(i)\) 表示最大的能使 \([g(i), i]\) 为合法子串的数。于是 \(f(i) = f(g(i) - 1) + 1\)。
于是我们只要找出办法求出 \(g(i)\) 即可。
可以发现如下性质：\([g(i), i]\) 一定是 \(cAc\) 形式的。否则若 \([g(i), i]\) 是 \(AB\) 形式的，那么 \(B\) 以 \(i\) 结尾并且可被消除，与 \(g(i)\) 的最大性矛盾。因此，\(s_i = s_{g(i)}\)。
初始化 \(g(i) = i - 1\)。应用如下算法：重复 \(g(i) \gets g(g(i)) - 1\)，直到 \(s_{g(i)} = s_i\) 或 \(g(i) = 0\)。（后者表明没有以 \(i\) 结尾的合法子串。）
为什么这是对的呢？
当 \(i = 1\) 时，显然没有以 \(i\) 结尾的合法子串，此时 \(g(i) = 0\)。
待
别解：
待
-
-
-
特殊性质 A （25pts）
其实自己想了一个贪心，但是以为是假的，没有多加思考就弃了，看了题解才知道这是对的。对于贪心，还是仔细得论证其正确性啊。
\(c_i = 0\)，说明第 \(i\) 棵树每天生长的高度是定值 \(b_i\)，它生长到 \(a_i\) 需要的天数 \(t_i = \left\lceil \dfrac{a_i}{b_i} \right\rceil\)。
按 \(t_i\) 从大到小排序，枚举 \(i\)，如果它还没有被种下，则种下它到根节点简单路径上的所有未被种下的树。不难发现，这个贪心是正确的。
-
特殊性质 B-链 （10pts）
在链上，种树的顺序被固定了，我们只需求出每棵树生长到对应高度的时间。
对于第 \(i\) 棵树，假设它在第 \(l\) 天被种下（实际上在这里有 \(l = i\)，因为我们是按顺序种的，且显然在种满之前我们每一天都会种树），在第 \(r\) 天完成任务，我们希望能求出 \(r\)，也就是解以下不等式：
\[\sum_{d=l}^{r} (b_{i} + d \times c_{i}) \ge a_{i} \\ (r-l+1)b_{i} + \dfrac{1}{2}(l+r)(l+r-1)c_{i} \ge a_{i} \]整理到这一步，会发现很难把 \(r\) 孤立出来。不妨换一个思路：不必解出 \(r\)，而使用二分求出 \(r\)：
i64 calc(int x, int L) // 在第L天种下第x棵树，求它在第几天满足条件 { auto check = [&](int R) -> bool { i128 h = 0; if(p[x].c >= 0) { h = (R - L + 1) * p[x].b + p[x].c * (L + R) * (R - L + 1) / 2; } else { i128 m = ceil(1 - p[x].b, p[x].c) - 1; if(m >= R) h = (R - L + 1) * p[x].b + p[x].c * (L+R) * (R-L+1) / 2; else if(L <= m && m < R) { h += (m - L + 1) * p[x].b + p[x].c * (L + m) * (m - L - 1) / 2; h += (R - m); } else h = (R - L + 1); } return h >= p[x].a; }; int l = L, r = 1e9, ret; while(l <= r) { int mid = (l + r) >> 1; if(check(mid)) ret = mid, r = mid - 1; else l = mid + 1; } return ret; } -
\(O(n \log V \log n)\) 满分做法
-