主要思路
刚开始以为是搞\(\log n\)个基底点，然后双向边上面做事情，最后发现找图上最小环的复杂度非常的高。所以 GG。
正解考虑把问题的规模进行缩小：也就是把一些答案预先特判掉。比如说，如果某一个位上有超过三个点连接，那么环的大小就可以被确定为是\(3\)，也就是最小的可能。考虑超出\(3 \times 60\)这么多就可以直接判定答案为\(3\)。
再考虑剩下的情况。此时，\(n\)已经缩小了很多，所以我们暴力建图，用 Floyd 跑最小环即可。
标签归档： 图论
[Fortuna OJ]Aug 10th – Group A 解题报告
A – 数学题
这道题二次函数的暴力分有 60 分，正解来自于论文。
这道题的主要是利用了一个结论，并且运用了辗转相除法的一种思想来对问题进行化简。首先，我们把向量调整至同向，且使\(|\vec{a}| < |\vec{b}|\)，然后再来推导一个结论：
结论 对于\(\vec{a}, \vec{b}\)，如果\(<\vec{a}, \vec{b}> \geq \frac{\pi}{3}\)，那么答案就是\(min\{|\vec{a}|, |\vec{b}|\}\)。
这个结论的证明参见《欧几里得算法的应用》。所以，我们就可以大概知道，我们可以将较长的向量分解：\(\vec{b} = k\vec{a} + \vec{b’} \)。由于我们知道，这道题可以笑掉这个\(k \vec{a}\)，所以就可以用辗转相除法的套路进行处理。具体见代码：
[Fortuna OJ]Aug 9th – Group A 解题报告
[Fortuna OJ]Aug 1st – Group A 解题报告
A – 水叮当的舞步
真的是玄妙重重。
我们先思考正常的暴力搜索：枚举每一次按下的颜色，然后检查继续更新。考虑用 IDA* 优化这个过程，首先估值函数就是剩下的颜色个数，因为至少需要更新这些颜色才有可能到达最终状态。然后注意控制 BFS 求连通块的个数的优化就行了。很好的一道题。
P3345:[ZJOI2015]幻想乡战略游戏题解
主要解法
动态点分治真不友好。
我们先来考虑\(O(nq)\)的静态做法。我们可以随便定一个根，\(O(n)\)处理两个数组来记录子树的权值和与子树之外的权值和，然后再来一次\(O(n)\)判定答案是否最小。
其实从这个地方，我们可以发现一些关系：如果一个点的子节点比父节点更优，会有这样的关系：
\[ dist(fa[u], u) * (sum[fa[u]] – sum[u]) < dist(fa[u], u) * (sum[u]) \]
其中\(sum\)数组是子树的权值和。总结一下就是：
\[ 2 * sum[u] > sum[fa[u]] \]
[Fortuna OJ]Jul 11th – Group B 解题报告
A – 照片
这道题是一道很考察思维的题目，我在这里介绍 DP 的做法。
我们考虑 DP。大概的方程可以写成：
\[ dp[i] = max\{ dp[j], j \in S_i \} + 1 \]
其中，\(dp[i]\)代表\([1, i]\)之间最多的斑点奶牛数量，然后\(S_i\)就是我们可以转移来的区间。我们可以提前处理好每一个点对应的\(lft_{S_i}, rig_{S_i}\)，也就是每一个点集合的左右端点。这个区间满足一个根本的条件：这个区间是点\(i\)左边最近的、不包含\(i\)的集合。我们肯定可以从这一段区间搞出最大的答案。预处理的时候先默认\(rgt[i] = i – 1\)，最后做个小 DP 更新数据即可。