noip模拟赛55总结

· · 个人记录

T1

没有复杂度正确的做法。但是凭借一手爆搜还是拿了满分。
首先求出所有因数。然后直接爆搜，有两个剪枝。
1.如果当前因数剩余数量不足以到达 k 直接返回 0
2.如果当前因数选最小的 k-now 个还是比当前 w 大，直接返回 0
然后就搜过去了。

T2

简单交互题，观察到边数不大，考虑用 log 次求出每条边相连的点。设当前已经处理 [1,i-1] 点之间的边，考虑加入 i 号点，我们直接询问 [1,i] 的点，减去 询问 [1,i-1] 的点，可以得到 i 号点与 [1,i-1] 中的点的边数。然后再二分求出每条边分别是什么。
可是这样会有两倍常数，复杂度来到 2m \log n+n 无法通过，把二分换成整体二分就过了。

T3

树形 dp，首先问题等价于给 [1,n-1] 个点每个点选一个 pre_x 满足， \forall dep_x>dep_y,dep_{pre_x}<dep_{pre_y}。即所有选择区间包含或者无交。
先从根到叶子开始考虑，一个点可以选择的点是他的父亲到根的路径上，不被区间包含的点，设有 j 个。当前点在 u，我们发现往下延申一格到达点 v，假设 v 选第 k 个可选的点，会使 j \leftarrow j+2-k ，这是因为往下一个会使 u 成为可选的点，然后会覆盖 k-1 个可选的点。由于这是一棵树形结构，如果答案都在叶子不好统计。
考虑把这个过程逆过来。设 f_{u,i} 表示当前在 u 节点，钦定 u 能选择 i 个不同的祖先， u 子树内的方案数。子树之间是不影响的。

f_{u,i}=\sum\limits_{j=1}^{i+1} \prod_{v \in son_u} f_{v,i+2-j}

使用前缀和优化转移即可 O(n^2)

T4

首先二分答案，考虑怎么判断一个 mid 是否可行，我们把异或起来大于等于 mid 的边挑出来。然后建一个二分图，如果有一条边 x,y 就让左侧图中 x 点连右侧图 y 点。 mid 满足条件的充要条件是这个二分图存在完美匹配。每次建图跑网络流显然不行。
考虑将这个二分图弱化为一般图（在同侧点之间连边），在这个图上找一组完美匹配。 可以证明这两个问题是等价的。
1.完全图是在二分图上加边建成的，答案一定不会更劣。
2.一组匹配可以转化为二分图，所以答案一定不会更优。
我们给这些点以他们的权值建一颗 trie 树，考虑两个节点，他们的 lca 深度越浅，意味着他们的 xor 越大。
还是沿用上面的二分答案。然后再 trie 树上树形 dp。
分两类dp：
设 f_x 表示在 x 子树内选则尽量多的匹配个数。
设 g_{x,y} 表示同时在 x,y 的最多匹配数。
设当前到了 x 节点
1.当前这位强制要为 1，那么只能选一个在左子树，一个在右子树的匹配，即 g_{ls_x,rs_x}。
2.当前这位没有限制，那么先尽量匹配横跨的，然后再递归处理没匹配完的那颗子树。
接下来考虑以下 f,g 怎么求
还是分类讨论，先从 f 开始。
1.当前这一位强制为 1，f_x=g_{ls_x, rs_x}
2.没有限制，令 l=min(cnt_{ls_x}, cnt_{rs_x}),r=max(cnt_{ls_x}, cnt_{rs,x})

f_x=l+min(f_{\text{[没匹配完的子树]}}, (r-l)/2)

下面是 g
1.当前这一位强制为 1，按左右子树的01， 10匹配，即 g_{x,y}=g_{ls_x,rs_y}+g_{rs_x,ls_x}
2.当前这位没有限制，跟 f 的2有点像。先尽量匹配横跨的，再把剩下的匹配。
容易发现复杂度就是遍历一边trie树，复杂度 O(n \log^2 n) 卡常后可以通过。

其实有 O(n\log n) 做法。
考虑从高到低考虑第 i 为是否能为 1 也就是检查 xxxxxxxx100000 这个答案是否合法，其中前缀的 x 已经检查过了，而且只有一个 1 后面全是 0，实际上只用遍历这一层的节点就可以了。