C 秋天的第一杯奶茶以下复杂度默认 $n,m,q$ 同阶。 考虑询问 $[x,y]$ ，差分一下就是区间 $[1,x-1]$ 的修改对 $[x,y]$ 的询问的影响（记作 $[1,x-1][x,y]$）。 然后可以直接莫队一下，这个往左往右加入拿 BIT 维护即可。复杂度 $O(n\sqrt n \log n)$ ，期望得分 $85\sim 95$ 、 这种东西的优化很类似于区间逆序对。考虑再次差分，变成 $[1,x - 1][1,y] - [1,x - 1][1,x - 1]$ ，也就是进行完 ...

草关机没保存。。重写一遍。。 CF1434D题解证明了答案的一端一定是直径的一端。 于是对每个点维护它到根的距离以及它到根的路径的颜色即可。相当于区间反转，全局 $0$ 位置最大值。线段树维护即可。 CF1423F$k > n$ 与 $k < n$ 的情况显然。 考虑一个不变的量，在修改前后 $\sum i a_i \bmod n$ 是不会改变的。于是可以猜这么个结论，并且手动打表后发现没啥问题。 CF1406E考虑先把所有小于 $\sqrt n$ 的质因子删除。然后枚举每个 $\ ...

密码不难发现取对就做完了。 挑战基本上一样的原题：Complete the Projects (hard version) 首先，对于 $a_i \le b_i$ 的，我们选择了也不会有什么损失，直接按照 $a_i$ 排序从小到大拿就好了。 对于 $a_i > b_i$ 怎么处理呢？可以猜几个贪心结论但是会发现都是错的。我们考虑，如果已经知道了要选择的物品是哪些，设为 $(A_i,t_i)$ ，其中 $t_i = a_i - b_i$ ，也就是在选择这个物品后所损失的血量。我们能否找到一 ...

CF576D Flights for Regular Customers考虑从小到大加入边，一个众所周知的结论是邻接矩阵的 $k$ 次幂就相当于走 $k$ 次后的路径条数。在这里我们只关心 $k$ 步后能否走到一个点，于是是 $01$ 矩阵。每加入一条边就进行一次矩阵快速幂，然后加入下一条边。 考虑如何计算答案。当且仅当加入一条边后在 $n$ 步内能走到终点，才说明可以走到终点，每加入一条边后判一下能否 $n$ 步内走到终点即可。 CF1187D Subarray Sorting大概有两个做法， ...

T1 食堂计划最短路图是一张拓扑图，并且只要再这个图上走出的路径就一定是最短路。 于是考虑一个 $dp$ ：设 $dp[u][v]$ 表示当前一个路径结尾在 $u$ 另一个在 $v$ 的方案数量。但是直接转移会出现重点。 我们考虑转移的时候限制如果从 $(u,v) \to (x,v)$ ，必须要有 $dis_u < dis_v \or (dis_u = dis_v \and i < j)$ 才行。唯一可能走出重点的情况就是其中一个点走到了一个根到 $v$ 路径上的点，但是如果这种情况 ...

（多数都是水题 最优贸易缩点，拓扑排序，然后考虑 $dp$ 出 Mn 表示 $1$ 到这个位置的最小买入价格，然后用在下一个位置卖出的收益更新一下 $dp$ 。 其中 $dp[u]$ 表示 $1 \to u$ 路径上最大的差价，用上面说的方式更新即可。 Road Construction缩边双，会得到一个树，不难发现链接两个点就把这两个点所在边双在树上的路径给合并到同一个边双。 然后发现拿叶子最优，然后可以猜结论答案是叶子个数除以二上取整。 每轮找公共祖先最靠上的缩起来就好了。 矿场搭建考虑缩点 ...

contest A 二次剩余明显，当 $|x-m| \ge 320$ 的时候，这个二次函数的值必然大于了 $10^5$ ，但是 $k \le 10^5$ ，于是我们往两边枚举 $O(\sqrt n)$ 个，对于每个值维护一个堆即可。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include "iostream"#incl ...

目前做的这四个题里面最神仙的一个。 考虑任意枚举一对合法点，然后画出下面这种图： 不难发现，直线上方的点之间距离必然不超过 $d$ ，直线下方两个点之间距离仍然不超过 $d$ 。 于是我们只用考虑上下点之间的关系，我们可以对上下距离大于 $d$ 的点连边，表示这俩点不可一起选。于是我们相当于求这个二分图的最大独立集，二分图的最大独立集就是最大点覆盖的补集，最大点覆盖可以在二分图匹配的网络上转成最小割做。 最小割输出方案：从 $S$ 开始在残量网络 dfs 一次，对访问到的点打标记，这些访问到的 ...

