训练

不能掉到 $0$ 以下，这个限制特别烦。如果某一天掉到 $0$ 以下，那么这一天之前所做的练习都是无效的。也就是说一定存在一个最优方案，在开始练习一个技能之后，一定不会掉到 $0$ 以下。

令 $dp(i,0/1/2,d_1,d_2)$ 表示，考虑前 $i$ 天，第 $i$ 天练习了什么技能，另外两个技能分别有多少天没有练习。一个非常直观的感觉，$d_1,d_2$ 不会太大，是 $O(\sqrt {A})$ 级别的，$A$ 是值域。感性理解就是，超出这个级别会导致掉下来太多，而在这一段没有练习的时间的正中间强制练习这个技能，会取得 $\ge A$ 的收益，复杂度 $O(nA)$，注意一下要处理一些技能没开始练习的情况。

打摆

将图看做 $100$ 个点的完全图，每条边染成了黑色或白色。

先取出任意五个节点，解出这个大小为 $5$ 的团。每三个询问一下，得到了 $10$ 个未知数和 $10$ 个方程，把它解出来。由于未知数不多，可以暴力枚举。

每次选一个点 $u$ 加入团，将团中的节点随机打乱，得到排列 $p_1,p_2,\cdots,p_k$，令 $i=1$，询问 $(u,p_i,p_{i+1})$，将其减去边 $(p_i,p_{i+1})$ 的贡献，有两种情况。

• 边 $(u,p_i)$ 和 $(u,p_{i+1})$ 同色，我们可以知道具体的颜色，令 $i=i+2$，重复此过程。
• 边 $(u,p_i)$ 和 $(u,p_{i+1})$ 异色，令 $i=i+1$，重复此过程直到找到一对同色边，找到之后可以推出前面的一些边。

有一些细节：如果找完了都没有找到同色边，那么可以任意取一个 $j$，询问 $(u,p_j,p_{j+2})$ 或 $(u,p_1,p_j)$，得到 $(u,p_j)$ 和 $(u,p_{j+2})$ 的颜色，由于 $k \ge 5$，一定能找到一个合适的询问。

我们已经将团里面的点随机打乱了，每次问到同色的概率至少是 $0.5$。即，一次询问在最坏情况下，有 $0.5$ 的概率确定两条边，有 $0.5$ 的概率确定一条边，期望确定 $1.5$ 条边，询问次数期望大约为 $\frac{n^2}{2 \times 1.5}=\frac{n^2}{3}$。

抄袭

考虑 2-sat，有 $2n$ 个 $0/1$ 变量 $x_0,x_1,\cdots,x_{2n-1}$，每个变量表示 $x$ 轴上的一个点所在连线的方向，是向上还是向下的。想到这个，剩下的通过手玩都可以解决。

令 $l_i,r_i$ 表示颜色 $i$ 靠左，靠右的两个点的位置。

• 若 $l_i \lt l_j \lt r_j \lt r_i$，即区间包含，可以得到 $x_{l_j}=x_{r_j}$。
• 若 $l_i \lt l_j \lt r_i \lt r_j$，即区间相交，可以得到 $x_{l_j} \neq x_{r_i}$。

手玩 $2^4$ 种情况会发现是必要且充分的，构造方案可以对每个 $l_i$ 上的竖线钦定长度，$l_i$ 越小越长。用 2-sat 或并查集求解，复杂度 $O(n^2)$。可以主席树优化建图，复杂度 $O(n \log n)$。