ABC321题解

发布时间 2023-09-24 01:17:52作者: adam01

A

从低位到高位判断是否递增就行了。

B

直接暴力枚举。

C

深搜一下,答案最多 1023 个,然后要开 long long !!!

D

从小到大枚举 a 的同时从大到小枚举 b,然后前缀和优化一下就行了。

E

考虑把这棵树分成两部分,分界线为从 1 到 n 的路径。

然后在路径上从下往上dp出长为 \(k\) 的路径条数,对于其他的完全二叉树,路径条数要么是 \(2^k\) 要么是0。

然后从 \(x\) 开始一路向上走,答案累计 \(x\) 对面的另一颗子树(x xor 1)。注意要加上 \(x\) 这颗子树的答案。

大概就是令 \(f_{i,j}\) 为路径上端为 \(i\),长度为 \(j\) 的条数,然后

\(Ans=[deep > k] + f_{x,k} + \sum\limits_{i=0}^{deep}f_{(i\ \text{Rsh}\ i) \text{xor} 1,k-i-2}\)

F

对于 + 操作,普通的背包就行了。

对于 - 操作,注意到对于背包来说,物品的顺序是不重要的,那么把要删除的物品提到最前面来,然后反着做一次背包就行了。

G

状压dp。

\(f_i\) 表示 \(i\) 内的点构成了一个连通块的方案数。

容斥一下就出来了。

更新答案的时候就乘上可能的连边方案数累加进答案里就行了。

那么一种连边方式的贡献显然会被每个连通块分解并分别算入答案。