POI2012 简要题解
Festival 考虑差分约束。设 $dis_{i,j}$ 表示 $X_i$ 至多比 $X_j$ 大多少，则 若 $X_i+1=X_j$，则 $dis_{i,j}=-1,dis_{j,i}=1$，连边 $(i,j,-1)$ 和 $(j,i,1)$。 若 $X_i\leq X_j$，则 $dis_{i,j}=0$，连边 $(i,j,0)$。 考虑无解的情况。一种情况是出现负环，另一种情况是...
Festival 考虑差分约束。设 $dis_{i,j}$ 表示 $X_i$ 至多比 $X_j$ 大多少，则 若 $X_i+1=X_j$，则 $dis_{i,j}=-1,dis_{j,i}=1$，连边 $(i,j,-1)$ 和 $(j,i,1)$。 若 $X_i\leq X_j$，则 $dis_{i,j}=0$，连边 $(i,j,0)$。 考虑无解的情况。一种情况是出现负环，另一种情况是...
Codeforces Luogu 分析 显然可以直接 Dijkstra，问题在于实现一个支持加法和比较大小的优秀的高精度。设比较大小的复杂度是 $\mathcal{O}(\alpha)$，加法的复杂度是 $\mathcal{O}(\beta)$，则 Dijkstra 的复杂度为 $\mathcal{O}(\alpha(n+m)\log n+\beta m)$。 因为边权全部是 $2$ 的幂，...
Luogu 分析 先对每个串跑一遍 Manacher。设求出的分别为 $f_i$ 和 $g_i$。 这时第一、二类的最长长度即为 $\max\left\{f_i\right\}$ 和 $\max\left\{g_i\right\}$。 考虑第三类的最长长度怎么求。枚举中点 $i$，发现此时的扭动串变成了三段：一段是某个串中 $i$ 向外扩展出的回文串，一段是 $A$ 中继续向左扩展出的串，一...
Luogu 分析 先考虑一个 $\mathcal{O}(n^2)$ 的做法。 先求出以每个节点为根，整棵树的哈希值。 然后，把 $A$ 的所有 $n$ 个哈希值丢到一个 map 里去，然后枚举 $B$ 的每一个叶子节点，判断删掉后的哈希值是否在 map 中即可。 这个算法的主要瓶颈在于 $\mathcal{O}(n^2)$ 求哈希值，我们考虑优化这个过程。 异或满足可减性，很容易抵消掉。所以...