考虑对于一个位置，如果它不是 $s,e$ ，那么这个位置必然有一个入度一个出度。也就是说一个位置的方案有从右边进入，从左边进入，向左边出去，向右边出去。 我们考虑当前已经填完了前 $i$ 个位置，到现在为止还剩 $j$ 个向左的边和 $k$ 个向右的边。不难发现，如果这个点不是 $s,e$ 的一种，那么对于任何一种填这个点边的方案，要么使向左的、向右的边的个数同时 $+1,-1$ 要么使向左、向右的边的个数不变，分别对应： 然后如果新增的点是 $s$ ，那么只能是 如果新增的点是 $t$ ， ...

一个很妙的优化。 我们考虑 $\binom{x + y}{x}$ 的组合意义，是从 $(0,0)$ 到 $(x,y)$ 的方案数量。于是考虑这个式子本质上就是求 $(0,0)$ 到 $(a_i+a_j,b_i+b_j)$ 的路径数量。 这个东西看起来也不太能做。但是发现我们可以给它变成求 $(-a_i,-b_i)$ 到 $(a_j,b_j)$ 的方案数量。这个东西就可以 $dp$ 了，设 $dp[x][y]$ 表示 所有点到 $(x,y)$ 的方案数量。初始给 $(-a_i,-b_i)$ 设为 ...

考虑这个旋转操作，本质上就是把一个字符往左移动一些位。 如果两个字符串每个字符的数量相等，那么如果从左到右逐一归位必然可以构造出一组解，当然如果数量不同那肯定没法归位。 然后不难发现本质上就是一个匹配问题，我们固定一些 $S$ 中的位置，这些位置必须满足在 $T$ 中的相对顺序和在 $S$ 中一样，只归位剩下的，不难发现必然也是一组解。 相当于我们现在要找一个类似 LCS 的东西。但是会发现它和 LCS 是有差别的直接拿 LCS 不太对。因为当有一个 $S$ 中的位置和 $T$ 中的一个位置 $ ...

