洛谷4557 [JSOI2018]战争
Luogu LOJ 分析 设第一个部落的领地为 $A$，第二个部落的领地为 $B$。 假设 $B$ 移动了 $\vec{v}$ 后 $A$ 和 $B$ 仍有交，说明存在 $a\in A,b\in B$，满足 $b+\vec{v}=a$ 即 $\vec{v}=a-b$。 构造 $A$ 和 $-B$ 的闵可夫斯基和 $C$，问题变为判断 $\vec{v}$ 是否在 $C$ 内，二分出极角相邻的点...
分类 题解 下的文章
- 首页
- 题解
洛谷4559 [JSOI2018]列队
Luogu LOJ 分析 显然，所有学生跑到指定位置后，相对位置不改变会最优。 那么最终会有一部分学生向左跑，一部分学生向右跑，而且两部分一定是分开的。 考虑建立一棵以位置为下标的主席树。 设 $rk_i$ 表示 $i$ 是当前区间中的学生中编号第 $rk_i$ 小的。若当前递归的区间是 $[l,r]$ ，分四种情况： 没有学生，直接返回 $0$ 。 全部向左跑，直接返回 $\sum a_...
洛谷5772 [JSOI2016]位运算
Luogu 分析 先考虑 $n$ 个数互不相同的限制。为了方便设 $A_0=R$，则我们可以强制 $A_0>A_1>A_2>\cdots>A_n$。 考虑一个状压 DP。设 $dp_{i,S}$ 为前 $i$ 位，大小关系为 $S$ 时的方案数，这里的 $S$ 第 $i$ 位如果为 $0$ 则表示 $A_A_{i+1}$，否则表示 $A_i=A_{i+1}$。转移时直...
LOJ6053 简单的函数
LOJ 分析 注意到 不妨假装 $f(2)=1$，于是就可以 Min_25 筛了。 考虑到在 Min_25 筛的第二步即求 $S(n,j)$ 时，如果 $j=1$ 则质数部分算了 $2$ 的贡献，直接加上 $2$ 即可。 代码 // =================================== // author: M_sea // website: http://m-s...
洛谷5774 [JSOI2016]病毒感染
Luogu 分析 首先那个规定的意思是如果往左走就要把左边所有没治愈的村庄治愈。 可以发现整个过程可以划分成若干段，每段以任意顺序治愈后回到该段的起点，再治愈下一段。 考虑 DP。设 $dp_i$ 表示治愈前 $i$ 个村庄的最小死亡人数。记 $s$ 为 $a$ 的前缀和，$w_{i,j}$ 为从 $i$ 出发治愈 $[i,j]$ 中所有村庄再回到 $i$ 的最小死亡人数，容易得到转移 边...
洛谷5770 [JSOI2016]无界单词
Luogu 分析 容易发现一个性质：一个长度为 $n$ 的串的最小 border 的长度一定不超过 $\left\lfloor\frac{n}{2}\right\rfloor$。 第一问考虑 DP。设 $dp_i$ 表示长度为 $i$ 的无界单词的个数，转移时容斥并枚举最小 border 的长度，不难得到 第二问，考虑依次确定每个字符。每次先将当前字符设为 a 并计算无界单词的个数 $s$...
洛谷4324 [JSOI2016]扭动的回文串
Luogu 分析 先对每个串跑一遍 Manacher。设求出的分别为 $f_i$ 和 $g_i$。 这时第一、二类的最长长度即为 $\max\left\{f_i\right\}$ 和 $\max\left\{g_i\right\}$。 考虑第三类的最长长度怎么求。枚举中点 $i$，发现此时的扭动串变成了三段：一段是某个串中 $i$ 向外扩展出的回文串，一段是 $A$ 中继续向左扩展出的串，一...
洛谷4323 [JSOI2016]独特的树叶
Luogu 分析 先考虑一个 $\mathcal{O}(n^2)$ 的做法。 先求出以每个节点为根，整棵树的哈希值。 然后，把 $A$ 的所有 $n$ 个哈希值丢到一个 map 里去，然后枚举 $B$ 的每一个叶子节点，判断删掉后的哈希值是否在 map 中即可。 这个算法的主要瓶颈在于 $\mathcal{O}(n^2)$ 求哈希值，我们考虑优化这个过程。 异或满足可减性，很容易抵消掉。所以...
洛谷6096 [JSOI2015]地铁线路
Luogu 分析 第一问考虑最短路。对于每条线路建一个点，线路上的站向线路连边权为 $1$ 的边，线路向线路上的站连边权为 $0$ 的边。因为边权只有 $0$ 和 $1$ 所以可以 BFS。 第二问考虑一个 DP。设 $dp_i$ 表示到达 $i$ 时最多乘坐多少分钟的地铁。 假设一条线路的 $dis$ 为 $d$，则我们可能在 $dis$ 为 $d-1$ 的站上车，在 $dis$ 为 $d...
洛谷6095 [JSOI2015]串分割
Luogu 分析 先考虑 $k|n$ 时的做法。显然所有串的长度应相等。枚举第一个串的起始位置，则需要比较 $k$ 个串中最大的，事先倍长然后后缀排序即可利用 $rk$ 比大小。 考虑 $k\nmid n$ 时怎么做。显然最长的串至多比最短的串长 $1$。 考虑二分答案的排名 $mid$，check() 时仍然枚举第一个串的起始位置 $i$，然后记录一个指针 $p$ 一开始等于 $i$，每次...