A

• 注意到一种选项最多填对 \(n\) 个题
• 所以答案是 \(\min(n,cnt_a)+\min(n,cnt_b)+\min(n,cnt_c)+\min(n,cnt_d)\)

B

• 注意到操作只能让奇数变多，偶数变少，所以我们只能把偶数全变成奇数
• 特判掉全是偶数的情况，容易得到答案下界：偶数个数
• 容易想到一个 naive 贪心做法：每次都拿出奇数里面最大的和偶数里最小的来操作
• 注意到：容易发现一种不太妙的情况：奇数里最大的比偶数里最小的还小怎么办？
• 如果以上情况发生，那么至少要“浪费”一次操作
• 考虑如何最大化这次“浪费”的操作的收益：拿最大的偶数和任意奇数，这样就得到了一个比所有偶数都大的奇数
• 注意到，这样操作以后，可以保证此后的任何一次操作可以保证换掉一个偶数
• 于是答案下界：偶数个数 +1
• 实现：统计特判全是偶数的 coner case，统计一下偶数个数记为 \(cnt\)，直接模拟过程，每次都拿出奇数里面最大的和偶数里最小的来操作，当发现奇数里最大的比偶数里最小的还小，直接输出 \(cnt+1\)，如果一直模拟到所有偶数都被换掉，则输出 \(cnt\)

C

• 抽象一下题意，如果 - 表示开灯，. 表示关灯，那么一个灯的开关区间其实是一条这样的直线
• ----....----....----....
• 如果把所有的灯的开关情况横向对比放到从零时刻开始的时间轴上呢？
• .----....----....----....---
..----....----....----....--
...----....----....----....-
....----....----....----....
• 以样例一为例，其实只不过是一条相同的直线平移而已
• 如果只是一条直线在平移，不难发现，本质不同的平移种类是 \(O(k)\) 量级的，具体地，是 \(2k\) 种
• 因为：灯的一个开关周期是 \(2k\)，如果两个灯分别在 \(i\) 和 \(i+2k\) 时刻第一次开启，那么他们的开启时间本质相同
• 现在，我们的时间轴从无限长缩短到 \(2k\)，这时不难想到一个做法：对于每个灯，把它的开启时间段拍到时间轴上，具体地，做区间 +1，最后用每个值为 \(n\) 的点更新答案即可，更具体地，这容易用差分实现
• 但这有一个问题：我们有限长度的时间轴上的每个点其实都代表了无限个时间点
• 其实很好解决，显然答案的下届是 \(\max{(a_i)}\)，所以每次更新答案只需要找最小的 \(ans\) 满足 \(ans=k*m+i\ \wedge \ ans\ge \max{(a_i)}\) 即可

D

• 首先转化题意：长度为 \(n\) 的序列，每段长度为 \(k\)，删除 \((n-1)/k\) 段，剩下的数的中位数最大是多少
• 注意到限制的强度与中位数大小正相关，显然二分答案
• 考虑如何 check
• 考虑一圈，只能 dp
• 考虑 naive 的 dp
• \(b_i=(a_i\ge mid) ? (1) : (-1)\)
• \(f_{i,j} \ 表示前 i 个数，删除 j 段的最大值\)
• \(显然只要 f_{i,j} \ge 0 即可\)
• 时空复杂度 \(O(n^2)\) 不可接受
• 这块需要一点注意力：注意到对于一个 \(i\)，合法的状态最多只有两个，为什么？
• 首先，前 \(i\) 个数最多删除 \(i/k\) 个长度为 \(k\) 的连续段
• 其次，前 \(i\) 个数最少删除 \(i/k-1\) 个长度为 \(k\) 的连续段，因为如果再少删一个，前 \(i\) 个数里就已经剩下超过 \(k\) 个数了，到 \(n\) 个数的时候，显然不可能删够 \((n-1)/k\) 段
• 综上，每次记忆化搜索即可，时空复杂度 \(O(n)\)
• 实现坑：多测+二分记得清空