inline">\(X\)，李华每次rating的变化最大值

inline">\(n\)，问李华最多可以正式参加多少场cf。

由于div.1没有计分下限，所以让李华的rating尽可能低即可。

时间复杂度为

main(){ios::sync_with_stdio(0);cin.tie(0),

cout.tie(0);int

的表格，每个格子被染上黑白两色中的一个，你可以选择任意多个白色格子并将其染黑，问是否存在一种染色使得所有的黑格是联通的（对角相连不算联通），并且在任一行或一列存在连续3个黑格。

表示黑格（这里与原题符号不一样），那么关键发现是所有的满足条件的方案一定是如下形状的：

---

第一种情况可以直接判断是否只有四个黑格并且他们构成正方形，如果初始情况不是4个黑格而是一个子图，那么可以并入情况二和三。

第二种情况可以判断所有的黑格是否全部落在相邻的两个对角线上，如果用

main(){ios::sync_with_stdio(0);cin.tie(0),

cout.tie(0);int

为当前已经购买的物品的价值综合，如果购买某个物品时忠诚度等级升级了，那么当前购买物品的价值就是升级获得的积分，求可获得的最多的积分以及对应的一个方案。

\mod{x}\)），每次选择要买的物品时使用如下策略：如果还未被购买的物品中价值最大的（记其价值为

x\)，那么就购买它，否则购买价值最小的，每次买完后更新

inline">\(sum\)。

不难发现如果价值最大的都无法升级时价值小的也无法升级，所以取出的都是价值最大的。

时间复杂度

main(){ios::sync_with_stdio(0);cin.tie(0),

cout.tie(0);int

给定一个长为n的数组b，问最少移除多少个元素，才能使得不存在

\}\)，将这个数组排序，第一关键字按增序排列，第二关键字按降序排列，记

inline">\(dp_i\)，于是得到了上面的转移方程。

至于为什么第二关键字是倒序，这时因为对于

相等的数来说，它的原本的位置越靠前，越容易继承到第一关键字比它小但是第二关键字比它大的数的

inline">\(max\)，不难发现，处理到

a_i.first\)，这一类用树状数组维护最值（这里相当于将第二类情况延时处理了一轮），第二类是

a_i.first\)，这一类比较第二关键字，第三类是

a_i.first\)，这一类直接继承前一个数的

inline">\(peltorator\)（cf名），代码链接：https://codeforces.com/contest/2161/submission/346684700

这是本蒟蒻在比赛的评论区发现的大佬的解答orz，感觉很妙，在这里分享给各位佬。

对之间连一条边，那么这道题变为找这个图的最小点覆盖，注意到这个图是个二分图，因为点

的点相连，所以由Kőnig定理，最小点覆盖等于最大边匹配，这个边匹配可以贪心的取：

先找

inline">\(O(n)\)。