HNOI2014解题报告
Author: Pengyihao
Day1 T1 画框
思路
这个题目我其实是没有思路的。
网上说要用一种高深的最小乘积生成树的算法，我就学了一下。
我们把每一种搭配方案中，\(A\) 的和记做 \(x\)，\(B\) 的和记做 \(y\)。
那么一种搭配方案就可以看做一个坐标 \((x, y)\)。
因为 \(disharmony = x\cdot y\)，所以我们可以把 \(disharmony\) 看作反比例函数的 \(k\)。
因为反比例函数越靠近原点，\(k\) 越小。
所以我们要 \((x, y)\) 尽可能靠近原点。
找到 \(x\) 最小的方案 \(l\)，和 \(y\) 最小的方案 \(r\)，分别求出它们的坐标。
为什么大家都用KM算法，就我用费用流？好怕怕啊
然后我们就要找到在这两个方案的坐标的连线的下方，且三个方案形成的三角形面积最大的方案。
这个面积用叉积可以计算，最后发现形如 \(aA+bB\)，其中 \(A, B\) 是题目中的那个东西。
于是我们可以再跑一遍费用流求出这个方案 \(mid\)。
递归处理 \((l, mid)\) 和 \((mid, r)\)。
边界就是 \(l == mid || mid == r\)。
这个据说递归次数期望是 \(\sqrt{\ln n}\)，然后复杂度就对了。
代码
|
|
Day1 T2 世界树
思路
这也是我没学过的算法——虚树。
首先用单调栈维护右链，把虚树构建出来；
然后对于虚树上的每条边，把它的分界点找出来，然后分段赋给管理端点的那两个点。
注意判断管理端点的两个点相同的情况。
这个题目的构建虚树需要用lca，我用了倍增。
这个题目找到分界点也需要用倍增。
没有使用数据结构，代码却比数据结构题还要长。
代码
|
|
Day1 T3 米特运输
思路
根据每个点的权值，计算出根节点的权值。
然后用 \(n-\) 根节点权值的众数即可。
因为数据太大，所以需要取对数。
代码
|
|
Day2 T1 抄卡组
思路
首先，如果所有的字符串都有通配符，那么只需要两两比较前缀和后缀即可。
就是按每个字符串不包含通配符的最大前缀长度进行排序，比较一遍；
然后按每个字符串不包含通配符的最大后缀长度进行排序，比较一边。
如果所有的字符串都没有通配符，那么只需要比较hash值就可以了。
如果有些有通配符，有些没有通配符，将没有通配符的进行比较，看是否相同。
然后对于有通配符的，将通配符视作分隔符，即把原串分为一段一段的，分开进行匹配。
注意有通配符的字符串和没有通配符的字符串的首尾要对应。
代码
|
|
Day2 T2 道路堵塞
这是一道玄学题，需要依赖splay的复杂度的不确定性进行解题。
所以我跳过了它。
Day2 T3 江南乐
思路
首先用SG函数就可以做到 \(O(n^2)\) （枚举分开的情况，然后用朴素的统计就行了）
然后因为这题是分石子，我们可以发现分出来的石子很多都是一样的。
其实只可能分出两种石子，大小为 \(n mod i\) 的，和大小为 \(i-n mod i\) 的。
根据数量的奇偶性，最终会被消成不超过两个。
因为只关注奇偶性，所以对于 \(\lfloor n/i\rfloor\) 相等的多种分法，只需要计算最小的 \(i\) 和 \(i+1\) 两种即可。
复杂度为 \(O(n\sqrt{n})\)。
代码
|
|