补题A-E Codeforces Round 953 (Div. 2)

https://codeforces.com/contest/1979

在这里插入图片描述

A. Guess the Maximum

原题链接：https://codeforces.com/contest/1979/problem/A

求相邻元素的最大值的最小值。

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define ll long long
const int N = 2e5 + 5;
int n, m, k;
int a[N];
void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int minmx = 1e9;
    for (int i = 2; i <= n; i++) {
        minmx = min(minmx, max(a[i - 1], a[i]));
    }
    cout << minmx - 1 << endl;
}

int main() {
    IOS;
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

B. XOR Sequences

原题链接：https://codeforces.com/contest/1979/problem/B

因为异或运算满足两数相同为0，不同为1。

期望是区间内的数ai = ia ^ x等于bi = ib ^ y。

满足条件的所有ia和ib一定满足：ia ^ ib等于x ^ y。

由于是求区间长度。寻找区间左端点，显然有无数对符合条件。

假如现在x ^ y等于z。

那么ia ^ ib也应该等于z，并且ia + 1 ^ ib + 1也等于z。

如果+1之后仍相等，那么低位+1时受影响的连续的1或0应该是相等的。

一直加到lowbit(z)那一位，再加会影响第lowbit(z) << 1位。

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define ll long long
const int N = 2e5 + 5;
int x, y;
int lowbit(int x) { return x & -x; }
void solve() {
    cin >> x >> y;
    cout << lowbit(x ^ y) << endl;
}

int main() {
    IOS;
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

C. Earning on Bets

原题链接：https://codeforces.com/contest/1979/problem/C

题目要求，期望收益大于成本。

the total amount of coins you bet on all outcomes must be strictly less than the number of coins received back for each possible winning outcome

假设每个点都投资1元，对于a[i]，投资1元的期望收益是a[i]/n，总的期望收益是sum(a)/n。

需要sum(a)/n>n，假如在a[i]上再多投资1元，那么期望收益为(sum(a)+a[i])/n需大于n+1。

但如果没选到a[i]呢，损失会+1。

改动一处，会影响多处，需要尝试换个角度，减少变量数量。

如果让a[i]赢，那么投资1元的收益是a[i]，失败的损失是1，这个状态转移的难点在于，难以判断a[i]上投资增加之后，与其他a[j]上收益的关系。

比如我在a[i]上多投资1元，可以影响多次下注，他们必须再多投资1元，获胜收益才能大于支出。而新的投资有可能影响其他的投资。

如果让a[i]赢，那么投资1/a[i]元的收益是1元。

现在固定收益，每个点获胜都是1元，那么成本为1/a[i], i in a。

如果当前方案可行，那么1大于1/a[i], i in n

假如此时不满足这个式子，那么要么提高收益，要么降低成本，显然提高收益的同时会提高成本，降低成本的同时会降低收益，假如此时成本为1.2：

要增加收益，那么每个点的收益都应大于1.2，那么分母也会放缩到1.2*1.2。
要减去成本，那么部分点获胜的收益会减少0.2*a[i]，当该点获胜时，收益小于1，而此时总成本为1。如此递推，最终分子分母也会放缩成原来的1/1.2。

1/a[i]未必是整数。最小的整数就是lcm(a)，那么每个点的投资为lcm(a)/a[i]

期望的可行方案应满足：

lcm(a)大于sum(lcm(a)/a[i]) i in n

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define ll long long
const int N = 2e5 + 5;
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
int n;
int a[N];

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    ll L = 1;
    for (int i = 1; i <= n; i++)
        L = lcm(L, a[i]);
    ll S = 0;
    for (int i = 1; i <= n; i++)
        S += L / a[i];
    if (S >= L) {
        cout << "-1" << endl;
        return;
    }
    for (int i = 1; i <= n; i++) {
        cout << L / a[i] << " \n"[i == n];
    }
}

int main() {
    IOS;
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

D. Fixing a Binary String

原题链接：https://codeforces.com/problemset/problem/1979/D

题意是将一个01串分成左右两个部分，左边翻转之后追加到右边。

如果有合法的中断位置，那么，长度不等于k的连续0/1段至多两个。

翻转操作，可以拼接，断点前的最后一段和整串的最后一段，对其他段无影响。

分情况讨论即可。

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define ll long long
constexpr int N = 2e5 + 5;

int n, k;
string s;
int pre[N], suf[N];
void solve() {
    cin >> n >> k;
    cin >> s;
    if (k == n) {
        int cnt = count(s.begin(), s.end(), s.front());
        if (cnt == n)
            cout << n << endl;
        else
            cout << -1 << endl;
        return;
    }
    s = ' ' + s + ' ';
    pre[0] = suf[n + 1] = 1;
    for (int i = 1; i <= n; i++)
        pre[i] = pre[i - 1] && (i <= k || s[i] != s[i - k]);
    for (int i = n; i; i--)
        suf[i] = suf[i + 1] && (i >= n - k + 1 || s[i] != s[i + k]);
    int cnt = 1;
    for (int i = 2; i <= n; i++) {
        if (s[i] != s[i - 1])
            cnt = 1;
        else
            cnt++;
        if (cnt >= k && s[i] != s[i + 1]) {
            int p = i - k;
            if (!p || !pre[p] || !suf[p + 1])
                continue;
            int flag = 1;
            for (int j = n - k + 1; j <= n; j++) {
                int x = p - (j + k - n) + 1;
                if (x < 1)
                    break;
                if (s[x] == s[j]) {
                    flag = 0;
                    break;
                }
            }
            if (flag == 1) {
                cout << p << endl;
                return;
            }
        }
    }
    cout << -1 << endl;
    return;
}
int main() {
    IOS;
    int tt;
    cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}

E. Manhattan Triangle

原题链接：https://codeforces.com/contest/1979/problem/E

对于点i来说，曼哈顿距离为d的点，一定在一个以点i为中心，边长为$ \sqrt2d $的正方形边上。

假如正方形边框上又选定了图上这个点，那么第二点的合法点也是一个矩形，合法的交集为标注的边：

曼哈顿转切比雪夫，是将坐标系顺时针旋转45度，并放大$ \sqrt 2 $倍。

旋转前，第3点与前两点的距离都是$ \frac{d}{\sqrt2} $。

旋转后，由于放大了$ \sqrt 2 $倍，所以新的距离刚好是d。

预处理每条边，维护旋转后的横纵坐标和输入时的需要。

按新的横坐标分组并排序。

枚举每一个横坐标，他的点集应该在与x轴垂直的直线上。

枚举点集的每个点，找纵坐标+d处的第2点。
二分搜索左右两侧的区间，有没有合法的第三点。

#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define ll long long
const int N = 2e5 + 5;
using pii = pair<int, int>;
using aiii = array<int, 3>;
int n, d;
aiii p[N];
aiii ans;

void fuck() {
    map<int, set<pii>> mp;
    for (int i = 1; i <= n; i++) {
        mp[p[i][0]].insert({p[i][1], p[i][2]});
    }
    for (auto &x : mp) {
        set<pii> line1 = x.second;
        if (mp.count(x.first + d)) {
            set<pii> line2 = mp[x.first + d];
            for (pii it0 : line1) {
                int y1 = it0.first;
                auto it1 = line1.lower_bound({y1 + d, 0});
                if (it1 == line1.end() || it1->first != y1 + d)
                    continue;
                auto it2 = line2.lower_bound({y1, 0});
                if (it2 == line2.end() || it2->first > y1 + d)
                    continue;
                ans = {it0.second, it1->second, it2->second};
            }
        }
        if (mp.count(x.first - d)) {
            set<pii> line2 = mp[x.first - d];
            for (pii it0 : line1) {
                int y1 = it0.first;
                auto it1 = line1.lower_bound({y1 + d, 0});
                if (it1 == line1.end() || it1->first != y1 + d)
                    continue;
                auto it2 = line2.lower_bound({y1, 0});
                if (it2 == line2.end() || it2->first > y1 + d)
                    continue;
                ans = {it0.second, it1->second, it2->second};
            }
        }
    }
}

void solve() {
    cin >> n >> d;
    for (int i = 1; i <= n; i++) {
        int x, y;
        cin >> x >> y;
        p[i] = {x + y, x - y, i};
    }
    ans = {};
    fuck();
    for (int i = 1; i <= n; i++)
        swap(p[i][0], p[i][1]);
    fuck();
    for (int x : ans)
        cout << x << ' ';
    cout << endl;
}
signed main() {
    IOS;
    int tt = 1;
    cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}