A – 家族
这道题真的是送分题（快要想出来直接暴力枚举+并查集的时候去看了题解，最后发现就是这么 sb）。
考虑枚举频段区间\([L, R]\)（将边进行排序，确定下界之后再枚举上界），这个地方是\(O(m^2)\)的。每次枚举下界的时候都要初始化并查集，然后合并两个集合的时候按照大小来修改答案就行了。
网络流
定义
在有向图中，有唯一的源地（入度为 0）和汇点（出度为 0），每一条边都有非负的容量，且整张图都会保证平衡状态。这样的图叫做网络流图。
基本网络流算法
最大流 – Dinic
每秒钟每条管道流动的液体最多。常用的算法是 Dinic。先做一次 BFS 划分层次，再用 DFS 来进行流动。Dinic 算法就是在网络图上对残存网络进行利用求得最大流。
其中值得一提的是，Dinic 算法中有一个优化方式可以快速求最大流——当前弧优化。当前弧优化可以在每次找残余网络之前记录遍历到的 head 指针，避免不必要的遍历。
「Fortuna OJ」Jul 6th – Group B 解题报告
A – 调整 Tweak
这道题我在考场上打了一个错解，还骗到了 30 分。
正常的思路是：在最短路图上找到几个边进行修改。然而，最优的解决方案并不一定出现在最短路图上的边上，也可以通过修改次优边进行解决。所以，这道题其实跟最短路没什么太大关系，即使后面会用到 Djisktra 来求最短路。
我们可以把一个\(G(V, E), |V| = n, |E| = m\)复制\(n\)份，然后对于第\(k\)份图中的有向边\((u_k, v_k, w_k)\)，可以生成一个副本来连接下一层的目标点，也就是每一条边会派生出\((u_k, v_{k + 1}, 0)\)，当最后求最短路时，经过这样的一条边可以被认为是修改一条边，且，这个边是单向向下的，所以不会出现同一层修改多次的情况。最后只需要求这张图的最短路，然后判定满足\(dist[n_k] \leq c\)的最小\(k\)就行了。
「Fortuna OJ」Jul 4th – Group A 解题报告
A – 非回文数字
这道题还没写，是一道数位 DP，推荐记忆化搜索。
B – 管道
这道题是一道相当好的题目。
首先对于\(m = n – 1\)的情况，也就是树的形态下，可以考虑自下向上推，也就是从叶子节点开始推起，参考代码中 Toposort 的写法。然后，对于\(m > n\)的情况可以直接输出\(0\)，因为这个方程组并不存在唯一的解：\(m\)个未知数仅提供\(n\)个条件，这样是不成立的。
最后考虑\(m = n\)的情况。这种情况就是基环树了。首先，Toposort 会把支链上的答案全部统计完毕，并且合并到环上的点。最后，我们唯一要多做的事情，就是处理环上的方程组。考虑一个这样的环：
「Fortuna OJ」Jul 5th – Group B 解题报告
A – 铁轨
sb 题，不讲。（为什么 B 组会有这么水的题？）
B – 独立集
这道题翻译过来就是独立集计数，也是一道 sb 题。
首先，这种计数题肯定都是基于树形 DP 的，所以我们来设状态。起初，我设的状态是：该节点所在的子树的独立集个数为 \(dp[u]\)。后面发现不太对劲：状态转移时，大体可以分为两种进行计数，一种是儿子子树内的乘积（包括空集在内，这样就可以算所有的并集个数），还有一种是孙子子树和本节点的独立集。所以，这些信息要分开储存：设\(dp[u][1]\)为独立集个数，\(dp[u][0]\)孙子节点的独立集个数。所以，可以得到下列方程：
错题集
数学
三角函数的变换和解三角形
已知 \(2\sin^2 A + \sin^2 B = 2 \sin^2 C\)，求\(\frac{1}{\tan A}+\frac{1}{\tan B}+\frac{1}{\tan C}\) 的最小值。
很好的一道题。可以大概了解到需要用均值不等式解决最后的最小值，便不再关心正切的具体值，而去关心用一个角的正切来解决。考虑变形：
\[ \begin{gather}
2a^2+b^2 = 2c^2 \tag{1} \\
\text{考虑余弦定理:} \\
2ab \cos C = a^2+b^2-c^2 \tag{2} \\
\text{联立(1)(2)式:} \\
2ab \cos C = c^2 – a^2 \to 4ab \cos C = 2c^2 – 2a^2 \\
\text{带入(1)式:} \\
4ab \cos C = b^2 \to 4a \cos C = b \\
\text{考虑正弦定理转换:} \\
4 \sin A \cos C = \sin A \cos C + \sin C \cos A \\
3 \sin A \cos C = \sin C \sin A \\
3\tan A = \tan B \\
\end{gather} \]
之后裸的带入就行了，最后注意一点就是\(\tan C\)的转换用正切和公式和诱导公式变个型就可以了：
\[\begin{aligned}
\tan C &= \tan (\pi – A – B) = \tan (- A – B) = -\tan (A + B) \\
&= \frac{\tan A + \tan B}{\tan A \tan B – 1} \\
&= \frac{4 \tan A}{3 \tan^2 A – 1}
\end{aligned}
\\
\begin{aligned}
\text{原式} &= \frac{1}{\tan A} + \frac{1}{\tan B} + \frac{1}{\tan C} \\
&= \frac{4}{3 \tan A} + \frac{3 \tan^2 A – 1}{4 \tan A} \\
&= \frac{16 + 9 \tan^2 A – 3}{12 \tan A} \\
&= \frac{13}{12 \tan A} + \frac{3 \tan A}{4} \geq \frac{\sqrt{13}}{2}
\end{aligned}\]