比赛传送门
赛时做出来五道题,涨大分(开心)
A. First Grid
problem
有一个两行两列的矩阵,每个格子有黑和白两种颜色,至少有两个黑色格子,问黑色格子是否构成一个连通块(四连通)。
显然,如果左上、右下都是白色或右上、左下都是白色,那么不能构成,否则能。
B. Hard Calculation
problem
有两个正整数 a 和 b 做加法,问是否需要进位。
大水题,一位一位地判断即可。
C. Cheese
problem
有 n 种奶酪,第 i 种奶酪每千克能提供 ai 的美味度,但最多能使用 bi 千克。你一共最多能使用 W 千克奶酪,问获得的总美味度最大是多少。
n≤3×105,W≤3×108,bi≤1000
这题太坑了,我本来以为是个奇怪的背包,后来发现,既然每个物品的重量都是 1,那不就是优先选最美味的奶酪的简单贪心吗?
D. Longest X
problem
有一个只包含 X
和 .
的字符串 S,你每次可以将一个 .
变成 X
,问最多 K 次操作后能获得的最长连续 X
字串的长度。
∣S∣≤2×105,K≤2×105
如果 K 次操作足以把所有的 .
都变成 X
(即点的个数 ≤K),那么答案一定是 ∣S∣。
如果不能,那么容易发现,答案一定是把 K 次操作全部用完。那么我们就从后往前扫,维护一个数组 ti 表示从第 i 位开始往后用 K 次操作能到达的最远位置(如果用不完 K 次就到了末尾,那么就是结尾下标)。维护完后就可以直接取长度最大值输出。这里放一下维护的代码实现。
1 2 3 4 5 6 7 8 9 10
|
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) 排一个序,每加一个点就加上符合条件的边,然后用并查集维护连通性即可。