板刷2019~？的省选题 - 洛谷保存站

看看会不会咕/cf

除非极度不可做题，否则一般都是会写的。

每个题限时思考 $30\min$，如果有想法可以延长；然后自己写/看题解。

## BJOI2019

### P5322 排兵布阵

比较水的，略。

### P5323 光线

考虑记 $f_i$ 为直接穿过第 $i$ 面镜子的光有多少，记 $g_i$ 为从第 $i$ 面镜子反射回来的光有多少。

易得：

$$
\begin{aligned}
 f_i & = f_{i-1}a_i\sum\limits_{k=0}^{\infty} (g_{i-1}b_i)^k\\
 g_i & = b_i+g_{i-1}a_i^2\sum\limits_{k=0}^{\infty} (g_{i-1}b_i)^k
\end{aligned}
$$

核心思想是一道光从上面打下了和从下面打上来，一面镜子能射回去的光是相同的。

然后就做完了。

### P5324 删数

主要是之前做过其弱化版 AGC17C，所以一上来就有想法。

[My AGC17C solution](https://www.luogu.com.cn/blog/lvsiji/solution-at-agc017-c)。

首先观察到的是，这个题和 AGC17C 唯一的区别就是多了全局 $\pm 1$ 的操作，所以很自然的会去想到维护一个 $\Delta$ 去描述这个东西。

然后 update 操作就变成了 delete 掉 $a_p$ 再 insert 进去 $x+\Delta$，然后最后就是查询 $n-\text{sum of }(1+\Delta,n+\Delta)$ 的值。

看起来很对，但是有一种特殊情况：

![](https://s11.ax1x.com/2024/01/12/pFCXDII.png)

如图，我们的合法区间边界 $[1+\Delta,n+\Delta]$ 向左挪了一点（黑->蓝），然后红线（对应一条线段 $(x-cnt_x+1)\text{-}(x)$）的端点到了边框之外，这时候显然整个红线我们都要 change 掉（因为不满足 $a_i=n$ 了），但是事实上根据我们上面的做法还是会将其统计进去。

~~所以我们上面讲了一堆是个假做法。~~

考虑如何处理，一个比较自然的想法是，每次边框左移时，就把红线 delete 掉；右移时再把红线 insert 进去。

那么这个相对于要支持下面的一个数据结构：

- 区间修，不会出现负数，查询一个区间内有多少个 $0$。

考虑到如果一个区间内出现了零，则其必然时整个区间的最小值（因为值非负），所以我们维护一个区间的最小值和最小值出现个数即可，这个是简单的。

然后就做完了，复杂度 $\Theta((n+q)\log{n})$。

### P5319 奥术神杖

很套路的题。

考虑二分，得到：$\sqrt[c]{maigc}\ge x\Leftrightarrow maigc\ge x^c \Leftrightarrow\prod\limits_{i=1}^c v_i\ge x^c$。

然后时应该非常套路的东西：$\log{ab}=\log{a}+\log{b}$。

得：$\log \prod\limits_{i=1}^c v_i\ge c\log{x}\Leftrightarrow\sum\limits_{i=1}^c(\log{v_i}-\log{x})\ge 0$。

则每一次匹配成功会得到 $\log{v_i}-\log{x}$ 得代价，看看最后代价之和是否 $\ge 0$ 即可。

考虑建 AC 自动机，然后 dp，然后就做完了。

复杂度是 $\Theta(ns|\Sigma|\log{\frac{V}{\epsilon}})$，有点卡常。

### P5320 勘破神机

先鸽一下，不太想写。

## 	GXOI/GZOI2019

### P5304 旅行者

很典的 trick：$\text{path}(s,t)=\text{path}(s,u)+\text{edge}(u,v)+\text{path}(v,t)=\text{path}(s,t)=\text{path}(s,u)+\text{edge}(u,v)+\text{path}^{-1}(t,v)$。

正反图都跑一下多源最短路，再枚举一条边，把他们接起来即可。

复杂度是 $\Theta(m\log{n})$。

### P5305 旧词

考虑 $\text{depth}_{\text{lca}(u,v)}$ 的另一种求法：我们将链 $1-u$ 的节点全部标记成 $1$，然后在查询链 $1-v$ 上的权值和。

那么当 $k=1$ 时这样子扫描线一下，扫到一个点就链加，扫到一个询问就链求和，然后就做完了。

至于 $k>1$ 时就相当于区间加 $1$ 变成了区间加上对应位置的 $\text{depth}^k-(\text{depth}-1)^k$（因为这样子 $u$ 和 $fa_u$ 的贡献会消掉，最终只留下 $\text{depth}_{\max}^k$）；由于每个位置每次加的数是相同的，所以提前算一下前缀和，维护每个位置被加了多少次即可，然后就和 $k=1$ 一样了。

树剖维护，复杂度 $\Theta((n+q)\log^2{n})$。

### P5300 与或和

感觉很一眼的题。

显然地按位考虑，那么就变成了 $01$ 矩阵的情况。

对于第一问我们对于每个点向上求出可以拓展多少，那么对于每一行就是给定一个直方图，计数其矩形数量，单调栈即可。

具体来说，就是每加进一个数，钦定其成为右下角，看看有多少左上角满足条件，则维护一个单调递增的单调栈，考虑每次 ban 掉栈顶后的影响。

第二问就是把 $01$ 取反然后再拿总答案减去即可。

复杂度 $\Theta(n^2\log{V})$。

### P5303 逼死强迫症

这是省选题？这是省选题？这是省选题？

没有营养的矩阵乘法。

### P5301 宝牌一大堆

摆。

正在渲染内容...