12.29听课笔记

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/135297427

A

1，n个0，n个1

B

-1 放最小
+1 放最大

C

假如根定，可以直接dp

打表得只要根是叶子，答案取最小

---

直接暴摊也是对的

D

假如定根， $DP_u$ 内部分辨要多少个点。则 $DP_u=\sum DP_v-[存在一个儿子为叶子且分支>1]$ 。

每个节点的儿子最多丢掉一个，不然无法区分。而丢到的不能是叶子，因为不是叶子是不能不要的

打表得合法根为度数大于3的点

E

关键：保证有解

什么时候有解：
长宽看成边连边，原图为若干连通块。合法当且仅当每个连通块为树或者基环树。

基环树贡献为权值之和。树则贪心选一个点做根，这个是高，其他是宽。

（感觉挺妙的）

I

假如有 $(i,j)$ ，则 $i,j+m$ 连边，得若干连通块，相互独立

结论：任意一棵生成树都可以作为答案

对于最后操作一个格子，它的行和列一定抹不去，则一定可以保证剩下所有行和列都可以抹去

相当于选一个根，除了根都可以抹掉

相当于保留父亲删儿子

对于 $r$ 行 $c$ 列，有一行或一列不能选。可以直接背包。枚举哪行哪列不重要，所以直接做即可。

F

$\gcd(i,j)$ 可以直接容斥。 $f_i$ 表示右侧包含因子 $i$ 的左侧贡献和， $g$ 为恰好。 $g_i=f_i-\sum_{i|k}g_k$ 。这里是 $O(n\log n)$ 的

答案 $\sum g(i)\times i$

$f_k=\sum \gcd(a_i,a_j)[i|k ,j|k]$ 。取出所以下标元素，构造 $B=[a_k,a_{2k},\dots ,a_{tk}]$ .

则 $f_k=\sum \gcd(b_i,b_j)$ ， $b$ 的size总和小于 $n\log n$ 。

上面那东西可以写成 $\sum_k[\gcd(a_i,a_j)=k]k$ ，枚举 $k$ ，然后莫一下。 $\sum_{k|a_i}[\gcd(\frac{a_i}k,\frac{a_j}k)=1]k$ ，反一下： $\sum_{d}\mu(d)\sum_{d|\frac{a_i}k}1\sum_{d|\frac{a_j}k}1=\sum$

然后好像变了一轮成为 $\phi(d)=\sum_{d|x}\mu (d)$ ，

G

若 $x$ 不能表示，则 $a'=x-a$ ， $a'$ 也在 $A$ 里面。 $a$ 对应所有 $A$ 的元素。所以 $a`$ 是 $a$ 的循环平移。

把所有 $a$ 排序，再按 $m-a$ 排序。 $m-a$ 的序列后再添加 $m-a+m$ 。对于前面 $a$ 和后面某个区间为循环平移，则可以。差分判断一下是否循环平移即可，可以用哈希判断。

H

直接贪，然后流。右边相当于只有72个点

只需要判断是否满流，有Hall定理

左边每个子集，右边都有不小于size的，就一定存在完美匹配。左边只有64种子集，右边在64次时间找出流量总和。

---

另一种做法是每次的流和上一次很像，所以可以暴力退流，暴力增流

J

把 $B_x$ 视为 $x$ 这一位的值，若 $B_y\subseteq B_x$ ， 则形成DAG

结论：这个DAG任意一个闭合子图的集合都是可以构造出来的（就是这几位填1，其他位填0）。

必要显然。充分：取 $B_x$ 的代表元素（通过AND），然后全部OR起来

现在求40个点组成DAG的闭合子图个数，直接折半然后枚举子集