第一次上蓝名，指不准哪天掉下来就可以第二次蓝名了，好耶
B. Parity and Sum (CF1993B)
首先特判原数组奇偶性相同的情况，奇偶不同时，由于替换过程只能产生奇数，故目标是将所有偶数变成奇数。假设当前选中奇数 \(a_i\) 和偶数 \(a_j\)，若 \(a_i<a_j\)，第一次操作时 \(a_i:=a_j+a_i\)，故最多两次操作能使 \(a_j\) 变成奇数。贪心地选取序列中最大的奇数 \(a_o\)，从最小的偶数 \(a_e\) 开始替换，每次使用 \(a_e' = a_o + a_e\) 继续下一步操作，尽可能避免出现两次操作的情况；若不得已需要在某个偶数上操作两次，则使 \(a_o\) 从最大的偶数开始替换，可证明此后不可能出现 \(a_e'<a_i\)，总次数即偶数个数+1.
C. Light Switches (CF1993C)
\(a_i\leq 10^9\) 的数据范围显然不方便处理，可以利用周期的性质，将开灯和关灯的时间取模后放在 \(2k\) 大小的差分数组上，最后检查是否存在 \(s[i] = n\) 的时刻即可。注意考虑最后一盏灯的启动时间，若 \(i<t\space mod\space 2k\)，需后延一个周期计算。
D. Med-imize (CF1993D)
赛时到最后也没写出来，评价为不掉分都是奇迹。
\(n\leq k\) 时中位数唯一，接下来只讨论 \(n > k\) 的情况。对于一个序列直接求中位数需要排序，不便于寻找最优解，而对于一个确定的数 \(x\)，有相对容易的方法验证其是否为中位数：用另一个数组 \(b\) 记录当前数字 \(x\) 与 \(a_i\) 大小关系，\(a_i\geq x\) 时 \(b_i = 1\)，否则 \(b_i = -1\)；若最终 \(sum=\sum\limits b_i\leq 0\)，则 \(x\) 必然不是中位数。考虑二分答案。
对于不同的最终序列，\(x\) 对应的 \(b\) 值不同，只要存在任一 \(sum > 0\) 即 \(x\) 合法，应尽可能获得 \(sum\) 最大的最终序列。设最终序列为 \(a'\)，观察 \(a'\) 与 \(a\) 的下标分布规律：由于每次删去恰好 \(k\) 个数，若下标从 \(0\) 开始，\(a'_i = a_j\) 时，\(j\space mod\space k = i\)，每个数字只可能出现在固定的位置上。至此转移关系已经确定，dp递推即可求得 \(sum\) 的最大值。
二分check函数：
bool chk(int x) {
for(int i = 0; i < n; i++) {
if(a[i] >= x) b[i] = 1;
else b[i] = -1;
}
dp[0] = b[0];
for(int i = 1; i < n; i++) {
if(i % k == 0) dp[i] = max(dp[i - k], b[i]);
else {
dp[i] = dp[i - 1] + b[i];
if(i > k) dp[i] = max(dp[i], dp[i - k]);
}
}
return dp[n - 1] > 0;
}
有一说一我dp是真菜啊，该加训了）
标签：963,int,sum,中位数,Codeforces,leq,序列,Div,dp From： https://www.cnblogs.com/meowqwq/p/18344052