KSCD_ 的博客

博客

标签

暂无

【学习记录】24.02.17 树上问题 + 数据结构

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-17 09:38:07

树上问题/数据结构

树链剖分/树上差分

CF383C Propagating tree

分成深度为奇数和偶数两种点，对每一种点开线段树维护。

题解看到的更优做法：用一个树状数组维护，对于深度为奇数和偶数分别加减，最后输出时也分别改为正负。

BZOJ3306 树

没听。

P3128 [USACO15DEC] Max Flow P

树上差分，树上路径加 $1$ 转化为两端点各加 $1$，LCA和LCA的父亲减 $1$ 即可。

P2680 [NOIP2015 提高组] 运输计划

最大值最小，采用二分，把最优性问题转化为可行性问题。

P4216 [SCOI2015] 情报传递

先将在 $i$ 时刻大于 $c$ 转化为在 $i-c$ 时刻大于 $0$ ，考虑离线做法。

先读入所有询问，均转化为某时刻大于 $0$ 的点数，转化为单点修改+路径和，由于路径和可以用点到根的路径和计算，通过dfs序可转化为单点修改+前缀和，树状数组维护即可。

若强制在线，需要可持久化数据结构，~~不管了~~。

P5838 [USACO19DEC] Milk Visits G

转化为求路径上有多少等于 $C$ 的点，则只需要求点到根路径上有多少等于 $C$ 的点。

考虑离线做法，把询问按 $C$ 排序，每次将 $T_i=C$ 的点先变为 $1$，用dfs序和树状数组维护 $dis$ 数组，用树上差分求解，最后再把这些点变回 $0$，复杂度均摊可过。

以上两道题都用到了子树的dfs序连续，可以用树状数组维护。~~感谢学长~~

HDU5692 shacks

没听。

P4211 [LNOI2014] LCA

先考虑到差分的优化，转化为 $1$ 到两点的前缀和之差。

后边没听（~~其实是听到一半跟不上了~~）。

CF696E ...Wait for it...

紫题放弃了。

P4219 [BJOI2014] 大融合

离线，先建出完整的树，给每条边一个标记，表示这条边是否存在，则原加边操作变为把一条边的 $0$ 变为 $1$，修改后要修改这条边到最远的连通祖先所有点的子树大小，此处用并查集维护最远祖先，后边好像还需要用到上边的dfs序，但我听不懂了。

CF536E Tavas on the Path

离线操作，将询问按 $l$ 排序，每次把应为 $1$ 的点修改好后求这段路径的解。

可以树剖做，转化成区间查询，因此需要单点修改，用线段树维护答案。

可持久化数据结构

部分可持久化：可查询不可修改。
完全可持久化：可修改历史版本。

P3919 【模板】可持久化线段树 1（可持久化数组）

板子题，用路径复制思想，每次只把修改的版本建新节点，其他的连向上一个版本即可。

若线段树中有标记下放时，必须要重建后再下放。

P3834 【模板】可持久化线段树 2

维护序列每个前缀对所有数值的桶数组，每个前缀对应一个线段树，则第 $i$ 个线段树为第 $(i-1)$ 个线段树单点修改得到，用可持久化线段树维护，二分求解，也可以线段树二分，每次在两个线段树上同时向下跳，最后查找到叶节点。

P4592 [TJOI2018] 异或

可持久化01Trie树，放弃了，题解里说P4734、P2633是前置知识~~紫题太难了~~。

P3567 [POI2014] KUR-Couriers

如P3834一样建树，进行线段树二分，向下查找即可。

P2839 [国家集训队] middle

二分求解，放弃没听。

CF464E The Classic Problem

可持久化线段树和最短路结合的黑题？放弃放弃。

P3402 可持久化并查集

要完全可持久化，需要用复杂度均摊的按秩合并来做。

P3302 [SDOI2013] 森林

前置的可持久化并查集还没整明白，不听了。

LOJ6144 [2017 山东三轮集训 Day6] C

没听。

阅读全文

ABC341E 题解

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-17 22:41:06

题意

给出一个只包含 $0$ 和 $1$ 的字符串，要实现区间取反和检查区间内是否有相邻的相同字符两个操作。

思路

若暴力修改、暴力判断，时间复杂度太大，无法通过本题。

考虑优化，发现题目为区间修改和区间查询，自然想到用线段树来做。

