whk 考试前写题解攒 rp 有用吗

仍然是讲讲想出来的过程。

首先，我们只需要关心一个联通块中有哪些点，而不用关心图的具体形态。

%赛场切了！

矩阵是不太好处理的，所以考虑从一行去推下一行。

设上一行选择了 $p_1,p_2,\cdots,p_k$ 这几个横坐标的位置为 $1$，分情况讨论一下这一行选择的 $x$ 位置。

虚高 *2800。放模拟赛 T2 人均切了。

先想树的情况怎么做。枚举每个起点，剩下的贡献就是定值。求这个值可以钦定 $1$ 为根求出所有的 $siz$，然后枚举 $i$ 为起点，以 $i$ 为起点的答案就是 $\sum siz_i$ 加上 $i$ 到 $1$ 路径上，不含 $1$ 的所有点的 $\sum_j n-2\times siz_j$。

然后放到基环树上，发现需要注意环的情况，在一个环上先往一个方向走和另一个方向的贡献是不一样的。发现可以通过一个环上的区间 dp 解决。

虚高 *2800，放模拟赛 T1 人均切了。

这是 zlt 说的，不是我说的，我还是觉得没那么虚高的。

首先显然是数位 dp。

现场做了，离散化数组没开 ll，被卡 au 线 $\to$ 卡线 ag。

因为代码是半个月前写的了，回忆做法时可能有点偏差，如果发现有误请联系我修改。😃

考虑怎么刻画题目所给条件。发现对于一个区间 $[l,r]$，可以钦定其中一个卡牌 $i$，使得这张卡牌是第一张无法打出的牌。然后考虑它前面放什么牌，会发现前面会放所有 $a_i>b_i$ 的牌。

orz sinsop90/bx

乌龟和 sinsop 结芬！！！

题意即数最大匹配为 $k$ 的二叉树个数。数树问题，考虑不断加入子树 dp。但是这题是二叉树，所以可以直接每次将两个并作一个转移。

又是模拟赛题，感觉挺牛的。kkio 场了/bx

首先发现每一次大操作等同于进行一次置换，会形成若干个置换环。根据经典结论得，设这些环长为 $cyc_i$，则有 $k=\operatorname{lcm}cyc_i$。于是考虑在原图中构造若干置换环。

然后通过手玩发现，可以在 $4$ 步以内交换任意两个相邻的数。于是可以把矩阵按照 S 形拉成一条链，再在这条链上割出来若干段作环。

==Ambiguous Encoding。orz Wu_ren。

直接选两个拼成的字符串不好刻画，考虑增量。定义一对合法的字符串 $S,T$ 满足其中一个是另一个的前缀（这样才可能通过往后面加模式串变一样），每次往当前两个字符串中长度更短的后面塞一个模式串，使得一个字符串仍是另一个的前缀。

容易发现，任何时刻 $\left||S|-|T|\right|\le m$。所以此时可以考虑一个 dp：设 $dp_{i,j}$ 为当前更长的字符串最后的模式串编号为 $i$，$\left||S|-|T|\right|=j$ 的状态最少需要多长的字符串拼成。

@Explodingkonjac 学长讲的做法，题解区有一篇讲这个的，但是感觉细节真的好多……

我们先尝试构造出来一个合法序列。怎么构造呢？先枚举 $\sum a_i=s$，然后先将序列 $a$ 设为 $\max(p_n,0)$ 个 $1$ 后面接 $\max(p_n,0)-s$ 个 $-1$，也就是先到最大值再到最终值。

然后考虑往这个数列中插入若干 $\{-1,1\}$ 这个序列。画到一个折线图上，发现这就相当于增加一块凹陷。不难发现，对于一个有解的 $s$，这样一定能构造出解。

详细化 pb 的题解。

感性理解一下，把大数字单独放在一个盒子里，好像总不是太亏。

阅读全文 »

算是第一次独立想出这样难度的题。

首先考虑手玩一下“变成整个序列的异或和”这个操作。发现如果一开始对 $i$ 位置进行操作，记录一个值为原来所有的 $a_i$ 中，现在不在 $a$ 中的 $a_i=x$，则以后：

阅读全文 »

一个有点乱搞感觉的做法。

