A. 大富翁
诈骗题。
你会发现这个东西和先后手无关，如果某个人的某个点上面有其它人的点那么减一，如果子树内有其它人的点那么加一。
这个还是不好做。我们可以将一对属于同一个人的祖先儿子点对看成加了一又减了一，那么每个点的代价就是 \(-w_x\) 加上子树内点数减去祖先个数。
这个对于每个点独立，那么排序以后选就好了。
B. 拧螺丝
套个高精度也就算了，还卡高精度的常数，没意思。
正着做不好考虑，可以考虑反着做。将操作变为有一个 \(n\) ，每次可以减去总和为 \(k\) ，并且每次操作完了之后最大值会多一个。
这样的话显然每次减得尽量平均就好了，高精要压位，还要特判 \(n=2\)，时间复杂度 \(O(\frac{n^2}{\omega})\)。
C. 快速 LCM 变换
首先考虑拿走两个数分别为 \(p^{k_1},p^{k_2}\) 的方案数，其中 \(p\) 是质数，不妨令 \(k_1\leq k_2\)，那么对原来 LCM 的贡献是 \(p^{k1-k2}\)。
因为 LCM 对每个质因数是独立的，因此对于每个质因数，如果其最大值唯一且被拿走了，那么就会乘上一个贡献，然后如果新加出来的数出现了比原来大的质因数，那么再乘上贡献。
不难发现贡献只和 \(r_i,r_j,r_i+r_j\) 的值有关，那么写个 NTT 卷起来就好了。
D. 种苹果
树分块狗都不写。
E. 速战速决
首先有一个观察，就是对于两个人，只有一张牌的种类数和两张牌都在自己这里的种类数都是一样的。
那么实际上这可以一一对应，也就是说，可以用一张的把对面的同样的一张拿过来，用两张的把对面的两张破坏掉一张。因此在 \(n\) 步内一定能做完。又因为对面至少要出 \(n\) 步，所以最小步数就是 \(n\) 。
但是这做完了吗？显然没有，要不然哪里来的无解。
我们发现如果没有两张牌都在自己这里的情况，因为我们操作的人是先手，那么第一张放下去的牌一定会被对方收走，但是因为被收走的牌可以被控制在两张，因此可以用 \(n+2\) 步做掉。\(n=1\) 的情况无解。
F. 公平合作
我们发现第二个人会根据第一个人的最终状态来决策自己到底要怎么弄。假设第一个人的最终状态为 \(s\)，设 \(g_t\) 表示第二个人当前油桶内为 \(t\) 第一个人的胜率。
容易发现当 \(t>s\) 时不会继续操作，\(g_t=0\)。否则如果不动那么必败，因此一定会有转移 \(g_t=\frac{1}{n}\sum\limits_{i=1}^{n}{g_{t+a_i}}\)。最后要 \(g_0\)。
但是 \(L\) 高达 \(10^9\)，不能直接递推，矩阵乘法是 \(O(n^3\log L)\) 的显然过不了。
设 \(A=\max a\)。 将序列翻转，变成已知 \(g_{0}\) 到 \(g_{A-1}\)，求 \(g_L\) 。将 \(g_L\) 逆推回去，算出 \(g_0\) 到 \(g_{A-1}\) 的系数。
这个过程实际上就是多项式取模的过程。也就是说我们要求 \(x^L\bmod(x^A-\sum\limits_{i=1}^{n}{\frac{1}{n}x^{A-a_i}})\) 的各项系数，这个可以用类似快速幂的方法，暴力取模，复杂度 \(O(n^2\log L)\)。
我们还有 \(O(A)\) 次对初始序列的修改，同样也用这种推系数的思想即可。
对于第一个人的 dp 也是同理，而且模出来的结果是一样的。时间复杂度 \(O(n^2\log L)\)。
G. 喵了个喵 II
爆搜过了，我反手叉掉了，这好吗，这很好（
首先我们对着这个东西不能直接做，肯定要有一些结论。我们猜想：存在一种方案，使得对于任意前缀，第一个序列都不少于第二个序列。
考虑归纳，对于第一个数显然成立，现在假设 \(i-1\) 成立来构造第 \(i\) 个。如果 \(i-1\) 的前缀中第一个序列中的元素严格大于第二个序列，那么都是成立的。如果等于第二个序列，那么这个无论放哪边都是一样的，所以可以钦定放在第一个序列。因此原命题成立。
同时利用上述归纳，我们还可以证明，对于每个元素来说，这都是成立的。因此每种颜色的四个中，第一个可以认为是第一个序列的，最后一个可以认为是第二个序列的，不改变有解性。
因此我们现在的问题变成了中间两个到底哪个是哪边的。这显然是一个二选一的问题，也就是 2-SAT，由元素在序列中的位置关系可以导出一些限制。
用主席树优化建边，时间复杂度 \(O(n\log n)\)。
H. 背包
看到这个 \(V_i\) 很大，说明性价比很高的要选大多数。剩下的可以同余最长路解决。
J. 欺诈游戏
题目里面写得挺清楚的，另一方无论如何改变自己的策略都不会更优，说明每个贡献是相同的，然后就可以算了。
K. 众数
从大到小排，没了。
L. 最后的活动
考虑设 \(f_i\) 表示打出 \(i\) 分的概率。
为了转移每个 \(f_{i}\)，考虑设 \(g_{i,S}\) 表示到了第 \(i\) 个关，当前分数为 \(S\) 的最大概率。注意到 \(S\) 只有 \(O(2^n)\) 种取值，因此状态数是 \(O(n2^n)\) 的。
但是可能会从自己转移，直接上分数规划就好了。时间复杂度 \(O(Mn2^n\log \frac{1}{\varepsilon})\)。
K.世界杯
我们中国真是太厉害了！
标签：那么,log,submission,复杂度,初赛,序列,THUPC2023,第一个 From： https://www.cnblogs.com/275307894a/p/17196009.html