首先考虑区间合并，发现当且仅当左右两区间本身合法，且两区间相邻处不同时，合并后的区间合法。因此线段树要维护区间是否合法和区间左右两端的值。

接着是区间取反，与线段树模板区别不大，只是修改时只需把区间左右两端的值取反，区间的合法性并不改变，最后打上标记即可。

然后是标记的维护与下放。标记也用取反来维护，因为取反偶数次相当于没操作。下放标记时也像修改一样，把两个儿子的左右两端都取反即可。

最后是区间查询，这里需要把左右两部分区间都查询出来再合并，才能得到最终结果。

具体请看代码实现。

代码

其实是比较裸的线段树题，这里用了异或 $1$ 来取反。

#include<iostream>
using namespace std;
const int N=5e5+10;
int read()
{
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){ if(ch=='-') w=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar();}
    return s*w;
}
int n,Q,t=1,aa[N]; 
char c[N];
struct nod
{
	int l,r;\/\/左儿子编号，右儿子编号 
	bool lf,rf,f,tag;\/\/左右端点的值，区间是否合法，懒惰标记 
}a[N*2];\/\/线段树记得开两倍空间
void pushup(nod &u,nod lc,nod rc)
{
	if(lc.rf!=rc.lf&&lc.f&&rc.f)
		u.f=true;
	else
		u.f=false; 
	u.lf=lc.lf,u.rf=rc.rf;
} \/\/合并操作 
void pushdown(int u)
{
	if(a[u].tag==0)
		return;
	int lc=a[u].l,rc=a[u].r;
	a[lc].lf^=1,a[rc].lf^=1,a[lc].rf^=1,a[rc].rf^=1;
	a[lc].tag^=1,a[rc].tag^=1,a[u].tag=0;
} \/\/标记下放 
void build(int u,int l,int r)
{
	if(l==r)
	{
		a[u].lf=a[u].rf=aa[l],a[u].f=true;
		return;
	}
	int mid=(l+r)\/2;
	a[u].l=++t;
	build(t,l,mid);
	a[u].r=++t;
	build(t,mid+1,r);
	pushup(a[u],a[a[u].l],a[a[u].r]);
} \/\/建树 
void change(int u,int l,int r,int ll,int rr)
{
	if(l>=ll&&r<=rr)
	{
		a[u].lf^=1,a[u].rf^=1,a[u].tag^=1;
		return;
	}
	int mid=(l+r)\/2;
	pushdown(u);
	if(ll<=mid)
		change(a[u].l,l,mid,ll,rr);
	if(rr>mid)
		change(a[u].r,mid+1,r,ll,rr);
	pushup(a[u],a[a[u].l],a[a[u].r]);
} \/\/区间取反 
nod check(int u,int l,int r,int ll,int rr)
{
	if(l>=ll&&r<=rr)
		return a[u];
	int mid=(l+r)\/2;
	pushdown(u);
	if(rr<=mid)
		return check(a[u].l,l,mid,ll,rr);
	if(ll>mid)
		return check(a[u].r,mid+1,r,ll,rr);
	nod ta=check(a[u].l,l,mid,ll,rr),tb=check(a[u].r,mid+1,r,ll,rr),res;
	pushup(res,ta,tb);
	return res;
} \/\/区间判断 
signed main()
{
	n=read(),Q=read();
	cin>>c;
	for(int i=1;i<=n;i++)
		aa[i]=c[i-1]-'0';
	build(1,1,n);
	while(Q--)
	{
		int opt=read(),l=read(),r=read();
		if(opt==1)
			change(1,1,n,l,r);
		else
		{
			nod ans=check(1,1,n,l,r);
			if(ans.f)
				cout<<"Yes"<<"\n";
			else
				cout<<"No"<<"\n";
		}
	}
	return 0;
}

阅读全文

【学习记录】24.02.19 DP 及其优化

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-19 08:28:37

DP及其优化

（DP明显都听不太懂qwq）

背包问题

01背包（逆序）、完全背包（正序）

略。

多重背包

二进制分组，可单调队列优化（~~没听见~~）。

P4141 消失之物

退背包。

扩展求最优解

分治背包

P2371 [国家集训队] 墨墨的等式

同余~~最短路~~背包，状态优化。

P8392 [BalticOI 2022 Day1] Uplifting Excursion

