官方题解 HOLD-R1

HYdroKomide · 2023-02-03 12:45:34 · 算法·理论

A - 运算

这题想起来有点难度但是代码很简单，我们一点一点分析。

• 首先：k 一定为 2，这一点比较明显，因为 gcd 函数的参数项数增加，对于其值一定是不升的（及越来越小），因此给的 m 没有用处。

40 分：

暴力枚举这个长度为 2 的区间，打擂台记录答案。

正解：

仔细想想，发现 gcd 也是骗人的，因为我们求的是 c 的最大值，所以当两个值相等时，这个答案会是最大的。可以证明，对于两个值不相等的情况，一定能构造出另一个两个值相等的情况，使得答案不变。

• 接下来我们注意到数据保证 4\le b-a，这是为什么？

注意，根据题意，a-1 是能被使用的，b+1 不行。（K_j=a 时 K_j-1 就取到了 a-1）

按位与一定与二进制有关，我们不妨将这个数化为二进制，对其后两位（模 4 的余数）进行分类讨论：

首先，若 b\mod 4=1，b 的二进制就会形如 XX01。显然，XX00 无法满足要求，因为我们无法构造第二个 XX00。

逐步枚举分析，可以得到结果可能的最大值为 b-5。

剩余情况同理：

特别地，由于题面中的特殊规定，当 b\le 5 时，答案只能为 1。许多 70 分都是遗憾在此，第一组数据为 2 1 5。

每询问时间复杂度 O(1)。

B - 重合

本题算是坑点比较多且不易察觉的题目了，正解非常容易掉进坑。

首先看思路：

对于单个序列，既然高度有起始位置，那么所有的值本身显然不重要了，只需要求出差来。可以求出每两个值之间的查分序列，也可以对每个序列的第一项求差。

由于有“分度值” 的限制，可以直接对得到的差取 gcd（最大公约数）并将差全部除以 gcd，得到一个真正的结果序列。

到这里，出现了坑点：

• 在 __gcd 中的数必须取绝对值；
• 必须特判 gcd 为 0 的情况，否则整数除以 0 会 RE。

所以得到了 10 分做法：把所有结果序列都存起来匹配，O(n^3)。

正解：对每个序列求哈希后 O(n^2) 匹配；坑点三：开 long long。单哈希容易被卡（虽然这次没有），还是建议写双哈希。

C - 池塘