感觉完全没有 *2700？

看到题，猜测 $\max dis$ 不会很大，于是按照路径种类分类讨论一下路径 $(i,j)$。下设 $f_i$ 为最小质因数，并且更下面的情况不包括上面的情况。

阅读全文 »

套路题。想要做类似的还可以做做 P6116。

对于不断交换两个数的操作，容易发现确定开始位置 $s$ 和最终位置 $t$，操作次数固定为 $|s-t|$。所以可以考虑对答案序列进行 dp。

容易想到设 $dp_{i,j}$ 为当前已经放好了前 $i$ 个白色和 $j$ 个黑色，最少需要多少次操作。则有状态转移方程：

做起来真的没有想象中的那么难（？）感谢 @zltqwq 讲的好题/bx

首先考虑蜡烛可以烧到负数长度怎么做。发现这题等同于关路灯。设个状态：$dp_{i,j,0/1}$ 表示当前 $[i,j]$ 范围内的蜡烛都已熄灭，现在人在左/右端点的最大答案。枚举从 $[i+1,j]$ 或 $[i,j-1]$ 转移即可。

然后加入只能烧到 $0$ 长度怎么做。看起来变得非常麻烦，但是会发现一个性质：此时问题的答案不会比上面问题的答案更小。因为相对于上面的问题，此时长度 $<0$ 的蜡烛相当于是被我们删去了。

其实赛时可能可以做出来的，只是打了前 6 道想下班了，有点小小遗憾。

首先问题看起来很唬人，考虑转换一下。考虑已经固定 $m$ 条边，对于一个集合 $S$，什么时候会不与其他点有边。容易发现，此时需要满足 $\sum[R_i\in S]=\sum [B_j\in S]$。记这个数为 $c_S$。但是这还不够，因为 $S$ 中点连边方案数还没有计算。

这个答案显然不是 $c_S!$。因为 $S$ 可能可以分成两个集合 $s,t$ 都满足上述条件，则会重复计算。考虑如何去重。设 $dp_s$ 为集合 $S$ 的答案。我们钦定 $t$ 包含 $S$ 里最小的元素，则有 $dp_s=c_s!-\sum_{t\in S} dp_t\times (c_s-c_t)!$。

四维偏序板子题怎么只有一篇 cdq 题解呢/yiw

首先简单介绍一下 cdq 套 cdq 的思路。我们知道 cdq 的递归树可以理解成一棵线段树。cdq 的过程就是递归到叶子，再回溯回来。而 cdq 套 cdq 的过程则可以如此理解：

阅读全文 »

先 orz oyds。但是为什么没有 oyds 的简单预处理做法啊。

区间 dp。$dp_{i,j}$ 表示凑出区间 $[i,j]$ 的最小代价。考虑枚举当前区间 $[i,j]$ 与 $k$，表示 $[i,j]$ 在区间 $[p,j]$ 中出现了 $k$ 次，且 $p$ 取得最大值。则有转移：

$\min(dp_{p,j},dp_{i,j}+B+k\times C+(j-p+1-k\times len)\times A)\to dp_{p,j}$

居然自己想出了 AGC E。

首先考虑删边再加红边的本质是什么。容易发现，如果一条目标树上的边当前还没有被加上，且这条边所连两点在原树上的路径被切断，则此时一定无解。因为不管怎么加删边，这都是一棵树，而此时两点路径上一定有红边。

所以，我们就可以得到此时可以新增一条边 $(u,v)$ 的条件：路径上存在一条边，没有一条没有新增过的目标树上的边 $(u',v')$，使得原树上 $(u',v')$ 的路径不经过改变。容易发现，这等同于在原树上把所有 $(u,v)$ 路径上边的边权 $+1$，查询路径上有没有边权为 $1$ 的边。简单树剖维护即可。

居然差一点场切了。

首先可以将两棵树上对应的点看作一个点的两个不同状态考虑一个类似最短路的东西：设 $dis_{i,j,0/1,0/1}$ 为树上 $0/1$ 状态的 $i$ 点到 $0/1$ 状态的最短路。考虑怎样维护这个值。

由于是树上路径问题，容易发现设 $k$ 为树上 $(i,j)$ 路径上任意一个点,都有 $\min(dis_{i,k,p,0}+dis_{k,j,0,q},dis_{i,k,p,1}+dis_{k,j,1,q})=dis_{i,j,p,q}$。利用这个性质，容易发现，可以通过树剖加线段树维护 $dis$。

这是一篇决策单调性题解，好像现在还没有相同做法的题解。

还是类似的分治方式，每次点分成左右两半求两边贡献，再处理跨区间贡献。

但是有一种新的处理贡献方式：决策单调性。

补题。记录一下这道比较典的 E。

首先最后一步是诈骗，实际上就是 $\dfrac{\sum\limits_{i\in a}\sum\limits_{j\in a\land j\not=i}dis(i,j)}{C_k^2}$。

然后考虑如果点固定怎么计算上面的式子。这是个很常见的 trick：枚举每条边算贡献，即记录一个点 $v$ 的子树内有多少个有标记的点 $c_v$，这个点连向父亲的边的贡献即为 $c_v\times(k-c_v)$。

dp+根号分治，配得上省选题的难度。

一眼 dp，虽然暴力肯定过不了，但是把朴素转移先列出来绝对没坏处。

$dp_i=\min\limits_{1\leq j<i}(dp_j+\min\limits_{j\leq k\leq i}a_k\times v)$

同样来自 @Explodingkonjac 学长的讲题。但是我没认真听讲，所以自己想出来了。