没听见，放弃了。

P4322 [JSOI2016] 最佳团体

01分数规划、二分、树上背包。没听懂

区间DP

石子合并

断环为链。

BZOJ4380

没听。

[AGC026D] Histogram Coloring

前半部分没听见，讨论的是 $h_i$ 相等的特殊情况。

设 $dp_{l,r,k,0/1}$ 表示某区间高为 $k$，是否是 $0$ 和 $1$ 交替的方案数，按高度枚举求解。

笛卡尔树处理全局最小值，断开区间。

CF1372E Omkar and Last Floor

显然让 $1$ 在列里更集中更优，即令 $q_i$ 尽可能大。

设 $f_{l,r}$ 表示区间最优且只考虑包含该区间的行时的答案，没怎么听懂。

P6563 [SBCOI2020] 一直在你身旁

设 $f_{l,r}$ 表示该区间还需要多少代价。

则有$f_{l,r}=\min_{k=l}^{r-1}{\max{f_{l,k},f_{k+1,r}}+a_k}$

用单调队列优化，听不懂啊。好像还要线段树和二分。

四边形不等式

区间包含单调性，交叉优于包含。

P1912 [NOI2009] 诗人小G

放弃。

决策单调性

好了没了，下午全都放弃了（悲）

阅读全文

【学习记录】24.02.20 字符串

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-20 11:16:19

字符串算法

（感谢学长qwq）

Manacher

维护一个区间 $[l,r]$，表示 $r$ 最大的中心在 $i$ 之前的回文串，更新时：

若 $i>r$，暴力求解；
否则考虑 $d_{l+r-i}$，即回文串 $[l,r]$ 中与 $i$ 对应的那一位，令 $z_i=\min(r-i+1,d_{l+r-i})$。若用了 $r-i+1 $，则继续向后暴力扩展；
最后必须用 $i+z_i$ 尝试更新 $r$。

求长度为偶数的回文串可以用一个技巧，在两个字符之间均插入一个特殊字符，这样所有的回文串长度均为奇数。

P5446 [THUPC2018] 绿绿和串串

在速通，没听。

exKMP

维护一个区间 $[l,r]$，表示 $r$ 最大的已匹配的区间，更新时：

若 $i>r$，暴力求解；
否则考虑 $z_{i-l}$，即 $i$ 在 $[l,r]$中与 $S$ 的前缀对应的那一位，令 $z_i=\min(r-i+1,z_{i-l})$。若用了 $r-i+1 $，则继续向后暴力扩展；
最后必须用 $i+z_i$ 尝试更新 $r$。

P7114 [NOIP2020] 字符串匹配

在自己理解，没听。

学长讲了个性质，对于字符串来说，后缀border以外的部分为该字符串最小周期。

做完以后发现一个性质，字符串非空的最小匹配前缀之外的部分为该字符串最大周期。

KMP

在求 $s_i$ 时，尝试从 $j=s_{i-1}$ 向后加一位，若不相等，则跳到 $j=s_j$ 继续尝试，直到匹配到 $S_j=S_i$，记录 $s_i=s_j+1$。

P3435 [POI2006] OKR-Periods of Words

在听学长讲AC自动机，没听。

P2375 [NOI2014] 动物园

做过，在自己写笔记，没听。

P5829 【模板】失配树

出去了没听，但板子还是课后学一学吧。

对于KMP的 $nxt$ 数组，建出一棵树，由 $i$ 向 $nxt_i$ 连边，这样的失配树与AC自动机中的 $fail$ 树类似，是只有一个字符串的特殊情况。

HDU7138 String

还是没听。

KMP自动机

没听懂，后边再看Oiwiki吧。

P3193 [HNOI2008] GT考试

吃饭了不听了。

字典树

P2922 [USACO08DEC] Secret Message G

字典树维护，我以前写过，我写的方法是维护经过某节点的字符串数量和终止于某节点的字符串数量，简单容斥求解。

AC自动机

对于多个字符串，建出Trie后在Trie上求 $fail$ 数组，表示这个点表示的字符串的最长后缀对应的节点。

若$trie_{p,c}=u$，则转移为：

若 $trie_{fail_p,c}$ 存在，则 $fail_u=trie_{fail_p,c}$
否则不断令 $p=fail_p$，直到存在 $trie_{fail_p,c}$

