貌似这次很难，还好去吃烧烤了
发现原来G就是个类欧几里德算法，参考abc283 ex，更了个G

A - To Be Saikyo (abc313 A)

题目大意

给定\(n\)个数\(a_i\)，问第一个数要成为唯一的最大的数，应该加多少。

解题思路

找到后面的最大的数\(m\)，答案就是\(\max(0, m + 1 - a_0)\)。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& i : a)
        cin >> i;
    int ans = max(0, *max_element(a.begin() + 1, a.end()) + 1 - a.front());
    cout << ans << '\n';

    return 0;
}

---

B - Who is Saikyo? (abc313 B)

题目大意

给定\(m\)条关于 \(n\)个数的大小关系，问能否确定出最大的数。

解题思路

大小关系可以构成一张拓扑图，如果\(a > b\)则 \(a \to b\)。如果存在一个最大值，那么从该点出发可以到达所有点。

换句话说，最后看是否仅存在一个度数为 \(0\)的点。存在则其为最大的数。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    vector<int> du(n);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        --u, --v;
        du[v]++;
    }
    int zero = count(du.begin(), du.end(), 0);
    if (zero != 1)
        cout << -1 << '\n';
    else
        cout << find(du.begin(), du.end(), 0) - du.begin() + 1 << '\n';

    return 0;
}

---

C - Approximate Equalization 2 (abc313 C)

题目大意

给定\(n\)个数，要求进行尽量次数最小的操作，使得这些数的极差不超过 \(1\)。

操作为，选择两个数，一个\(+1\)一个\(-1\)。

解题思路

注意到一个性质，无论进行多少次操作，这\(n\)个数的和是不变的，设为 \(sum\)。

那最后极差不超过 \(1\)，且和为 \(sum\)，那自然就是所有数至少是 \(div = \lfloor \frac{sum}{n} \rfloor\)，其中有 \(mod = sum \% n\)个数要\(+1\)， 即为\(div + 1\)。

即最终的\(n\)个数是确定好的，那么自然小的数变成 \(div\)，大的数变成 \(div+1\)。于是排个序，每个数字变成目标数字的次数累加，即作个差就能得到答案了。注意要除以\(2\)，因为每次操作对应了两个数字的变化。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    LL sum = 0;
    for (auto& i : a)
        cin >> i;
    sort(a.begin(), a.end());
    sum = accumulate(a.begin(), a.end(), 0ll);
    int div = sum / n;
    int mod = sum % n;
    LL cnt = 0;
    for (int i = 0; i < n; ++i) {
        cnt += abs((div + (i + mod >= n) - a[i]));
    }
    cout << cnt / 2 << '\n';

    return 0;
}

---

D - Odd or Even (abc313 D)

题目大意

交互题。

有\(n\)个 \(01\)数。

给定奇数\(k\)，每次可以问其中 \(k\)个数的异或值。

最多 \(n\)次请求，还原出这 \(n\)个数。

解题思路

考虑\(n=4,k=3\)的情况，发现可以问

• 1 2 3
• 1 2 4
• 1 3 4

三个请求结果的异或值就是\(a_1\)的值。因为 \(k\)为奇数，每次询问都包括 \(1\)，最终 \(1\)的次数是奇数，而其他的都有一次询问没有被包含，因此出现次数是偶数，异或都消失。答案就是 \(a_1\)的值。

同理，如果再加上 2 3 4，结合1 2 3和1 2 4，那就能得出\(a_2\)的值。

由此可以对前 \(k + 1\)个数 进行询问，每次询问剔除一个数，得到的\(k+1\)个结果，取\(k\)个始终包含第\(i\)个数的结果进行异或，得到的 就是\(a_i\)的值，因此我们可以得到前 \(k+1\)个数的值。

