ABC-229解题报告

比赛传送门

赛时做出来五道题，涨大分（开心）

A. First Grid

problem

有一个两行两列的矩阵，每个格子有黑和白两种颜色，至少有两个黑色格子，问黑色格子是否构成一个连通块（四连通）。

显然，如果左上、右下都是白色或右上、左下都是白色，那么不能构成，否则能。

B. Hard Calculation

problem

有两个正整数 $a$ 和 $b$ 做加法，问是否需要进位。

大水题，一位一位地判断即可。

C. Cheese

problem

有 $n$ 种奶酪，第 $i$ 种奶酪每千克能提供 $a_i$ 的美味度，但最多能使用 $b_i$ 千克。你一共最多能使用 $W$ 千克奶酪，问获得的总美味度最大是多少。

$n\le 3\times 10^5,W\le 3\times 10^8,b_i\le 1000$

这题太坑了，我本来以为是个奇怪的背包，后来发现，既然每个物品的重量都是 $1$，那不就是优先选最美味的奶酪的简单贪心吗？

D. Longest X

problem

有一个只包含 X 和 . 的字符串 $S$，你每次可以将一个 . 变成 X，问最多 $K$ 次操作后能获得的最长连续 X 字串的长度。

$|S|\le 2\times 10^5,K\le 2\times 10^5$

如果 $K$ 次操作足以把所有的 . 都变成 X（即点的个数 $\le K$），那么答案一定是 $|S|$。

如果不能，那么容易发现，答案一定是把 $K$ 次操作全部用完。那么我们就从后往前扫，维护一个数组 $t_i$ 表示从第 $i$ 位开始往后用 $K$ 次操作能到达的最远位置（如果用不完 $K$ 次就到了末尾，那么就是结尾下标）。维护完后就可以直接取长度最大值输出。这里放一下维护的代码实现。

//a[i]为0则是点，为1则是X
//now表示当前的i能到达的最远位置
//nowf表示到达最远位置需要花费几次操作
int now=n,nowf=0;
for(int i=n;i>0;i--) {
    nowf+=(!a[i]);
    while(nowf>k)
        nowf-=(!a[now--]);
    t[i]=now;
}

E. Graph Destruction

problem

给你一个 $n$ 个点、$m$ 条边的无向图，依次删除编号为 $1-n$ 的结点，每次删完后问剩下的连通块个数。

正着删边没法维护，我们考虑反向处理，每次加边。仔细像一下就会知道，每次加一个点，就要加上这个点与已有结点的边，即 $\min(u,v)=i$ 的边。所以我们按照 $\min(u,v)$ 排一个序，每加一个点就加上符合条件的边，然后用并查集维护连通性即可。