XXI Open Cup named after E.V. Pankratiev. Grand Prix of Krakow
B. (Almost) Fair Cake-Cutting
当 $n\ge 3$ 时，一定是 $100%$。
接下来只需解决 $n=1$ 和 $n=2$。
可用半平面交或者大力分类讨论解决。
C. Jellyfish
要使得对于每个集合满足条件，则在两点的所有简单路径中至少有一条中间没选点。
贪心，选全部数的叶子结点。
或者在环上选一个点，然后选其余树的叶子结点。
或者在环上选两个点，然后选一边的叶子结点。
或者在环上选三个点。
第二种情况会出现当且仅当存在某个环上节点没子树。
第三种情况会出现当且仅当环上存在某相邻两节点均没子树。
这样就好判断多了。
D. Flat Organization
将竞赛图缩点，然后DP即可。
时间复杂度 $O(n^2)$。
E. Archer Vlad
设 $v_x=v\cos \alpha,v_y=v\sin \alpha$，
则有：$t=\frac{x}{v_x}$。
而：$v_yt-\frac{1}{2}gt^2\geq y$，即 $x\tan \alpha-\frac{g}{2}\frac{x^2}{v^2\cos^2\alpha}\geq y$。
而 $\frac{1}{\cos ^2\alpha}=1+\tan^2 \alpha$。
变成关于 $\tan \alpha$ 的二次不等式。
解 $n$ 个这样的不等式即可。
时间复杂度 $O(n)$。
F. A Very Different Word
每次字典序加一，加 $26$ 次之后一定出现过 $a\sim z$。
时间复杂度 $O(n)$。
G. Cactus
每个点最多在一个环上。那么对于每个环，就只有dfs树中最上的那一个点是确定的。
很容易算出一个长度为 $m$ 的环的方案数。
时间复杂度 $O(n+m)$。
I. GCD vs. XOR
不妨设 $a\geq b$，有：$(a,b)=(a,a-b)\le a-b\le a\oplus b$。
若 $(a,b)=a\oplus b$，则 $(a,a-b)=a-b=a\oplus b$。
那么 $a$ 为 $a-b$ 的倍数，$a&b=b$。
设 $a=k(a-b)$，则 $b=\frac{k-1}{k}a$，那么对于每个 $a$，符合条件的 $b$ 的和一定不超过 $n\log n$。
预处理即可。
J. Civilizations
这样的 $Ax_i+By_i+Cx_iy_i$ 最大值没办法求。
考虑固定一个，发现周长最多是 $O(n^2)$ 级别的。
也就是最多会有 $\sqrt{O(n^2)}=O(n)$ 种不同的周长。
固定其中一个数后，要求 $(B+Cy_i)x_i$ 的最大值。
用set存，分两种情况讨论。
然后存在当前不同的 $l_p$ ，也可以用set存。
枚举即可。
时间复杂度 $O(n^2+qn)$。
K. We apologize for any inconvenience
离线，将删除变成增加。
考虑增加一个点，以这个点为中介点Floyd一遍即可。
时间复杂度 $O((n+k)^3)$。
M. Social Justice
首先求出最大能留下的人数 $mx$。
可以发现，对于一个集合，删掉最小的那个不会更差。
那么枚举最大值后，二分找到最小值。
对于所有的长度为 $mx$ 的合法区间内的人，都是可以留下的。
剩下的需要判断不在这些区间内的人是否可以，那么就是对于前面的每个区间，都去掉最后一个人并加上当前需要判断的那个，然后看是否可行。
但这样时间复杂度高达 $O(n^2)$。
那么只需对于每个区间计算出删掉最后一个人后加进去的那个人的最小权值，然后求后缀最大值即可。