Practice.
A. Consecutive Sum
题意
给定一个序列 \(a\)，以及整数 \(k\)，定义操作为选择 \(i, j\)，满足 \(i \bmod k = j \bmod k\)，并将 \(a_i\) 和 \(a_j\) 交换。
输出任意次操作后，所有长为 \(k\) 的连续子序列的和的最大值。
思路
我们直接枚举 \(p \in [0, k - 1]\)，并求出所有 \(i \bmod k = p\) 位置上 \(a_i\) 的最大值，并输出总和即可。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;
void solve(){
int n, k;
cin >> n >> k;
vector<int> a(k);
for(int i=1;i<=n;i++){
int cur;
cin >> cur;
a[i % k] = max(a[i % k], cur);
}
int ans = 0;
for(int i=0;i<k;i++) ans += a[i];
cout << ans << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}就好了
B. Rule of League
题意
规定对于 \(n\) 个选手，一共有 \(n - 1\) 场对决，第 \(i\) 场为上一场的赢家和第 \(i + 1\) 号选手之间的对决。
给定三个整数 \(n, a, b\)，其中 \(n\) 为选手数，所有选手要么赢了 \(a\) 场，要么赢了 \(b\) 场。
输出每场的赢家，若有多个方案，任选其一输出。
思路
显然，我们需要满足 \(\min(a,b)=0, (n - 1) \% \max(a,b) = 0\)。
那么，我们完全可以让第 \(2 + ky\) 号选手连续赢 \(y\) 场，这样即可满足条件。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;
void solve(){
int n, x, y;
cin >> n >> x >> y;
if(x > y) swap(x, y);
if(x != 0 || y == 0 || (n - 1) % y != 0){
cout << -1 << '\n';
}else{
for(int i=2;i<=n;i+=y){
for(int j=0;j<y;j++) cout << i << ' ';
}
cout << '\n';
}
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}乱猜即可
C. Parity Shuffle Sorting
题意
给定一个序列，定义操作如下：
选择两个下标 \(l, r\)，其中 \(1 \leq l < r \leq n\)。
如果 \(a_l + a_r\) 为奇数，那么将 \(a_r\) 改为 \(a_l\)，否则相反。
输出将序列变为不递减序列的一种方案，满足方案数不超过序列的长度。
思路
我们不妨将序列全都改成一样的。
首先，我们将左右两个端点变为一样的，这只需选择 \(1, n\)，我们无需考虑端点的奇偶性。
其次，我们枚举剩余的元素，如果它和端点的和为奇数，那么我们选择 \(1, i\)，将 \(a_i\) 改为 \(a_1\)；如果为偶数，那么我们选择 \(i, n\)，将 \(a_i\) 改为 \(a_n\)，最后所有元素都会变为同一个值，且所需操作数为 \(n - 1 < n\)。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;
void solve(){
int n;
cin >> n;
cout << n - 1 << '\n';
if(n > 1) cout << 1 << ' ' << n << '\n';
int f = 0;
for(int i=0;i<n;i++){
int cur;
cin >> cur;
if(i > 0 && i < n - 1){
if((cur + f) % 2 == 1) cout << 1 << ' ' << i + 1 << '\n';
else cout << i + 1 << ' ' << n << '\n';
}else f = cur;
}
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}也是乱猜，但是很有道理（x
D1. Zero-One (Easy Version)
题意
给定两个长度相等的二进制字符串 \(a, b\)，定义操作如下：
选择两个下标 \(l, r\)，其中 \(l < r\)；
将 \(a_l\) 修改为 \(1 - a_l\)，\(a_r\) 修改为 \(1 - a_r\)；
如果 \(l + 1 = r\)，那么这次操作代价为 \(x\)，否则代价为 \(y\)。
本题满足 \(x \geq y\)。
输出最小的代价和，使 \(a\) 变为 \(b\)。
思路
首先，本题等效于将 \(a\) 和 \(b\) 按位异或后得到的二进制字符串 \(c\) 中所有 \(1\) 变为 \(0\) 的代价和。
其次，修改是成对的，也就是说，如果 \(1\) 的个数是奇数，那么无解。
那么，这里存在两种操作：
选择两个进行一次操作；
选择任意一个其他元素作为跳板，进行两次操作
因为操作相邻元素的代价是大于操作不相邻元素的，所以当个数多于 \(2\) 的时候，我们完全不需要考虑操作相邻的，因为我们一定可以避免取相邻的对。
而当个数为 \(2\) 时，如果相邻，我们就需要考虑执行哪种操作了，操作 \(1\) 的代价为 \(x\)，操作二的代价为 \(2y\)，那么我们取最小值即可。当然，如果不相邻，答案就是 \(y\)。
时间复杂度：\(O(n)\)
对应AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
const int N = 110, inf = 0x3f3f3f3f3f3f3f3f;
void solve(){
int n, x, y;
cin >> n >> x >> y;
string a, b;
cin >> a >> b;
vector<int> dif;
for(int i=0;i<n;i++){
if(a[i] != b[i]) dif.emplace_back(i);
}
int cnt = dif.size(), ans;
if(cnt % 2 == 1) ans = -1;
else if(cnt == 2) ans = dif[0] + 1 == dif[1] ? min(x, 2 * y) : min(x * (dif[1] - dif[0]), y);
else ans = cnt / 2 * y;
cout << ans << '\n';
}
signed main(){
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while(t --) solve();
}依然还是乱猜（什