加训
追踪最近的用户名外显变动记录。
最近的文章、讨论、云剪贴板与社区记录
主要任务：加训 gym，多思考。 希望这次训练小记是今年最长的一篇。 ## [qoj 10970](https://qoj.ac/contest/2071/problem/10970) > 太久没写倍增，忘完了，这里写详细一点，帮自己巩固一下。 设 $f(i)$ 为最小的满足 $j>i$ 且 $a_j>a_i$ 的 $…
学习了 jiangly 的做法，获益匪浅。 对于每一个颜色，处理出它的所有连通块（森林中的每棵树），每个连通块都进行编号。 从点 $x$ 到 $y$ 的路径，一直有颜色 $c$，等价于 $x$ 和 $y$ 都在某个编号的连通块内，而这个连通块的颜色是 $c$。进一步地，我们可以将不同连通块视作不同颜色，因为只需要回答数…
在讨论《为什么所有题解复杂度都带 log ？？？》回复：
@[chennie](luogu://user/1032348) 捕捉野生的捏宝
长为 $n$ 的序列，任意重排，本质不同的方案数为 $\frac{n!}{\Pi c_x!}$，其中 $c_x$ 为 $x$ 的个数。为什么呢？可以将其理解为：先是 $n$ 个数随便排，然后对于每个 $x$，要去除 $x$ 内部随便排的贡献，也就是除以 $c_x!$。 我们动态地维护 $res=\frac{(n+m)!…
设 $g(b, x)$ 表示数组 $b$ 中，大于 $x$ 的数的数量。则对于一个右端点 $r$，我们要求一个数 $x$ 和一个左端点 $l$，使 $x$ 不出现在 $a[l\cdots r]$ 中，且 $g(a[l\cdots r], x)$ 最大。 假如我们选取一个数 $x$，肯定有一个贪心选 $l$ 的策略，那就…
> 9 月预推免+网络赛，太忙碌，到月底才有空训练。但好在有书读了，大四课又少，狠狠 all in xcpc。 好题： - [gym 104160i](https://codeforces.com/gym/104160/problem/i) 可以放进线段树练习题单里的题，很有教学意义。 ## 二项式反演 笔记 设 $f…
设 $L_i$ 为最大的 $j x_i$ 且 $y_j>y_i$；设 $R_i$ 为最小的 $j>i$，使 $x_j>x_i$ 且 $y_j>y_i$。 先假装我们已经得出了所有的 $L_i$ 和 $R_i$。 对于一个询问 $[l, r]$ 和一个 $i$, $i$ 产生贡献仅当 $L_i y_i$。线段树二分即可。…
我们先想一个最最暴力的方法：用 $f(x,c)$ 表示连接点 $x$ 的边中，**另一点**颜色为 $c$ 的边权之和。那么每次更新节点颜色，该点的状态不需要动，但得把与它相邻的所有点都拿出来更新一下，顺便更新答案。 该怎么优化呢？如果每次更新，拿出来的点少一些就好了。 这是可以做到的，题目给的是一棵树，除根节点外，每…
首先最差情况时，拿的牌之和肯定不比对手的大，否则交换你和对手的牌，就有更差的情况了。 假设最差情况下你的牌和为 $a$，对手牌和为 $b$，$s=a+b$，$d=b-a$，那么 $a=\frac{s-d}{2}$，因此求出最小的差 $d$，就能得出最大的 $a$。 现在来看怎么通过交换让 $d$ 最小。 把一张牌拿出来…
需要一些数论的基础。 - 让 $a_i \leftarrow (a_i+k) \bmod m$，$a_i \bmod \gcd(m, k)$ 的值是不会改变的，即 $a_i$ 在 $\gcd(m, k)$ 的同余类中。 先给定一个 $k$，设 $d=\gcd(m, k)$。接下来我们来看看怎么操作序列 $a$。 既然能…
> 7 月猪蹄：[P13094](https://www.luogu.com.cn/problem/P13094) > > 拆解为两个经典的二维偏序问题，很有学习价值。 > > 8 月猪蹄：[cf 2131h](https://codeforces.com/contest/2131/problem/H) > > 莫比乌…
一个非常经典的模型：长为 $n$ 的序列，有多少个子段满足和为 $s$？ 我们转化一下，做个前缀和，现在求有多少组 $(l, r)$ 满足 $pre_r - pre_{l-1} = s$。再转换一下，对于每个位置 $r$，求它之前之前有多少个 $i$ 满足 $pre_{i-1}=pre_r-s$。 那么维护 $pre_…
> 思路来自 [capps 老师](https://codeforces.com/profile/Capps)。 要找 $f(l, x) + f(x, r)$ 的最小值，不妨分为两部分处理。 - 首先是 $l$ 和 $r$ 的最长公共前缀，因为 $x$ 的选取要在两者之间，因此这部分不得不产生贡献。 - 然后是后面的部…
这届篮球杯比较有意思的题。 要求一个 $\prod_{i=1}^n G_i$，其中 $G_i=G_{i-1}G_{i-2}$，$G_1=2$，$G_2=3$。那么所有的 $G_i$ 和 $\prod G_i$，都可以表示成 $G_1^p G_2^q$ 的形式。 设 $G_i=G_1^{a_i} G_2^{b_i}$，由…
赛时还有一个信息补充，没有写在题面里：每一个土地至多只能平整一次——这个信息就是在告诉我们，对每个高度统计答案，最后取最小值即可。 实现不用多说：维护一个 `lst[]` 记录每个数上一次出现的位置，以及以每个数作为最终高度进行平整的花费 `cost[]`。从前到后扫过去就行了，复杂度是线性的。 需要注意的是，$\te…
区间翻转，区间询问，很容易想到懒标记线段树，维护一个区间长度和区间正面的个数就做出来了。 但这里有隔一个翻一个，和隔两个翻一个，要怎么办？ 先想，如果只有隔一个翻一个的操作，好像可以转化为对奇偶位置的更新，开两个线段树，一个记录奇数位置，一个记录偶数位置就行了。 进一步地，如果只有隔两个翻一个的操作，同样的思路，我们可…
对于每个操作，可以不做，或者选一个位置进行替换。最后需要整个字符串字典序最小。 换个角度想，我们可以先把所有操作离线下来。然后从前到后，对每个位置，找能让结果变优的操作，进行匹配。 分为三类： - $s_i=a$，已经是最优了，不用管； - $s_i=b$，有两种途径变优：$b\rightarrow a$ 和 $b\r…
在讨论《这题能推广到任意 k 吗》回复：
@[Genius_Star](luogu://user/979266) 我表达错了，本来想说能推广到任意模数吗
在加边的时候就要想着怎么判断它本身就不合逻辑的情况，比如 $a>b, b \leq a$，也要判断合理但强于的情况 $a>b, a\geq b$。 题解区一些老题解是过不了的。
在讨论《趣事一则》回复：
这题能不能用普通莫队做呀
用了一个错误做法，加了一些卡常手段之后竟然能卡过，别人提醒我了才发现。 简单来说，我使用普通莫队，对值域开了一个链表来维护区间中值的下标，再用一个 `dis[]` 数组存结果出现的次数。以我写的 `add` 函数为例，可以很容易发现端倪。 ```cpp auto add = [&](int p) { int x = a…
如果有代码实现上的疑问，可以翻看笔者的提交记录，也可以私信联系。 --- 每个月会选出个人最喜欢的题目——猪蹄奖。 > 5 月猪蹄奖：[cf 2104g](https://codeforces.com/contest/2104/problem/G) > > 非常综合的题目，可撤销并查集 + 线段树分治只是一个维护的途径…
先不考虑询问，就给你两个静态的图 $A$ 和 $B$，怎么求添加的最少边数，使 $A$ 能包含 $B$ 呢？ 我们把 $A$ 和 $B$ 并起来，令 $C=A\cup B$，即 $A$ 如果要包含 $B$，就“至少”得长成 $C$ 的样子。则我们要的答案就是 $A$ 与 $C$ 的连通块个数的差（一条边能减少一个连通块…
提供一个比较无脑的做法。 对于符合要求的排列，它不能只有某一位符合要求，而是要从最开始连续地符合 $p_i=i$。 最暴力地想，就是对每个排列 $a_i$，从第一列开始枚举所有排列，不断维护从头开始就符合要求的序号，直到没有符合要求的，或者走到了最后一列。 换句话说，对于排列 $a_i$ 的第 $j$ 列，记 $x=a…
首先有一个重要的性质——翻转区间的前面和后面是不变的。因为翻转不会改变各操作的次数。那么再考虑翻转区间中的点有什么变化。 一个在 $(a_1, b_1)$ 和 $(a_2, b_2)$ 区间中的点 $(x, y)$，意味着操作向量 $\vec o =(x-a_1, y-b_1)$，翻过去就是 $(a_2-x+a_1,…
对于每个圆，求过原点与圆的两条切线的斜率，将斜率转化成角度，那么这两个角度之间是不能选择的。 于是这题就能转化成：在一个范围内有很多个线段，求没有被线段覆盖的总长度。扫描线即可。 关于如何求过原点与圆的切线的斜率，我赛时的方法是往上往下用二分找，到圆心距离等于半径的斜率。可能有更快捷的方法。 ```cpp #inclu…
如果时间的范围很小，是非常好做的，我们直接遍历每个时刻，模拟即可。 现在时间的范围非常大，不能遍历每个时刻了，我们用扫描线遍历每个“事件”——每个用户开始或退出传输——的时刻。 想想两个时刻之间会发生什么。**参与传输的人数不会变**；如果有传输的行为，那么传输速度就会逐渐增加，直到大于带宽，然后减半，再逐渐增加……如…
在讨论《为什么？》回复：
bfs 保证了复杂度，因为每个点只会入队一次@[noiiloveyou](luogu://user/1492018)