官方题解

A. ARC Arc

给定 01 串aa，问能否构造一个字符串tt，使得执行若干次操作后，aa 串全为 1。一次操作定义为：

  • 选择一个下标ii，满足tt 的[i,i+2][i,i+2] 三个位置为 ARC 或 CRA，将aa 的[i,i+1][i,i+1] 两个位置替换为 1。（字符串是循环的，t−1=tn−1t_{-1}=t_{n-1}）
什么样的 t 串最好，也即什么样的 t 串能覆盖尽可能多的位置？

ARCRARCR...

有可能覆盖所有位置吗？应当如何分类讨论？

ARCRARCR... 的周期是 4。

当aa 串长度nn 是 4 的倍数时，ARCRARCR...ARCR 总是最好的。应当按字符串长度模 4 分类讨论。

另外注意，无解的情形不会很多。

完整解析

发现 ARCRARCR... 这样的串能覆盖尽可能多的位置。而且这个字符串的周期是 4。

无解的情形不会很多。因为操作ii 和操作i+2i+2 是相互绑定的，只能是 ARCRA；而操作ii 和操作i+3i+3 总是没有影响，可以是 ARCARC 也可以是 ARCCRA。进一步分析，如果 1 超过两个，一定是 Yes。

当aa 串长度nn 是 4 的倍数时，ARCR...ARCR 总是最好的。应当按字符串长度模 4 分类讨论。

  • 如果n mod 4=0n \bmod 4=0，总是 Yes。
  • 如果n mod 4=1n \bmod 4=1，只有当aa 全 0 时是 No。否则，不妨设an=1a_{n}=1，构造 ARCR...ARCRA，可以将除最后一位以外的都变成 1。
  • 如果n mod 4=3n \bmod 4=3，同n mod 4=1n \bmod 4=1。
  • 如果n mod 4=2n \bmod 4=2，0 个 1 和一个 1 都是无解，关注两个 1 的情况。刚才提到，操作ii 和操作i+3i+3 总是没有影响，而最优情况是隔两个 3，这就需要这两个 1 分别位于奇数位和偶数位。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>

#define cerr(x) cerr << #x << " == " << (x) << endl;

using namespace std;
using LL = long long;

constexpr LL inf = 0x3f3f3f3f3f3f3f3f;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    if (n % 4 == 0) {
        cout << "Yes" << endl;
    } else if (n & 1) {
        bool ok = false;
        for (int i = 0; i < n; i++) {
            ok |= (a[i] == 1);
        }
        cout << (ok ? "Yes" : "No") << endl;
    } else {
        bool ok[2]{};
        for (int i = 0; i < n; i++) {
            ok[i & 1] |= (a[i] == 1);
        }
        cout << (ok[0] && ok[1] ? "Yes" : "No") << endl;
    }

    return 0;
}

B. Fennec VS. Snuke 2

尝试简化问题，去除无关条件。

每个数只有奇偶性重要，将序列变成 01 串。

C. Range Sums 2

完整解析

突破口在ai>0a_{i}>0，这样询问结果的最大值一定是整个数组的和。

先任取xx，问xx 和[1,n][1,n]。询问结果的最大值是其中一个端点ss，再问ss 和[1,n][1,n]，按大小排序就能得到答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <bits/stdc++.h>

#define cerr(x) cerr << #x << " == " << (x) << endl;
#define cerr2(x, y) cerr << #x << " == " << (x) << ", " << #y << " == " << (y) << endl;

using namespace std;
using LL = long long;

constexpr LL inf = 0x3f3f3f3f3f3f3f3f;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr), cout.tie(nullptr);

    int n;
    cin >> n;

    auto query = [](int s, int t) {
        cout << "? " << (s + 1) << " " << (t + 1) << endl;
        LL x;
        cin >> x;
        return x;
    };

    set<pair<LL, int>> res;
    for (int i = 1; i < n; i++) {
        res.insert({ query(0, i), i });
    }

    auto [_, s] = *res.rbegin();

    // cerr(s);

    res.clear();
    for (int i = 0; i < n; i++) {
        if (i == s) continue;
        res.insert({ query(s, i), i });
    }

    vector<int> p(n);
    vector<LL> a(n);
    auto it = res.begin();
    for (int i = 1; i < n; i++, it++) {
        auto [x, y] = *it;
        p[y] = i;
        a[i] = x;
    }

    vector<int> pinv(n);
    for (int i = 0; i < n; i++) {
        pinv[p[i]] = i;
        // cerr2(i, p[i]);
    }

    a[0] = (*res.rbegin()).first - query(pinv[1], pinv[n - 1]);

    for (int i = n - 1; i > 0; i--) {
        a[i] -= a[i - 1];
    }

    if (p[0] > p[1]) {
        for (int i = 0; i < n; i++) {
            p[i] = n - 1 - p[i];
        }
        reverse(a.begin(), a.end());
    }

    cout << "! ";
    for (int i = 0; i < n; i++) {
        cout << (p[i] + 1) << " ";
    }
    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << endl; 

    return 0;
}