>定义一个序列 $\{a_n\}$ 合法，当且仅当对于任意一个质数 $p$，$\{\gcd(a_n,p^{+\infty}\}\}$ （非严格）单峰。 > >一个序列的权值 $f(a)$ 为，将这个序列的 $1$ 改成任意值（包括 $1$）使得序列合法，并且 $\operatorname{lcm}$ 不增的方案数。 >…

>你在一个 $n \times m$ 的网格中滑雪。这个网格的边缘全部是翔。你初始在 $(sx,sy)$，每次可以拉一坨，然后朝着一个地方不停地滑，直到前方有翔而不得不停在前一格（特别地，你要滑的那个方向的下一格不能是翔，否则你就会踩到你刚拉的上面）。求到 $(tx,ty)$ 的最短操作次数。 观察：你不会被自己之前拉…

>给定一棵树，点有点权 $t_i$，有颜色黑白，初始全白。 > >需要维护：单点翻转颜色，问有多少个白点内部有至少 $t_i+1$ 个黑点。 > >$n,m \le 10^5$。 果断考虑分块。考虑建立 dfs 序之后维护 $a_i=t_i$ 减去子树内黑点的个数。则修改可以直接转化为对一系列区间进行区间 $-1/+1…

>给定两个长度为 $n$ 的字符串 $a,b$ 以及一个长度为 $m$ 的字符串 $s$。问有多少个四元组 $(l_1,r_1,l_2,r_2)$ 满足 $a[l_1:r_1]+b[l_2:r_2]=s$。$n \le 5 \times 10^5,m \le 10^6$。 一个比较错误的切入点是枚举 $a$ 贡献的前缀…

感觉真的很迷。前一天晚上梦见自己只把第一题过了，然后就开始胡最后三个题，最后一个题都没写，只有 100pts，造成了一定的心理阴影。 开场。 T1：我去一眼开不出来。是 DP 吗？感觉不太会啊。怎么办？$\frac{n}{2}$ 的这个限制一定有玄机。考虑 $a_{i,3}=0$ 的部分分：首先让所有人都选择最高的那一…

>给定一个 $01$ 序列，问有多少个区间满足其长度整除其和。$n \le 2 \times 10^5$。 首先第一时间考虑到合法的长度/和对至多只有 $n \ln n$ 个，于是考虑求这么多次以下问题： >问有多少个长度为 $p$ 的区间和为 $q$。 发现完全做不了一点！怎么办？ 考虑根号分治。对于这种整除问题一个…

考虑从左往右进行填数，并且记录当前已经有多少个没有被录用的人。 初步令 $dp_{i,j}$ 为填完第 $i$ 个人的时候，有 $j$ 个人没有录用的方案数。此时会分成两类人：第一类是 $c \le j$ 的——一定不会被录用。第二类是 $c > j$ 的：只有 $s_i=0$ 的时候才不会被录用。 令 $S_i$ 为…

### 1A 所有 $n \times m$ 的网格题面不给 $n>m$ 的样例的出题人，祝你们的母亲在天堂相遇。 ### 1C >有一个长为 $n \le 3 \times 10^5$ 的数组 $\{a_n\}$，满足 $a_i \le 10^7$。以及一个 $t \le 5 \times 10^7$，求： > >$…

在文章《6 2》发表评论：

@m1kusama 我要在 3 天之内看见鸡贼娘

### CF1864H >给定变量 $x$，初始为 $1$，每次等概率随机进行以下两种操作之一：$x \leftarrow x+1,x \leftarrow x \times 2$。求期望多少次操作之后 $x$ 会 $\ge n$。 令 $n \leftarrow n-1$。 首先拆贡献，转化为对于 $i \in [1…

完成以下题目的实现： https://www.luogu.com.cn/article/pri4s5qb https://www.luogu.com.cn/article/f30v315l https://www.luogu.com.cn/article/6zy60fb9

T1 显然若干个连通块加边连成基环树强于连成树，这启示我们利用以下定理： >有 $k$ 个连通块，每个连通块大小为 $a_i$，并且 $\sum a_i =n$，则使用 $k-1$ 条边将这些连通块连接起来的方案数为 $n^{k-2}\prod a_i$。 > >证明：由 prufer 序列的性质可得，当 $k$ 个连…

首先一件珠宝的选取与否无法同时对四个限制作出回应，所以单纯以网络流上的一个节点代表一个珠宝是否选取是行不通的。于是可以考虑对所有横坐标以及纵坐标分别建图。设坐标为 $x$ 的点为 $c_x$，则对于一个位于 $(x,y)$，价值为 $v$ 的珠宝，建边 $(c_x,c_y,1,v)$。 如果每一维只有小于等于某坐标最多…

首先考虑边缘的数值域只有 $2$ 怎么做。考虑网络流，通过让 $i$ 与 $S$ 连通来代表 $i$ 选 $1$，与 $T$ 连通代表 $i$ 选 $2$。相邻的两个点连一条权值为 $1$ 的双向边。**不考虑边界上已经确定的点，用与 $S/T$ 直接连边替代与它们连边**。这样就能做到 $O(n^2)$ 了。 显然存…

