给 n n n 个点 m m m 条边无向图，边权均为 1 1 1，每次询问两个点之间是否有长度为 d d d 的路径，可以不是简单路径。
因为你可重复经过一个点，所以你可以让一个距离无限加 2 2 2 也就是在不改变奇偶性的前提下无限增大。这样我们跑最短路，对于每个点我们接纳第一个偶数最短路和奇数最短路，预处理任意两点这样的两个不同奇偶性的最短路径。询问的时候，看看与它奇偶性相同的最短路径长度是不是比它短即可。
f i = max 1 ≤ i ≤ k ( s r i − s l i − 1 + p i + max 1 < i f i ) f_i = \max_{1 \leq i \leq k} (s_{r_i} -s_{l_i-1} + p_i +\max_{1 <i} f_i) fi=1≤i≤kmax(sri−sli−1+pi+1<imaxfi)
外面的 max \max max 暴力一下，里面的 max \max max 维护一下前缀最大值。
这意味着一块地你开垦一次就可以了，那么 dp 也不知道哪些土地被开垦了。那么先随便限制一个东西大小，就按左端点从小到大排序，状态还是 f i f_i fi 是种的最靠右的土地为 i i i 的最大价值，那么枚举一下转移，也不知道转移哪个点是吧那就讨论一下，假设要转移到 f j f_j fj，也就不包含、部分包含、完全包含三个情况。因为你限制了左端点，所以你只要看看 j j j 与 l i l_i li 和 r i r_i ri 之间的关系，它可能转移到 j j j，也可能在 j < i j<i j<i 时转移到 i i i，所以用一棵区间加和区间取 min 值的线段树即可。考虑前缀和，区间 [ l , r ] [l,r] [l,r] 总数的奇偶性相当于问你 s l − 1 s_{l-1} sl−1 和 s r s_r sr 的奇偶性是否相同，那么可以在 l l l 和 r r r 之间连一条边，如果一个联通块中有一个点我们知道了，那么就全知道了。现在确定了 s u m 0 = 0 sum_0 = 0 sum0=0，那么我们求一个将全部点连起来最小生成树即可秒啊。
有带边权的树，有 k k k 条路径，告诉你它们的起点终点，求允许把一条边边权改为 0 0 0，最小化最长的路径的长度。
先二分，问题转换成了把一条边改成 0 0 0 的前提下能否所有路径的长 < m i d <mid <mid，然后你找出不合法的路径，用树上差分和求它们的交删掉边权最大的边再看看合不合法。
这个东西随便做吧，只不过方案数不好求，那么我们按每个人按能力排序，当你转移到不得不选队长时再选，这样不会算重了。
给你一棵大小为 n n n 的有根有点权树支持换根、修改点权、查询子树最小值。
与顺序无关，优先队列
从 DAG 上一个点出发的路径条数按照倒着的拓扑序进行 dp
求拓扑图上 S → T S \to T S→T 的必经边先求出 S S S 到每个点的路径条数 f f f 和每个点到 T T T 的路径条数 g g g。如果一条边 ( x , y ) (x,y) (x,y) 满足 f x × g y = f t f_x \times g_y = f_t fx×gy=ft 那么是必经。
秒啊跑一下 DAG 最短路，容易求可以在 S 1 → T 1 S_1 \to T_1 S1→T1 的最短路上的边和在 S 2 → T 2 S_2 \to T_2 S2→T2 最短路上的边，那么这些边的交集构成了最多两个拓扑图，求一下 DAG 最长路即可。
求有向图尽量长的简单路径，可以不是最长，保证存在哈密顿回路。
1 ≤ n ≤ 1 0 5 1 \leq n\leq 10^5 1≤n≤105。
写了 G 和 J 两道大水题，还把 M 丢给 ljh 大佬了，菜死了。
G Years下标较大的区间覆盖问题，对区间离散化在差分覆盖，并记录对应回去的编号
int n = read(); for (int i = 1; i <= n; i++) { a[i].l = read(), a[i].r = read(); a[i].r--; d[++cnt] = a[i].l, d[++cnt] = a[i].r+1; } sort(d + 1, d + cnt + 1); int num = 0; for (int i = 1; i <= cnt; i++) { if (d[i] == d[i - 1]) continue; mp[d[i]] = ++num, rev[num] = d[i]; } J Lonely Numbers给你 n n n 个数 1 ∼ n 1\sim n 1∼n，求有多少个数是孤独的。一个 a a a 是孤独的当且仅当不存在 b ∈ [ 1 , n ] b \in [1,n] b∈[1,n] 使得 gcd ( a , b ) , a gcd ( a , b ) , b gcd ( a , b ) \gcd(a, b), \frac{a}{\gcd(a, b)}, \frac{b}{\gcd(a, b)} gcd(a,b),gcd(a,b)a,gcd(a,b)b 能构成三角形。
假设 a < b a< b a<b
a ∣ b a|b\quad a∣b 三条边为 1 , a , b a 1,a,\frac{b}{a} 1,a,ab 易知 1 ≤ a 1 \leq a 1≤a
a = b a a = \frac{b}{a} a=ab 即 a 2 = b a^2=b a2=b 满足 1 + a > a 1 +a > a 1+a>a a ≠ b a a \not= \frac{b}{a} a=ab 显然 ∣ a − b a ∣ ≥ 1 |a - \frac{b}{a}| \ge 1 ∣a−ab∣≥1 不满足gcd ( a , b ) = 1 \gcd(a,b) = 1\quad gcd(a,b)=1三条边为 1 , a , b 1,a,b 1,a,b 而 a ≠ b a \not= b a=b 所以不可能构成三角形。
gcd ( a , b ) ≠ 1 \gcd(a,b) \not= 1 gcd(a,b)=1 且 a ∤ b a \not| b\quad a∣b 即为 a , b ∉ P a,b \notin \mathbb{P}\quad a,b∈/P 令 d = gcd ( a , b ) d=\gcd(a,b) d=gcd(a,b) 易知 a d < b d \frac{a}{d} <\frac{b}{d} da<db
d + b d − a d = d + b − a d ≥ 2 b − a > 0 d+\frac{b}{d}-\frac{a}{d}=d+\frac{b-a}{d} \ge2\sqrt{b-a}>0 d+db−da=d+db−a≥2b−a >0 b d + a d − d = a + b − d 2 d \frac{b}{d}+\frac{a}{d}-d=\frac{a+b-d^2}{d} db+da−d=da+b−d2 有 d ≤ a d\leq \sqrt{a} d≤a 所以 a + b − 2 × a d > 0 \frac{a+b-2 \times a}{d} > 0 da+b−2×a>0综上，答案为 f ( n ) − f ( ⌊ n ⌋ ) + 1 f(n) - f(\lfloor \sqrt{n} \rfloor )+1 f(n)−f(⌊n ⌋)+1。其中 f n f_{n} fn 为 [ 1 , n ] [1,n] [1,n] 内质数的个数。线性筛一下就可以 O ( 1 ) O(1) O(1) 回答询问了。
M Ancient LanguageCF510C Fox And Names 这个题和 M 差不多吧，就是拓扑排序一下子了，复杂度瓶颈在于输入，卡常差评。
给你一个括号组成的序列（不一定是合法的括号序列）。
你要任意交换 2 2 2 个位置，使得得到的序列有尽量多的循环移位，使得移位后序列是合法的括号序列。
我们先循环移位让它变成一个合法括号序列，因为两次循环移位可以通过一次循环移位搞定。还是老套路，建个折线图把左括号看成上升右括号看成下降。 如果我们交换了两个括号呢，假设它构成了一个低谷，那么交换了还不如不交换的，那么我们交换一定想让它多几个低谷。而一次交换要让一段的纵坐标向下平移一个单位，那么我们找到一个左括号一个右括号交换一下，使得中间出现的低谷尽可能多，也就是中间的 2 2 2 尽可能多。
这个性质神仙啊，你考虑在正确答案中某一位你寄存了，你啥时候让令一个人取走了，假设你在 t t t 的时间让它取走了，那么你之间还不如交替取，也就是你帮我我帮他去取，这样最多也在 t t t 取走，那就枚举从哪个地方开始就行了。
dp 乱入，因为序列的顺序是没关系的，所以排个序，搞个状态 f i , j f_{i,j} fi,j 表示前 i i i 个数和为 j j j 然后转移上 k k k 次，转移次数很少的话可以存有用状态。子段的话，直接暴力 dp 或求出所有的子段冲。
求字符串第 k k k 小字典序子序列优先队列乱入，虽然好多人写的 SAM。这个你就将一个个字符插进去，每次取出字典序最小的，加上在它后面的字符做 k k k 次就行。
求字符串第 k k k 小字典序的子串SAM 乱入，TJOI2015 弦论直接冲。
n ≤ 1000 n \leq 1000 n≤1000 拿出所有的子串排个序，二分一下答案用 dp check。设 f i , j f_{i,j} fi,j 表示前 i i i 个划分成了 j j j 段，然后接下来新划分的串要大于你的二分那个串。
区间 gcd 和线段树或 ST 表维护区间 gcd，每个点为右端点，二分向左找有多少段不同的 gcd，我们知道长 n n n 的序列最多有 log n \log n logn 个不同的 gcd，所以带两个 log \log log。
给定序列 a a a，每次操作 ( a i − 1 , a i , a i + 1 ) → ( a i − 1 + a i , − a i , a i + 1 + a i ) (a_{i-1},a_i,a_{i+1}) \to (a_{i-1}+a_i,-a_i,a_{i+1}+a_i) (ai−1,ai,ai+1)→(ai−1+ai,−ai,ai+1+ai)，求序列 a a a 能否到序列 b b b。
前缀和一下
x y z x + y -y z + y x x + y x + y + z x + y x x + y + z屑题。
