CodeForces Round #821 (div.2) A~C

A. Consecutive Sum

题意：

给定一个长度为 n 的数组，每次操作选择索引 i 和 j ，满足 i % k == j % k ，并交换 a[i] 和 a[j] ，最多不超过 k 次操作。

操作完后，选择 k 个连续的元素，使得其和最大，输出最大值。

思路：

i % k == j % k 翻译过来就是表示 元素 a[i] 与 a[j] 的距离为 k 。

所以，可以选定前 k 个数，然后以 k 的距离单位去依次遍历数组，选出每个对应位置上的最大元素，相加即为最大值。

代码如下：

#include 
#define ll long long
using namespace std;
const int N = 110;

int a[N];

void solve()
{
    memset(a, 0, sizeof(a));

    int n, k;
    cin >> n >> k;

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    ll sum = 0;
    for (int i = 1; i <= k; i++){
        int mx = -1;
        for (int j = i; j <= n; j += k){
            mx = max(mx, a[j]);
        }
        sum += mx;
    }

    cout << sum << endl;
}

int main()
{
    int t;
    cin >> t;
    while (t--){
        solve();
    }

    return 0;
}

---

B. Rule of League

题意：

有 n 个人在比赛，编号为 1 ~ n 。

规则如下：玩家 1 和玩家 2 打一场比赛，然后获胜者与玩家 3 打一场比赛，然后获胜者与玩家 4 打一场比赛，以此类推。因此，共进行 n - 1 场比赛，最后一场比赛的获胜者成为冠军。

给定一组 n, x, y，每个玩家要么赢 x 场，要么赢 y 场，找到是否有符合条件的结果，输出每场赢的玩家的编号，没有则输出 -1 .

思路：

首先排除掉 x,y 均为 0 的情况，不可能没有人赢。

再看，如果一个人赢了，输了的那个人就一定会被淘汰，所以一定会有人赢 0 场，因此 x, y 中必然有一个为 0 ，另一个不为 0 。

选出 x, y 中不为 0 的数，将其赋值给 t，赢的玩家都赢 t 次，一共要比赛 n - 1 次，那么 t 一定能被 n - 1 整除。输出时，只需要第一次让玩家 1 赢，赢 t 次后，轮到的下一个人继续赢即可。

代码如下：

#include 
#define ll long long
using namespace std;
const int N = 2e5 + 10;

void solve()
{
    int n, x, y;
    cin >> n >> x >> y;

    if (x == 0 && y == 0) puts("-1");

    else if (x && (n - 1) % x == 0 && y == 0 ||
        y && (n - 1) % y == 0 && x == 0)
    {
        int t; //存x或y
        if (x) t = x;
        else t = y;

        for (int i = 1; i <= t; i++)
            cout << 1 << " ";
        for (int i = t + 2; i <= n; i += t)
            for (int j = 1; j <= t; j++)
                cout << i << " ";
        cout << endl;
    }
    
    else puts("-1");
}

int main()
{
    int t;
    cin >> t;
    while (t--){
        solve();
    }

    return 0;
}

---

C. Parity Shuffle Sorting

题意：

给定一个数组，每次操作选定两个序号 l, r ，若 a[l] + a[r] 是奇数，则 a[r] = a[l] ，若 a[l] + a[r] 是偶数，则 a[l] = a[r] . 要求构造出一个不下降序列，操作次数不超过 n 次，输出 总的操作次数 和每次操作的 两个数的序号 。

思路：

因为只需要任意一组解，我们可以构造任意一组符合题意的数列。

由于是不下降序列，所以我们可以优先考虑将整个数组都变成一样的数。

先处理首尾元素，只要它们不相等，就将其改变：和为奇数，就都变成 a[1] ；和为偶数，就都变成 a[r] .

再遍历中间元素，将其分别与首尾元素相加，其和为奇数，就变成 a[1] ，其和为偶数，就变成 a[n] 。

每次操作用 vector> 存储，最后输出结果即可。

代码如下：

#include 
#define ll long long
#define PII pair<int, int>
using namespace std;
const int N = 1e5 + 10;

int a[N];

void solve()
{
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    vector<PII> ans;
    if(a[1] != a[n]){
        ans.push_back({1, n});
        if ((a[1] + a[n]) % 2) a[n] = a[1];
        else a[1] = a[n];
    }

    for (int i = 2; i < n; i++){
        if ((a[i] + a[1]) % 2){
            a[i] = a[1];
            ans.push_back({1, i});
        }
        else {
            a[i] = a[n];
            ans.push_back({i, n});
        }
    }

    cout << ans.size() << endl;
    for (auto [x,y] : ans)
        cout << x << " " << y << endl;
}

int main()
{
    int t;
    cin >> t;
    while (t--){
        solve();
    }

    return 0;
}

---