前 \(k+1\) 个数都知道了，要得到第 \(k+2\)个数，那就询问 \(3,4,…,k,k+1,k+2\)的异或值，再异或\(a_3,a_4,…,ak,a{k+1}\)就得到了 \(a_{k+2}\)的值。依次就可以得到剩下的所有数了。

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, k;
    cin >> n >> k;
    vector<int> ans(n);
    auto solve = [&](int l, int r) {
        vector<int> tmp(r - l);
        vector<int> q;
        for (int i = l; i < r; ++i) {
            q.clear();
            for (int j = l; j < r; ++j)
                if (j != i)
                    q.push_back(j);
            cout << "?";
            for (auto& i : q)
                cout << ' ' << i + 1;
            cout << endl;
            cin >> tmp[i - l];
        }
        for (int i = l; i < r; ++i) {
            for (int j = l; j < r; ++j) {
                if (j != i) {
                    ans[i] ^= tmp[j];
                }
            }
        }
    };
    solve(0, k + 1);
    for (int i = k + 1; i < n; i++) {
        cout << "?";
        for (int j = i; j > i - k; --j) {
            cout << ' ' << j + 1;
        }
        cout << endl;
        cin >> ans[i];
        for (int j = i - 1; j > i - k; --j)
            ans[i] ^= ans[j];
    }
    cout << "!";
    for (auto& i : ans)
        cout << ' ' << i;
    cout << endl;

    return 0;
}

---

E - Duplicate (abc313 E)

题目大意

给定一个数字字符串\(s\)，每次进行一次操作，问经历了多少次，最终的字符串的长度为\(1\)。

操作问，得到一个字符串\(t\)，依次对于 \(s\)的每个数\(si\) (除了最后一个)，重复 \(s{i+1}\)次添加到字符串 \(t\)的末尾。

如果最终长度不能为\(1\)，则输出 \(-1\)。

解题思路

首先考虑何时\(-1\)。

每次操作实际上是删掉一个数，如果每次操作是生成一堆\(1\)的话，容易发现不会造成 \(-1\)的情况，但如果生成了其他的数，那就会叠罗汉一样不断增加，比如生成了\(2\)个\(2\) ，那它们会不断叠起来，而每次删除都只删一个数，那最终就会无限长了。

因此每个非\(1\)的数的后面一个数 一定是\(1\)，否则就会无限长。

考虑如何求答案，我们考虑消除每个数所需要的次数，这个次数既然包括消除它本身，也包括消除其产生的所有的\(1\)（不包括原本的 \(1\)）。

对于每个 \(1\)，自然会需要一次操作将其消除，

而对于一个非 \(1\)数\(si\)，其前一个数\(s{i-1}\)一定是 \(1\)，要考虑消除因它而产生的\(1\)的个数。

由于我们每操作一次，这个\(s_i\)就会产生 \(s_i-1\)个 \(1\)出来，那当这个数 \(s_i\)变成最后一个数时，假设我们已经进行了 \(cnt\)次操作，包括消除这个\(s_i\)的操作带来的一次 \(s_i-1\)个 \(1\)，一共生成了\((s_i - 1) \times (cnt + 1)\) 个\(1\)，因此我们需要\(1 + (s_i - 1) \times (cnt + 1)\)次操作才能将这个数\(s_i\)以及其带来的所有 \(1\)消除掉。

而如何求 \(cnt\)，就是消除\(s[i+1, n]\)所需要的次数，因此得倒过来依次考虑每一个数消除所需要的次数。

即设 \(dp[i]\)表示消除 \(s[i,n]\)需要的次数，那么 \(dp[i] = dp[i + 1] + 1 + (s[i] - 1) \times (dp[i + 1] + 1)\)

上述转移式就是三部分：

• 消除\(s[i + 1, n]\)的次数\(dp[i+1]\)
• 消除\(s[i]\)的次数\(1\)
• 消除\(s[i]\)带来的所有 \(1\)的次数\((s[i] - 1) \times (dp[i + 1] + 1)\)

最后答案就是\(dp[1]\)，初始条件\(dp[n + 1] = 0\)

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const LL mo = 998244353;

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    string s;
    cin >> n >> s;
    auto ok = [&]() {
        for (int i = 0; i < n; ++i) {
            if (s[i] != '1' && i + 1 != n && s[i + 1] != '1')
                return false;
        }
        return true;
    };
    if (!ok())
        cout << -1 << '\n';
    else {
        LL ans = 0;
        for (int i = n - 1; i >= 1; --i) {
            ans += 1ll * (s[i] - '1') * (ans + 1) + 1;
            ans = ans % mo;
        }
        cout << ans << '\n';
    }

    return 0;
}