这样维护出的 $fail$ 数组是一棵树，后边还没深入。

P5357 【模板】AC 自动机

板子题。

P2414 [NOI2011] 阿狸的打字机

板子不会就放弃。

P3041 [USACO12JAN] Video Game G

板子不会就放弃。

P2444 [POI2000] 病毒

板子不会就放弃。

题目选讲

P5329 [SNOI2019] 字符串

要在 $O(1)$ 的时间复杂度内比较，把整个字符串的比较转化为比较两字符串的不同部分。

真正~~看题解~~要做的时候发现，只要找到相邻两个字符的大小关系，就可以确定它们之前的大小关系，总复杂度为 $O(n)$。

P3426 [POI2005] SZA-Template

没咋认真听，但~~题解说~~应该是用KMP求出 $nxt$ 数组，然后利用性质和dp求解。

P6216 回文匹配

KMP+Manacher+前缀和，不详细说了~~可以看题解~~。

CF1654F Minimal String Xoration

放弃了。

阅读全文

【学习记录】组合数学

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-22 14:56:11

组合数学

放球问题

规定 $n\geq m$

$1$. $n$ 球 $m$ 盒均有区别，允许空盒

方案数 $m^n$

$2$. $n$ 球有区别，$m$ 盒无区别，无空盒

设 $S_{n,m}$ 为答案，则 $S_{n,m}=S_{n-1,m-1}+m\times S_{n-1,m}$，$S_{n,m}=0(n<m),S_{1,1}=1$

$S$ 即为第二类斯特林数。

$3$. $n$ 球有区别，$m$ 盒有区别，无空盒

把盒子排列，答案为 $S_{n,m}\times m!$

为第二类斯特林数的扩展。

$4$. $n$ 球有区别，$m$ 盒无区别，允许空盒

答案为 $\sum_{i=1}^{m} S_{n,i}$，即为贝尔数。

$5$. $n$ 球无区别，$m$ 盒有区别，插板法

$1$. 无空盒方案数 $C_{n-1}^{m-1}$，

$2$. 允许空盒方案数 $C_{n+m-1}^{m-1}$

$6$. $n$ 球 $m$ 盒均无区别，推式子（DP）

设 $f_{n,m}$ 为无空盒，$g_{n,m}$ 为允许空盒。

则有 $f_{n,m}=g_{n-m,m}=\sum_{i=1}^mf_{n-m,i}=g_{n-m,m-1}+f_{n-m,m}$，

即 $f_{n,m}=f_{n-1,m-1}+f_{n-m,m}$（DP式子）

P5824 十二重计数法

$I$ 对应 $1$，$m^n$
$II$ $C_m^n\times n!(n\leq m)$；$0(n>m)$
$III$ 对应 $3$，$S_{n,m}\times m!$
$IV$ 对应 $4$，$\sum_{i=1}^{m} S_{n,i}$
$V$ $1(n\leq m)$；$0(n>m)$
$VI$ 对应 $2$，$S_{n,m}$
$VII$ 对应 $5.2$，$C_{n+m-1}^{m-1}$
$VIII$ $C_{m}^n$
$IX$ 对应 $5.1$，$C_{n-1}^{m-1}$
$X$ 对应 $6.g$，为 $g_{n,m}$
$XI$ $1(n\leq m)$；$0(n>m)$
$XII$ 对应 $6.f$，为 $f_{n,m}$

阅读全文

ABC338D 题解

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-29 07:15:30

题意

$n$ 个点顺序连接的环，边长为 $1$，去掉其中一条边，使顺序访问 $m$ 个点的路程最短，求最短路程。

思路

暴力求解复杂度必炸，考虑优化。

显然可以把计算每条路径转化成记录每条路径的贡献。

1.路径计算

若求两点 $l,r$ 间距离，可以先令 $r \gt l$，方便处理。

我们发现在环上从 $r$ 走到 $l$ 只有两种路径，

且断掉一条边以后为一条链，即只有唯一的路径，

那么我们就可以先求出两种路径分别的长度：

其中直接从 $1$ - $n$ 内部走（即 $l,l+1 \cdots r-1,r$）的路程即 $(r-l)$
而另一种为经过 $n$ 和 $1$ 连接的这条边（即 $r,r+1 \cdots 1,2 \cdots l-1,l$）

通过分析可知两种的路径长度和为环的总长度 $n$

