传送门
这么多打表 / 乱搞题。
tricks from
- 凸函数平移 / 扩倍还是凸函数。
- 二分如果用贪心进行 judge，有时可以借助贪心的思路来把二分的 log 去掉。
B
定义 \(f_{i,j}\) 表示第 \(i\) 轮还剩 \(j\) 元的胜率，则 \(f_{i,j}=\max_\limits{k=1}^{\min(j,n-j)} \{p\cdot f_{i+1,j+k}+(1-p)\cdot f_{i+1,j-k} \}\)。打表发现最大值一定在 \(k\) 最大时取到，即每次都拿尽可能大的数做赌注。证明先咕着。code
C
here
D
以 \(1\) 为根。考虑当前 LCA 即为链 \((u,v)\) 上离当前根 \(r\) 最近的点。设 \(p\) 为 \((u,v)\) 的 LCA，展开讨论：
- \(r\) 在 \(p\) 子树外。此时 LCA 就是 \(p\)。
- \(r\) 在 \(u\) 到 \(p\) 的路径上。此时 LCA 为 \(\operatorname{lca}(u,r)\)。
- \(r\) 在 \(p\) 到 \(v\) 的路径上。此时 LCA 为 \(\operatorname{lca}(v,r)\)。
事实上，分讨可以合并为 \(\operatorname{lca}(u,r) \oplus \operatorname{lca}(u,r) \oplus \operatorname{lca}(u,v)\)。
code
F
定义 \(c(x)\) 为 \(x\) 的质因子个数（可以相同），打表发现 Vera 赢当且仅当 \(c(y) < c(x)\)。对 \(c(x)+c(y)\) 归纳即证。code
G
可以二分答案 \(x\)，问题变成是否可找到一个次序使得 \(i \le x+d_{a_i}\)。考虑 \(i\) 越大，满足条件的 \(a_i\) 越少，考虑倒着扫描 \(i\) 然后找符合条件的 \(a_i\)，限制部分可以拓扑排序实现，保证队列内都是 \(x+d_j \ge i\) 的 \(j\)。二分前把 \(d\) 排好序可做到单 log。
由上可得，只需倒序枚举 \(i\)，把当前入度是 \(0\) 的所有点用优先队列维护，每次取最大的 \(d\) 来最小化答案。写起来简单很多。code 用上边线性的 judge 替换掉优先队列，配合基数排序可以去掉二分的 log，但没有必要。
J
又是喜闻乐见的蒙特卡洛搜索。考虑给节点赋随机点权，然后求出该点所有可达点的点权和。重复若干次，将每个点所有的和加起来，输出总和最大的节点。感性理解正确性。