我们考虑生成一棵生成树的过程，本质上相当于是选择一些生成树拼起来，而两个生成树拼起来的代价就是把拼接点的权值乘上点的个数积。 于是可以考虑一个 $dp$ ，设 $dp[S][u]$ 表示一个点集 $S$ 组成的根为 $u$ 的树可以得到的最小权值。 于是我们考虑枚举一个子集来进行转移，也就是对于一个子集 $T$ ，我们可以枚举一下这个树的根，然后转移： dp[S][u] = \min\{dp[S][u] , dp[T][v] + dp[S \setminus T][u] + (n - siz[ ...

Interesting Drug考虑选择物品的过程，选择物品就会删掉这个东西，所以相当于是一个扩展区间的过程。 第一步选择 $i$ ，也就是说最开始区间是 $(i,i)$ ，每轮可以扩展到 $(i-1,i)$ 和 $(i,i+1)$ 。 把这个看成一个二维平面上行走的过程，那么我们可以把这个过程倒过来，也就是初始在 $(1,n)$ ，走到 $(i,i)$ 能得到的最大权值。 如果第 $i$ 个物品在 $C_i$ 步被选择，相当于是从 $(i+1,i+C_i-1)$ 走到 $(i,i+C_i-1) ...

第二次学了，上次的文章在这里：生成函数与组合计数 先粘一下以防以后忘了： 这次会以 $F(z),x$ 作为形式幂级数，也就是说后文的 $x,x_0,\dots$ 都是形式幂级数。 前置芝士：泰勒展开，在上次的文章中可以看到。 牛顿迭代 F(G(z)) = 0求 $G(z) \bmod z^n$ 设 $x_0 = x\bmod z^n$ ，考虑求 $x \bmod z^{2n}$ 。 我们将 $F(x)$ 在 $x_0$ 处展开，那么有 F(x) = F(x_0) + F'(x-x_0) + ...

根据 LP对偶（我不会的东西）有这么个结论： 最大费用循环流等价于： \min \sum_{(u, v) \in E} c(u, v) \max \left(w(u, v)+h_{u}-h_{v}, 0\right)其中 $h_u$ 是给每个点任意定的一个权值，$c(u,v)$ 为一条边的容量，$w(u,v)$ 为一条边的费用。可以带入最大流和最小割验证。 对于这个题，如果二分答案为 $\lambda$ ，我们相当于是要最小化 \sum x_{u,v}满足 d_u + x_{u,v} + ...

首先，跑两千次 dijk 或者 spfa 肯定是不行的。 发现每次只会给边权加一，并且一共才加 $10^6$ 次，所以最短路长度的增加量其实只有 $10^6$ 级别。 我们考虑去求这个增加量。有一个操作：先设最开始跑一遍最短路后 $1$ 到 $u$ 的最短路为 $dis_u$ ，对于一条边 $u\to v$ 设其权值为 $w$ ，那么把它的权值改成 $w + dis_u - dis_v$ 。由于 $dis_u + w \ge dis_v$ 所以这个值肯定是非负的，且如果这条边在 $1$ 到 $v ...

昨天写了忘发了。。 考虑容斥，设 $f(i)$ 表示钦定了 $i$ 个数只出现了 $\le 1$ 次时的方案数量，那么答案显然等于 ans = \sum_{i=0}^n (-1)^i f(i)考虑我们钦定的 $i$ 个数，显然可以直接假定为 $1\sim i$ ，最后再乘个 $\binom n i$ 的系数即可。 先考虑除开前 $i$ 个的数，这些数是没有限制的，他们可以组成集合的方案数量是 $2^{2^{n-i}}$ 种，因为任何一个这 $n-i$ 个数的子集都可以作为某一种集合出现或者不出 ...

Day 0Day 0 居然放假。。在家里打了下各种多项式板子认真背了下 ppt 上的经典套路。。 据说要考多项式，字符串和计算几何？ 考到计算几何就放弃吧（？）大概写了下凸包和半平面交。。反正几何算是知识盲区了。。不过按照前几年的惯例SC出几何多半全场都不可写吧（确信。。（mmp后来证明毒奶了） 背不到SA，写了下后缀平衡树（写不来SA要排序就上这个反正复杂度一样）SAM 写了一下还是忘不掉的，PAM 前两天也复习过了。 假装准备得很充分了。。晚上和 wkr 和 ywh 颓了会儿 arc 。。 ...

由于是做题时写的思路所以可能很乱 /kk 首先考虑 $k = 1$ 的情况。我们希望对于每一个 $i$ 求出一个 $j$ 使得 $\gcd(i,j) = 1,\max |a_i - b_j|$ 。 考虑把绝对值拆开，对于每个 $i$ 分别求最大的 $b_j$ 和最小的 $b_j$ 。这两个问题明显是对称的，考虑求最大的 $b_j$。 我们可以整体二分一下，比如当前二分的数为 $x$ ，把 $\ge x$ 的数的编号拿出来放到一个集合里面。我们预处理出每个编号的所有质因数 （$O(\log n)$ ...

比赛链接 A 异或树考虑假设我们已经确定了最高位，则可以按照最高位为 0/1 分成两类。 而最小生成树必然是两边连成一个联通块，中间再连一个边。我们可以分别算这两类贡献。 显然，最高位全是 $0$ 和最高位全是 $1$ 砍掉最高位后是一个子问题（只是少了一位），可以递归下去做。 注意 $n$ 很小，我们可以枚举一边联通块的大小（另一边就已经知道了），递归算 $ans(i,m-1)$ 。然后对于左边的所有方案和乘上右边的方案数量，对于右边的所有方案和乘上左边的方案数量，最后再乘一个组合数即可。 现 ...

比赛链接 A qiqi20021026 的 T1这题出的真离谱。。 考虑 $O(qn)$ 怎么做。显然建 trie 树后直接在上面求子树内第一个串的个数和第二个串的个数的最小值贡献在答案里面就行了。 正解，直接上四维莫队。由于 $n$ 比较大，串长期望很小，可以看成移动 $O(1)$ ，然后复杂度 $O(nq^{\frac 3 4})$ （莫队复杂度）。 为什么能跑过去 我也不知道啊。。玄学 。题解写了最后一个指针的移动次数实际上不多。。 $n\le 10^4 , q\le 5\times 10 ...

616模拟赛题目背景是 arcaea B Tempestissimo抽象一下，这题相当于有一个盒子里面有 $n$ 个球，其中 $m$ 个关键球，求期望抽出所有关键球的时间。 我们可以考虑倒过来，也就是求期望抽出第一个球的时间，最后由 $n$ 减去即可。 考虑这个东西本质上就是 \sum_{i=1}^{n-m} P[这个球在第一个关键球之前被抽出]如果我们把关键球先加进去，每个球在哪两个关键球直接抽出本质上是相同的。由 $m$ 个关键球可以分成 $m+1$ 段，于是概率就是 $\frac{1}{ ...

比赛链接 A sequence首先，和谐的数列可以仅由前两个数递推得到。然后可以证明，如果第一个数确定，答案关于第二个数凸，如果第二个数永远取最优，答案关于第一个数凸。所以可以直接三分套三分来做。但是这样是 $O(n\log^2 v)$ 的，很可能会被卡 T 。 考虑和谐的序列的循环节一定是 $6$ ，所以可以对于 $\bmod 6$ 的所有值分别整个 vector 再做个前缀和，查询可以直接从每个 vector 二分。复杂度 $O(n\log n + \log^3 v)$ 当然，也可以暴力整凸 ...

现在看了看以前的题感觉好妙啊。。多校的时候好像是找出原题直接做的。。 为了回答询问，可以贪心地做前缀的线性基。由于只有 append 操作，可以方便地维护这个。 对于 $1\sim i$ 的线性基，我们可以对每个位置记一个编号，表示能够选择这一位的最靠右的数编号是什么。 在插入一个数到线性基的时候，从高到低位考虑，如果这个数比这个位置上的数更靠右且这个数可以更新这一位，我们可以把这个数和线性基中这个数字交换一下，再更新编号，然后继续向低位更新。 考虑正确性，对于一个位置，它显然只会被比它的编号高 ...

我们考虑把输入的矩阵看成邻接矩阵，于是相当于是给了个图。 然后考虑询问，1 的位置就相当于前后有边相连，0 的位置就相当于没有边。于是相当于通过 1 分成了很多个联通块，这些联通块之间不能有边，求可以满足这个条件的排列个数。 这个不好求，我们考虑求钦定了某些位置有边，剩下无限制的方案数量，最后做一次逆与卷积即可。因为设 $F[s]$ 表示钦定了 $s$ 集合的 $1$ 的位置有边，剩下无限制的方案数量，$f[s]$ 表示恰好只有 $s$ 的 $1$ 的位置有边的方案数量。我们显然有 F[S] ...

我们考虑对每行没列 $\min-\max$ 容斥。 考虑某种状态（行列的状态）每个集合内部的元素（一行或者一列）出现了一个数的最大时间，也就是全部都有数的时间（类似 [HAOI2015]按位或）。由于式子 \max(S) = \sum_{T\sube S} (-1)^{|T|+1} \min(T)也就是我们得算的实际上是每种状态（一些行与列）中的数第一次被选到的期望时间。 如果我们实际枚举了行列的状态，对于每个状态，设这些行列的和是 $x$ ，那么贡献就是 $(-1)^T\frac {tot} ...

考虑对于每一个右端点 $r$ ，维护 $ans_i$ 表示 $\min |a_i-a_j|,j\in[i,r]$ 。 那么如果我们离线下来询问，我们要求的 $[l,r]$ 的答案就是一段后缀的最小值。但是为了保证复杂度，事实上我们维护的 $ans_i$ 只是保证了一段后缀的最小值就是 $[l,r]$ 的答案，而 $ans_i$ 是可能大于 $\min |a_i-a_j|,j\in[i,r]$ 。 现在考虑我们把 $r - 1$ 移动到了 $r$ ，并且已经维护好了右端点为 $r - 1$ 时的 ...

考虑跑出 dfs 树。如果两个点在 dfs 树上路径本身长度就是奇数，可以直接走过去。 否则，相当于可以在这两点之间的路径上有两个点 $u,v$ ，可以通过在 $u$ 离开 dfs 树上的路径然后从 $v$ 回来继续走到另一个点的方式改变奇偶性。不难发现，这个条件等价于 $u,v$ 之间的路径存在于一个奇环上。同时我们还有一个结论，一个点双（因为这题要求点不相交）内部如果有一个奇环，那么点双内部任何两个点都处在一个奇环。 于是我们考虑给所有点双内有奇环的点打个标记，然后树上差分，询问的时候就询问 ...

考虑一次查询，比如查询 $[l,r]$ 区间。 首先找出区间内最小值的位置，设为 $pos$。 考虑把询问的区间的子区间分成三种： 跨过了 $pos$ 左右端点都在 $[l,pos-1]$ 左右端点都在 $[pos+1,r]$ 考虑分别处理。对于第一种，明显贡献是 $(pos-l+1)(r-pos+1)$ 。 下面设 $[l,r][L,R]$ 表示左端点在 $[l,r]$ 内，右端点在 $[L,R]$ 内的所有区间的最小值的和。 我们考虑怎么求 $[l,r][l,r]$ 的值。我们把这个拆成 ...

一种用来求最短线性递推的奇妙算法。复杂度是 $O(n^2)$ 。 忘了怎么做建议看看这个博客，很清楚了。 模板题 CF848E 123456789101112131415161718192021222324252627int Pow( int x , int a ) { int ans = 1 , cur = x % P; while( a ) { if( a & 1 ) ans = 1ll * ans * cur % P; c ...