省选 2018 杂题汇总

本文主要是介绍省选 2018 杂题汇总，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

由于这些省太强了，6道做完不现实，于是就选了一些简单的做
[SDOI2018]战略游戏
答案为两条路径的必经的割点，正好是两点在圆方树上的圆点个数
然后每次询问建立虚树查询一下即可
[SDOI2018]荣誉称号
题意：将所有二叉树上含有 k+1 个点的路径的 $\sum a_i$ 变成 m 的倍数的最小代价
发现一个点与它的 k+1 级祖先同余，也就是说我们只需要考虑 k+1 层
考虑 dp，令 $f_{i,j}$ 表示从 i 往下，止于 k+1 层，链的和为 j 的最小代价，转移的话枚举当前边怎么变
发现需要预处理 $va{l}_{i,j}$ 表示把 $a_i$ 以及 i 的附属结点的一堆 $a_i$，变成 $j$ 的最小代价
$mdzz$ 预处理是 $O(nm)$ 的，然后发现可以$O(n)$ 预处理出 $va{l}_{i,0}$ 然后通过增量法 推到 $va{l}_{i,j}$
如何增量？ i 的附属结点有先全部充钱，增量为 $\sum b_i$， $sum$ 可以 $O(n)$ 处理
但是有些充了 m 的就可以全部不冲，所以要减去 ${\sum }_{a_i=j}m\ast b_i$，也可以$O(n)$ 处理，
用一个 $O(2^k\ast m)$ 的数组来存
复杂度是神仙一般的 $O(n+2^k\ast m)$
[八省联考2018]劈配
花式匈牙利，匈牙利匹配的时候可以强行匹配多个，如果匹配满了，就把那些人全部丢去在同一志愿重新匹配，复杂度是神仙一般严重不满的$O(m\ast n^2\ast c)$
对于第二问，可以二分答案，把排名在它前面的做一次匈牙利，然后再对它做一次看最多能匹配到哪儿
复杂度是$O(n^3\ast m\ast logn\ast c)$
然后发现可以暴力记录每次匈牙利完了的结果(前缀)，然后就可以跑严重不满的 $O(n^2\ast m\ast logn\ast c)$
[八省联考2018]林克卡特树lct
冷静分析后发现需要在树上选 k+1 条链，使和最大化
然后可以树形 $dp$，令 $f_{i,j,0/1/2}$ 表示到 i，选了 j 条链，当前点不在链上，是链的一个端点，或是在链的中间的方案数
$f_{u,j,0}=max(f_{u,j,0},f_{u,k,0}+f_{v,j-k,0})$
$f_{u,j,1}=max(f_{u,j,1},f_{u,k,0}+f_{v,j-k,1}+w_i,f_{u,k,1}+f_{v,j-k,0})$
$f_{u,j,2}=max(f_{u,j,2},f_{u,k,1}+f_{v,j-k-1,1}+w_i,f_{u,k,2}+f_{v,j-k,0})$
每个点递归完后合并 $f_{u,i,0}=max(f_{u,i,0},f_{u,i-1,1},f_{u,i,2})$
当 $k\le 3e5$ 时，我们可以在每形成一个链的时加一个$mid$，然后看最后选出几个链，如果多了就把
$mid$减小，反之加大，又名 dp 凸优化
[FJOI2018]领导集团问题
在一棵树上选一些点，使得祖先比儿子小，问最多选多少个
俗称：树上LIS
类似一般LIS，我们维护大小为1，2…，n 的LIS的最大高度是多少
每次进来一个点的时候，二分到第一个比它小的，然后把它改成当前点的权值
如果没有比它小的，那么把它插入，表示最大长度又大了1
于是用 set 启发式合并就可以了，其实 set 的大小就是 LIS的大小

这篇关于省选 2018 杂题汇总的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---