Contestant~. Rank 257. Rating +51.

A. Make It Zero

题意

给定一个序列，定义一次操作为选定一个区间，并将区间内的所有数全都替换为他们的异或总和。

输出不超过 \(8\) 次操作后，让整个序列变为 \(0\) 的一种方案。

思路

我们分奇偶性来考虑：

1. 如果序列长度为偶数，显然偶数个相同的元素异或和为 \(0\)，那么我们只要对整个序列进行异或，然后再重复一次操作即可；

2. 如果序列长度为奇数，那么我们同上，对前 \(n - 1\) 个元素执行两次操作。因为任何数和 \(0\) 异或都是它本身，因而我们对最后两个元素操作两次即可。

时间复杂度：\(O(1)\)

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

const int N = 1e6 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    if(n % 2 == 0){
        cout << 2 << '\n';
        cout << 1 << ' ' << n << '\n';
        cout << 1 << ' ' << n << '\n';
    } else {
        cout << 4 << '\n';
        cout << 1 << ' ' << n - 1 << '\n';
        cout << 1 << ' ' << n - 1 << '\n';
        cout << n - 1 << ' ' << n << '\n';
        cout << n - 1 << ' ' << n << '\n';
    }
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//    init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

脑子不好使卡了一会儿qaq

B. 2D Traveling

题意

给定 \(n\) 个点，其中前 \(k\) 个点位于主城内，主城内的点相互传送代价为 \(0\)，否则代价为两点横纵坐标差值的绝对值之和，即 \(|x_i-x_j|+|y_i-y_j|\)。

现在，给定起点和终点所在的点的标号，输出从起点走到终点的最小代价和。

思路

首先，因为主城内相互传送无代价，所以当我们传送到主城后，我们就直接另找一个更近的点传送到外面即可。

并且，因为三角不等式，我们可以发现 从一个点走到另一个点 总是优于 从一个点走到一个点再走到另一个点。

因而，我们只需先走到主城，再从主城走到终点，最多需要使用三个点。对于点的选择，暴力判断即可。

当然，也会有直接从起点走到终点的方案，我们特判一下即可。

时间复杂度：\(O(n)\)

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

const int N = 1e6 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int n, k, a, b;
    cin >> n >> k >> a >> b;
    vector<pii> p(n + 1);
    for(int i=1;i<=n;i++){
        cin >> p[i].fs >> p[i].sc;
    }
    int mn1 = inf, mn2 = inf;
    for(int i=1;i<=k;i++){
        int now = abs(p[i].fs - p[a].fs) + abs(p[i].sc - p[a].sc);
        mn1 = min(mn1, now);
    }
    for(int i=1;i<=k;i++){
        int now = abs(p[i].fs - p[b].fs) + abs(p[i].sc - p[b].sc);
        mn2 = min(mn2, now);
    }
    int ans = min(mn1 + mn2, abs(p[a].fs - p[b].fs) + abs(p[a].sc - p[b].sc));
    cout << ans << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//    init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

妥妥一个诈骗

C. Fill in the Matrix

题意

给定矩阵的规模 \(n \times m\)，构造矩阵，满足每一行都是 \([0, m - 1]\) 内数的排列。

对于构造好的矩阵，我们计算每一列每个元素的 \(MEX\) 值，然后再对每一列的 \(MEX\) 值再求一次 \(MEX\)。

构造矩阵，让最后的 \(MEX\) 最大，并输出值和方案。

思路

我们可以发现，下面的矩阵总是更优的：

\(M= \begin{pmatrix} 0&1&\cdots&m-2&m-1\\ 1&2&\cdots&m-1&0\\ 2&3&\cdots&0&1\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ m-2&m-1&\cdots &m-4 & m-3\\ 0&1&\cdots&m-2&m-1\\ 0&1&\cdots&m-2&m-1\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ 0&1&\cdots&m-2&m-1\\ \end{pmatrix}\)

对于 \(MEX\) 值，我们可以暴力计算（需要适当剪枝），也可以寻找规律：

1. 当 \(m = 1\) 的时候，可以发现只有一列，且都为 \(0\)，那么该列的 \(MEX = 1\)，对所有列的结果求 \(MEX = 0\)；

2. 当 \(n > m - 1\) 的时候，因为后面都是相同的行，通过计算得到 \(MEX = [0, m - 1]\)，最后的答案是 \(MEX = m\)；

3. 否则，由我们的构造，可以发现 \(MEX = [0, n]\)，最后的答案是 \(MEX = n + 1\)

时间复杂度：\(O(nm)\)

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

const int N = 1e6 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int n, m;
    cin >> n >> m;
    if(m == 1) cout << 0 << '\n';
    else if(n > m - 1) cout << m << '\n';
    else cout << n + 1 << '\n';
    for(int i=0;i<min(n,m-1);i++){
        for(int j=0;j<m;j++){
            cout << (i + j) % m << ' ';
        }
        cout << '\n';
    }
    for(int i=min(n,m-1);i<n;i++){
        for(int j=0;j<m;j++) cout << j << ' ';
        cout << '\n';
    }
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//    init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

能暴力求是没想到的

D1. Candy Party (Easy Version)

题意

给定一个序列，定义一个元素可以选择一个不超过自己本身的 \(2^k\)，并将其给其他元素。

在本题中，一个元素需要恰好给另一个元素 \(2^p\)，同时也需要恰好从另一个元素得到 \(2^q\)。

