A Power看到这题数据随机就可以想到可不可以乱搞。我们考虑从 $P-1$ 开始向下枚举，每次用 BSGS 解出这个数第一次出现的位置，如果这个数小于之前的最小位置，我们就用它来代替最小位置继续做。然后考虑设置一个阈值 $B$ ，如果当前的数已经小于了 $B$ 就停止这个做法直接枚举前 $B$ 个数。 然后写出来试了试发现只能过 $10^7$ 。冷静分析一波复杂度，会发现如果 $B$ 控制合理大概是 $O(P^{\frac 3 4})$ 的东西。具体来说，随机情况下如果我们找到了一个比当前最优 ...

任意模数下的积和式并没有多项式解法。考虑积和式的组合意义，$i,A_i$ 都是互不相同的，可以看作是二分图的一个完美匹配。因此任意矩阵的积和式就是 $A_{x,y}$ 看作左侧 $x$ 右侧 $y$ 之间的边权后所有完美匹配边权的积的和。 如果我们给所有 $A_{x,y} \neq 1$ 拆成 $1,A_{x,y} - 1$ 这两个东西，然后所有边上都有了一个长度为 $1$ 的边。于是现在就可以不考虑所有长度为 $1$ 的边了。我们求出除开边权为 $1$ 的边后的任意一个二分图匹配，那么这个匹配 ...

以前做的，没发博客。 如果两个串的 endpos 等价类相同，显然把任意一个放进 $s_i$ 里面是一样的效果。 于是我们可以建出 SAM 的 fail 树，考虑做 $dp[u]$ 表示当前在树上的 $u$ 节点，同时我们最后一次选择的是这个点上的最长串，最多可以选出的序列长度。 显然，我们选择一个深度更大的位置比选择一个深度更小的位置作为序列的上一个位置好。因为深度更小的位置一定在深度更大的位置的所有 endpos 中出现过。所以我们可以考虑找到最深的一个位置，满足这个位置在当前串中出现过至少 ...

Ｂ口罩太经典的题了，以前这场之后都见过两次了。 考虑钦定 $k$ 条边，然后把这 $k$ 条边删掉，再加入回去，求有多少种树。最后再二项式反演回去即可。 一个结论：有一个 $n$ 个点的森林，其中有 $k$ 个连通块，设每个连通块大小是 $d_i$ ，连边可以形成的树的个数是 n^{k-2} \prod d_i考虑 $\text{prufer}$ 序，构造一个长度为 $k-2$ 的值为 $1 \sim n$ 的 $\text{prufer}$ 序。然后还原方法是把连通块看成点，把 $1 \do ...

好题。也是一个会一半的题目，最后一半是一个没怎么见过的套路。 考虑字典序比较，常见的方法是枚举 $\text{LCP}$ 长度，然后固定下一位小于，然后剩下的随便放。 在这个题中，我们一样可以枚举 $\text{LCP}$ 的长度，比如长度为 $k$ ，也就意味着第 $p_1 \dots p_k$ 小在 $A,B$ 中是相等的，而 $A$ 的第 $p_{k+1}$ 小比 $B$ 的小。 我们考虑对两个集合分别排序后处理。对于每个 $k$ ，我们考虑 $p_{k+1}$ 处 $A$ 的取值对答案的 ...

CF Edu 30E Awards For Contestants考虑枚举前两个奖分别有多少人获得，然后会发现合法第三种奖的数量形成了一段区间，我们可以预处理 RMQ 来快速得到第三种奖的最大 $c_3 - d_{-1}$ 这个东西。 然后复杂度就是 $O(n\log n + n^2)$ 了。 F Forbidden Indices套路题。 有两种做法。首先最简单的就是建一棵 $\text{SAM}$ 然后插入 $1$ 的节点的时候把 $siz$ 设置为 $0$ ，否则为 $1$ ，然后直接算出 ...

CF Edu 20 / CF803A Maximal Binary Matrix贪心填数，每次先填 $(i,i)$ ，然后两个两个填 $(i,i+k),(i+k,i)$ ，如果只能填一次就放到 $(i+1,i+1)$ 上。不难发现每步都最优了，满足最大字典序。 罚时是代码在 $k = 0$ 的时候会放个 $1$ 进去。 B Distances to Zero$L[i],R[i]$ 分别表示左右最近的 $0$ ，然后转移显然讨论下这个位置是否为 $0$ 即可。 C Maximal GCD如果最终整 ...

CF Edu 25 / CF825D Suitable Replacement+1 二分 check 时候没有注意，炸 int 了。 二分一下会拿多少个 $T$ ，然后判断一下字母个数够不够用即可。复杂度 $O(n + 26\log n)$ 。 E Minimal Labels1A 以前的 Edu round 总是可以做到做过的套路题欸。 字典序最小的拓扑序是在 菜肴制作 见过。做法是建反图，然后每次拿最大的点放当前能放的最大标记。 考虑证明，最大的标记肯定出现在出度为 $0$ 的点里面。考虑出 ...

