AT_abc366 补题报告【G】

zhangjinxuan

前言

我感觉我写这些内容对自己有很大益处，尤其是考试补题，因为补题不仅仅是一个“能多几个 AC”的作用，还是一个吸取教训、总结、提升自己的一个重要途径。从某种意义上来说这是写给自己的。

每一场（方便公开）的比赛如果改完题目（达到能力上限）就会来总结。由于 lz 水平有限，所以一些帖子的学术性问题欢迎在本贴讨论指出错误。

---

ABC 的比赛就从 C 开始补起吧，比赛题目：https://atcoder.jp/contests/abc366/tasks

问题 C

你有一个空袋子，对其处理 $Q$ 个操作，种类如下：

$1 x$ ：将一个写有整数 $x$ 的球放入袋子中。
$2 x$ ：从袋子中取出一个写有整数 $x$ 的球并丢弃。当给出此查询时，保证袋子中有一个写有整数 $x$ 的球。
$3$ : 打印袋中写有不同整数的球的个数。

模拟即可，因为 $x$ 的值域很小，所以可以记录一个桶表示数字 $x$ 的出现次数，如果是 $1$ 操作且桶中无数就对答案加一，如果是 $2$ 操作且桶中只有一个数就答案减一即可。

场切：https://atcoder.jp/contests/abc366/submissions/56516401

问题 D

题目大意：三维前缀和板子。

三维的前缀和和二维的前缀和类似，直接容斥做即可。

场切：https://atcoder.jp/contests/abc366/submissions/56525330

问题 E

给定 $N$ 个整数点对，第 $i$ 个点对是 $(a_i, b_i)$，求出整数点对 $(x,y)$ 满足 $\displaystyle \sum_{i=1}^N (|x-x_i|+|y-y_i|) \leq D$ 的数量。

显然括号可以拆，于是贡献就被拆开了。

先来考虑给定一个数字 $x$ 的情况下，怎么求出他对于一个数组所有元素的差绝对值之和，静态的。

排序之后就可以二分了，假设二分出来的位置是 $p$，那么对于 $1\sim p$ 的位置，$x$ 都比他们大，就转换成了 $x-a_i$，对于 $p+1\sim n$ 的位置同理，预处理前缀和即可。

因此就可以先预处理出所有有效的 $y$ 他们对于 $b$ 数组的所有元素的差绝对值之和，并计入一个桶 $cnt$ 中，第 $i$ 个内容表示这个答案为 $i$ 的 $y$ 的个数。

于是再枚举 $x$，再求解一遍这个东西，假设得到了 $tmp$ 这个结果，那么答案的贡献就会增加 $cnt$ 中 $0\sim D-tmp$ 的所有内容的值。

对 $cnt$ 前缀和就可以很快求出来了。

问题 F

有 $N$ 个函数，第 $i$ 个函数是 $f_i(x) = a_i x + b_i$，找到一个元素两两不桶，长度为 $K$ 的序列 $p = (p_1, p_2, \ldots, p_K)$，使得 $f_{p_1}(f_{p_2}(\ldots f_{p_K}(1) \ldots ))$ 的值最大。

歪解：

如果有一条 $p_i < p_{i+1}$ 的限制，那么动态规划的做法显然，$dp_{i,k}$ 表示后 $i$ 个函数用了 $k$ 个的最多函数值就可以做了。显然是假的，因此考虑排序之后（四种不同的比较方式）再来做一遍随机化，能在赛场上过。

场切：https://atcoder.jp/contests/abc366/submissions/56550368

正解：

歪解之所以需要随机化的原因是调换顺序后可能得到更优解，于是考虑构造一种排序方案，使得排序之后再调换顺序不会得到更优解。

考虑 $f_i(f_j(x))$ 和 $f_j(f_i(x))$ 决定大小关系的充分条件是什么。

展开如下：       

$$f_i(f_j(x)) = a_i a_j x + a_i b_j +b_i\\
f_j(f_i(x)) = a_j a_i x + a_j b_i + b_j$$

发现两边都有一个 $a_i a_j x$，消掉就与 $x$ 无关了，只需要比较 $a_i b_j +b_i$ 和 $ a_j b_i + b_j$ 的大小即可。

这时候再做 dp 就一定正确了。注意不要写错式子。

赛后：https://atcoder.jp/contests/abc366/submissions/56576859


总结教训

sfqxx

总结教训：

空

小甲鱼的二师兄

又进步了！