---

F - Flip Machines (abc313 F)

题目大意

<++>

解题思路

<++>

神奇的代码

---

G - Redistribution of Piles (abc313 G)

题目大意

给定\(n\)堆石头\(a_i\)，可以进行以下两种操作：

• 从所有还有石头的堆里面都拿走一个石头，放到包里。
• 从包中取 \(n\)个石子，给每堆石子都放上一个石子。

两种操作可以以任何顺序执行任意多次，问操作执行之后， \(n\)堆石子的局面数的个数。

解题思路

首先考虑两种操作的关系，容易发现对于最终的某种局面，其操作的顺序都可以通过先进行若干次操作一，再进行若干次操作二得到。即先执行操作一，之后才执行操作二。因为执行了操作二后再执行操作一，相当于原来撤销了原来的操作二。

由此我们考虑执行了多少次操作一，再次基础上我们收集了\(sum\)个石头，之后便可执行 \(\lfloor \frac{sum}{n} \rfloor\)次操作二，每执行一次操作二，会发现得到的都是一个不同的局面（对初始石子堆排个序容易发现）。由此我们对所有的操作次数求个和即为答案。

注意到每次执行操作一后，\(sum\)增加的数量不一定是一个定值，这取决于当前还剩下多少堆非零的石子堆，因此我们先对石子堆从小到大排序，枚举前\(i\)堆石子变成零，此时枚举的操作一的操作数范围为\(a{i} \sim a{i + 1} - 1\)。

当操作一的次数是 \(j\)时，可进行的操作二的次数为\(\lfloor \frac{presum_{i} + (n - i) \times j}{n} \rfloor\) ，注意这里的下标都是从\(1\)开始的，\(presumi = \sum{j = 1}^{i} a_j\)。

因为此时操作一的次数范围为\(a{i} \sim a{i + 1} - 1\)，累加一下即为

\[\sum{j = a{i}}^{a{i+1} - 1}\lfloor \frac{(n - i) \times j + presum{i}}{n} \rfloor \]

注意到每一项都是形如\(\sum\limits_{j} \lfloor \frac{aj+b}{c} \rfloor\)的形式，可用类欧几里德算法在\(O(\log)\)时间内算出其和，即

\[\sum{j = a{i}}^{a{i+1} - 1}\lfloor \frac{presum{i} + (n - i) \times j}{n} \rfloor = \sum{j = 1}^{a{i+1} - 1}\lfloor \frac{presum{i} + (n - i) \times j}{n} \rfloor - \sum{j = 1}^{a{i} - 1}\lfloor \frac{presum{i} + (n - i) \times j}{n} \rfloor \]

枚举所有的\(i\)求和，即为答案。

总的时间复杂度是 \(O(n\log a_i)\)

神奇的代码

#include <bits/stdc++.h>
using namespace std;
using LL = long long;

const LL mo = 998244353;

LL floor_sum(LL a, LL b, LL c, LL n) {
    if (n < 0)
        return 0;
    LL val = 0;
    if (a >= c) {
        val += n * (n + 1) / 2 * (a / c) % mo;
        a %= c;
    }
    if (b >= c) {
        val += (n + 1) * (b / c) % mo;
        b %= c;
    }
    LL m = (a * n + b) / c;
    val += n * m % mo - floor_sum(c, c - b - 1, a, m - 1);
    val %= mo;
    val = (val + mo) % mo;
    return val;
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& i : a)
        cin >> i;
    sort(a.begin(), a.end());
    LL ans = (a.back() + 1) % mo;
    LL presum = a[0];
    for (int i = 1; i < n; ++i) {
        ans += floor_sum(n - i, presum, n, a[i]) -
               floor_sum(n - i, presum, n, a[i - 1]);
        ans %= mo;
        ans = (ans + mo) % mo;
        presum += a[i];
    }
    cout << ans << '\n';

    return 0;
}

---

Ex - Group Photo (abc313 Ex)

题目大意

<++>

解题思路

<++>

神奇的代码

---