题解
基础线段树贪心二叉堆链表
题意
给定长 $n$ 的序列 $h_i$ ，每次操作可以使 $h_i\leftarrow h_i-1$ ， $q$ 次询问， 每次给出一个 $X$ , 求使用不超过 $X$ 次操作后 $\sum_{i=1}^{n-1}|h_i-h_{i+1}|+h_1+h_n$ 的最小值。
$n,q\leq5\times10^5,h_i\leq10^{12},X\leq10^{18}$ 。
…
Jayun 发布于 2023-11-11 15:17:49
00
区间动态规划（区间 DP）线性动态规划（线性 DP）
题意
给定一个长 $n$ 的序列 $a_i$ ，可以进行操作，每次操作选区间 $[l,r]$ ，条件是 $\wedge_{i=l}^{r}~a_i=0$ ，操作完会删除 $[l,r]$ 。问最多操作次数。
$n,a_i\lt64$ 。
题解
区间 DP。设 $f_{l,r}$ 表示若区间 $[l,r]$ 可以合法，它的最大值，考虑 $l<k_1\leq k_2< …
Jayun 发布于 2023-11-11 15:01:40
00
CDQ 分治树状数组
题意
有 $n$ 个元素，第 $i$ 个元素有 $a_i,b_i,c_i$ 三个属性，设 $f(i)$ 表示满足 $a_j \leq a_i$ 且 $b_j \leq b_i$ 且 $c_j \leq c_i$ 且 $j \ne i$ 的 $j$ 的数量。 对于 $d \in [0, n)$ ，求 $f(i) = d$ 的数量。
$1 \leq n \l …
Jayun 发布于 2023-11-11 07:25:02
00
拉格朗日插值法
题意
给定 $n,k$ ，求
$$\sum_{i=1}^ni^k
$$
对 $10^9+7$ 取模的值。
$n\leq10^{18},k\leq5\times10^4$ 。
口胡
多项式做少了就想不到多项式。
首先令 $F(x)=\sum_{i=1}^xi^k$ ，然后它是 $k+1$ 次的多项式。那么可以先求出前 $k+2$ 项，然后拉插求出 $F(n)$ 。
题解
MD 原 …
Jayun 发布于 2023-11-10 21:43:48
00
Hash容斥原理
题意
给定 $n$ 个元素，每个元素是一个六元组，求有多少对元素满足相同位恰好有 $k$ 个。
$n\leq10^5$ 。
题解
高情商：在这道题上学了点东西。
低情商：md这么简单的题都不会，我到底是什么玩意。（簡単なことも解らないわ あたしって何だっけ）
这道题的状态有点巧妙，有点 tip。知道直接求恰好的很难，那就设个至少的：设 $f_i$ 表示至少 $i$ 位相同的对数。 …
Jayun 发布于 2023-11-10 21:34:49
00
倍增
题意
$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