在讨论《求问，洛谷评测机一秒跑多少？》回复：

取模是常数比较大吗？

rt。

一定要看清题啊qwq $l>r$ ~~估计也只有我会犯这种错误了~~

在讨论《早苗？》回复：

!

在讨论《2^k n log n CCF能卡多少？》回复：

洛谷最慢1.5s

在讨论《2^k n log n CCF能卡多少？》回复：

那我最大样例跑了 100ms

在讨论《2^k n log n CCF能卡多少？》回复：

但这是 1e8 级别的呀

在讨论《2^k n log n CCF能卡多少？》回复：

神奇优化

rt。

## 前言 一道 DP 大运，可能我的转移有些复杂，大家了解一下状态，转移最好还是自己写吧（或许有更简单的转移）。~~被大运撞飞~~。 ## 思考 假设主人公已经经过了一段区间的点，那他肯定最终会停留在这个区间的两端（如果不是在两端那说明他到了两端之后又往回走了，这不优）。 ## 状态定义 一个四位状态，$d_{i,j…

一道树状 DP。 ## 题意 在树上找一条路径，使得路径上的每一个点连接的非路径边的数量最大。 转化一下，设一个点 $u$ 出边数为 $s_u$，则要找的最大值变成一条路径所有点的 $s$ 之和减去两倍的路径长度（因为路径上的每一条边会被算两次）。 ## 思路 在把树的根设为 $1$ 号点后，我们发现每一条路径都会有一…

在文章《题解：P12690 [KOI 2022 Round 1] ABBC》发表评论：

sto WQC orz %%%%%%%%%%%%%%%%%%%%%

一道可持久化线段树加哈希题。 ## 题意 有 $m$ 个长度为 $n$ 序列，给定第一个序列，之后的每一个序列都有上一个序列修改一位得来。最后将它们按字典序排列。 ## 思路 首先想怎么比较两个排列。想到二分哈希，如果左半边的哈希值相等，就把范围缩小到右半边，反之。这其实就是一个线段树，每一个节点存一段区间内的哈希值。…

一道双指针优化 DP 题。 ## 题意 给定一个长为 $m$ 的数轴，每一次可以标记一单位长度，求题目给定的每一个区间都至少有一单位长度是被标记的最小标记数以及在标记数最小情况下的所有标记方案数。 ## 状态 先离散化。定义 $d_{i,0/1}$ 和 $s_{i,0/1}$ 表示是否标记 $i-1$ 至 $i$，让所…

一道贪心题。 ## 题意 两种操作： - 找一个 A，匹配之后的一个 B 并把它们删除。 - 找一个 B，匹配之后的一个 C 并把它们删除。 换一个角度想，在序列里找一个 B，与它前面的 A 或后面的 C 匹配并删除。 ## 思路 从左往右找，每找到一个 B，匹配之后的距离它最近的一个 C，若没有则匹配一个前面的 A。…

一道小贪心、大诈骗的 DP 题。 ## 贪心 发现一个栅栏的长度最多只会增长 $2$。因为一个栅栏最多只会受到两边栅栏的两种长度影响，如果增长多了，则一定存在一个其他栅栏长度不变，但当前栅栏长度更短的合法方案。 ## DP 定义状态 $d_{i,j}$，表示前 $i$ 个点，第 $i$ 个栅栏长度增长 $j$ （$j=…

一道贪心题，~~本人感觉这题有绿的难度~~。 ## 题意 一棵树，要求在上面标记点，使得任意一条长度为 $k$ 的简单路径都至少含有一个被标记的点。求最少标记多少点。 转化一下题意，给每一个叶子节点都向外扩展出一个虚拟的被标记的点，合法方案即任意两个被标记的点，若它们之间没有其他被标记的点，则它们的简单距离不超过 $k…

记得在可持久化 trie 里加上异或前缀和 $s_0$，要不然程序不会将 $p$ 取到 $1$。 hack： ``` 2 1 1 2 Q 1 2 0 ```

## 前言 身为一名蒟蒻，刚接触多源 BFS，前面众多大佬的题解看不懂，于是我决定写一篇入门一点的题解。 ## 暴力 枚举所有点，当一个点 $s$ 的 $d_s$ 不为 $-1$ 的时候，从它开始跑 BFS，找到所有到 $s$ 距离为 $d_s$ 的点并将它们标记一次。答案就是被所有 $d$ 不为 $-1$ 的点标记过…

一道贪心加线段树题。 ## 题意 在树上标记点，任意两点的简单距离不小于 $d$，求最多能标记多少个点。 ## 贪心思路 我们定义，对于一个被标记的点，称与其简单距离小于 $d$ 的点为被其覆盖的点。贪心思路为每一次找未被覆盖的点中的最深的点标记。 ## 证明 在未被覆盖的点中，对于一个的点 $v$，若选了他会覆盖最深…