Codeforces Round 1059 (Div. 3) 题解

A Beautiful Average

值为取区间和除以区间长度，显然取最大的数字即可。

void solve() {
    int n, mx = 0;
    cin >> n;
    for (int i = 0, x; i < n; ++i) cin >> x, mx = max(mx, x);
    cout << mx << "\n";
}

B Beautiful String

取出所有 $0$ 或者所有 $1$ ，全部相等所以单调不降，剩下的全部相等所以一定是回文。

void solve() {
    int n;
    string s;
    cin >> n >> s;
    vector<int> ans;
    for (int i = 0; i < n; ++i) {
        if (s[i] == '0') ans.pb(i + 1);
    }
    cout << ans.size() << "\n";
    for (int i = 0; i < ans.size(); ++i) cout << ans[i] << " ";
    cout << "\n";
}

C Beautiful XOR

令 $c=a\oplus v$ ，如果 $c\leq a$ 就可以一次操作直接完成，否则就把 $c$ 贪心地拆成两部分小于 $a$ 即可。

void solve() {
    ll a, b;
    cin >> a >> b;
    if (a == b) {
        cout << 0 << "\n";
        return;
    }
    ll c = a ^ b;
    if (c <= a) {
        cout << 1 << "\n" << c << "\n";
        return;
    } else {
        ll r = 0;
        for (int i = 0; i <= 60; ++i) {
            ll bit = 1ll << i;
            if ((c & bit) && !(a & bit)) r |= bit;
        }
        if (r <= a) {
            ll a1 = a ^ r;
            ll x2 = a1 ^ b;
            if (0 <= x2 && x2 <= a1) {
                cout << 2 << "\n" << r << " " << x2 << "\n";
            } else {
                cout << -1 << "\n";
            }
        } else {
            cout << -1 << "\n";
        }
    }
}

D Beautiful Permutation

先询问整个数组的差得到数组长度，再二分找到第一个增加点，即可求出整个区间。

void solve() {
    ll s1, s2, n;
    cin >> n;
    cout << 1 << " " << 1 << " " << n << endl;
    cin >> s1;
    cout << 2 << " " << 1 << " " << n << endl;
    cin >> s2;

    ll len = s2 - s1;

    int l = 1, r = n;
    while (l < r) {
        int mid = (l + r) >> 1;

        cout << 1 << " " << 1 << " " << mid << endl;
        cin >> s1;
        cout << 2 << " " << 1 << " " << mid << endl;
        cin >> s2;

        ll diff = s2 - s1;
        if (diff == 0) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }

    cout << "! " << l << " " << l + len - 1 << endl;
}

E Beautiful Palindromes

• 如果所有数字都出现过，那么把前面的排列复制一遍即可。
• 如果有一个数字没出现过
  • 如果第一个数字等于最后一个数字，那么第一个数字和第二个数字必然不相等，所以把 $a_2$ 和 $a_1$ 加入没出现过的数字， $3$ 循环即可
  • 如果第一个数字不等于最后一个数字，判断一下第一个数字和第二个数字是否相等，不等就放 $a_1$ 和 $a_2$ ，否则放 $a_1$ 和 $a_3$
• 如果有两个数字没出现过，因为这两个数字会把前面隔断，所以再放入一个前面出现过的数字即可。
• 如果没有出现过的数字大于等于 $3$ 个，那么循环放置 $3$ 个数字即可。

void solve() {
    int n, k;
    cin >> n >> k;
    vector<bool> vis(n + 1);
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i], vis[a[i]] = 1;

    vector<int> nt;
    for (int i = 1; i <= n; ++i) {
        if (!vis[i]) nt.pb(i);
    }
    if (nt.size() == 0) {
        for (int i = 0; i < k; ++i) {
            cout << a[i] << " ";
        }
        cout << "\n";
        return;
    }

    if (nt.size() <= 2) {
        if (nt.size() == 1) {
            if (a[0] == a[n - 1]) {
                nt.pb(a[1]), nt.pb(a[0]);
            } else {
                if (a[0] != a[1]) {
                    nt.pb(a[0]), nt.pb(a[1]);
                } else {
                    nt.pb(a[0]), nt.pb(a[2]);
                }

            }
        } else if (nt.size() == 2) {
            nt.pb(a[0]);
        }
    }
    for (int i = 0; i < k; ++i) {
        cout << nt[i % 3] << " ";
    }
    cout << "\n";
}