则第二种的路径长为 $(n-(r-l))$

2.记录求解

因为最终要求的是 $(m-1)$ 段路程的和最小，

考虑把每一段路程分别计算，最后再一起求和。

设 $a_i$ 表示断掉连接 $i$ 和 $i+1$ 之间这条边后的总路程，

$a_n$ 即为断开 $n$ 和 $n-1$ 之间边时的总路程，

注意到 $l$ 和 $r$ 将 $a$ 数组分成三部分，

第一部分是 $1$ 至 $l-1$ ，贡献为第一种；

第二部分是 $l$ 至 $r-1$ ，贡献为第二种；

第三部分是 $r$ 至 $n$ ，贡献仍为第一种。

特别地，当 $l=1$ 时，第一部分不存在，需要特殊处理。

因此这三部分的区间加操作可以使用差分数组 $s$ 记录。

最后用前缀和恢复 $a$ 数组，输出最小值即可。

具体看代码实现吧。

代码

我的赛时代码~~（写得有点啰嗦）~~

以下是我重写的~~对新手友好的~~代码。

#include<iostream>
using namespace std;
const int N=2e5+10;
int n,m,x[N];
long long ans=1e18,s[N];\/\/初始化，记得开longlong 
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
		cin>>x[i];
	for(int i=1;i<m;i++)\/\/处理(m-1)段距离的贡献
	{
		int l=x[i];
		int r=x[i+1];
		if(l>r) 
			swap(l,r);\/\/使r>l 
		int sn=r-l;\/\/第一种的距离
		int sw=n-sn;\/\/第二种的距离
		if(l==1)
			s[l]+=sw;\/\/s[l]即s[1]，断掉1和2之间的边时只能先到n，即第二种
		else
		{
			s[1]+=sn;
			s[l]+=(sw-sn);
		}
		s[r]+=(sn-sw);
	}
	for(int i=1;i<=n;i++)
	{
		s[i]+=s[i-1];
		ans=min(ans,s[i]);
	}\/\/求前缀和及最小值答案 
	cout<<ans;
	return 0;
}

阅读全文

ABC339E 题解

本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-03 23:14:39

题意

给定一个序列 $A$ ，求相邻两项绝对差不大于 $D$ 的最长子序列长度。

分析

子序列问题很容易想到动态规划。

设 $f_i$ 为以 $A_i$ 为结尾的合法子序列长度最大值。

易得 $f_i=max(f_j)+1 $ ,其中 $j<i$ 且 $\left|A_i-A_j\right|\le D$。

暴力枚举时间复杂度为 $O(n^2)$，必炸。

考虑优化到 $O(n\log n)$ 以通过本题。

我们发现对于一个 $A_i$，可以取到的 $A_j$ 范围为 $A_i-D \le A_j \le A_i+D$。

现在要求在 $O(\log n)$ 的时间复杂度下查找到这个区间内 $f_j$ 的最大值。

由于 $A_i$ 域值为 $5\times10^5$，可以使用线段树优化。

设 $s_i$ 为目前以 $i$ 为结尾的合法子序列长度最大值。

初始 $s$ 数组均为 $0$，建出线段树。

枚举到每个 $A_i$ 时，所有符合 $j<i$ 的 $A_j$ 已经全部更新完。

因此查找该区间最大值并加一，以此来更新答案和 $A_i$ 对应 $s$ 的值。

此时若更新了 $s$ 的值，就同时在线段树内维护。

最后输出答案即可。

代码

