AT_abc365 补题报告【F】

zhangjinxuan

前言

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

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

---

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

这次的题目真的有点难，所以只有明天早上发布。

问题 C

求最大的 $x$ 使得 $\sum_{i=1}^{n} \min(x, a_i) \le M$，不存在最大输出 Inf。

显然 $\sum_{i=1}^{n} \min(x, a_i)$ 具有单调性，所以二分即可。判 Inf 直接看 $\sum A_i$ 与 $M$ 的大小关系即可。

场切：https://atcoder.jp/contests/abc365/submissions/56243664

问题 D

你玩石头剪刀布，你知道了在所有局中对手的出拳顺序，如果你在某一局获胜你将获得 $1$ RMB，平局获得 $0$ RMB，失败则获得 $-10^{100}$ RMB，问相邻两次出拳不同情况下获得的最多 RMB。

只要记录目前的局数和上一次出拳的结果是什么，就可以进行动态规划。

场切：https://atcoder.jp/contests/abc365/submissions/56256312

问题 E

求 $A$ 所有区间的异或和。

做一遍前缀异或和就可以转换成一个序列两两元素异或之和，于是就可以统计第 $i$ 位二进制位 $1,0$ 的出现次数，在统计答案的时候枚举每一个数的同时枚举 $i$，如果对应数字的第 $i$ 位是 $0$ 就把统计的 $1$ 的个数乘 $2^{i}$ 加入贡献，是 $1$ 也同理。

场切：https://atcoder.jp/contests/abc365/submissions/56256312

问题 F

二维平面网格，第 $i$ 列的 $[L_i, U_i]$ 区间的网格可以通行，$Q$ 次询问两个点不经过障碍可以得到的最小移动步数。

改不了一点。

问题 G

有 $N$ 组区间，第 $i$ 组区间有 $m_i$ 个区间，其中的第 $j$ 个区间是 $[L_{i,j}, R_{i,j}]$。$Q$ 次询问求第 $A,B$ 个区间的交集大小。

$\sum M \le 2\times10^{5}$

考虑使用根号分治，指定一个值 $B$，那么对于每一个区间数量大于 $B$ 的就可以直接用它来计算这个对于所有答案的贡献，显然 $O(N)$ 可以解决，并且只有 $O(\frac{N}{C})$ 种。

剩下的区间就都是区间数量小于 $B$ 的，暴力判断即可。取 $B=\sqrt{N}$ 即可，使用记忆化答案以获得更优秀的常数。

赛后：https://atcoder.jp/contests/abc365/submissions/56324742

总结教训

根号分治的大块考虑求所有，小块考虑单独求。

柿子饼同学

请务必放进心之碎片计划口牙!

想吃虾尾

1