题解
倍增
题意
$n$ 个格子， $m$ 种走路方式，第 $i$ 个方式可以从 $l_i$ 走到 $r_i$ 花费代价 1。往左走不花代价。 $q$ 次询问，每次询问禁用一种方式，问 $s$ 到 $t$ 的最少花费（无解输出 -1)。
$n,m,q\leq2\times10^5$ 。
题解
每次只禁用一个的基本思想就是提前维护最优和次优。
倍增维护 $f_{i,j,0/1}$ …
Jayun 发布于 2023-11-10 17:53:11
00
贪心双指针
题意
在 $n$ 个数中选出最多对使得它们差的绝对值大于 $K$ 。
$n\leq10^6,K\leq10^9$ 。
题解
一个结论：升序下最后一定是砍两半。双指针贪心即可。
代码
const int N = 1e6 + 5;
inline ll Read() {
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && …
Jayun 发布于 2023-11-10 17:44:21
00
数学推导杂项
题意
给定 $f_i,p$ ，求 $x$ 使得
$$\left\{\begin{matrix}
x^i & \equiv & f_{a_i} \pmod{p}\\
& \vdots &
\end{matrix}\right.$$
其中 $a_i$ 是一个位置的排列。
$n\leq2\times10^5,x< p$ 。
题解
注意到解一定 …
Jayun 发布于 2023-11-10 17:38:15
00
折半搜索
题意
给定 $n$ 元高次方程
$$\sum_{i=1}^na_ix_i^{p_i}=0
$$
求整数解数。
$1\leq n\leq6,1\leq m\leq150$ 。
题解
一眼折半。用 pbds。
代码
要开 __int128，这里没开。
using namespace __gnu_pbds;
const int N = 10, M = 155;
inline ll Read() …
Jayun 发布于 2023-11-09 21:41:11
00
鸽笼原理组合意义双指针折半搜索二分答案
题意
给定 $n,p$ 和长度为 $n$ 的整数序列 $a$ ，你需要输出整数序列 $b$ 满足：
$b_i\in \{-1,0,1\}$ 且不全为 $0$ 。
$\sum a_ib_i\equiv 0\pmod p$
保证 $2^n\gt p$ 。
$1\leq p\lt 2^n, 1\leq n\leq 40,0\leq a_i\lt p$ 。
口胡
考虑转化一 …
Jayun 发布于 2023-11-09 21:36:57
00
整除分块树状数组
题意
给定整数 $n, m, V$ ，以及四个整数列 $a_i,b_i,A_i,B_i$ 。其中 $A_i,B_i$ 均为非降序列，且四个序列中除 $B_i$ 外元素的值均不超过 $V$ 。
对于所有 $q\in[1,m]$ ，你需要求出最小的 $k\leq n$ ，使得： $\sum_{i=1}^k\left\lceil\frac{b_i}{A_q}\right\rceil a …
Jayun 发布于 2023-11-09 20:59:18
00
树形动态规划（树形 DP）构造
题意
从前有棵树。找出 $K$ 个点 $A_1,A_2,\cdots,A_k$ ，使得 $\sum_{i=1}^{K-1}\mathrm{dis}(A_i,A_{i+1})$ 最小。
$1\leq k\le n,1\le x,y\le n,1\le z\le 10^5,n\le 3000$
口胡
两个结论：
$K$ 个点一定要缩在一起，即选出来的一定是恰好 $K$ 个点构成 …
Jayun 发布于 2023-11-09 14:57:27
00
轮廓线 DP计数
题意
一个 $n\times n$ 的方阵中，有些点可以放洒水器，有些点不能放。洒水器有两个种类：一个种类可以让它和它的左下角变成 $\texttt{C}$ ，一个种类可以让它和它的右上角变成 $\texttt{A}$ ，现在问放洒水器的方案数使得每个格子有且仅有一个字符。
$n\leq2000$ 。
题解
好题！
这个方阵一定会被一条轮廓线分成两部分，那么 DP 维护这个轮廓线方案数。 …
Jayun 发布于 2023-11-08 18:53:52
00
Manacher
题意
定义一种操作，以最后一位为中心将字符串 $s$ 的前 $|s|-1$ 位回文。
现在给定一个字符串 $s$ ，问有多少种长度的初始字符串 $t$ ，使得 $s$ 是 $t$ 翻转若干次后的前缀。
$|s|\leq10^6$ 。
题解
由于本题一定是奇长度的回文串，所以不用在字符串中加入特殊字符。
然后跑 Manacher，如果 $R_i$ 的范围大过 $|s|$ …
Jayun 发布于 2023-11-08 16:54:52
00
扩展 KMP（Z 函数）
题目大意
在一个圆环上从两个位置出发转圈圈，经过的位置随机变换，求环的最大长度。
正文
假设我们以及知道了环的最大长度 $l$ 。由于这是一个环，所以 $A$ 串的部分一和 $B$ 串的部分二、 $A$ 串的部分二和 $B$ 串的部分一必定相同：
一个串的第一部分在另一个串里找相同的第二部分的这个过程，就可以用扩展 KMP 实现。也就是两次扩展 KMP 的得到 $A$ 对于 …
Jayun 发布于 2023-11-08 16:45:44
00