CC 采用 $\text{CC BY-NC-SA 4.0}$ 许可，转载请注明：“转自 HDUMUTC2020-02 LAYOUT”
Intro
学业稍微有点重，趁着假期和几个朋友打打比赛复健一下。
不是很在状态，所以难题这里基本上都不会有，基本上都是签到题。
http://acm.hdu.edu.cn/contests/contest_show.php?cid=880
题目
1001 Total Eclipse
题意
给定一个图，每个点有权值。每次操作可以给一个连通块点权 -1，求全变 0 的最少操作次数。
题解
联想到 NOIP2018-d1t1，感觉就是同样的模型扩展到了图上。维度增加了！
做法大概是每次操作减去一个连通块的最小值。
感性理解一下，觉得如果最小值在割点，不可避免要去减；如果不在，减了不亏
反过来搞一下，按点从大到小排序写个并查集就行
备注
有个乘法的地方没开LL，WA了 1 发 + 查了 10min，有点毒性
1005 New Equipments
题意
给定 n 个工人，每个工人要匹配一个机器，机器编号从 1 ~ m。工人 i 匹配机器 x 的费用是 $ A_ix^2 + B_ix + C_i$， $B_i^2 \leq 4A_i C_i $。对每个 $ k, 1 \leq k \leq n $，输出 k 个工人匹配机器的最小花费。
$ n \leq 50, m \leq 10^8$
题解
这个题出的太丑了吧，整什么b^2-4ac，不如直接给模板题
实际上每个工人只有最近的 n 个机器有用，拎出来跑个二分图最大权匹配就行
$ n^2 $ 个点，$ n^2 $ 条边，最大流为 $ n $，直接费用流是 $ O(n^5) $ 的，能过。
还可以用 Johnson 算法去掉负权跑 DJ，会更快一些。
备注
这个题不知道为啥现场没过
最短路杂谈
这里稍微写点关于最短路的东西：
所谓 SPFA 实际上应该称作 队列优化的 Bellman-Ford 算法。
Bellman-Ford 算法：对图中每条边做一次松弛操作，整个过程暴力做 N 次。
正确性：最短路不含超过 N - 1 条边。相应的，如果第 N 次循环松弛成功，说明存在负环。
队列优化的 Bellman-Ford 算法：如果某个点权值不变就没必要松弛，所以每次把要松弛的点入队即可。如果某个点入队达到 N 次，说明有负环。
1006 The Oculus
题意
定义“斐波那契进制”：把数写成Fib数列中元素和的形式，每一位为 0 或 1，代表取不取Fi，不能有相邻两项为 1。给定 A, B, C 的Fib进制形式，已知 C 是 A * B 然后把某一位从 1 改成 0 得来的，求出是哪一位。
$ T \leq 10^4, \sum |A|, \sum |B| \leq 5\times10^6$。（5s）
题解
枚举究竟是改的哪一位，然后用HASH验证。可以多模数。
备注
这个题不是我做的
1007 In Search of Gold
题意
给一棵树，每条边有 A 类边权和 B 类边权。初始全为 B 类，可以把恰好 k 条 B 类变为 A 类。求直径的最小值。
题解
二分直径长度，树背包 A 类条数
备注
这个题之前一直读的是假题，然后最后一个小时才写，状态还是不太行，要好好读题 不过出人意料地没有出问题，这很好
1009 It’s All Squares
题意
给一个 n*m 的网格。人可以在网格的边界上走，网格里面有数。每次询问人从一个点开始走，用字符串 S 来刻画，走出一个简单多边形，问多边形里面有多少种不同的数。
$ n,m \leq 4\times10^2 , q \leq 2\times10^5, \sum|S|\leq4\times10^6 $。（4s）
题解
不规则多边形通用方法：射线法（判断是否在多边形内）
考虑暴力枚举多边形（矩形边界）内所有数。那么我们希望用|S|围出尽量多的面积：显然是：$ \frac{\sum|S|}{4n}\times n^2 \leq 4\times 10^8 $，可行
射线法：判断两个方向与多少个边界相交。这个可以在矩形边界的格子里递推，时间复杂度关于面积线性。
备注
某种意义上这个也算简单题，但是感觉这场大家都不是很在状态…
1010 Lead of Wisdom
题意
有 n 个物品，每个物品有所属种类，和四个属性值 a, b, c, d。每个种类选至多一种，最大化：$(100 + \sum a)(100 + \sum b)(100 + \sum c)(100 + \sum d)$。 $ n \leq 50, T \leq 10 $（8s）
题解
暴力。算出来大概是7e7级别，能过。
注意要跳过空的种类，否则复杂度多一个 n 就T飞了。
备注
这道题是通过人数最多的题，然而我们还是没过。原因如上。
也有我的怠惰在里面，如果我仔细分析的话是能看出来多写了一个 n 的。
当时强行去脑补各种随机化算法了。后来有橙分析说实际上这个难度要高于四维偏序，虽然我不太懂为啥
所以实际上捞题还是要注意，先看能不能补救原来的算法，再想新的：
- 复杂度分析
- 确认代码流程
- 确认算法模板正确性
- 最后再尝试构建新算法
Author: Fanfaredash
