About Me

在无数久的 🐦咕咕咕 后一个新博客它建成了！

Ｂ口罩

太经典的题了，以前这场之后都见过两次了。

考虑钦定 $k$ 条边，然后把这 $k$ 条边删掉，再加入回去，求有多少种树。最后再二项式反演回去即可。

一个结论：有一个 $n$ 个点的森林，其中有 $k$ 个连通块，设每个连通块大小是 $d_i$ ，连边可以形成的树的个数是

$n^{k-2} \prod d_i$

考虑 $\text{prufer}$ 序，构造一个长度为 $k-2$ 的值为 $1 \sim n$ 的 $\text{prufer}$ 序。然后还原方法是把连通块看成点，把 $1 \dots k$ 写下来，每次找到最小的没有一个点在 $\text{prufer}$ 出现的连通块拿出来，和首项连边。连边的时候会找到当前连通块的一个点去连。序列长度为 $2$ 则直接分别选一个点连。而每个 $1 \dots k$ 的连通块都正好需要选一次点，所以乘上每个连通块的大小。

然后可以发现，$\prod d_i$ 本质上就是把树分成若干个连通块，每个连通块选正好一个点的方案数。所以我们可以 $dp[u][k][0/1]$ 表示当前在 $u$ 选了 $k$ 个连通块出来了，$u$ 所在连通块是否选点。树形 $dp$ 即可。

复杂度根据某经典证明是 $O(n^2)$ 的。

好题。也是一个会一半的题目，最后一半是一个没怎么见过的套路。

考虑字典序比较，常见的方法是枚举 $\text{LCP}$ 长度，然后固定下一位小于，然后剩下的随便放。

在这个题中，我们一样可以枚举 $\text{LCP}$ 的长度，比如长度为 $k$ ，也就意味着第 $p_1 \dots p_k$ 小在 $A,B$ 中是相等的，而 $A$ 的第 $p_{k+1}$ 小比 $B$ 的小。

我们考虑对两个集合分别排序后处理。对于每个 $k$ ，我们考虑 $p_{k+1}$ 处 $A$ 的取值对答案的影响，设这个位置到左边第一个已经确定的位置中间有 $l$ 个空位，这个位置到右边第一个有 $r$ 个空位，这个位置到两边的值域分别由 $L,R$ 个数，那么贡献是是

$\sum_{c \ge B_{k+1}} \binom{c-L}{l} \binom{R-c}{r}$

而这个位置一旦确定，也就是枚举到了 $k+1$ ，那么相当于是删除前后位置间这一段的贡献，加入新的两段的贡献。明显这个贡献是个组合数。

CF Edu 30

E Awards For Contestants

考虑枚举前两个奖分别有多少人获得，然后会发现合法第三种奖的数量形成了一段区间，我们可以预处理 RMQ 来快速得到第三种奖的最大 $c_3 - d_{-1}$ 这个东西。

然后复杂度就是 $O(n\log n + n^2)$ 了。

CF Edu 20 / CF803

A Maximal Binary Matrix

贪心填数，每次先填 $(i,i)$ ，然后两个两个填 $(i,i+k),(i+k,i)$ ，如果只能填一次就放到 $(i+1,i+1)$ 上。不难发现每步都最优了，满足最大字典序。

罚时是代码在 $k = 0$ 的时候会放个 $1$ 进去。

CF Edu 25 / CF825

D Suitable Replacement

+1 二分 check 时候没有注意，炸 int 了。

二分一下会拿多少个 $T$ ，然后判断一下字母个数够不够用即可。复杂度 $O(n + 26\log n)$ 。

区间赋值与区间最小值，并且下标可以达到 $10^9$ 。

遇到这种下标很大的情况，往往做法有几种，要么离散化后变成一个下标不大的情况，要么用动态开点线段树，要么用平衡树来维护连续段。

然后可以考虑利用动态开点线段树来维护这个东西。如果初始序列全是 $0$ ，那么这个东西是很好维护的，只需要区间赋值后打上标记，每个节点维护区间中的最小值。

那么在初始区间非 $0$ 的时候是否可以套用这个做法？实际上，如果可以快速查询一个区间的最小值，也就是查询一个区间在主席树节点上应是的值，那么可以用类似的做法，具体而言，在动态开点线段树新增一个点的时候，并不把初始值设置为 $0$ ，而是设置为这个区间在动态开点线段树上应该维护的值。这样这棵动态开点线段树就等价于真正对这个序列建线段树建立出来的东西了。

题目来源：

• CF316D3
• CF477D
• CF468D

A 队伍分配

考虑建反图。然后问题就变成了把这个图分成两个集合，使得这两个集合内部没有任何边，仅在集合间有边。不难发现这就是在问这是不是一个二分图。

然后由于反图不一定联通，我们相当于是把若干个二分图联通块拼起来。也就是说相当于是有很多个数 $S_R - S_L$ ，每个数的贡献是 $+x$ 或者 $-x$ ，我们需要找到一种选贡献的方法使得最后得到的数的绝对值尽量大。由于显然 $S_R - S_L$ 是 $O(n)$ 的，和也是 $O(n)$ 的，直接背包即可。由于这个背包只需要判断是否可达，也可以直接用 bitset 维护。

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 - A_2 - A_3 + A_1 - A_2 + A_3)$ ，也是 $A_1 - A_2$ 。

因此最后答案就是 $A_1 - A_2$ 。

题面

首先考虑，如果所有圆的交是一个面积而不是一个点，那么一定不优。因为可以通过调整，把一些圆从交往外拖的方式，让交的面积进行很多次贡献，答案肯定变优。所以边界的交一定是一个点。