直接讲结论：每次取出最小的若干个乘积 $<10^{18}$ 的质数相乘询问，每次如果问出 $p\mid x$ 就再问一次判断有几个 $p$ 的因子，更新当前 $ans$ 和剩下因数乘积的上界 $lim$。如果全部询问用完就输出 $\left\lfloor\dfrac{9\times ans}{2}\right\rfloor$，如果枚举到的质数 $p^3>\lim$ 就输出 $ans\times 2$。

先讲后一种回答为什么是对的：在这种情况下，$\ge p$ 的质数对答案的贡献最多是 $\times 4$，最少是 $\times 1$，则输出 $ans\times 2$ 一定两倍范围内。

来一个无脑线段树合并做法。

考虑记前 $t$ 秒有 $f_u(t)$ 头牛能通过 $u$ 点到父亲的边。则有：

$f_u(t)=\min(m_ut,\sum_{v\in son_u}f_v(t))$

看到计算逆序对数量，毫无疑问是要分开算贡献的，但是怎么算是个问题。

先不考虑怎么算，先考虑怎么处理字典序小于 $p$ 这个条件方便。设一个字典序小于 $p$ 的排列为 $p'$，发现可以用和数位 dp 类似的方式，看最前面多少位是顶到上界的，再根据第一位没顶满的 $p_i'$ 的取值算贡献。

设当前枚举第一个位没顶满的是第 $i$ 位，此时发现已经可以将序列分成不同的几部分算贡献了：

Daily problem.

感觉是一个易懂的方法。

首先手玩样例，发现罪犯可以在警察进入一棵子树时从警察后面溜走，所以警察很有可能要重复走某些路径，这样用树形 dp 比较困难，所以可以考虑更像放在序列上的 dp。

从 loj6240 来的，是仙人掌强化版。建议大家都尝试一下。

本篇题解将从树的做法一直讲到仙人掌的。

树

挺简单的交互题。不知道为什么这题在 cf 上的版本 评了 *2700。并且有双倍经验。

首先显然是要二分答案然后用交互 check 的。我们先尝试从 $P=1$ 开始是否可行。容易发现，如果得到 $ans>mid$，$P$ 此时原本在 $\dfrac{n}{2}$ 左右，而第二次我们要找到一个 $P'$ 使得 $|P'-P|\approx \dfrac{3n}{4}$。这显然是无解的。

不过这也启示我们应该从每次跳的距离都最大的情况去考虑，如何找到一个合法的起点。

感觉也是很 well-known 了吧。

对于要求 $a_x>a_y$ 这种，我们一般是考虑连 $x\to y$ 跑拓扑排序。但是这题要求一个点向一段区间或一段区间向一个点连边，怎么办？我们会优化建图。

由于是在树上，树剖+线段树优化建图常数可能偏大，考虑倍增（或称 ST 表）优化建图。由于上面的连边操作显然有可重复贡献性，每次对一条链 $(u,v)$ 连边或从一条链 $(u,v)$ 连出边，把这条链拆成 $(u,x),(y,v)$ 两个长为 $2^k$ 且并集为 $(u,v)$ 的链，找到 ST 表上对应点连边即可。

非常好的经典题！

先有一个暴力的想法：一个一个枚举每个数加进哪个集合或不加，对于两个集合，分别状压记录每个质因数是否被选中，转移。状态数是 $O(2^{\dfrac{2n}{\ln n}})$ 的（$\sum_{i\le n}[i\in P]\approx \dfrac{n}{\ln n}$）。显然过不了。

又有另一个想法：为什么不能将有同样质因数的数拿出来，钦定他们其中被选中的都在同一个集合呢？但是发现可能出现一种情况，就是这些数中存在一个更小的质因数 $p$，而 $p$ 这个质因数在另一个集合也出现了。

线段树维护历史版本和做法。

首先注意到我们可以每次只保留矩形中 $x\in[0,+\infty],y\in[1,+\infty]$ 的部分，做四遍，每做一边旋转坐标系（即 $(x,y)\to(-y,x)$）再继续做。

然后考虑这个问题怎么解决。发现操作就形如矩形加，矩形查。于是考虑套路扫描线。把 $x$ 轴转化成时间，则变成了要求维护两个操作：