CVBB ACM Team

题意:问一个正$n$边形是否有两条垂直的边。

题解:答案为$[n \mod 4 = 0]$，相当于把$2\pi$分成四份$\frac{\pi}{2}$。

题意:过水已隐藏。

题解:摸了。

题意:将$n$个元素分成$k$组，每组$w_i$个，每组的权值为该组所有元素最大值最小值之和，求所有组权值之和最大值。

题解:贪心，最大值要最大的$k$个，然后按照$w_i$排序，最小值尽可能地选$k$个最大的。(不会证，蒙对了）

题意:鬼畜的树。每次每个点都会进行如下生长：如果是叶子节点，就增加一个子节点；如果有一个子节点，就增加两个子节点；否则不生长。问第$n$次生长后可以选择多少个不重叠的爪子，即一个父节点和三个子节点。

题解:画图可以发现如果只考虑新长的树，两次前的节点全都会长成爪子，因此有$f_i=f_{i-1}+2f_{i-2}$。这只是考虑了所有最新长的，画图可以发现每过$3$个就可以把之前的也选上，因此答案最后要加上$f(n-3),f(n-6)\ldots$。也可以考虑每过$3$个就可以选上一个新根，即$f_i=f_{i-1}+2f_{i-2}+[i \mod 3 = 0]$

题意:$n$道菜，每种有$w_i$个，有$m$个客人，每个客人会轮流光顾，一个人会喜欢两种不同的菜，每种菜只要有就会吃一个，如果两个都没有就会把厨师吃了。问能否给出一种顺序使得厨师活下来。

题解:首先如果有一种菜最后有剩余，那么喜欢这种菜的客人肯定不会吃厨师，把他们扔最后即可，然后减去对应的需求。继续考虑，如果最后所有客人都符合条件即不会死，否则会死。（因为后面的人无论前面怎么放都不会死，而前面的人吃的时候后面的人还没来，不用考虑它们，因此这个贪心是对的）

题意:博（巴）弈（耶）论（力）。一共有$t$轮游戏，每次有两个数字$s$和$e(s \le e)$，两人轮流操作，可以将$s$变为$s+1$或$2s$，先将$s$变为大于$e$的数的人输。每一轮输的人下一轮先手，最终是否胜利取绝于最后一轮。第一轮你先手，问你是否有：无论对手如何操作都必胜的方案，和无论对手如何操作都必输的方案。

题解:本质就是判断每一轮双方都在最优/差策略下，是先手必胜还是后手必胜，是先手必输还是后手必输，这样我们就可以判断每一轮是否可以必先手和是否可以必后手，进一步判断下一轮的状态，直到最后一轮。设$win(s,e)$为初始条件为$s,e$时先手是否必胜。

如果$e$是奇数，如果$s$是偶数，每次只需要$+1$，对手无论哪种操作都会将$s$变为偶数，若超过$e$你直接获胜，否则你继续$+1$得到的值依旧是奇数不会超过$e$，因此先手必胜。反过来$s$是奇数则后手必胜。

如果$e$是偶数，$2s>e$，双方都不能用翻倍，因此只能一个个加，那么$s$是奇数必胜，否则后手必胜。

如果$e$是偶数，$4s>e$，那么先手可以控制到达$2s>e$时$s$的奇偶性，因此先手必胜。

如果$e$是偶数，$4s \le e$，那么答案等同于$win(s,\frac{e}{4})$，因为如果先手可以让对方先超过$\frac{e}{4}$，相当于让自己到达了$4s>e$的状态，因此先手必胜，否则后手必胜。

考虑先手是否必输，如果$2s>e$，显然直接乘就输了，因此先手必输。

否则答案和$win(s,\frac{e}{2})$相同，因为如果先手可以让对方先超过$\frac{e}{2}$，相当于让自己到达了$2s>e$的状态，因此先手必输，否则后手必输。