Codeforces Round 965 (Div. 2) ABCE1_codeforces round 965 (div. 2)题解

A题：Find K Distinct Points with Fixed Center

题意

给定坐标xc和yc，要求给出k个坐标，使得其中点是给定的坐标

思路

明显地，我们只要从xc和yc向两边“扩散”即可

代码

inline void solve() {
     int x, y, k; cin >> x >> y >> k;
     vector<int> a, b;
     if (k & 1) cout << x << ' ' << y << endl;
     for (int i = 1; k - 2 * i >= 0; i ++ ) {
        cout << x - i << ' ' << y - i << endl;
        cout << x + i << ' ' << y + i << endl;
     }
	 return;
}

B题：Minimize Equal Sum Subarrays

题意

给定一个排列，要求你也构造一个排列。

使得两者在（l，r）上的总和相等的（l，r）对数最少

思路

l取1，r取n的时候，无可避免地，两者会相等。

但是，我们看到样例二

5

1 2 3 4 5

构造

2 3 4 5 1

对于前面4个无论怎么取l和r，我们构造的一定比给定的排列大，因此不可能相等

然后再考虑最后一个

最后一个，当且仅当l取1，r取n的时候可以相等，所以这个构造方法是最优解

代码

inline void solve() {
     int n; cin >> n;
     for (int i = 1; i <= n; i ++ ) {
        int x; cin >> x;
        x += 1;
        if (x > n) x -= n;
        cout << x << " \n"[i == n];
     }
	 return;
}

C题：Perform Operations to Maximize Score

题意

给定一个数组和k次操作次数，每次操作可以使得数组中你选定的元素值加上1.

问对于所有的元素ai，ai和去掉第i位后的数组中位数之和最大的是多少？

思路

可以明确知道的是，当我们用完所有操作次数后

一定是a[n] + a[n/2]取到最大的（已经sort过后）

也就是数组中最大的，和中位数

所以，我们可以分出两种情况

1.不变最大的，让中位数增大

2.变最大的，一直增大最大的

为什么就这两种情况呢？

第一种不过多解释

第二种，如果我们把1～n-1数组中的某个ai变成了最大的，再往上加，贡献能够始终加一，是其他方案中的最优解，因此可以覆盖掉其他的考虑

在第二种情况下，我们只要看其是否能加，加上k和中位数再比较即可（当然是选最大的）

而对于第一种，我们可以二分出最大的中位数

二分过程中，我们看cost和cnt

如果x可以是中位数

那么一定有对于前n-1个元素，一定有n-n/2个元素大于等于x（要包括上中位数），而且cost一定小于等于k

代码

inline void solve() {
     ll n, k; cin >> n >> k;
     vector<PLL> a(n + 1);
     for (int i = 1; i <= n; i ++ ) cin >> a[i].first;
     for (int i = 1; i <= n; i ++ ) cin >> a[i].second;
     sort(a.begin() + 1, a.end());
     function<bool(ll)> check = [&](ll x) {
        ll cnt = 0, cost = 0;
        for (int i = n - 1; i; i -- ) {
            if (a[i].first >= x) cnt += 1;
            else if (cnt < (n - n / 2) && a[i].second) cost += x - a[i].first, cnt += 1;
        }
        return (cnt >= n - n / 2) && cost <= k;
     };
     ll l = 0, r = 1e9 + 7, ans = 0;
     while (l + 1 != r) {
        ll mid = l + r >> 1;
        if (check(mid)) l = mid;
        else r = mid;
     }
     ans = max(ans, a[n].first + l);
     for (int i = n; i; i -- ) {
        if (a[i].second) {
            swap(a[n], a[i]);
            sort(a.begin() + 1, a.end() - 1);
            ans = max(ans, a[n].first + k + a[n / 2].first);
            break;
        }
     }
     cout << ans << endl;
	 return;
}

E1:E1. Eliminating Balls With Merging (Easy Version)

题意

（简化）给定一个数组a，每次可以选定i和j，删去两者中小的一个，另一个变成两者之和。

问最后剩下来的最后一个元素的情况有多少种？

 思路

对于i，如果它能够留下来，那么一定能够把其他n-1个元素消灭。

每次我们进行操作，帮i进行扩散，把i旁边所有小于a[i]的给消灭掉

然后更新a[i]的值

这样的时间复杂度一定是够的，如果一开始值是a[i]，下一次进行扩散的值就一定大于等于2*a[i]

所以时间复杂度是log级别的，然后看是否可以扩散就看最大值即可，用st表维护

代码

const int maxm = 2e5 + 9;
ll st[maxm][30], a[maxm], lg2[maxm], pre[maxm];
int n, k;
inline void build() {
    for (int i = 2; i <= n; i ++ ) lg2[i] = lg2[i >> 1] + 1;
	for (int i = 1; i <= n; i ++ ) st[i][0] = a[i];
	for (int j = 1; (1 << j) <= n; j ++ ) {
		for (int i = 1; i + (1 << j - 1) <= n; i ++ ) {
			st[i][j] = max(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
		}
	}
}
inline int query(int l, int r) {
	int s =  lg2[r - l + 1];
	return max(st[l][s], st[r - (1 << s) + 1][s]);
}
inline void solve() {
     cin >> n >> k;
     for (int i = 1; i <= n; i ++ ) cin >> a[i], pre[i] = pre[i - 1] + a[i];
     build();
     int ans = 0;
     function<void(int)> work = [&](int x) {
        int l = x, r = x;
        ll cur = a[x];
        while (true) {
            int temp1 = l, temp2 = r;
            int r1 = n + 1;
            while (r + 1 != r1) {
                int mid = r + r1 >> 1;
                if (query(x, mid) <= cur) r = mid;
                else r1 = mid;
            }
            r1 = 0;
            while (r1 + 1 != l) {
                int mid = r1 + l >> 1;
                if (query(mid, x) <= cur) l = mid;
                else r1 = mid;
            }
            cur = pre[r] - pre[l - 1];
            if (l == temp1 && r == temp2) break;
        }
        if (l == 1 && r == n) ans += 1;
     };
     for (int i = 1; i <= n; i ++ ) work(i);
     cout << ans << endl;
	 return;
}