CSP2019 Solutions
CSP2019 题解
代码早晚会有的。
D1T1 格雷码
Description
给定 $n,k$，求 $n$ 位二进制格雷码中第 $k$ 个是多少。$n\leqslant64,0\leqslant k<2^n$。
Solution
可以递归求，也可以找规律得到答案为 k ^ (k >> 1)。
注意 $k$ 需要用 unsigned long long 存储。
D1T2 括号树
Descrption
给出一棵有根树，每个结点上有一个括号。对每个点询问从根到它的括号字符串有多少个子串是合法括号串。
$n\leqslant10^5$
Solution
考虑计算根到每个点的字符串有多少个后缀是合法字符串，之后只需要求一个树上前缀和。
定义一个点的深度 $d_x$ 为：从根到它的路径上左括号比右括号多多少个。
那么令 $f_{x,i}$ 表示从根到 $x$ 的路径上有多少个点 $y$ 满足：
- $y\dots x$ 这一段路径上的括号串任意前缀的左括号个数都大于等于右括号个数。也就是说，这个串可以通过在右边添加一些右括号得到合法括号串；
- $y$ 的深度等于 $i$。
容易发现如果 $x$ 上面为右括号，$y\dots x$ 满足上述条件 1 且 $d_y=d_x+1$，则 $y\dots x$ 是合法括号串。所以 $x$ 的答案就是 $f_{x,d_x+1}$。
可以发现当 $x$ 上面为左括号的时候
$$ f_{x,i}=\begin{cases}f_{fa_x,i}&i\neq d_x\\f_{fa_x,i}+1&i=d_x\end{cases} $$
$x$ 上面为右括号的时候
$$ f_{x,i}=\begin{cases}f_{fa_x,i}&i\neq d_x\\0&i=d_x\end{cases} $$
无论如何 $f_{x}$ 和 $f_{fa_x}$ 都只有一个位置不同，因此可以直接边 dfs 边修改 $f$（回溯的时候改回去就可以了）。复杂度$O(n)$。
D1T3 树上的数
待填。
D2T1 Emiya 家今天的饭
Desciption
$n$ 种烹饪方式 $m$ 种食材，第 $i$ 种方式第 $j$ 种食材有 $a_{i,j}$ 种做法，要求做若干道（至少一道）菜使得每道菜的烹饪方式不同，且每种食材的菜不能超过一半（向下取整）。求共有多少种方式，对 998244353 取模。
$n\leqslant100,m\leqslant2000,a_i<998244353$。
Solution
不考虑每种食材不超过一半的限制，答案是 $$ \prod_{i}\left(1+\sum_ja_{i,j}\right)-1 $$ 减去 1 是去掉一道菜都不做的方案。
显然只可能有一种菜超过一半，于是枚举这种菜，对每个方式做背包即可（记一维状态表示这种菜比别的菜多做了多少份）。
背包复杂度 $O(n^2)$，总复杂度 $O(n^2m)$。分治 FFT！
D2T2 划分
Description
给定一个长为 $n$ 的正整数序列，要求把它划分成若干段分别求和后单调不降，最小化每一段的和的平方和。
$n\leqslant4\times10^7$。
Solution
结论：最优解同时一定也是所有合法解中最后一段的和最小的解。
这个结论我还不会证...虽然它看上去很正确...
有了这个结论之后可以令 $S_i$ 表示 $a_1+\dots+a_i$，$f_i$ 表示只靠虑 $1\dots i$ 的时候最后一段最小可以是多少。那么 $$ f_i=\min\{S_i-S_j\mid S_i-S_j\geq f_j\} $$ 显然会选择最大的合法的 $j$，并且条件相当于 $S_j+f_j\leqslant S_i$。单调队列即可。
不能直接记录答案，要 DP 之后沿着转移从 $n$ 走回去求平方和（因为要高精度）。
复杂度 $O(n)$。
D2T3 树的重心
Description
给出一棵树，分割掉每条边之后在两边求重心，最后求所有重心的编号之和。如果有两个重心就都加上去。
（重心定义为以其为根、每个子树大小都不超过总大小的一半（下取整））
$n\leqslant3\times10^5$。
Solution
显然任意情况下两个重心一定是相邻的，我们先求出其中较靠下的那个重心，最后 check 一下其父亲是不是也是重心就可以了。
首先说明一个结论：任意一个树，以任意点为根，重心（所有重心）一定在根所在的重链上。证明省略，挺简单的。
我们选择一个重心作为树根。
接下来考虑每个点的子树的重心。令 $f_i$ 表示 $i$ 的字数的重心，$w_i$ 表示 $i$ 的重儿子。可以发现 $f_i$ 一定是 $f_{w_i}$ 的祖先，暴力跳就可以了（每条重链上都只会从下往上跳，所以总复杂度是 $O(n)$）。
复杂的是求每个点字数外的重心。下面用 $r$ 表示树根（也是全树的重心）。
如果某个点 $x$ 不在 $w_r$ 的子树里，那么删掉 $x$ 的子树之后 $r$ 的重儿子一定还是 $w_r$，从而重心还在原来那条重链上。把这条重链从上到下排列下来记作 $p_1(=r),p_2(=w_r),\dots,p_k$，那么删掉 $x$ 的子树后，重心就是最靠下的点 $p_i$ 使得 $siz_{p_i}\geq\lceil\frac{n-siz_x}{2}\rceil$。可以直接预处理出对每个 $t$，最靠下的 $siz_{p_i}\geq t$ 的点是哪个，然后 $O(1)$ 查询。
还剩下 $w_r$ 的子树里的那些点。记 $v_r$ 表示 $r$ 的次大的儿子，我们“假装”把根节点的重链转而连到 $v_r$ 上；如果 $x$ 是 $w_r$ 的子树里的点，那么有两种可能：
- 删掉 $x$ 及其子树之后根节点的重儿子没变。但是这样的话既然本来重心就是 $r$，删掉 $x$ 的子树显然不会使得重心反而往 $x$ 的方向靠近。因此这时候重心还会是 $r$；
- 删掉 $x$ 的子树后根节点的重儿子变了，那显然会变成 $v_r$。于是重心会在 $r$，或者 $v_r$ 的重链上。
总之我们可以假装把 $r$ 的重儿子改成 $v_r$，然后对重儿子子树里所有的点做一个像之前求不在 $w_r$ 子树里的点的答案一样的做法。
所有处理都是线性的，总复杂度也仅仅是 $O(n)$。