20联赛集训day13 题解
A. 异或考虑第 $i$ 位的贡献，发现每 $2^i$ 个数才会变化一次，所以答案是 $\sum_{i \geq 0} \lfloor\frac{n}{2^i}\rfloor $。考场上降智了，写了个枚举前缀卡到哪里算剩余贡献的垃圾做法。。#include <bits/stdc++.h> #define fi first #define se second #define db...
A. 异或考虑第 $i$ 位的贡献，发现每 $2^i$ 个数才会变化一次，所以答案是 $\sum_{i \geq 0} \lfloor\frac{n}{2^i}\rfloor $。考场上降智了，写了个枚举前缀卡到哪里算剩余贡献的垃圾做法。。#include <bits/stdc++.h> #define fi first #define se second #define db...
A做法一：答案一定是相邻两个的差的最小值。考虑反证法：如果 $[l,r](l+1 < r)$ 是答案，那么中间一定能取到一段小于等于平均数的。做法二：二分答案。首先答案是 $\min_{i,j} \frac{a_i-a_j}{j-i}$，考虑二分最小值，那么相当于对于所有 $j>i$ 要有 $a_i-a_j \geq kj-ki$，也就是 $a_i+k_i \geq a_j+k_...