A. FashionabLee
问是否可以通过旋转使得在平面直角坐标系中的正 \(n\) 边形同时有至少一条边与 X 轴平行，有至少一条边与 Y 轴平行。
显然，当且仅当 \(n\bmod 4=0\) 时有解，因为通过轴对称性可知可以被分为全等的四份（我一开始没看清题WA了一次/dk）
提交记录：#84757021
B. AccurateLee
给定一个01串 \(s\) ，如果 \(s_i=1\) 且 \(s_{i+1}=0\) 那么可以选择这两个数中的一个删除，然后后面的串向前补全。问这个串经过若干操作后最短的长度是多少，如果有多个最短的，输出字典序最小的。
我们考虑 \(1...0...1... 0\) 这样的串，我们可以把它消到只剩下一个 \(0\) （先用每个0前面的1消掉0，留下最后一个0消掉前面的所有1）。
对于含有前缀0和后缀1的情况，显然它们都不能被消去，所以最后答案为 前缀0的个数+[除去前缀0和后缀1后不是空串] 个0 和 后缀1的个数 个1。
提交记录：#84770401
C. RationalLee
给定 \(n\) 个元素，\(k\) 个集合，你需要把每个元素恰好放在一个集合内。第 \(i\) 个集合需要放进恰好 \(w_i\) 个元素，第 \(j\) 个元素的价值为 \(a_j\) ，每个集合的价值为它包含的元素的价值的最大值和最小值之和（如果只有一个元素计算两次），求所有集合的价值之和的最大值。\(k\leqslant n\leqslant 2\times 10^5\)。
考虑贪心，如果我们有 \(w=1\) 的集合，那么一定优先把最大的元素放到这种集合里。我们把元素按价值从大到小排序，把集合按大小从小到大排序，那么首先往第 \(i\) 个集合内放入第 \(i\) 个元素，然后贪心把价值小的元素放入大的集合中（比如说剩下的元素为 \(5,3,1\) 集合大小为 \(2,1\)，那么就分成 \(\{3,1\},\{5\}\) ，这样就是答案。
提交记录：#84777478
D. TediousLee
给定一种有根树的构造方式，版本1为一个单独的节点，对于版本 \(i\) ，我们从版本 \(i-1\) 递推：对于版本 \(i-1\) 的每个节点，如果它没有儿子，那么长出一个儿子；如果有一个儿子，那么再长出两个新的儿子；如果有三个儿子，那么不变。
现在给定版本 \(n\) 的树，每个节点一开始都是绿色，如果一个节点有三个儿子，且它们和这个节点本身都是绿色，那么可以把这四个点染成黄色，问最多能染出多少黄色的节点，答案 \(\bmod 10^9+7\)。\(n\leqslant2\times 10^6\)。
我们发现对于版本 \(i(i\geqslant3)\) ，它实际上由一个根接上两个版本 \(i-2\) 的树再接上一个版本 \(i-1\) 的树构成，那么我们可以考虑递推。发现这实际上在求一个类似最大独立集的东西，设 \(f[n][0/1]\) 为版本 \(n\) ，是否染了根节点的色的答案，那么对于 \(n\geqslant 3\) 则有 \[ \left\{ \begin{aligned} &f[n][0]=2*\max(f[n-2][0],f[n-2][1])+\max(f[n-1][0],f[n-1][1])\\ &f[n][1]=2*f[n-2][0]+f[n-1][0]+4 \end{aligned} \right. \] 这个东西在取模意义下是会WA的，因为取模后的 \(\max\) 不一定是取模前的 \(\max\) ，但是如果你直接这样交上去是会AC的，因为 \(f[n][0]\) 和 \(f[n][1]\) 的差实际上很小，在 \(n\leqslant 2\times 10^6\) 的情况下不会出现两个数取模次数不一样的情况。
考虑能不能不用 \(\max\) 来做，我们设 \(f_n\) 表示 \(n\) 的答案，\(r_i\) 表示是否可以在不染根节点的情况下让答案达到 \(f_n\) （对应到我们刚才的想法就是若 \(f[n][0]\geqslant f[n][1]\) 则 \(r_n=1\)），那么有 \(r_0=r_1=1\) ，我们发现当 \(r_{n-1}=r_{n-2}=1\) 时，我们可以把根节点染色，这时候染色的答案是不染色的答案+4，所以此时 \(r_n=0\) ，其他时刻如果我们强制染根节点，最多只会让答案+4，但是子树的答案至少少了4，所以不优，这时 \(r_n=1\)。简单归纳就知道当且仅当 \(n\bmod 3=0\) 时 \(r_n=0\) ，所以有 \(f_n=f_{n-1}+2*f_{n-2}+4[n\bmod 3=0]\) ，这样就避免了同时取模和取 \(\max\) ，然后这题也可以用矩阵快速幂或者其他方法加速到 \(n=10^{18}\)。
提交记录（第一种方法）：#84785701
E. DeadLee
你有 \(n\) 种菜和 \(m\) 个朋友。每种菜有 \(w_i\) 份，每个朋友有两种喜欢的菜（不会相同）。你需要安排朋友来的顺序，每个朋友来了会吃掉他喜欢的菜各一份（如果某一种没有就不吃那一种），问是否有一种顺序使得每个朋友都能吃到至少一种他喜欢的菜，有的话输出任意一种方案。\(n,m\leqslant 2\times 10^5\)。
我们把菜看成点，对每个朋友喜欢的两种菜之间连上一条边，设每个点的度数为 \(d_i\)，即喜欢吃这种菜的朋友的个数。
首先，我们发现如果 \(\forall i,d_i>w_i\) 则无解（证明待补），如果 \(\exist i,w_i\geqslant d_i\) ，那么对于所有与 \(i\) 相连的边都可以吃 \(i\) ，我们把这些边放到栈中，并且将与这些边相连的点的 \(d\) 都减去1（重边减去多次）。重复这个步骤如果最终所有边都被访过那么就合法，这时从栈顶一个一个输出就是答案。
提交记录：#84807161
F. BareLee
鸽了。