题解
基础栈线性动态规划（线性 DP）
[CSP-S 2023] 消消乐
题目
有一个长度为 $n$ 且仅由小写字母构成的字符串。我们称一个字符串是可消除的，当且仅当可以对这个字符串进行若干次操作，使之成为一个空字符串。
其中每次操作可以从字符串中删除两个相邻的相同字符，操作后剩余字符串会拼接在一起。
求这个字符串的所有非空连续子串中，有多少个是可消除的。
$1 \le n \le 2 \times 10^6$ ，且询问的字符串仅 …
Jayun 发布于 2023-10-23 07:28:26
00
决策单调性优化动态规划（决策单调性优化 DP）
题意
给定一个长度为 $n$ 的非负整数序列 $[a_1,…,a_n]$ ，求它的一个子序列 $[{a_i}_1,{a_i}_2,…,{a_i}_k]$ $(1≤i_1<i_2<⋯<i_k≤n)$ ，使得 $\sum^{k−1}_{j=1}({a_i}_j\text{and} {a_i}_{j+1})$ 最大。你只需要输出这个最大值即可。
$n\leq2\tim …
Jayun 发布于 2023-10-20 15:35:28
00
费用流
口胡
这个网格图求最小割即求对偶图上最短路。对于任意两个附加点之间的空间都是一个点（同色边权为 0），然后两两配对，如果存在路径有交集的，一定不是最优的（这里在思考时花的时间多，我也不知道为啥……），那么 $\mathcal{O}\left(\left(\sum k\right)nm\log nm\right)$ 建二分图，其中对数是跑最短路的时间。对这个二分图跑最优匹配即可。
Jayun 发布于 2023-10-19 19:39:31
00
稀疏表（ST表）树状数组
题面
给出一个长度为 $n$ 的序列 $s$ ， $q$ 组询问。
每次给定区间 $[l,r]$ 。
如果 $i,j \in [l,r]$ ， $s_i|s_j$ 则 $i$ 得一分。
问有多少个没有得到满分，即 $r-l$ 。
题解
考虑能整除区间内所有数的数的个数。可简单证明即为求区间内区间最大公因数的个数。
代码
const int N = 1e5 + 5;
inli …
Jayun 发布于 2023-10-18 19:49:46
00
矩阵快速幂
Mushroom Gnomes
题面
很久以前，在蘑菇森林的灌木丛中生活着蘑菇地精。它们以神奇的蘑菇而在邻居中闻名。它们的神奇特性使得它们每分钟可以在相邻的两个蘑菇之间长出另一个蘑菇，而该蘑菇的重量等于两个相邻蘑菇的重量之和。
蘑菇地精喜欢一切都井井有条的，这就是为什么它们总是按照重量递增的顺序将蘑菇种成一行。
地精们种下蘑菇后就去吃饭了。 $x$ 分钟后，他们返回，发现新的蘑菇长大了，因此打 …
Jayun 发布于 2023-10-18 17:06:14
00
线性动态规划（线性 DP）
题面
现在有两台机器 $A$ 和 $B$ 。有 $n$ 个任务，编号 $1,2,\cdots,n$ 。你必须把每个任务安排到一台机器上处理，同时需要满足以下一些条件。
你必须把每个任务安排到任意一台机器上处理。
在任何时刻，一台机器只能最多处理一个任务。
任务 $i(0< i\leq n)$ 可以被处理当且仅当每个任务 $j(j<i)$ 已经被完成或者正在进行。
…
Jayun 发布于 2023-10-18 16:28:41
00
斜率优化动态规划（斜率优化 DP）
简单斜率优化，这里保存代码。
const int N = 1e5 + 10, M = 1e4 + 5;
inline ll Read() {
ll x = 0, f = 1;
char c = getchar();
while (c != '-' && (c < '0' || c > '9')) c = getchar();
if (c == '-') f = …
Jayun 发布于 2023-10-18 09:46:30
00
并查集
奇偶树
题面
有一棵 $n$ 个节点的树，节点编号为 $1\sim n$ 。树的边权的取值只有 $0$ 和 $1$ ，且应当满足 $Q$ 个条件。每个条件形如 $(u,v,x)$ ，其中 $u$ 和 $v$ 是树中节点的编号， $x$ 是 $0$ 或 $1$ 。
条件的含义为树上从 $u$ 到 $v$ 的路径上的边权和在模 $2$ 意义下应与 $x$ …
Jayun 发布于 2023-10-18 09:25:56
00
Hash概率
Osmosmjerka
题目描述
给定一个 $M \times N$ 的字母矩阵，以下面的为例：
honi
hsin
接着我们将其进行无限延伸，得到：
...honihonihonihoni...
...hsinhsinhsinhsin...
...honihonihonihoni...
...hsinhsinhsinhsin...
在无限延伸后得到的新矩阵后，我们随机选取其中一个区域的字 …
Jayun 发布于 2023-10-17 16:07:44
00