#include<iostream>
#include<cmath>
using namespace std;
const int N=5e5+10;
const int M=5e5;\/\/N为开数组用的范围，M为实际范围 
int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){ if(ch=='-') w=-1;  ch=getchar();}
	while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar();}
	return s*w;
}
int n,d,ans=0,t=1;
int s[N],A[N];\/\/A为原数组，s为目前线段树中存储的最大值 
struct nod
{
	int u,l,r,s;
}a[N*2];\/\/线段树记得开两倍范围
void pushup(int u)
{
	a[u].s=max(a[a[u].l].s,a[a[u].r].s);
}\/\/传递孩子的最大值给父亲 
void build(int u,int l,int r)
{
	if(l==r)
	{
		a[u].s=s[l];
		return;
	} 
	int mid=(l+r)\/2;
	a[u].l=++t;
	build(t,l,mid);
	a[u].r=++t;
	build(t,mid+1,r);
	pushup(u);
}\/\/建树
void change(int u,int l,int r,int ll,int k)
{
	if(l==r&&l==ll)
	{
		a[u].s=k;
		return;
	}
	int mid=(l+r)\/2;
	if(ll<=mid)
		change(a[u].l,l,mid,ll,k);
	else
		change(a[u].r,mid+1,r,ll,k);
	pushup(u);
}\/\/更改元素并维护最大值 
int check(int u,int l,int r,int ll,int rr)
{
	if(l>=ll&&r<=rr)
		return a[u].s;
	int mid=(l+r)\/2,ans=0;
	if(ll<=mid)
		ans=max(ans,check(a[u].l,l,mid,ll,rr));
	if(rr>mid)
		ans=max(ans,check(a[u].r,mid+1,r,ll,rr));
	return ans;
}\/\/查询区间最大值
int main()
{
	n=read(),d=read();
	for(int i=1;i<=n;i++)
		A[i]=read();
	build(1,1,M);\/\/建树
	for(int i=1;i<=n;i++)
	{
		int l=max(1,A[i]-d);
		int r=min(M,A[i]+d);\/\/注意范围要在1-5e5之间，避免越界 
		int maxx=check(1,1,M,l,r);\/\/查询最大值 
		if(ans<maxx+1)
			ans=maxx+1;\/\/更新答案 
		if(s[A[i]]<maxx+1)
		{
			s[A[i]]=maxx+1;
			change(1,1,M,A[i],maxx+1);
		}\/\/更新以Ai为结尾的最大长度并维护线段树
	}
	cout<<ans;
	return 0;
}

阅读全文

共 137 篇博客

KSCD_ 的博客

博客

【学习记录】24.02.17 树上问题 + 数据结构

树上问题/数据结构

树链剖分/树上差分

CF383C Propagating tree

BZOJ3306 树

P3128 [USACO15DEC] Max Flow P

P2680 [NOIP2015 提高组] 运输计划

P4216 [SCOI2015] 情报传递

P5838 [USACO19DEC] Milk Visits G

HDU5692 shacks

P4211 [LNOI2014] LCA

CF696E ...Wait for it...

P4219 [BJOI2014] 大融合

CF536E Tavas on the Path

可持久化数据结构

P3919 【模板】可持久化线段树 1（可持久化数组）

P3834 【模板】可持久化线段树 2

P4592 [TJOI2018] 异或

P3567 [POI2014] KUR-Couriers

P2839 [国家集训队] middle

CF464E The Classic Problem

P3402 可持久化并查集

P3302 [SDOI2013] 森林

LOJ6144 [2017 山东三轮集训 Day6] C

ABC341E 题解

题意

思路

代码

【学习记录】24.02.19 DP 及其优化

DP及其优化

背包问题

01背包（逆序）、完全背包（正序）

多重背包

P4141 消失之物

扩展 求最优解

P2371 [国家集训队] 墨墨的等式

P8392 [BalticOI 2022 Day1] Uplifting Excursion

P4322 [JSOI2016] 最佳团体

区间DP

石子合并

BZOJ4380

[AGC026D] Histogram Coloring

CF1372E Omkar and Last Floor

P6563 [SBCOI2020] 一直在你身旁

四边形不等式

P1912 [NOI2009] 诗人小G

决策单调性

【学习记录】24.02.20 字符串

字符串算法

Manacher

P5446 [THUPC2018] 绿绿和串串

exKMP

P7114 [NOIP2020] 字符串匹配

KMP

P3435 [POI2006] OKR-Periods of Words

P2375 [NOI2014] 动物园

P5829 【模板】失配树

HDU7138 String

KMP自动机

P3193 [HNOI2008] GT考试

字典树

P2922 [USACO08DEC] Secret Message G

AC自动机

P5357 【模板】AC 自动机

P2414 [NOI2011] 阿狸的打字机

P3041 [USACO12JAN] Video Game G

P2444 [POI2000] 病毒

题目选讲

P5329 [SNOI2019] 字符串

P3426 [POI2005] SZA-Template

P6216 回文匹配

CF1654F Minimal String Xoration

【学习记录】组合数学

组合数学

放球问题

P5824 十二重计数法

ABC338D 题解

题意

扩展求最优解