原本的想法是设对于每一组分别设 $dp_{i,j}$ 为当前枚举到第 $i$ 个位置，已经钦定了 $j$ 个该组中的人投给自己组的方案数。转移就是枚举有多少人投给 $i$ 然后容斥。

但是可能是我没有处理好，总之这种转移似乎使每次切换组时就算上组内没被钦定的数的贡献。然而这样是错的因为后面组剩余的数量就是不确定的，有后效性了。

唯一的一篇题解用了点分治。太暴力了！这很蠢（指做法）。我们有一个优美的做法。

首先 $n$ 为奇数时，答案一定为 $1$。

证明：设答案点集为 $T$，则 $T$ 显然一定为一个连通块。考虑从 $T$ 中一个点 $x$ 移动到 $y$ 时，$S$ 中有些点对答案距离贡献增加，有些减少。只有这两者相等时答案不变。但是 $n$ 为奇数，不可能取等，所以 $|T|=1$。

先假设对于所有 $(i,j)$ 之间都连一条长度为 $X$ 的边，则问题转换成：只保留树边，记 $D(i,j)$ 表示 $\min(dis(i,j),X)$，求 $\sum D(i,j)$。

考虑套路点分治，算出 $\sum_i\sum_{j>i}[dis(i,j)<X]=A,\sum_i\sum_{j>i}[dis(i,j)<X]\times dis(i,j)=B$，则 $ans=B+(\binom n2-A)\times X$。算的方式就是将当前处理的以 $rt$ 为根的子树中所有点 $i$ 的 $dis(i,rt)$ 排序后双指针。

这一部分是一个板子，不做赘述。只需要注意点分治常见错误，如求重心某些地方写成 $n$ 而不是 $siz$ 即可（我怎么又踩坑啊）。

模拟赛搬了这题的 $k=10^5$ 加强版。于是有了一个复杂度和 $k$ 无关的做法。感觉学到了。

设 $f_i$ 为左端点为 $i$ 时，最小的可行右端点。考虑维护这个东西。但是你发现修改一个位置的值很难维护。

你又发现每次只修改一个数，考虑线段树分治。但是你又发现你连插入都不会做。但是删除非常简单。设删了 $p$ 位置的一个 $x$，左右第一个 $x$ 分别在 $l,r$，就只要 $\forall i\in[l+1,p],f_i\to \max(f_i,r)$ 就行。于是还是线段树分治，但是对删除操作进行。

感觉我的做法更魔怔一点。

下取整显然不好搞。于是考虑套路化地变成 $\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{k=0}^{j-1}\frac{ik+x-(ik+x)\bmod j}{j}$。$\frac{ik+x}{j}$ 部分是好处理的，接下来就只考虑 $\frac{(ik+x)\bmod j}{j}$。

注意到 $k$ 取遍 $[0,j-1]$，所以根据 $\gcd(i,j)$ 相同的 $i$，$\sum\limits_{k=0}^{j-1}\frac{(ik+x)\bmod j}{j}$ 是一样的，而这部分可以 $O(1)$ 算。于是先枚举 $j,\gcd(i,j)$ 再推式子。

非常巧妙的题！

先尝试分析一些简单的性质。

首先，每个棋子可以视作只往一个方向移动若干距离，因为这个操作相当于原本边权为 $0$，每走一步将边权 $\oplus1$。显然走回头路会抵消掉之前走的。也就是说，可以将问题转化成，对于每个 $a_i$ 选择一个 $b_i$，将 $[a_i,b_i]$ 间的边权 $\oplus 1$，使得最后的边权序列满足要求。

场上 20min 过了。感觉现有题解对复杂度分析有点问题，于是写一写。

首先置换的形状显然是若干个环。考虑设操作次数为 $k$，依次对每个环贪心。对于一个长为 $l$ 的环 $i$，在满足限制的情况下，贪心地把 $a$ 中更小的放到前面。设在这种情况下要求 $k\bmod l=f_i$。

考虑这个环的操作对于其他环的操作有什么限制。若后面有另一个长为 $l'$ 的环 $j$。若 $\gcd(l,l')=1$ 则显然没有限制。否则，若存在 $d|l,d|l'$，则会有限制：$f_i\bmod d=f_j\bmod d$。

为啥这种题大半的题解会都是一样的？来个不同做法的。

首先可以发现，对于一个固定位置操作若干次大概是能使这个位置变成任意一个数的。于是有个猜测的做法：倒序枚举 $i$ 不断对 $0$ 操作直到 $P_0=i$，然后再操作一次使 $P_i=i$。

试了一下发现不太行。因为如果此时 $a_0=0$ 就怎么也动不了了。然后发现 $0$ 其实非常不好，但是发现，可以通过操作若干次数字 $n-1$ 的方式使 $P$ 循环位移，于是先不断操作 $n-1$ 使 $0$ 固定到 $P_{n-1}$ 的位置。

这种小清新题真是太有趣啦！

如果你做过 AGC027E，看到这种两个字符合成一个，最后还要计数的问题，可以构造一个关于 $S$ 的简单函数 $f(S)$，使得不管怎么操作 $f(S)$ 都不变，然后从这个不变中寻找性质。

对于 AGC027E，这个构造的方法就是令 $a\to 1,b\to 2$，$f(S)=\sum S_i \bmod 3$。于是这题我一开始也想的是模意义下的东西，但是一直没想出来。直到想到异或，瞬间有如醍醐灌顶：令 $a\to 1,b\to 2,c\to 3$，设 $f(S)=\bigoplus S_i$，这样就成功构造出来了一个不变的 $f(S)$ 了。