ABC396 题解集合

__vector__ · 2025-03-14 17:36:34 · 题解

A

暴力枚举就可以了。

B

注意到删除操作最多 100 次操作，不会出现删除操作的时候没有可以删除的卡牌的情况。

先进先出，队列维护。

C

显然在已经确定选择的球的数量的情况下，优先选择大的。

首先将黑色白色分别降序排列。

然后，枚举白色球选择的数量 x，然后，黑色球最优贡献值就是 \max\limits_{y=x}^n pre_y，pre_i 代表前 i 个黑色球的价值总和。
把 pre 的后缀最大值预处理一下就可以了。

D

这道题无法使用状压 dp，原因在于无法将所需要的所有状态加入。

但是注意到 n\le 10，可以暴力枚举所有可能的路径，判断是否合法即可。

一个简单的实现是 O(n!) 枚举全排列作为路径顺序，检查合法的过程则仅截取到 n 第一次出现的位置。

E

考虑在 x_i,y_i 之间建一条权值为 z_i 的边。

注意到每一位都是独立的，并且由于异或的性质，同一个连通块只要有一个点的某一位翻转，连通块内所有其他节点的这一位也都需要翻转。

找到所有的连通块，对于每个连通块，随便找一个起始节点将其赋值为 0，然后求出连通块内每一位的 0,1 数量。

根据这个数量决定每一位是否翻转即可。

F

考虑任意一对数造成的贡献。

• 对于 \forall i \lt j,a_i \lt a_j：
  会对 k \in [m-a_j,m-a_i) 造成 +1 的贡献。
• 对于 \forall i \lt j,a_i \gt a_j： 会对 k \in [0,m-a_i),[m-a_j,m] 造成 1 的贡献。

把包含 i 作为未知量的归类到 i 的贡献，包含 j 作为未知量的归类到 j 的贡献，同时包含的那一项拆一下也可以分别归类。

归类完之后可以转化为若干个区间加，最后统一查询一遍就可以。

G

这里