CF666E Forensic Examination
Codeforces Luogu 分析 先对 $T_{1..m}$ 建立广义 SAM，然后把 $S$ 丢上去匹配，记录每个前缀匹配到的节点 $pos_i$。 考虑对每个节点维护一棵以 $T$ 的下标为下标的线段树，线段树上的每个节点维护当前串在这些 $T$ 串中的出现次数的最大值及其下标。这可以通过线段树合并预处理出来。 询问时，我们首先找到 $s_{l..r}$ 所在的节点，直接从 $po...
标签 倍增 下的文章
- 首页
- 倍增
洛谷4384 [八省联考2018]制胡窜
Luogu LOJ 分析 首先容斥一下，求出三段都不包含 $s_{l..r}$ 的方案数，然后用 ${n-1\choose 2}$ 减掉即为答案。 我们先把所有和 $s_{l..r}$ 相等的子串位置都找到，然后分类讨论一下： 如果有三个互不相交的串，方案数是 $0$。 如果最左边的串和最右边的串相交： 考虑 $i$ 的位置： 如果 $i\in[1,l_1)$，那么 $j\in(l_m,...
洛谷5284 [十二省联考2019]字符串问题
Luogu LOJ 分析 容易想到一个图论模型，即从每个 A 类串向它所支配的 B 类串连边，从每个 B 类串向以它为前缀的 A 类串连边，并将所有 A 类串的权值设为长度。这样问题变为求最长路，如果有环输出 -1。 第一类边可以直接连，但第二类边暴力连显然不行，考虑一些优化。 对反串建 SAM，此时 Parent 树上每个点的祖先都是它的前缀，于是我们只需要将树上每个 B 类串对应的节点向...
LOJ2865 「IOI2018」狼人
LOJ UOJ Luogu 分析 以端点的 $\min$ 为边权建一棵 Kruskal 重构树，以端点的 $\max$ 为边权建一棵 Kruskal 重构树。 那么我们在第一棵树上从 $s$ 向上跳到最浅的 $\geq l$ 的点，其子树就是人类状态下从起点出发能走到的点；在第二课树上从 $t$ 向上跳到最浅的 $\geq r$ 的点，其子树就是狼人状态下能走到终点的点。 那么我们只需要求这...
POI2011 简要题解
Conspiracy 考虑如果已经有了一组方案怎么得到其它的方案，可以发现只有以下三种情况：团内的一个点移了出去、团外的一个点移了进来、交换了团内和团外的两个点。只需要求出每个点是不是之和对方集合中的一个点冲突即可。 于是考虑构造一组方案。注意到每个点只能在团内或团外，于是 2-SAT 即可。 可能会有些卡空间。 代码 Lollipop 可以发现如果存在一段和为 $w$，则一定存在一段和为 ...
洛谷3517 [POI2011]WYK-Plot
Luogu LOJ 分析 首先要会最小圆覆盖而且知道它是期望 $\mathcal{O}(n)$ 的。 显然可以二分答案，于是我们只要想办法判定能否分成最小圆覆盖半径都 $\leq mid$ 的 $\leq m$ 段即可。 显然最小圆覆盖半径是随着点的增多而不降的，所以每段的点越多越好。于是可以想到暴力找每段的右端点，然而可以卡成 $\mathcal{O}(n^2)$。还有一个想法是二分右端点...
CF1067D Computer Game
Codeforces Luogu 分析 显然我们会在刷出一次升级机会后升级 $b_i\times p_i$ 最大的那个游戏，然后在接下来的时间内一直玩它。为了方便设 $M=\max\left\{b_i\times p_i\right\}$。 考虑 DP。设 $dp_i$ 表示还剩 $i$ 秒且还没有得到过升级机会的最大期望收益，枚举每个游戏可以得到转移 于是只要快速找到决策点改变的位置即可...
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)$。 考虑无解的情况。一种情况是出现负环，另一种情况是...
CF1354G Find a Gift
Codeforces Luogu 分析 蓝题都不会做了 /kk 因为 $k\leq \frac{n}{2}$，所以随机一个盒子是石头的概率 $\geq\frac{1}{2}$。 那么我们可以先通过若干次随机来较高正确率地判断第一个盒子是不是石头。 如果不是的话直接输出即可；否则，可以通过倍增找到第一个礼物所在的区间 $[2^k+1,2^{k+1}]$，在这个区间中二分即可。 代码 // ==...
洛谷4768 [NOI2018]归程
Luogu 分析 考虑把边按海拔从大到小排序并建 Kruskal 重构树。 每个询问从 $v$ 往上倍增找到最浅的 $a>p$ 的点 $u$，则子树 $u$ 中的点是可以开车到达的，找一个到 $1$ 的距离最小的点即可。 一遍 Dijkstra（关于 SPFA：它死了）预处理出每个点到 $1$ 的最短路，在重构树上维护子树最值即可。 代码 // ====================...