在满足上述操作的条件下，判断最后能否让整个序列所有元素相等。

思路

首先，既然是序列内的互相给予，那么最后的总和是不变的，且最后所有元素都会变为平均值 \(avg\)。那么我们可以先特判总和是否是 \(n\) 的倍数。

其次，按照题给条件，对于每个元素 \(a_i\)，一定存在 \(p, q\)，满足 \(a_i - 2^p + 2^q = avg\)。

我们可以发现，就算出现了不够的情况，也一定有一种方案可以避免，因为这种依赖是环形的。

那么，最后我们只需按照上式，令 \(cnt[j]\) 为当前整个序列 \(2^j\) 多余或缺少的数量，那么我们对每一个元素枚举，找出 \(p, q\)，然后 \(cnt[p] --, cnt[q] ++\) 即可。

最后，我们判断是否 \(cnt\) 里所有元素都是 \(0\)，不是的话就出现了多余或不够的情况。

时间复杂度：\(O(32n)\)

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

const int N = 1e6 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    int sum = 0;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        sum += a[i];
    }
    if(sum % n != 0) {
        cout << "NO\n";
        return;
    }
    sum /= n;
    vector<int> cnt(32);
    for(int i=1;i<=n;i++){
        bool f = false;
        for(int j=0;j<32;j++){
            for(int k=0;k<32;k++){
                if(a[i] - (1ll << j) + (1ll << k) == sum){
                    f = true;
                    cnt[j] ++;
                    cnt[k] --;
                }
            }
        }
        if(!f){
            cout << "NO\n";
            return;
        }
    }
    for(int i=31;i>=0;i--){
        if(cnt[i] > 0){
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//    init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

二进制多少有点抽象（

D2. Candy Party (Hard Version)

题意

同 \(D1\)，区别是加粗的条件替换为：

在本题中，一个元素需要最多给另外一个元素 \(2^p\)，同时也需要最多从另外一个元素得到 \(2^q\)。

思路

我们需要分类讨论：

1. 刚好比平均值少 \(2^k\)，那么我们可以从别的元素拿来 \(2^k\)，或者将自己的 \(2^{k + 1}\) 给别的元素，并从别的元素拿来 \(2^k\)；

2. 否则，执行和 \(D1\) 一样的操作

我们可以将情况 \(1\) 的数单独拿出来考虑，并将剩余的数按照 \(D1\) 的方式，更新得到 \(cnt\) 数组。

对于情况 \(1\) 的数，因为最高位的更高一位的 \(cnt\) 一定是 \(0\)，从而不可以进位上来，所以可以发现最高位是不可以进位的。

那么，我们先统计情况 \(1\) 的数，第 \(i\) 位缺少 \(pn[i]\) 或 多余 \(pl[i]\)，然后我们从最高位开始递推更新 \(cnt\)：

1. 首先，更新 \(cnt[i] := cnt[i] + (pl[i] - pn[i])\)；

2. 然后，若要满足 \(cnt[i] = 0\)，我们需要从下一位进位或在本位退位；

   前者，我们从 \(pl[i - 1]\) 借 \(cnt[i]\) 个来进位，此时 \(i - 1\) 位自然就少了 \(cnt[i]\) 个多余的数；后者同理

最后，我们判断 \(cnt[0]\) 是否为 \(0\) 即可，因为我们上述的操作已经满足 \(i > 0, cnt[i] = 0\)。

自然，我们需要判断每一位 \(pl[i], pn[i]\) 是否小于 \(0\)，是的话说明无解。

时间复杂度：\(O(32n)\)

对应AC代码

#define chatgpt3_5 "bits/stdc++.h"
#define chatgpt4 "bits/extc++.h"

#include chatgpt3_5

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define tpi tuple<int, int, int>
#define fs first
#define sc second
#define pb emplace_back
#define ep emplace
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

const int N = 1e6 + 10, M = 2e5 + 10, mod = 1e9 + 7, inf = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9, PI = acos(-1);

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    int sum = 0;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        sum += a[i];
    }
    if(sum % n != 0) {
        cout << "NO\n";
        return;
    }
    sum /= n;
    vector<int> cnt(32), pl(32), pn(32);
    for(int i=1;i<=n;i++){
        bool f = false;
        for(int j=0;j<32;j++){
            if(a[i] - (1ll << j) == sum){
                f = true;
                pl[j] ++;
            }else if(a[i] + (1ll << j) == sum){
                f = true;
                pn[j] ++;
            }
        }
        if(f) continue;
        for(int j=0;j<32;j++){
            for(int k=0;k<32;k++){
                if(a[i] - (1ll << j) + (1ll << k) == sum){
                    f = true;
                    cnt[j] ++;
                    cnt[k] --;
                }
            }
        }
        if(!f){
            cout << "NO\n";
            return;
        }
    }
    for(int i=31;i>=0;i--){
        if(pl[i] < 0 || pn[i] < 0){
            cout << "NO\n";
            return;
        }
        cnt[i] += (pl[i] - pn[i]);
        if(i == 0) break;
        if(cnt[i] < 0){
            pl[i - 1] -= -cnt[i];
            cnt[i - 1] -= -cnt[i];
        }else{
            pn[i - 1] -= cnt[i];
            cnt[i - 1] += cnt[i];
        }
    }
    cout << (cnt[0] == 0 ? "YES\n" : "NO\n");
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
//    init();
    int t = 1;
    cin >> t;
    while (t--) solve();
}

好一个分类讨论