区间赋值与区间最小值，并且下标可以达到 $10^9$ 。 遇到这种下标很大的情况，往往做法有几种，要么离散化后变成一个下标不大的情况，要么用动态开点线段树，要么用平衡树来维护连续段。 然后可以考虑利用动态开点线段树来维护这个东西。如果初始序列全是 $0$ ，那么这个东西是很好维护的，只需要区间赋值后打上标记，每个节点维护区间中的最小值。 那么在初始区间非 $0$ 的时候是否可以套用这个做法？实际上，如果可以快速查询一个区间的最小值，也就是查询一个区间在主席树节点上应是的值，那么可以用类似的做法， ...

题目来源： CF316D3 CF477D CF468D A 队伍分配考虑建反图。然后问题就变成了把这个图分成两个集合，使得这两个集合内部没有任何边，仅在集合间有边。不难发现这就是在问这是不是一个二分图。 然后由于反图不一定联通，我们相当于是把若干个二分图联通块拼起来。也就是说相当于是有很多个数 $S_R - S_L$ ，每个数的贡献是 $+x$ 或者 $-x$ ，我们需要找到一种选贡献的方法使得最后得到的数的绝对值尽量大。由于显然 $S_R - S_L$ 是 $O(n)$ 的，和也是 $O( ...

A 小鸣的疑惑曾经做过。 考虑归纳证明。假设我们已经得到了前 $n-1$ 个数得到的答案是 $A_1 - A_2$ 。现在考虑 $n$ 个数的情况。 如果合并的两个数不包含 $A_1,A_2$ ，那么就得到了一个子问题，答案是 $A_1 - A_2$ 。 如果合并的两个数包含 $A_1,A_2$ ，有两种情况，要么一步变成了 $A_1 - A_2 , A_3$ ，要么变成了 $A_1,A_2 - A_3$ 。出现这两种情况的概率是一样的，于是这两种情况的期望值就是 $\frac 1 2(A_1 ...

CF1307F Cow and Vacation首先在边上建点，于是距离就从 $k$ 变成了 $2k$。 距离变成偶数后，对于两个位置，它们可达的条件就是从其中一个走 $k$ 另一个走 $k$ 能到的点有交。 首先考虑以每个点作为中转点可以到达的点。也就是只要某一步到达了这个点就一定可以通过转驿站来走到的点。做法是把所有驿站加入队列距离设置为 $0$ 进行一次 bfs 。考虑当我们从一个点到达另一个已经访问过的点，那么这两个点所对应的联通块可以直接合并，因为总是可以通过这两个点的初始驿站互相到达 ...

后面是某 $dp$ 讲义的习题，前面是前两天讲的题。 APIO 2018 New Home 新家考虑按照年份枚举一下，相当于在 $l_i$ 加入 $i$ ，在 $r_i + 1$ 删除 $i$ 。然后询问就是二分一下答案，考虑 $[a-m,a+m]$ 是否存在所有类型的商店，也就是是否存在某个 $(a+m,\infin)$ 的数的 $pre$ 小于 $a-m$ ，是否存在某个 $(-\infin ,a-m)$ 的数的 $nxt$ 大于 $a+m$ 。 线段树维护，在线段树叶子结点开个 set 即 ...

题面 首先考虑，如果所有圆的交是一个面积而不是一个点，那么一定不优。因为可以通过调整，把一些圆从交往外拖的方式，让交的面积进行很多次贡献，答案肯定变优。所以边界的交一定是一个点。 如图，我们现在相当于是在给每个圆分配一个角度（例如圆 $C$ 的 $\ang KNO$），使得角度的和是 $2\pi$ 同时面积的并尽量大。 对于同一个圆来说，如果半径和角度都确定，显然当 $ON,KN$ 相等的时候也就是对称的时候面积取到最值。这种情况下，也就是面积的上界是 \begin{aligned} S(\ ...

一个非常重要的观察： \sqrt{1 + x^2} < \sqrt{(1+x)^2}也就是，对于一个点，我们一定会找一个距离最近的有点的行最远的位置，如果有多个，就找是否存在一个位置最近的有点的行只有一边有点，且这里可以和这一行错开，这样可以让距离变大一些。所以，两个点实际上的距离可以变成以行号差做第一关键字，列号差做第二关键字的距离。虽然大致思路是这样，但是其实这个东西有很多细节，如果用 set 维护会显得非常难写，于是考虑线段树维护。 我们对每一个线段树的节点维护出这个节点所代表的区间内的 ...

首先在边上建点，于是距离就从 $k$ 变成了 $2k$。 距离变成偶数后，对于两个位置，它们可达的条件就是从其中一个走 $k$ 另一个走 $k$ 能到的点有交。 首先考虑以每个点作为中转点可以到达的点。也就是只要某一步到达了这个点就一定可以通过转驿站来走到的点。做法是把所有驿站加入队列距离设置为 $0$ 进行一次 bfs 。考虑当我们从一个点到达另一个已经访问过的点，那么这两个点所对应的联通块可以直接合并，因为总是可以通过这两个点的初始驿站互相到达。如果当前点与最近的驿站的距离已经超过了 $k$ ...

感觉这个结论题好神仙啊，开始还以为是 $\max,+$ 凸包之类的东西没想到是结论题。。 一个结论：对于一个选择 $k$ 个数的最优状态，一定不存在多于 $1$ 个序列被选了一部分。 我们设有两个序列选了一部分 $a_p,a_q$ ，同时设两个序列分别选择了 $t_p,t_q$ ，我们可以设 $a_{p,t_p+1} \le a_{q,t_q+1}$ 。 然后考虑，如果我们调整 $k$ 个数从 $p$ 到 $q$ 内，于是更改量就是 \sum_{i=1}^k a_{q,t_q + i} - \ ...

考虑这个限制本质上就是限制了 $i$ 在 $a_i$ 后被选，也就是如果从 $i$ 向 $a_i$ 连边，然后就是必须先选择祖先再选择儿子的一个选择点的问题，使得最后 $\sum{iA_i}$ 尽量大。如果存在环，显然无解。 我们考虑全局最小的点，我们显然可以把它合并到它的父亲上，因为在选择它的父亲后选择这个点本身一定是最优的决策。如果一直合并，我们会得到很多的联通块。但是如何确定两个块谁先被合并？我们考虑合并 $W,V$ 的代价： v \to u : \sum_{v \in V} w_vp_ ...

部分分很好做。如果任意两个展会都不在同一天举行，也就是对展会按照时间进行排序后，问题就可以转化成选择一个子序列，使得最后的权值尽量大。而且不难发现新加入一个点只和之前最后的一个点的权值有关，可以很简单地写出方程： f[i] = \max\{f[j] - cost(j,i) + w_i\}然后可以分成从上游来还是从下游来： f[i] = \max\{f[j] - (L_j - L_i) U + w_i\} (L_j > L_i)\\ f[i] = \max\{f[j] - (L_i - L_j ...

由于没有 OJ 只能写题意了 题意： 给定一个长度为 $n$ 的序列，求区间 $[l,r]$ 内的 $a < b$ 满足 $\frac{\sum_{i=a}^b A_i}{b-a}$ 最大 也就是区间和除以区间长度减 $1$ 尽量小。 显然可以考虑前缀和，然后就是 $\frac{S_b - S_{a-1}}{b-a}$ 。我们考虑每个点维护两类点，一类 $A(a,S_a)$ 一类 $B(b,S_{b-1})$。 然后问题就转化成了区间内选择一个靠前的 $B$ 类点，一个靠后的 $A$ ...

AGC006已单独开坑。 CF1083A显然，点权减边权最大的路径上不可能存在让油量变成 $0$ 的一段。所以找点权减边权最大的路径，这个可以直接 $dp$。 CF1083B首先，我们把 $s,t$ 都直接拿一遍肯定是前两步的最优操作。相当于除了 $s,t$ 的 $lcp$ 其他部分都拿了两遍。 然后可以直接把 $lcp$ 给丢掉了。现在，对于 $s$ 的每一个 $0$ 位置，我们如果在这里放 $1$ ，我们可以有 $1$ 个贡献为 $n-i+1$ 的串，一个贡献为 $n-i$ 的串，两个贡献为 ...

AGC002已经单独开题解写了就不放在这里了（ CF1179C看题就会了贪心。。最后那个线段树卡了好久。。不会找最后一个大于 $0$ 的位置是不是没救了啊。。 考虑贪心，我们把 $a_i,b_i$ 放到数轴上，然后从后往前扫。扫到一个 $b_i$ 就给维护的值 -1 ，扫到 $a_i$ 就 +1 ，也就是做一个类似括号匹配的东西。我们要找到的就是第一个位置，满足这个位置的值大于 $0$ 。 所以我们直接开一棵值域上的线段树。把 $b_i$ 的修改看成删除一个 $b_i$ 再加入一个新的，也就是前 ...

AGC001F已单独写题解就不粘过来了。 Gym101806T根据某知名贪心，先给 $L$ 加上 $D$ ，然后按照 $L$ 排序，可以得到一个正确的顺序，最后答案的序列一定是在这个顺序下选取的。 相当于我们需要选择一个最长子序列，满足这个子序列任意一段前缀的和小于等于这个位置的 $L$ 。 这个问题类似于 LIS 。有一种直接贪心的做法。我们考虑对当前位置，维护出满足当前位置以及之前所有位置的限制的的最长的子序列，且满足 $\sum D$ 尽量小。 我们用堆维护当前子序列中所有的 $D$ 。每 ...

AGC006D非常有意思的一个题。 直接做复杂度是 $O(n^2)$ 的而且看不出什么优化空间。 “中位数”的题往往和二分答案有关，因为这样可以转化成区间内 $0/1$ 的个数。这个题，可以先二分答案，设二分出来的值是 $x$ ，我们尝试判断第一层的数是否 $\le x$ 。我们把所有 $\le x$ 的数设置为 $0$ ，把剩下的数设置为 $1$ 。不难发现这个序列在进行操作后得到的序列的 $01$ 含义是不变的。现在我们转化成了一个 $01$ 序列进行操作，最后堆顶的数是 $0$ 还是 $1 ...

A STring操作这么多次。。显然能消的 ST 都没了变成了 TTT...TSSS...S 。不难发现其实就是括号匹配，直接拿栈匹配就行了。 B Minimum Sum按最小值来分治即可。每次贡献就是左右两端长度加 $1$ 的乘积。 复杂度 $O(n\log n)$，需要预处理 ST 表。 C Tree Restoring考虑这 $n$ 个数字中最大的，必然是直径长度。然后我们先把直径画出来： 不难发现，对于 $[\lceil\frac d 2\rceil,d]$ 的长度我们至少的有两个点， ...

神仙题。 考虑一个 $n$ 个点的树的情况怎么处理。 首先进行一次转化，树是一个二分图，于是就进行一次二分图染色。不难发现新图上两端颜色不同当且仅当原图两端颜色相同，所以我们可以把操作从同色翻转变成异色反转，也就是我们进行的操作其实就是在新图上移动黑色点。抄一个官方题解的图： 然后问题就变成了一棵树，有一些位置是黑色点，一些位置是白色点，我们每次要移动一个黑色点到相邻的白色点，最后要让所有黑色点归位。 对于树的情况，如果黑点白点数量不同，必然无解。 这是一个经典模型，首先答案是有下界的。我们随 ...

A Wanna go back home判一下 S,N ，W,E 是否同时存在或者同时不存在即可。 B Simplified mahjong考虑一种贪心，从 $1$ 到 $n$ 逐个操作，我们假定已经把 $1\sim n-1$ 给操作完了，并且 $1\sim n-1$ 的位置如果剩余奇数就会留下 $1$ 。对于 $n$ 这个位置，可以贪心一下，尽量和前面的剩下的那个先配对。如果这个位置是奇数，那么配对了必然是优秀的。否则，如果这个位置是偶数，那么这个位置本身就变成了奇数，只能往后操作，这里相当于 ...

AGC002C找到一个结两边和不小于 $L$ 然后把剩下的依次删除即可。如果不存在显然无解。 AGC002 D首先一种不动脑子的做法，直接建 kruskal 重构树然后二分 + 倍增跳即可。复杂度 $O(n\log^2 n)$ 。 然后，通过整体二分 + 可撤销并查集也可以做。但是可撤销并查集无法路径压缩，所以也是 $O(n\log^2 n)$。 然后其实是可以做到单 $\log$ 的。 如果我们按照 bfs 的顺序来做整体二分。如果当前加入的边超过了我们期望的边，那么就删掉所有边重做。不难发现 ...

首先考虑求出原排列的逆置换，设为 $Q$ ，于是交换就变成了如果 $|Q_i - Q_{i+1}| < k$ 那么可以交换相邻的两个元素。 于是，对于任意 $i,j$ 如果满足 $|Q_i - Q_j| < k$ 那么他们的相对顺序一定无法改变。 而且可以证明，如果两个排列 $Q,P$ 中所有元素的相对位置的关系是一样的，那么一定可以从 $Q$ 移到 $P$ 。考虑这种情况下的一次移动就可以让逆序减少 $1$ 。有限步的操作后一定可以让 $Q$ 成为 $P$ （画一下发现很对）。 于 ...

题目 首先嘛，这个 $b$ 放到这里就是吓人的，明显这个式子就是 \sum_{i=0}^n a^i \binom{nk}{ik}考虑 $a=1$ 怎么做，也就是 \sum_{i=0}^n \binom{nk}{ik}这个东西可以单位根反演，但是不难发现也可以循环卷积来做。也就是 (x+1)^{nk}在长度为 $k$ 的情况下做循环卷积的 $[x^0]$ 系数。 这个东西有一个优美的结论：在长度为 $k$ 的情况下做循环卷积等价于 [x^0] (x+1)^{nk} \pmod{x^k - ...