归档: 2022/8

2022

08

29

Prefix Function Queries题目传送门题意有一个长度为 $n(1 \leq n \leq 10^6)$ 的字符串 $s$ ，有 $q(1 \leq q \leq 10^5)$ 次询问。每次询问给出一个非空字符串 $t(

2022-08-29 狂刷字符串

acm 字符串

26

区间本质不同子串个数题目传送门前言借鉴了题解中的这篇。起因前面多校训练的时候，出了一道和这道题十分类似但是又差别很大的题目。于是想着先把这道题给学会了，然后再尝试写多校训练中出现的那道题目。本题知识点一览 $SAM$ + $LCT$

2022-08-26 狂刷字符串

acm LCT 字符串后缀自动机线段树扫描线离线

25

LCT(link-cut tree)前言关于我为什么要学这个东西学这个是因为我要学习这道题的写法，而这道题是用到了 $LCT$ ，于是，学一下。大概解释这里不做详细解释，只粗略的做个描述。 $LCT$ 和树链剖分很像，但是， $LCT$

2022-08-25 算法学习

acm LCT

24

【模板】轻重链剖分/树链剖分题目传送门题目大意已知一棵包含 $N$ 个结点的树（连通且无环），每个节点上包含一个数值，需要支持以下操作： 1 x y z，表示将树从 $x$ 到 $y$ 结点最短路径上所有节点的值都加上 $z$。 2

2022-08-24 算法学习

acm 树剖

10

2022杭电多校第7场contest传送门战况这次贼猛，前几题写的也贼快，甚至在前面的时候甚至排到了第3名。这次我也写了一道题，和曹佬一块讨论出了1002。这次没有找到字符串题目。补题1006-Sumire (数位dp)题意计算

2022-08-10 2022杭电多校

acm

05

AC/DC题目传送门前言这是2022hdu多校第5场的1008，当时因为通过率过低，题目都没看，结束后看了之后发现是道 $SAM$ 好题，在这里补一下。题目大意给出一个初始字符串 $s$ ，有三种操作 $1\ c$ : 在 $s$ 的

2022-08-05 狂刷字符串

acm 字符串后缀自动机

05

2022杭电多校第5场contest传送门战况这次总体来看没有之前那么猛这次我也算是写了0.5道，我和姚老师讨论出了10的结论。这次有字符串题目，但是通过率都非常低，当时的08连题都没看。补题08-AC/DC我感觉这是一道非常好的

2022-08-05 2022杭电多校

acm

01

Reverse the String题目传送门题意给出一个字符串，有一种操作，将其中一个子串反转，我们可以进行最多一次这样的操作，需要使得这个字符串字典序最小。 $T$ 组数据， $1 \leq |s| \leq 10^5$ ， $\su

2022-08-01 狂刷字符串

acm 字符串字符串哈希二分