Codeforces Round 703 (Div. 2)（A~D）

A. Shifting Stacks

给出一个数组，每次可以将一个位置-1，右侧相邻位置+1，判断是否可以经过若干次操作后使得数列严格递增。

思路：对于每个位置，前缀和必须都大于该位置应该有的最少数字，即第一个位置最少是0， 第二个位置最少是1，第三个位置最少是2，取一下前缀和。

AC Code：

#include <bits/stdc++.h>typedef long long ll;
const int N = 105; 
int t, n;
ll a[N];int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin >> t;while(t --) {std::cin >> n;ll num = 0;bool flag = true;for(int i = 1; i <= n; i ++) {std::cin >> a[i];a[i] += a[i - 1];if(a[i] < num)flag = false;num += i;}std::cout << (flag ? "YES" : "NO") << '\n';}return 0;
}

B. Eastern Exhibition

给出二维平面上若干个坐标，在二维平面上选择一个位置，使得这个位置到所有点的距离之和最小，求满足条件的点有多少个。

思路：考虑先放到一维里考虑，这样很容易想到是放到中间位置，即中间两个点之间的距离都可以；如果放到二维其实也是一样的，就是两个维度的中间两点距离差的乘积。

AC Code：

#include <bits/stdc++.h>
using namespace std;long long solve(vector<int> x) {sort(x.begin(), x.end());return x[x.size() / 2] - x[(x.size() - 1) / 2] + 1;
}void solve() {int n;cin >> n;vector<int> x(n), y(n);for (int i = 0; i < n; ++i)cin >> x[i] >> y[i];cout << solve(x) * solve(y) << '\n';
}int main() {int t;cin >> t;while (t--) solve();return 0;
}

os：贴的标解hhh

C. Guessing the Greatest

交互题，每次可以询问任意区间内第二大的数的位置，在不超过20次询问后得到最大值的位置。

思路：20次，可以想到二进制枚举，因为数据范围在1e5内，完全可以完成枚举。考虑倍增，如果一开始的次大值位置为p，若是1~p内存在最大值，则可以用倍增不断增大l，缩减当前范围，到最后最大值一定是l的位置；反之，则用倍增不断缩小r的范围，最后最大值的位置就是r。

AC Code;

#include <bits/stdc++.h>typedef long long ll;
#define int long long
const int N = 1e3 + 5; 
int n;
int pow2[25];int ask(int l, int r) {if(l == r) return -1;std::cout << "? " << l << ' ' << r << '\n';std::cout.flush();int pos;std::cin >> pos;return pos;
}void init() {pow2[0] = 1; for(int i = 1; i <= 20; i ++) {pow2[i] = pow2[i - 1] * 2;}
}signed main() {init();std::cin >> n;int l = 1, r = n;int p = ask(l, r);if(ask(1, p) == p) {for(int i = 18; i >= 0; i --) {if(pow2[i] + l <= p && ask(l + pow2[i], p) == p)l += pow2[i];}std::cout << "! " << l << '\n';}else {for(int i = 18; i >= 0; i --) {if(r - pow2[i] >= p && ask(p, r - pow2[i]) == p)r -= pow2[i];}std::cout << "! " << r << '\n';}std::cout.flush();return 0;
}

D. Max Median

给出一个数组，要求找到长度至少为k，中间数最大的序列，输出最大的中间数的值。

思路：可以考虑二分答案。在值域上二分，对于每个mid，判断序列中是否存在长度为至少为k的子序列中位数为mid。可以这样处理check函数：遍历数组，大于等于mid的为1，小于mid的为-1，处理前缀和和前缀最小值。处理前缀最小值的原因是这样可以不局限于长度为k的子序列，长度大于等于k的子序列只要有满足条件的都会被找到。

AC Code：

#include <bits/stdc++.h>typedef long long ll;
const int N = 2e5 + 5;
int n, k;
int a[N], pre[N];bool check(int mid) {int sum = 0;for(int i = 1; i <= n; i ++) {if(a[i] >= mid)sum ++;elsesum --;pre[i] = std::min(pre[i - 1], sum);if(i >= k && sum - pre[i - k] > 0)return true;}return false;
}int main() {std::ios::sync_with_stdio(false);std::cin.tie(0);std::cout.tie(0);std::cin >> n >> k;for(int i = 1; i <= n; i ++) {std::cin >> a[i];}int l = 1, r = n;while(l < r) {int mid = l + r + 1 >> 1;if(check(mid)) l = mid;else r = mid - 1;}std::cout << l << '\n';return 0;
}