PKUWC/SC 乱做
Minimax
之前写过题解，在这里 很好想，不过代码有点难写…
Slay the Spire
看错输入啦OAO。以为强化牌可以有小数w。 强化牌$ > 1$，并且都是整数的情况下，出强化一定比出攻击优秀。 分类讨论，有两种情况： 选的强化牌$\geq k - 1$，那么出$k-1$次，然后攻击一次。这种情况下剩下的牌两种都可以选。 选的强化牌$ < k - 1 $，全出然后攻击。这种情况下多出来的牌只能选攻击牌。 那么定义$f_{i,j},g_{i,j}$分别表示前$i$张牌，选了$j$张强化，各方案价值积的和，与前$i$张选了$j$张攻击价值和的和。然后分类随便统计即可。
斗地主
大模拟，咕咕咕
随机算法
考虑一个$O(3^nn)$的大暴力。令$f_{s1,s2}$表示$s1$集合，构成的独立集是$s2$的方案。枚举加点转移。 发现最优答案一定是由一个子最优状态扩展来的。那么可以压掉具体独立集的状态。 具体来说我们令$f_s,g_s$表示$s$集合构成最大独立集方案，最大独立集大小。 考虑加入一个点$x$，令$w_x$表示$x$与所有和$x$相连点的集合。 首先更新$g$，如果变大把$f$清零。 $$f_{s \cup w_x} \leftarrow f_s P_{n - s - 1}^{w_x - (w_x \cap s) - 1}$$
猎人杀
首先做一个非常脑洞的转化：一个猎人死了，不把它删掉，留在集合中。更改打枪方案为：如果打到的是死人，就继续再打一枪。 记录人数和为$A$，挂掉的人数为$K$。令打中某个人，原来的概率，新的概率为$P_1,P_2$ $$P_1 = \frac{ w_i }{A - K }$$ $$P_2 = \frac{K}{ A } P_2 + \frac{w_i}{A}$$ 可以发现$P_1 = P_2$ 那么一个容斥，枚举在$1$之后被打死的集合$s$。记$s$的$w$和为$S$ $$ans = \sum_{s} (-1)^{ s } \sum_{i=0}^{\infty} (1- \frac{S + w_1}{A}) \frac{w_i}{A} $$ 拿出后面的部分，发现是收敛的，直接提出来： $$ \sum_{i=0}^{\infty} (1- \frac{S + w_1}{A}) \frac{w_i}{A} = \frac{w_1}{S + w_1}$$ $$ans = \sum_{s} (-1)^{ s }\frac{w_1}{S + w_1} = w_1 \sum_{s} \frac{ (-1)^{ s } }{S + w_1} $$ 考虑记录对于$S$，$\sum (-1)^{s}$是多少。 构造生成函数$F(x)$ $$F(x) = \prod_{i=2}^{A - w_1} (1 - x^{w_i}) $$ 那么$[x^i]F(x)$就是要的东西。 这个式子可以用分治FFT求出来。
随机游走
考虑$\rm{min-max}$容斥，求出到每个集合的$\min$即可。枚举集合$s$，定义$f_x$为$x$点走进$s$的期望步数。 如果$x \in s$，$f_x = 0$ 否则有： $$f_x = \frac{1}{deg_x} (f_{fa} + \sum_{y \in son} f_y) + 1$$ 有一个树上高斯消元的套路：每个$f$都可以被表示为$f_x = A_x f_{fa} + B_x$ 推一下式子： $$deg_x f_x = f_{fa} + \sum_{y} A_y f_x + B_y $$ $$f_x = \frac{1}{deg_x - \sum_y a_y} f_{fa} + \frac{\sum_y b_y + deg_x}{deg_x - \sum_y a_y} $$ 那么可以快速求出$f_{root}$。
真实排名
签到题，考虑哪些选手翻倍不会影响自己。 如果自己不翻倍，翻倍后还是比自己小的，和本来就大于等于自己的可以动。 如果自己翻倍，那么翻倍前到翻倍后的一段都要翻。 组合数算一算就好了。
最大前缀和
观察数据范围发现显然是$O(2^nn)$的算法。考虑状压DP，钦定一些点是本次答案点。 用$f_s,g_s$分别表示$s$集合排列，使得最后一个位置前缀和最大的方案数，与$s$集合排列，任意时刻前缀和$ \leq 0$的方案数。 $$f_s = \sum_{s - i} f_{s - i} (sum_{s - i} > 0)$$ $$g_s = \sum_{s - i} g_{s - i} (sum_s \leq 0) $$ 第二个意义很明确。第一个转移的意思是，把$i$元素插到$s-i$排列的最前面。 注意到本题中最小前缀和必须选择至少一个数字，所以这样转移合法。 最后用两个数组计算答案即可。
主斗地
并没有什么思维难度的恶心搜索题。。。还没写。。。
星际穿越
观察可以发现，最优秀的方案要么是直接向左跳，要么是向右跳一次再一直向左。钦定一个起点，向左走的距离一定是一段一段的。 于是利用性质可以考虑一个$O(n^2)$的简单暴力，计算出任意点对的距离就行了。 优化这个暴力，把记录两点间距离，改成记录一个点跳$i$次最左可以跳到哪里。倍增优化。 具体来说，定义数组$f_{x,i}$表示从$\forall x \in [x, n]$点开始跳$2^i$次可以跳到哪里。 求出$f$后，记录$g_{x,i}$表示跳整个$[f_{x,i},x-1]$的点一共需要多少次。 最后统计答案。首先向左跳一次，然后用$f$数组计算答案。容易发现这样是没有问题的。
神仙的游戏
考虑一个做法。问号是匹配符，无视之。我们定义$A(x),B(x)$，使得$A(x)=\sum [S_i == 0] x^i,B(x) = \sum [S_i == 1] x^i$，然后做一个减法卷积。 然而这样是有问题的。对于长度大于一半的$border$，会有重复部分，然而这样匹配出的方案可能一个问号分别充当了$0,1$各一次。 考虑$border$和$period$的关系。如果存在一个$border$长度为$x$，那么剩下的部分在$\mod S - x $意义下相等。这个显然是不相交的。 NTT求一下减法卷积，然后枚举每一段检查。复杂度是一个调和级数。
PKUSC
把每个点的概率加起来就行了。考虑把一个点放在一个圆上，它与多边形交的弧长就是答案。 那么直接解方程解出所有的交点，极角排序，判断每一段弧在多边形内还是外。 判断一个点在多边形内外，可以考虑向任意方向作射线，如果没有和点相交，可根据与边交点数量奇偶性判断内外。 本题中坐标都是整数，所以选要判断的弧上一个非整数点作射线即可避免交到点上的事情。
下面的题并没有地方交OAO 题面
T1
令$f_s$表示集合$s$的方案数，枚举拓扑序最后的点再枚举出边转移。
T2
钦定一个点或边做代表元素，考虑过这个元素的方案。把点和边分开计算，减一下，发现每种方案只被算了一次。 令$f_i$为有$i$种颜色经过的点的数量，则有 $$ans_x = \sum_{i=x}^n f_i \binom{i}{k}$$ 然后卷卷就行了。
T3
不会斗地主。
T4
网上找到的题和题解貌似不符，233，咕了
T5
如果两个环有公共边，它们在一个强联通内。先求强联通，考虑每个分量，把有向边变无向，可以感性理解到，如果有公共边一定在一个点双内。
T6
咕。
T1
猜结论可以猜到就是逆序对数量
T2
大概就是做一个DP，记录$f_{i,j,s}$，$s$表示其他桌子的状态。$s$记录大小关系。然后不会了233
T3
可以交换Trie的左右儿子，于是做一个小DP，bitset优化。
T4
做一个暴力大DP：$f_{i,j}$表示$i$点颜色$j$，转移显然。发现很多$j$的答案都是一样的，记录被钦定ban掉的颜色集合即可。然后做一个线段树合并。
T5
咕咕
T6
咕咕