Solutions
Sqrt-DecompositionBinary Indexed Tree (BIT)
题意
给定整数 $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
Dynamic Programming on Trees (Tree DP)Constructive Algorithm
题意
从前有棵树。找出 $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
Contour Line DPCount
题意
一个 $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
Z Algorithm
题目大意
在一个圆环上从两个位置出发转圈圈，经过的位置随机变换，求环的最大长度。
正文
假设我们以及知道了环的最大长度 $l$ 。由于这是一个环，所以 $A$ 串的部分一和 $B$ 串的部分二、 $A$ 串的部分二和 $B$ 串的部分一必定相同：
一个串的第一部分在另一个串里找相同的第二部分的这个过程，就可以用扩展 KMP 实现。也就是两次扩展 KMP 的得到 $A$ 对于 …
Jayun 发布于 2023-11-08 16:45:44
00
Two PointerSimple Segment Tree
题意
有 $n$ 个区间，选 $m$ 个，使得最大区间长度减去最小区间长度最小。
$n\leq5\times 10^5,m\leq2\times10^5$ 。
题解
按区间长度排序，然后双指针扫区间，右指针扫当前选的大区间，左指针扫小区间。对于当前已选数量，用线段树维护。
代码
const int N = 5e5 + 3;
inline ll Read() {
ll x = 0, f …
Jayun 发布于 2023-11-08 07:35:38
00
Suffix Automaton (SAM)Depth First Search (DFS)Breadth First Search (BFS)
题意
给定一个长为 $n$ 的字符串 $s$ ，随后有 $q$ 次询问，询问对于每次输入的字符串 $t$ ，其在 $s$ 中出现的次数。
$n,\sum|t_i|,q\leq10^5$
题解
SAM 板题，把失配树子树大小跑出来直接做。
代码
const int N = 2e5 + 5;
inline ll Read() {
ll x = 0, f = 1;
char c …
Jayun 发布于 2023-11-07 21:52:06
00
Linear Dynamic Programming (Linear DP)Enumeration
题
小L养了很多马，朋友说在景区收费骑马可以赚很多钱，于是小L想试一试。小L在某4A景区内，收费骑马，有三个项目，骑大圈，骑小圈，过河。小L在正式开业前，有一天试营业，他提前在网上约了朋友，朋友们已经告诉小L他们想要体验的项目。小L想尽可能多地满足朋友们的需求，但他也不希望有马太过劳累而导致生病。小L定义疲劳值，当一匹马的疲劳值大于 100 时（初始时疲劳值为 1），马会累倒，小L会生气。
小L拜 …
Jayun 发布于 2023-11-07 19:49:27
00
TriePrime FactorizationEnumeration
[AGC003D] Anticube
题面
给定 $n$ 个数 $s_i$ ，要求从中选出最多的数，满足任意两个数之积都不是完全立方数。 $n\le 10^5$ ， $s_i\le 10^{10}$ 。
题解
爆草评测机做法。对于每个数，把指数化简，模三等于 1 或 2 才是有价值的，就是一个至多长 15 的链（16 个质数乘在一起一定大过 $10^{10}$ ）。把这些链放在 Trie …
Jayun 发布于 2023-11-07 19:09:30
00
GreedyLinear Dynamic Programming (Linear DP)
题意
有 500,100,50,10,5,1 这些面额的纸币，有 $X$ 块钱，使用最少的纸币数表示的。
然后有一些物品，每种只有一个，有费用。每次你可以选择一些没买过的买，付一定的钱，用最小的纸币数会找你钱。
要求最大化最后 1 元纸币的数量。
$n\leq10^5,X\leq10^{14}$ 。
口胡
有性质是一次只会买一个。
然后有 $\mathcal{O}(n^2)$ 的背包做法 …
Jayun 发布于 2023-11-07 07:30:52
00