文章

门门 如果限制条件只有 1,2,4，是个人基本都会做。 问题在3，不妨考虑 $x>y$的情况(方便去掉绝对值)，显然另一种情况 $y>x$是对称的，我们只需要考虑现在的这种情况即可。 因为涉及到减法，有一些退位的问题就很烦，比赛的时候过的人也少，队里就没人做这题了。 我们把 k 给二进制展开成 $( 阅读更多…

传送门 题目大意 给两个串 $S$和 $T$，每次操作可以将 $S$的第一个字符移动到新字符串 $D$的最左边或者最右边，求有多少种操作序列 (序列长小于等于 $S$的长度) 使得 $T$是 $D$的一个前缀。 题解 先思考一个更简单的模型。求 $T=D$的方案数 设 $S$的长度是 $n$，$T$ 阅读更多…

传送门 我做梦也没想到这题原来这样做.wva 首先看到 $n$的范围是 $10^{10}$，直觉告诉我复杂度肯定与 $\sqrt n$有关。 知道整个 $p_i$序列和最后的位置 $k$，很容易能倒退回删除之前的位置 $x$，这里就不讲了。 比较显然的一点是 $divmed(x) \leq \sqr 阅读更多…

传送门 题意：给一个模板串 $S$，$q$次询问，每次求模板串 $S[L,R]$内恰好在字典序上严格大于 $T$串的一个串 $S_1$ 用来复健 $SAM$的一道题。 挺模板的，首先做过 NOI2018 你的名字的同学一定会想到用线段树合并维护 $SAM$上每个节点的 $Right$集合，我们每次可 阅读更多…

原文作者：莉墨 lymoe 官方题解所有者：我 所以文章中的一些第一人称指的是 lymoe 不是我 qwq 另外在此说明了版权问题 Problem Link 题目灵感 当初其实是想考察一下 “树上全源最短路” 和 “二分图染色”，想了很久也没想出怎么出。 最后就把这两个算法合到一块，就出现了这个题。 阅读更多…

首先需要解释一下题意问题。 假设一天有 $a$ 个单位的蔬菜变质，而你这一天卖掉了 $b\leq a$ 个蔬菜，那么只有 $a-b$ 个单位的蔬菜会被丢掉。 考虑将每天建一个点表示，对于一种蔬菜，将其第 $i$ 天变质的个数记到第 $i$ 天的点上，也就是从 $S$ 连边。这个时间点的蔬菜不能放到更 阅读更多…

千年大坑。 合法排列有什么性质 首先考虑排列如何达到交换下界。 单独的考虑排列中的一个数，对于其目标位置，容易发现每一次关于这个数的交换一定是朝着目标位置的方向换的。对于排列 $2,1$ ，$2$ 要到后面 $1$ 要到前面，所以交换不会浪费次数。但是如果在前面加上 $3$ ，$3$ 要到后面去，$ 阅读更多…

考虑设 $dp_{u}$ 表示点 $u$ 的最少资金，有转移： $$ \begin{aligned} dp_u&=q_u+\min_{dis(u,v)\leq L_u} dp_v+(dep_u-dep_v)p_u\\ &=q_u+dep_up_u+\min_{dis( 阅读更多…

Link Counting Prime Description 给定一个数 $N$，求 $[1,N]$ 中有多少个质数。 $1 \le N \le 10^{11}$ Solution 法一：暴力判质数。 对于每个在 $[1,N]$ 的 $i$，主要分为若干个判断流程： 如果 $i\le 1$，则这个 阅读更多…

“ 恰好” 不好处理，考虑转化为” 小于等于 $k$ “ 的减去” 小于 $k$ “ 的。 定义 $dp_{i,j}$ 表示默认一个宽为 $i$ ，高为 $j$ 的矩形是一定安全的。其他格子的概率。 转移的话就是考虑： 从上一行 阅读更多…