2021-08-02新高二一期暑假集训7

D 小P走迷宫

标签

$dp$​ + $lgv$​ 引理 + 计数

思路

求从 $(1, 1)$​ 到 $(n, n)$​ 不相交，可以转化为 $A$​ 从 $(1,2)$​ 到 $(n - 1, n)$​ , $B$​ 从 $(2, 1)$​ 到 $(n, n - 1)$，路径不相交。 因为只有这样，才能使两人除起点和终点外路径不相交。

用 $lgv$​​ 引理可解.

Code

总结

两个人从 $(1, 1)$ 到 $(n, n)$ 可以考虑转化成 $(1,2)$, $(2, 1)$ 到 $(n - 1, n)$ , $(n, n - 1)$​​​ ，这样做可以去除两个人起点和终点相同的影响

C 关押罪犯

标签

状压 $dp$

思路

由于 $n$​ 很小，所以考虑状压，设 $f[i]$​ 表示集合 $i$​ 中的罪犯已经被分配, $cnt[i]$ 表示集合 $i$ 中罪犯的矛盾数。

那么有 $f[i] = f[j] + 1 (cnt[i \ xor \ j] \leq k \land j 是 i 的子集)$​​

复杂度为 $O(3^n)$

Code

总结

用 for (int j = i; j; j = i & (j - 1)) 可以总共 $O(3^n)$​​​​ 对每个集合枚举子集

B 小Z爱求和

标签

链表

思路

求每个区间第 $k$​​ 小的和， 可以转化为对于每个数，求它在多少个区间中是第 $k$​​ 小，把所有数从小到大排序，处理完一个数后把它删除，其它数的下标不变，这样可以保证序列中的所有数大于等于当前数。只需要从左边找 $i$ 个数，右边找 $k - i - 1$​ 个数， 那么在这些数中当前数一定是第 $k$​ 小。只要枚举 $i$​​ 就可以了。删除操作可以用链表.

Code

总结

求每个区间具有某个性质的数的和，可以对于每个数求一下它产生多少次贡献。

和第 $k$ 小有关的题，求每一个数的贡献，可以先把所有数从小到大排序，处理完一个数后把它删除。这样可以保证序列中的所有数大于等于当前数

A 吊灯

标签

性质 + 卡常

思路

性质

对于一棵树，它可以分成几个大小为 $d$ 的联通块，当且仅当满足以下条件.

1. $d|n$
2. 有 $\frac{n}{d}$ 个子树满足大小为 $d$​ 的倍数.

充要性和必要性都显然. 因为每分出一个联通块，一定会减少一棵大小为 $d$​ 的子树，同时一些子树的大小变成 $d$ ，如果找不到大小为 $d$​ 的子树，那么就不满足要求了.此时显然不能保证有 $\frac{n}{d}$ 个子树满足大小为 $d$​​​ 的倍数.因为一定有至少一个点是不能分到联通块中的.

枚举 $d$ ,开一个桶 $cnt_i$ 表示大小为 $i$​ 的子树有多少个, 在 $O(\frac{n}{d})$ 的时间内可以求出大小为 $d$ 的子树的个数.

总复杂度为 $(10 \times \sigma(n))$​​，只有 $70$​​ 分. 因为被卡常了.

发现我们并不需要把树真正的建出来，这样可以省掉递归的常数，拿到 $100$ 分。

Code

总结

有时候，如果只需维护一些简单的信息，尤其是只从儿子向父亲转移，可以不用把树真正建出来。这样可以省掉递归的常数.