ARC119D Grid Repainting 3
题意有 $n$ 行 $m$ 列的棋盘，每个位置颜色一开始是红色或蓝色。每次操作你可以选择一个红色格子，选择将这个格子所在行/列都涂成白色格子。求构造一组最大化白色格子的方案。$n,m \leq 2500$。题解比赛的时候没有尝试往二分图上去想，因为感觉这种带先后覆盖顺序的问题好像不是很能做，但是事实证明错了。。这种每次覆盖一行，或者一列的做法都考虑将行列抽象成点，操作位置抽象成边。对于这个题...
题意有 $n$ 行 $m$ 列的棋盘，每个位置颜色一开始是红色或蓝色。每次操作你可以选择一个红色格子，选择将这个格子所在行/列都涂成白色格子。求构造一组最大化白色格子的方案。$n,m \leq 2500$。题解比赛的时候没有尝试往二分图上去想，因为感觉这种带先后覆盖顺序的问题好像不是很能做，但是事实证明错了。。这种每次覆盖一行，或者一列的做法都考虑将行列抽象成点，操作位置抽象成边。对于这个题...
由于是恢复训练，所以会把所有题目解法都写写。A显然是少的每一堆就放一个，大的尽量均摊，设 $r < b$，那么就是判断 $\lceil \frac{b}{r} \rceil -1\leq d$。B模拟一下发现这东西无论什么路径权值都是 $nm-1$。证明可以考虑对 $n+m$ 归纳：首先 $n=m=1$ 是对的，考虑到达 $(n,m)$ 最后一步是怎么走的，如果是从 $(n-1,m)$...
A先将其压成二进制数，考虑两个人 $(i,j)$ 他们不可能拥有相同的通过数当且仅当它们不同的位的数量是奇数，也就是 $x\text{ xor } y$ 有奇数个 $1$。然后我赛时直接冲了个 FWT 过了稍微分析一下，发现两个数不同，当且仅当一个是 $1$ 一个是 $0$，我们只考虑这些不同的位置，发现恰好一个 $1$ 的数量是奇数一个是偶数。反过来也是对的。所以统计一下有奇数个 $1$ ...
A如果 $x > k$ 那么可以随便选。$[1,k]$ 我们选择后一半，这样保证任意两个数字相加都 $> k$ 就好了。B直接枚举即可。$0,1,8$ 反转后不变，$2,5$ 反转后互换。C$\geq s$ 最小，也就是尽量靠近 $s$。于是从大到小枚举相同的前缀长度，每次暴力看一下是否有一种方案可行，如果有的话就直接贪心按照字典序放置剩下的字符。D我赛时的做法：对于 $\leq...
A暴力枚举每个字母对应的括号即可。$O(2^3 n)$CodeB发现行列之间的影响只会在于四个角上，所以暴力枚举四个角是否填，然后确定上下界判断即可。$O(2^4)$。CodeC显然 $a_i,b_i > 0$ 和 $a_i,b_i < 0$ 可以分开做：我们只考虑 $a_i,b_i > 0$ 的情况。排序之后，我们枚举「推」到的最后一个位置是 $b_x$，那么我们找到 $...