CF1703 F, G 题解
F. Yet Another Problem About Pairs Satisfying an Inequality
思路(来源于官方题解)
观察题目中的不等式 。可以发现,对于数组中的任意元素,只要不符合 ,那就绝对不会和任何的元素组成一个合法的数对。所以我们可以直接跳过不符合 的元素。
我们可以把这个不等式拆成三个部分 和 。
那对于所有符合 的元素,第一个和最后一个不等式已经满足了,只要找到满足 的元素,就可以构成一个合法数对了。
我们设 去掉不满足 的数组为 (听起来有点奇怪,但是 中的每个元素的下标是跟 一样的)。
比如我们说数组中的一个元素有值和下标两个属性,并且用这样的方式标记:,那么如果 数组是:
那去掉所有 的,就能得到 :
那只要我们对于每个 找到所有符合的 ,就可以解决本题。
其中不难发现 是单调递增的,所以可以使用二分来找最大的,小于 的 。那么 中所有 小于 的元素(以及 自身)都可以跟 构成一个合法数对。
除了二分法,我们还可以用树状数组来找到 中所有 小于一个特定值的元素的数量。
具体来说,我们可以用树状数组维护一个前缀和数组,然后遍历 中的元素,每次都做 upd(id)
的操作。也就是使查询所有大于等于 的数时,查到的值都增加 。
这样,在树状数组中查询某个 的时候,就会返回比 小的所有 了。
当然,用差分的方法,也可以得到和树状数组相同的前缀和数组。而且本题不需要我们在得到这个前缀和数组后做别的更新,所以差分可以用 的复杂度解决本题。
代码
复杂度:
#include <bits/stdc++.h>
using namespace std;
#define ll long long
// author: ttzytt (ttzytt.com)
// ref: https://codeforces.com/blog/entry/104786
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin>>n;
int a[n + 1];
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
ll ans = 0;
vector<int> valid; // 前文所说的 b 数组,但是只储存了下标
// 因为我们只需要找最大的,小于 b_i 的下标 j
for (int i = 1; i <= n; i++) {
if (a[i] >= i) continue; // 不符合就直接跳过
// 这里可能算是一个优化吧,可以发现 valid 中的下标 i 都是小于 j 的
// 我们并没有把全部的 b 的下标都塞进 valid 中,因为 a[i] < i < a[j] < j
// 所以只有 i < j 才可能符合。
ans += (ll)(lower_bound(valid.begin(), valid.end(), a[i]) -
valid.begin());
// lower_bound 会找到 valid 中第一个大于等于 a[i] 的元素。
// 那么这个元素**之前**的全部是可用的。一个区间的长度为 r - l + 1
// 因为只有这个元素之前的才是可用的,所以这个 1 我们就不加了
valid.push_back(i);
}
cout << ans << '\n';
}
}
G. Good Key, Bad Key
思路(来源于官方题解)
我们能发现,对于所有的盒子,交错的使用好钥匙和坏钥匙总是更加不合算的。
并且,连续的,在前面的盒子使用好钥匙会更合算。(或者说使用好钥匙作为前缀)。
假设我们在一个好钥匙之前使用了一个坏钥匙,那么我们获得的收益是:
但如果先使用好钥匙,后使用坏钥匙,获得的收益是:
很明显,先使用好钥匙更合算。
更直观一点的解释是,不管先使用哪种钥匙,都会减去 的收益,但是如果先使用坏钥匙,我们会把两个盒子的收益减半,但如果先使用好钥匙,就只会把一个盒子的收益减半。
所以我们只会在最后的部分使用坏钥匙,在某些 比较大的情况下,可能相比减去 ,把 减半更合算。
所以只需要枚举一个使用好钥匙和坏钥匙的分割点,在这个点前面全部使用好钥匙,后面全部使用坏钥匙。
我们设这个分割点为 。
那么在分割点 后面使用坏钥匙,每个盒子的收益就会变成:
能发现这个 会增长的很快,在某个点之后, 就会变成 。那么在这个点之后我们就没必要再计算了。
因为最大的 为 ,所以 之后就没必要计算了。(或者你可以想,一直右移一个数,那么过了某个点整个数的二进制形式就没有 了)。
代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
// author: ttzytt (ttzytt.com)
// ref: https://codeforces.com/blog/entry/104786
int main() {
int t;
cin >> t;
while (t--) {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
ll psum = 0, ans = 0;
// psum 是使用好钥匙获得的收益
for (int i = -1; i < n; i++) {
if (i != -1) psum += (ll)(a[i] - k);
ll cur = psum;
// 枚举 i 这个分割点
for (int j = i + 1; j < min(n, i + 32); j++) {
// 过了 i + 32 就没必要继续计算了
int bkval = a[j];
bkval >>= (j - i); // i + 1 要 / 2, i + 2 要 / 4 ...
cur += bkval;
}
ans = max(ans, cur);
}
cout << ans << endl;
}
}