本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平
题目编号 题目标题 难度 T1 午枫的切蛋糕 入门 T2 午枫的卡片游戏 普及- T3 午枫的分割数组 普及- T4 小午的构造 普及- T5 午枫的mex 普及/提高- T6 午枫的陪伴时间 普及+/提高
T1 午枫的切蛋糕
题目大意
有 n+1n+1n+1 个人分蛋糕，蛋糕可以沿着直径或半径切开，问平均分配最少需要切几刀。
解题思路
因为需要平均分且切蛋糕时只能沿着直径或者半径切开，所以我们可以考虑人数的奇偶性。
如果有偶数个人分蛋糕，则每一刀可以沿着直径切开；如果有奇数的人分蛋糕，则每一刀只能沿着半径切开。
注意总人数为 n+1n+1n+1 人，当只有一个人的时候，不需要切蛋糕。
时间复杂度 O(1)O(1)O(1)
参考代码
T2 午枫的卡片游戏
题目大意
双方都有 nnn 卡片，小枫告诉了小午自己的出牌顺序，双方进行比较点数，如果小午点数大本轮小午获胜，否则小枫获胜。求最终谁的胜场多。
解题思路
我们可以通过“田忌赛马”的思想，用自己尽量小点数的卡片和对方尽量大点数的卡片进行比较，最大化的减少敌方战力的同时最小化减少己方战力。让我们赢的时候尽量也选取最接近对方点数的卡片。
因此原本的卡片顺序已经不重要了，我们可以将双方的卡片排序，通过双指针模拟比较双方的点数。
时间复杂度 O(nlogn)O(nlogn)O(nlogn)
参考代码
T3 午枫的分割数组
题目大意
小午可以将一个数组分成前后两部分，第一部分给小午，第二部分给小枫，之后小午和小枫分别可以在各自的数组中选取 k1k_1k1 和 k2k_2k2 个数，然后比较两人选出的数的众数，大的一方获胜。判断小午是否可以获胜。
解题思路
题目中所选的数中数量最多的数称为众数，以下都称众数。
考虑当前有一个数组，最多选 kkk 个数，如何让选出来的数的众数最大，显然，我们只要选一个最大的数即可。
那么对于小午来说，他需要让小枫拿到的数尽可能少，因为小枫拿到越少的数，能选出比小午大的数的可能就更小。所以小午的最优选择一定是把前 n−1n-1n−1 个数分给自己，最后一个数分给小枫。
时间复杂度 O(n)O(n)O(n)
参考代码
T4 小午的构造
题目大意
有 a 、c 、w 三个字母若干个，有 ac 、wa 、aa 三种组合，求最多能得到多少组合，并且在得到最多组合的情况下，wa 的个数最少是多少?
解题思路
首先考虑组合出最多数量的单词：由于 c 和 w 只会被用于组成 ac 和 wa ，所有我们优先消耗 c 和 w ，最后剩下的 a 两两组合。
再来考虑如何让 wa 的个数尽量少：
* 在消耗 c 和 w 的情况下，我们一定优先消耗 c ，再消耗 w ；
* 当 w 被消耗完且 a 两两组合成 aa ，a 还有剩余时，我们可以将 wa 拆开，用其中的 a 去和剩余的 a 组合。
对于上述第二点，我们会发现最终如果有 a 剩余，那么一定只会剩下一个 a ，所有我们最后要拆 wa 时也只会拆一个，那么我们只需要判断组合完 ac 之后的 a 和 w 的奇偶性就可确定是否需要拆 wa 。
参考代码
T5 午枫的MEX
题目大意
求 mex{i⊕j∣i∈[1,n],j∈[1,n]}mex\{i\oplus j \mid i\in [1,n],j\in[1,n] \}mex{i⊕j∣i∈[1,n],j∈[1,n]} .
解题思路
通过打表，善于观察的同学可能会发现一定规律：{1,n≤22⌈logn⌉,n>2\begin{cases} \begin{aligned} 1,n\leq 2\\ 2^{\lceil\log{n}\rceil},n>2 \end{aligned} \end{cases}{1,n≤22⌈logn⌉,n>2 。
证明：对于 nnn 的最高位 111，仅保留这一位 111，对于低位可以任取，此时覆盖了 nnn 最高位为 111 的所有情况；然后 nnn 的最高位 111 这一位为 000，次高位为 111，对于低位可以任取，此时覆盖了 nnn 次高位为 111 的所有情况。依次类推，所以最小的不能被表示的就是 2⌈logn⌉2^{\lceil\log{n}\rceil}2⌈logn⌉，n=1,2n=1,2n=1,2 特判。
时间复杂度 O(Tlogn)O(Tlogn)O(Tlogn)
参考代码
T6 午枫的陪伴时间
题目大意
有 nnn 个开始陪伴的时间，每次陪伴必续连续陪 ttt 天，期间不能进行别的陪伴的任务，如果陪伴需要花费 costcostcost 元，否则需要花费 valvalval 元，求最少花费。
解题思路
首先我们可以考虑按照 aia_iai 从小到大排序，然后考虑通过DP如何解决。
设 dpi,0dp_{i,0}dpi,0 表示前 iii 个选项，其中没选第 iii 项的最小花费； dpi,1dp_{i,1}dpi,1 表示前 iii 个选项，其中选择了第 iii 项的最小花费。
其中 dpi,0dp_{i,0}dpi,0 的状态转移很简单： dpi,0=min(dpi−1,0,dpi−1,1)+vidp_{i,0}=min(dp_{i-1,0},dp_{i-1,1})+v_idpi,0 =min(dpi−1,0 ,dpi−1,1 )+vi 。
令 sis_isi 为 viv_ivi 的前缀和，pospospos 为 iii 左侧第一个小于 ai−ma_i-mai −m 的下标。那么 dpi,1dp_{i,1}dpi,1 的状态转移为：dpi,1=min(dppos,0,dppos,1)+si−1−spos+costidp_{i,1}=min(dp_{pos,0},dp_{pos,1})+s_{i-1}-s_{pos}+cost_idpi,1 =min(dppos,0 ,dppos,1 )+si−1 −spos +costi
最后答案取 dpi,0dp_{i,0}dpi,0 和 dpi,1dp_{i,1}dpi,1 的最小值即可。
参考代码