首先对于一对限制 $(x,y)$，形象来说就是能不能将 $a_x,a_y$ 与 $b_x,b_y$ 配对，使得 $a_x \ge b_{tox}$，$a_y \ge b_{toy}$。也即 $\min(a_x,a_y) \ge \min(b_x,b_y)$，$\max(a_x,a_y) \ge \max(b_x,b_y…

>有 $n$ 个仓库，每个仓库中有 $a_i$ 个机器人。你可以在最开始激活若干个仓库，这会使得其中的所有机器人被激活。被激活的机器人可以沿有向边移动，去激活沿途的仓库。问最初最少激活多少个仓库才能让所有仓库都被激活。 如果一个强连通分量内有一个仓库被激活了，则这等同于强连通分量的所有仓库都被激活了。于是可以缩点。强连…

显然能够二分。 ``check`` 答案是否 $\ge 1$ 显然不弱于最小割，所以本题明显需要使用网络流。 我们不妨直接钦定 $1$ 到所有点的单源最短路。 具体地，我们使用一个常用的建图技巧，并求其最小割：对于一个点 $d_{i,j}$，其与 $S$ 连通等价于 $\text{dis}_i \ge j$，通过建立…

显然问题相当于要把整棵树重标号。 首先有一个粗略的观察：一个点要么小于其所有的邻居，要么大于其所有的邻居。我们下文称这两类点分别为大点与小点。 此时我们可能会想到钦定某个点是大点/小点。不过一个比较显然的事实是大点周围只会有小点，小点周围只会有大点，结合树是一张二分图可以得到大小点的分配方案本质上是树的一个黑白染色，可…

考虑按位贪心，即每次选择一个最小的能够使得后面有至少一个选择方案的方案选择。 首先我们探究一下一个序列有解的充要条件。直觉地，我们可以每次选择 $K$ 个不相同的点放在最前面，直到最后剩余的点不足 $K$ 个，并且每种颜色都有 $\le 1$ 个。此时把它们放在最前面即可。既然 $N=K$ 时都能通过 $1234\do…

结论题。 题意是问有多少种保留位置合法，于是想到令 $dp_i$ 为以 $i$ 作为最后一个保留位置的方案数，则转移方程形如 $dp_i = \sum dp_j\text{able}(i,j)$，其中 $\text{able}(i,j)$ 为对于 $a[i:j]$，仅保留 $a_i,a_j$ 是否合法。 现在的重头戏就…

首先两种方案本质不同等价于其最后保留的数不同，**等价于其删除的数不同**。于是可以将问题转化为对删除集合计数。 显然当执行到一个 $2$ 操作的时候，删除前面的哪个下标的 $1$ 操作都可以。于是我们可以钦定 $2$ 删除离其最近的一个没有删除的 $1$。 我们将这个操作序列改造一下：**让每一个 $2$ “吸收”掉…

首先枚举 $i$ 计算 $i$ 与前面所有数的贡献之和的方法是行不通的。因为在从高到低枚举位的过程中，$(a_j,b_j)$ 的第 $b$ 位不管与 $(a_i,b_i)$ 的第 $t$ 位全部相同还是全部不同，都无法直接处理贡献，得递归。于是复杂度就会退化到 $O(n^2)$。 但是按位处理贡献这个思路绝对是可行的，…

脑电波题。 >断言：令 $D = \sum \limits_{i=1}^n \sum \limits_{j=1}^n |a_i-a_j|$，即每个点到其它所有点的距离之和，则答案为 $\frac{1}{4}D$。 > >证明：我们可以把每次操作拆成若干次操作，使得每次操作过后，不会有一对 $p,q$ 满足在操作前有 $…

在下文的叙述中，默认 $i$ 为小孩，$j$ 为零食。 有一个显而易见的网络流：左部点为小孩，右部点为零食，$S$ 向 $i$ 连 $c_i$ 大小的边，$i$ 向 $j$ 连 $b_i$ 大小的边，$j$ 向 $T$ 连 $a_j$ 大小的边。求最大流即可。时间复杂度 $O(n^4)$，过不了一点。 考虑最大流转最小…

看到 $\sum \prod$ 状物直接想组合意义。具体地，我们计算在操作之后，从每个人手中挑出一个球的方案数。 考虑令 $f_{i,0/1}$ 为 $i$ 手中的球为原本有的，**不**计算 $i$ 从中选出一个球/上一个人给球，**算** 有多少种方案从 $i-1$ 手里拿球的方案数。二者均不考虑 $i$ 传几个给…

我们令 $f(i)$ 为 $A$ 在第 $i$ 天的等级，$g(i)$ 为 $B$ 的。 首先考虑一下没有天数上限怎么做。 我们考虑直接计算 $\sum \limits_{L} \sum \limits_i [f(i)=L][g(i)=L]$。 可以发现其对应到数轴上就分别是一个长度为 $B_x$ 与 $B_y$ 的区…

一个简单直接的想法是从前往后 ``push_back``，探究一个数能在前面有若干个数的情况下能够成功插入的条件。很不幸，无法直接写成我们可以利用的形式。 **考虑从后往前插入**。具体地，我们考虑一个数 $a_i$ 能够成为最后一个数的条件：显然为 $\operatorname{lcm} \limits_{j \ne…

解法 $1$： 考虑什么样的树合法。 >断言：一棵树合法当且仅当在断掉所有 $\operatorname{OR}$ 边后，至少有一个联通块没有 $0$。 > >证明： > >充分性：直接把全 $1$ 联通块缩在一起，并且操作除该联通块邻接 $\operatorname{OR}$ 边外的所有边，然后再操作邻接边即可。 >…

考虑令 $dp_i$ 为在 $i$ 时刻喝最后一次的代价。容易发现其为 $dp_i = \max\{dp_j+cost(i,j)\}$ 状物。 对于每种饮料，如果 $j$ 大于等于最近补饮料的时刻，那么 $i$ 就喝不到这个饮料，贡献为 $0$。否则 $i$ 就能喝掉饮料，贡献为对应美味度。 在 $i$ 向右移动的时候…

在文章《P11822 题解》发表评论：

问一下怎么卡？给组数据谢谢。@eastcloud