如图，我们现在相当于是在给每个圆分配一个角度（例如圆 $C$ 的 \ang KNO），使得角度的和是 $2\pi$ 同时面积的并尽量大。

一个非常重要的观察：

$\sqrt{1 + x^2} < \sqrt{(1+x)^2}$

也就是，对于一个点，我们一定会找一个距离最近的有点的行最远的位置，如果有多个，就找是否存在一个位置最近的有点的行只有一边有点，且这里可以和这一行错开，这样可以让距离变大一些。所以，两个点实际上的距离可以变成以行号差做第一关键字，列号差做第二关键字的距离。虽然大致思路是这样，但是其实这个东西有很多细节，如果用 set 维护会显得非常难写，于是考虑线段树维护。

我们对每一个线段树的节点维护出这个节点所代表的区间内的位置，表示用这个位置到左右最近的有点的行的距离为第一个关键字，是否可以错开作为第二关键字的大小的最大的位置，同时维护这个距离。如果区间内一个点也没有或者只有一个点，那么就不维护这两个东西了，直接设 $0$ 。

首先在边上建点，于是距离就从 $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} - \sum_{i=1}^k a_{p,t_p + 1 - i}$

由于每个 $a$ 单增，所以

$a_{q,t_q + i} \ge a_{q,t_q + 1}\\ a_{p,t_p + 1 - i} \le a_{p,t_p + 1}$

所以

$\sum_{i=1}^k a_{q,t_q + i} - \sum_{i=1}^k a_{p,t_p + 1 - i} \ge a_{q,t_{q} + 1} - a_{p,t_p + 1} \ge 0$

所以我们直接设 $y = t_p$ 调整，把 $p$ 调整空即可。

考虑这个限制本质上就是限制了 $i$ 在 $a_i$ 后被选，也就是如果从 $i$ 向 $a_i$ 连边，然后就是必须先选择祖先再选择儿子的一个选择点的问题，使得最后 $\sum{iA_i}$ 尽量大。如果存在环，显然无解。

我们考虑全局最小的点，我们显然可以把它合并到它的父亲上，因为在选择它的父亲后选择这个点本身一定是最优的决策。如果一直合并，我们会得到很多的联通块。但是如何确定两个块谁先被合并？我们考虑合并 $W,V$ 的代价：

$v \to u : \sum_{v \in V} w_vp_v + \sum_{u \in W} w_u(k_u + m_v)\\ u \to v : \sum_{u \in W} w_up_u + \sum_{v \in V} w_v(k_v + m_u)\\$

考虑下面大于上面，也就是说先选择 $u$ 更优秀，那么

$\sum_{v\in V} w_um_v \le \sum_{v \in W} w_vm_u$

也就是

$\frac{\sum_{u\in W} w_u}{m_u} \le \frac{\sum_{v\in V}w_v}{m_v}$

按照这个东西贪心，拿堆维护即可。

最后所有东西都会被合并到 $0$ 上。

部分分很好做。如果任意两个展会都不在同一天举行，也就是对展会按照时间进行排序后，问题就可以转化成选择一个子序列，使得最后的权值尽量大。而且不难发现新加入一个点只和之前最后的一个点的权值有关，可以很简单地写出方程：

$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) D + w_i\} (L_j < L_i)$

拿两个 BIT 维护前后缀最大值即可。

由于没有 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$ 类点，求这两个点的最大斜率。

首先考虑如果只有一次询问怎么做。这是一个经典的问题，有一种很仙的线形做法。首先，直接对这个点前面的 $B$ 点建凸包并在凸包上二分是可以的，但是复杂度会带一个 $\log$ （而且我场上这个东西还没写挂了）。但是，sjx 教了我一种很神仙的线形做法。考虑由于 $x$ 坐标单调递增，虽然 $y$ 坐标的变化无规律，但是我们仍然可以确定，在维护凸包的队首不优于第二个值的时候，队首就可以弹掉了。这样可能会导致局部的最优值挂掉，但是一定可以找到全局的最优解。因为这个东西挂掉的情况一定是两个最优线出现了一个交叉状的东西，但是后面的一定不优于前面的。（大概也可以画图感性理解一下）。

于是我们现在得到了一个 $O(nq)$ 的做法。可以通过前 $40\%$ 的数据。然后最开始数据太水被 $n^2$ 或者 $nq$ 水到了 $70$ 甚至 $100$ 。。后来加强数据只能 $40$ 了。

AGC006

已单独开坑。

CF1083A

显然，点权减边权最大的路径上不可能存在让油量变成 $0$ 的一段。所以找点权减边权最大的路径，这个可以直接 $dp$。

AGC002

已经单独开题解写了就不放在这里了（

CF1179C

看题就会了贪心。。最后那个线段树卡了好久。。不会找最后一个大于 $0$ 的位置是不是没救了啊。。

考虑贪心，我们把 $a_i,b_i$ 放到数轴上，然后从后往前扫。扫到一个 $b_i$ 就给维护的值 -1 ，扫到 $a_i$ 就 +1 ，也就是做一个类似括号匹配的东西。我们要找到的就是第一个位置，满足这个位置的值大于 $0$ 。

所以我们直接开一棵值域上的线段树。把 $b_i$ 的修改看成删除一个 $b_i$ 再加入一个新的，也就是前缀的 $+1,-1$ 操作。然后对每个区间维护最大值，每次在线段树上如果右儿子大于 $0$ 就尽量往右走即可。复杂度 $O(q\log v)$。