文章

我第一次写游记竟然是在退役之后 qwq $day\;0$ 中午从被关了一个月的学校出来回了家，然后就跑去了机场，坐地铁到了酒店已经是十点多，然后 $uoj$群上有人说有 $cf$一场 $educational\;round$过 10 分钟就开始了，因为超级累所以带着玩的心态用小号打了打，打完 $AB 阅读更多…

这里的题目前来说都是 Atcoder 中比较简单的题。但我还是没几道是自己想出来的。 AGC018C : Coins : 贪心 $x+y+z$个人，每个人有 $a,b,c$三个参数，将这些人分为 $X,Y,Z$三类，求 $\sum_{i\in X}a_i+\sum_{i\in Y}b_i+\sum_ 阅读更多…

$68\ pts$ 比较套路的后缀自动机。 $100\ pts$ 使用线段树维护节点的 $endpos$ 集合即可，由于父节点包含所有其子节点的 $endpos$ 集合，用线段树合并求父节点的 $endpos$ 集合即可。 然后在找 $1-i$ 这个前缀的最长可以匹配 $S$ 的后缀时判断一下当前所 阅读更多…

$20\ pts$ 暴搜 直接枚举 $\rm{L}$ 集合即可。 $40\ pts\ \rm{DP}$ 暴力 $O(n^4)\ \rm{DP}$ ，即设 $f_{i,a,b,c}$ 表示选到第 $i$ 个，第一个序列选了 $a$ 个，第二个序列选了 $b$ 个，两个序列选的数中下标一样的有 $c$ 阅读更多…

$40\ pts$ 完全是送的。 直接枚举需要修改的集合然后算贡献，复杂度大概是 $O(2^{2^n})$ 级别。 $100\ pts$ 发现自己好蠢啊…… 设 $f_{i,j}$ 表示树上第 $i$ 个点其子树下的叶子节点中有 $j$ 个 $\rm{B}$ 类结点，其他的全 阅读更多…

好像最近更博很不积极啊。 先介绍一下李超线段树是什么。 李超线段树用于维护二维平面上的线段，并支持查询 $x=k$ 的轴上或者是一段 $l,r$ 的区间中的线段所在的 $y$ 的最大值/最小值。 插入操作：对于每一个线段树上的点 $x$ ，定 $x$ 的代表区间为 $l,r$ ，那么 $x$ 点所记 阅读更多…

这题可以用牛顿多项式做，不过也可以用生成函数搞。 设 $f_i$ 的 $\rm{OGF}$ 为 $\rm{F(x)}$，那么有： $$ \begin{aligned} F(x)&=\sum_{i=0}^{\infty} f_ix^i\\ &=\sum_{i=0}^{\ 阅读更多…

循序渐进地来 Pre-section 分析题目要求 要找长度 $>3$的等差序列 那么这个等差序列一定有一个长度为 3 的等差子序列 显然长度为 $3$的好找 还好找的不是一点点 所以我们的问题变成了找序列中是否有长度为 3 的等差子序列 Grade 1 首先想暴力 我们可以直接枚举公差和首项 设公 阅读更多…

引入 CF710F 维护一个字符串集合，支持三种操作： 1. 加字符串 2. 删字符串 3. 查询集合中的所有字符串在给出的模板串中出现的次数 操作数 $m≤3∗10^5$，输入字符串总长度 $L≤4∗10^6$ 如果只有第三个操作其实用 AC 自动机或者广义 SAM 都很好解决，但是它们都不支持动 阅读更多…