D1T1 Coreputer
题意：交互题，有隐藏的 01 序列 \(a_{1 \sim 16}\)，查询给出集合 \(S\)，记 \(f(S) = \sum_{i \in S} a_i\)，交互库返回：
- \(f(S) > f(U \setminus S):1\)。
- \(f(S) = f(U \setminus S):0\)。
- \(f(S) < f(U \setminus S):-1\)。
需要在 \(18\) 次查询内求出 \(a_{1 \sim 16}\)。
考虑如果我们知道一个集合 \(S\) 满足 \(f(S)=0\)，那么我们可以根据 \(f(S \cup \{i\})\) 的值来确定 \(a_i\)。基于这个想法，我们先花 \(4\) 次操作二分出一个分界点，然后再 \(16\) 次查询查询出来 \(a_{1 \sim 16}\)。
但是这样超了两次，先确定 \(a_{p+1}=1\) 减少一次，再由于知道 \(a_{1 \sim 15}\) 可以直接知道 \(a_{16}\) 的值，还可以凹一次。
D1T2 Tree
题意：给定一棵大小为 \(n\) 的树 \(T\) 和一个常数 \(m\)，定义 \(f(S)\) 为 \(S\) 最小斯坦纳树的最小点覆盖大小，求所有 \(S\) 的 \(f(S)^m\) 之和。
\(1 \le n \le 3 \times 10^5,1 \le m \le 200\)。
套路化地转下降幂，考虑一下 \(\binom{f(S)}{i}\) 的组合意义，也就是钦定 \(i\) 个最小点覆盖中的点。
- 树上最小点覆盖事实上有贪心策略：如果一个点的所有儿子有一个没被覆盖的则覆盖自己，否则不覆盖。
基于此我们设计 dp 状态为 \(f_{i,j,0/1}\) 代表做完了子树 \(i\)，钦定了 \(j\) 个点，这个点是否被覆盖。应该要注意这里计数的对象是什么，事实上是对 \(S\) 计数而非对连通块计数，所以我们要考虑每个连通块中的点是否需要选入 \(S\) 集合。
- 如果节点 \(i\) 为根，并且节点 \(i\) 有 \(\ge 2\) 个儿子，那么 \(i\) 可选可不选；否则 \(i\) 必须选。
考虑到实现，我们拿不考虑此限制的方案数，减掉只有 \(1\) 个儿子的方案数即可，复杂度为树形背包 \(O(nm)\)。
D1T3 Weight
题意：https://qoj.ac/problem/15436/statement/zh_cn。
我们把 \((|S|,|N(S)|)\) 看成平面上的一个点，首先有用的点只有 \(n\) 个，并且这 \(n\) 个点横纵坐标单增。因为每个 \(|S|\) 只有 \(|N(S)|\) 最大的一个会被启用，不过这里暂时不提如何求最大的一个。
- 存在一种方案，选择的集合不会超过 \(2\) 个。
考虑三个点 \((x_{1 \sim 3},y_{1 \sim 3})(x_i \le x_{i+1})\)，如果 \((x_2,y_2)\) 在 \((x_1,y_1),(x_3,y_3)\) 的连线上方，把它的权值分给两边的点一定不劣；同理如果 \((x_2,y_2)\) 在 \((x_1,y_1),(x_3,y_3)\) 连线下方，则把两边的权值分给它一定不劣。
基于这个观察，我们可以说明有用的点必须是下凸包上面的点，并且可以将下凸包上的点的权值重分配到相邻的两个点。
考虑如何去求这个凸包。首先 \((0,0)\) 和 \((n,n)\) 都是合法的点，考虑分治求两个点 \(L \to R\) 间的凸包，具体来说，我们斜率为 \(L\) 到 \(R\) 斜率的直线去切所有点，切出来的点一定在下凸包上面，不妨设是 \(M\)，如果 \((M \ne L \wedge M \ne R)\)，我们继续递归处理 \(L \to M, M \to R\)。
现在的问题是，如何去用一条斜率为 \(k\)（\(k\) 是分数）的直线去切点集，那么截距离就是 \(|N(S)|-k|S|\)，要最小化截距，也就是最大化 \(k|S| - |N(S)|\)。考虑对其网络流建模：
- 选择一个左部点，贡献为 \(+k\)，需要强制选所有相邻的右部点。
- 选择一个右部点，贡献为 \(-1\)。
这实际上就是最大权闭合子图模型，我们建模 \(S \to i\)，容量为 \(k\)，\(i+n \to T\)，容量为 \(1\)，\(u \to v\)，容量为无穷，跑最小割即可求出对应的 \((|S|,|N(S)|)\)。
我们已经求出来了下凸包，考虑如何求答案，则有约束：
- \(p_1 + p_2 \le 1\)。
- \((ax_1 + y_1)p_1 + (ax_2 + y_2)p_2 \le k\)。
所求即为 \(a(x_1p_1 + x_2p_2)\) 的最大值，最大值在前两条限制的交点取到。
分析复杂度，凸包上的点是 \(O(n^{\frac{2}{3}})\) 级别的，时间复杂度 \(O(n^{\frac{2}{3}}) \text{flow}(n,m)\)，卡不满所以足以通过。暂时没写。
Day1 非传统题选讲 刘家炜
QOJ1139
努力的方向是去维护子树信息，想要去维护 \(t\) 位于 \(s\) 哪个子树，或者父亲方向。
最直观的想法是按 DFS 序标号，但是 DFS 序标号会有漏洞，最后一个子树我们并不知道右端点是多少。我们发现维护子树信息并没有很好利用父亲和自身的编号，考虑以某种方式重编号，同时还要保持子树内的编号连续。
我们对树二分图染色，按如下方式编号：
- 如果是黑点，则先给子树内的点编号，最后给自己编号。
- 如果是白点，则先给自己编号，然后再给子树内的所有点标号。
QOJ8650
我们考虑随便挑一个点为根，并且以这个点为根查询 \(n\) 次求出到所有点的优先级。
现在有一个点 \(u\)，考虑不停去查询离它优先级 \(1 \sim i\) 的点，直到查询出来 \(a_i\) 使得 \(1\) 对 \(a_i\) 的优先级比 \(1\) 对 \(u\) 更高，那这个 \(a_i\) 就是 \(u\) 的父亲。
这样看起来是 \(3n\) 次操作，不过分析一下发现在查询到父亲之前的查询，都可以查出来一个儿子，所以是均摊 \(2n\) 次操作。
QOJ13902
首先观察一下 \(n=3\) 咋做，第一次查询肯定查询 \(p_0-1\)，得到了 \(p_1\) 或者 \(p_1+p_2\) 的值。
前者是好做的，考虑后者如何才能避免再次购买到 \(p_1\)；事实上，考虑用 \(p_1+p_2\) 的值除以二再次进行查询即可避免买到 \(p_1\) 的同时买到 \(p_2\)。
考虑类似地进行扩展，记我们一次查询出来 \(c = \sum_{i \in [1,k]} a_{p_i}\) 的值，那么 \(\min(p_i)\) 的值肯定大于 \(\left \lfloor \frac{c-1}{k} \right \rfloor\)。我们拿 \(\left \lfloor \frac{c-1}{k} \right \rfloor\) 去进行购买，则会递归到一个后缀的子问题。
不妨设可以解决这个子问题，我们给刚刚的 \(c\) 减去所有后缀中的数，重新递归去做类似的子问题即可。分析操作次数，每一个递归的子问题都最多会对后缀每个数购买一次，所以是对的。
QOJ16001
首先随机一个满秩的序列是 \(\prod (1 - \frac{1}{2^i})\) 收敛于 \(\frac{1}{4}\) 的，也就是期望随机 \(4\) 次可以随机出来一个满秩的序列。
考虑去删掉一个数递归子问题；设删掉 \(C_n\)，求剩余元素的子空间。维护空间的一组基，初始的基为 \((1,2,...,2^{n-1})\)。
对基底中每个元素 \(x\)，询问 \(C_n:=C_n \oplus x\) 的秩是否发生变化；记不发生变化的为 \(x'_{1 \sim m}\)，变的为 \(x''_{1 \sim n - m}\)。
- 若 \(a,b\) 都不在子空间中，则 \(a \oplus b\) 一定在子空间中。
根据这个结论，那么 \((x_{1 \sim m},x''_2 \oplus x''_1,x''_3 \oplus x''_1,...,x''_{n-m} \oplus x''_1)\) 为 \(C_{1 \sim n-1}\) 的一组基，也就可以递归子问题。
假设已经求出来了 \(a_{1 \sim n-1}\)，现在要解 \(a_n\)，当前的基底为 \(s_{1 \sim n}\)，我们需要依次判断 \(a_i\) 在每个基上面是否有分量。用 \(s_{1 \sim n-1},C_n\) 查询即可判断 \(s_n\) 是否在 \(C_n\) 上有分量，如果有，则 \(C_n \to C_n \oplus s_n\)，然后类似递归做下去即可。
QOJ14330
建出来表达式树，考虑只把 \(x_1\) 和 \(x_k\) 设为 \(1\)，其他都为 \(0\)。答案为 \(1\) 当且仅当 \(x_k\) 向上只经过一次右儿子。根据这个，我们可以求出来左链的右子树大小，递归处理可以做到 \(O(n^2)\) 次。
改一下表达式树，将一个括号内若干个并列的减号改为多叉树。当且仅当第一个儿子为 \(1\)，后面都为 \(0\)，子树会向上返回 \(1\)。
考虑从小到大去加点，假设现在已经加入了 \(1 \sim i\) 的点，并且当前点 \(i\) 在这个多叉树上根到 \(i\) 的链为 \(u_{1 \sim k}\)。考虑 \(u_{1 \sim k}\) 一定都会有第一个儿子并且已经在前面求过了，这里我们将它们全部设为 \(1\)，其他设为 \(0\)，考虑 \(a_{i+1} :=1\)，\(i+1\) 一定为 \(u_{1 \sim k}\) 的某个点的某个子节点的第一个儿子：
- 如果是 \(u_{k}\) 的某个子节点的第一个儿子，则表达式的值会反转。
- 如果是 \(u_{k-1}\) 的某个子节点的第一个儿子，则表达式的值会不会反转。
- 如果是 \(u_{k-2}\) 的某个子节点的第一个儿子，则表达式的值会反转。
也就是说，这个是否会反转和向上跳的祖先的个数的奇偶性相关。如果值没变，则可以断定不是 \(u_k\) 的子节点的第一个儿子，直接向上退出递归；否则，将 \(u_k\) 和 \(u_{k-1}\) 的第一个点改为 \(0\)，再查询一遍，来确定是否位于 \(u_k\) 的某个子节点的第一个儿子。
这样做的操作次数是 \(3n\) 次，超限了 \(2.5n\) 次。考虑退栈的过程，如果值没变，则下一次查询 \(u_{k-1}\) 的结果我们已经知道；否则可以直接向上跳两层跳到 \(u_{k-2}\)，因此总操作次数可以优化到 \(2.5n\) 次。