hdu2020多校2
一些总结
做的时候越来越困，导致一堆那种还算简单的题最后想不到了。
其实也不只是困的原因，更重要的还是当遇到困难的时候真的应该安静下来努力克服，或者重新开会理一遍思路，这样就会快点想到，以免浪费太多没有意义的时间。
比如下面的一道裸费用流题，自己想来想去，先是想了想随机，然后再想DP，这是就应该静下心来，思考自己的方案是不是对的。看到匹配问题的时候就应该一开始就想到网络流类的问题才行。
A. Total Eclipse
题意
给你一个无向图，上面每个点有权值 $b_i$。进行若干次操作，每次选择一个连通块，然后将连通块内的 $b_i$ 减去 $1$。问至少多少次操作，使得 $b_i$ 全变为 $0$。
$n\le 10^5,m\le 2\times 10^5$。
题解
这是第一道做出来的题。
显然贪心，每次选择一个极大连通块内 $b_i$ 最小的点，然后将这个连通块的所有点权都减去 $b_i$，然后删掉 $i$ 这个点。
但是我们无法维护删掉后的连通性。
考虑倒着做，那么就只需要维护加点之后的连通性就可以了。
时间复杂度 $O(n\log n)$。
程序
1 |
|
E. New Equipments
题意
$n$ 个工人，$m$ 件设备编号 $[1,m]$。第 $i$ 个人选第 $j$ 个设备花费 $a_ij^2+b_ij+c_i$ ，对于每个 $k\in[1,n]$，求在 $n$ 个人里选 $k$ 个和设备配对的最小花费是多少。每个设备最多只能被匹配一个工人。
$T\le 10,n\leq 50,n\le m\le 10^8,b_i^2\geq 4a_ic_i,1\le a_i\le 10,|b_i|\le 10^8,0\le c_i\leq 10^{16}$
题解
因为 $a_i>0$，所有的二次函数有最下值。因此对于一个工人而言，他肯定会贪心的选择 $-\frac{b_i}{2a_i}$ 附近的设备。
这个附近的设备可以表示成一个长度为 $n$ 的区间。
那么能被选到的设备就最多只有 $n^2$ 个。
那么把工人看成一个点，放在左边；有可能被选上的设备放在右边。
随着 $k$ 递增，每次将费用加 $1$ 就好了。
而费用流的时间复杂度是流量乘上最短路的复杂度。
spfa费用流复杂度为 $O(n^5)$，dijkstra优化的费用流复杂度为 $O(n^4+n^3\log n)=O(n^4)$。常数都较小。
程序
dijkstra优化版本。
1 |
|
F. The Oculus
题解
暴力哈希即可，我这里写了双哈希。
程序
1 |
|
G. In Search of Gold
题意
一棵树，边有两种权值 $a_i,b_i$。有 $k$ 条边可以选择 $a_i$，剩下的 $n-1-k$ 可以选择 $b_i$。问这个树的直径的最小值。
$n\leq 20000,k\le 20,\sum n\le 2\times 10^5$。
题解
刚开始做的时候想到直接DP，结果发现是不太行的。
要使得两点距离的最大值最小，可以二分答案 $mid$。
那么就只需判断所有可能的情况中，是否存在一种方案使得任意两点的距离 $\le mid$。
这样子就可以DP了，设 $f_{i,j}$ 表示以 $i$ 为根的子树中，满足直径 $\le mid$，用了 $j$ 个 $a$ 时，子树内的点离点 $i$ 最大的距离的最小值。
然后 $O(nk^2)$ 转移即可。
程序
1 |
|
I. It’s All Squares
题解
显然地，我们只需考虑平行于坐标轴的矩形内的点，这个矩形最小且完全包住询问的多边形。
那么如何判断某个点是否在一个多边形里面呢？
根据计算几何那套理论，从该点向任意方向引出一条射线，该射线与多边形经过奇数次则在简单多边形内。
对于一个询问，字符串长度为 $4k$，则最多会包住 $k^2$ 个点。
$n,m$ 同阶，那么算一下发现，所有的询问最多包住 $\frac{\sum |S| n}{4}$ 个点，这是可以承受的。
于是暴力就好了。
程序
1 |
|
J. Lead of Wisdom
题意
有 $n$ 个东西，每个东西有种类 $t_i$，以及数字 $a_i,b_i,c_i,d_i$。
现在要你选出一个集合 $S$，要求这个集合里有每个种类最多有一个，满足以下式子最大：
$\large (100+\sum_{i\in S}a_i)(100+\sum_{i\in S}b_i)(100+\sum_{i\in S}c_i)(100+\sum_{i\in S}d_i)$
$T\leq 10,n\leq 50,0\le a_i,b_i,c_i,d_i \le 100$
题解
算法1
这个东西DP复杂度太高，贪心也不对。
那么就来随机算法吧。
毫无思路，简单粗暴。
我这里写的是爬山。
1 |
|
算法2
考虑直接暴力，时间复杂度 $O(k^{\frac{n}{k}})$。
我们来分析复杂度，设 $f(x)=x^{\frac{n}{x}} (x > 0)$，我们需要求它的最大值。
对 $f(x)$ 求导，先取 $\ln$ 再 $\exp$ 就容易算了。
解得：$f’(x)=n(1-\ln x)x^2x^{\frac{n}{x}}$ 。
当 $f’(x)=0$ 时，有 $1-\ln x=0$，即 $x=e$。
当 $0<x<e$ 时，$f’(x)>0$，函数单调增。
当 $x>e$ 时，$f’(x)<0$，函数单调减。
也就是说，当 $k$ 取正整数时，$k=2,3$ 时复杂度是最大的，算一下发现这两个都能过。
于是暴力就好了。