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 <bits/stdc++.h>
#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 <bits/stdc++.h>
#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;
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<pair<int, int>> 存储，最后输出结果即可。
代码如下：
#include <bits/stdc++.h>
#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;
}
|