T1:大小为n的数组，最多进行k次操作：下标模k意义下相等则可进行交换。求操作后连续k个元素的最大值
固定最大值的k个连续因素小标为[0,k),现在只需使得它为最大即可，将可交换位置中的最大值交换[0,k)的相应位置即可获得最大值
点击查看代码
#include<bits/stdc++.h>
using i64 = long long;
constexpr int P = 998244353;
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int tt = 1; std::cin >> tt;
while(tt--){
int n, k; std::cin >> n >> k;
std::vector<i64> a(n);
for(int i = 0; i < n; ++i){
std::cin >> a[i];
}
for(int i = k; i < n; ++i){
if(a[i] > a[i % k]){
a[i % k] = a[i];
}
}
std::cout << accumulate(a.begin(), a.begin() + k, 0ll) << '\n';
}
return 0;
}
T2：n个人比赛，比赛规则，1，2比赛，胜者与3比赛，再胜者与4比赛，一次类推，最后得到冠军。故必定进行n - 1次比赛，游戏结束。
现在给定x, y，表示对于其中任何一个人，此人赢了x场或输了y场，问是否有满足该情况的比赛进程成立。
根据比赛特点，对于某个特定的人，要么连胜，要么直接输，这就意味着必定有(x > 0 && y == 0) || (x == 0 && y == 1)
现在我们假设存在满足情况的比赛进程，从1开始构造，取1在第一场比赛中胜，进行模拟，故[2, 2 + x - 1]均输，2 + x必输，于是再次从2 + x开始，使其为胜，重复1的过程，直到比赛次数大于等于n - 1,若合理，则比赛次数为n - 1,否则大于n
tip:对于构造题，几乎可以认为，只要寻找到一个非常特殊的情况，看其在满足限制条件得情况下是否满足题意来确定是否有满足题意得解，所以确定特殊情况(其特殊在哪里，优势)，并构造出该特殊情况就成为重中之重。
点击查看代码
#include<bits/stdc++.h>
using i64 = long long;
constexpr int P = 998244353;
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int tt = 1; std::cin >> tt;
while(tt--){
int n, x, y; std::cin >> n >> x >> y;
if(x < y){
std::swap(x, y);
}
if(x == 0){
std::cout << -1 << '\n';
continue;
}
if(y){
std::cout << -1 << '\n';
continue;
}
int now = 1, key = 0; std::vector<int> r;
while(now <= n){
r.push_back(now);
if(key == 0){
now += x + 1;
key = 1;
}else{
now += x;
}
}
if(now > n + 1){
std::cout << -1 << '\n';
continue;
}else{
std::vector<int> x(n + 1);
for(auto xx : r){
if(xx <= n){
x[xx] = xx;
}
}
for(int i = 2; i <= n; ++i){
if(x[i] == 0){
x[i] = x[i - 1];
}
std::cout << x[i] << ' ';
}
std::cout << '\n';
}
}
return 0;
}
T3：给定大小为n的数组，最多进行n次操作：选择下标为l和r的点，
\[(a[l] + a[r]) \% 2 == 0, a[l] = a[r] \]\[(a[l] + a[r]) \% 2 == 1, a[r] = a[l] \]是否存在某种操作序列，使得数组非递减。
构造题，寻找特殊情况(从终点出发，特殊在非递减，我们特殊至数组所有元素相等)，现在考虑在该操作下使得其所有元素相等。
先使a[1] == a[n],然后对于（1， n）内点一定存在其中某种操作使得其等于a[1],故该特殊情况符合构造要求
点击查看代码
#include<bits/stdc++.h>
using i64 = long long;
constexpr int P = 998244353;
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int tt = 1; std::cin >> tt;
while(tt--){
int n; std::cin >> n;
std::vector<int> a(n);
for(int i = 0; i < n; ++i){
std::cin >> a[i];
}
if(n == 1){
std::cout << 0 << '\n';
continue;
}
std::vector<std::pair<int, int>> q{{0, n - 1}};
if((a[0] + a[n - 1]) & 1){
a[n - 1] = a[0];
}else{
a[0] = a[n - 1];
}
for(int i = 1; i < n - 1; ++i){
if((a[i] + a[0]) & 1){
q.push_back({0, i});
} else{
q.push_back({i, n - 1});
}
}
std::cout << q.size() << '\n';
for(auto x : q){
std::cout << x.first + 1 << ' ' << x.second + 1 << '\n';
}
}
return 0;
}
T4：给定两个二进制字符串a,b，存在操作：在a选择两个位置,同时取反。若位置相邻，代价为x；若位置不相邻，代价为y;问操作后使得a=b的最小代价
有（x >= y）
预处理出不同位置序列，个数为res,若个数为奇数，则不可能使得a = b；
为偶数时：
0.0个最小代价为0
1.2个，若不相邻最小代价为y,否则为min(x, 2 * y)
2.不为两个，则必定存在两两不同位置，使得其不相邻，最小代价为(res / 2 * y)
点击查看代码
#include<bits/stdc++.h>
using i64 = long long;
constexpr int P = 998244353;
int main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int tt = 1; std::cin >> tt;
while(tt--){
i64 n, x, y; std::cin >> n >> x >> y;
std::string aa, bb; std::cin >> aa >> bb;
std::vector<int> a(n), b(n);
for(int i = 0; i < n; ++i){
a[i] = aa[i] - '0';
b[i] = bb[i] - '0';
}
std::vector<int> p(n); i64 res = 0;
for(int i = 0; i < n; ++i){
if(a[i] != b[i]){
p[i] = 1;
++res;
}
}
if(res & 1){
std::cout << -1 << '\n';
continue;
}
if(res == 2){
int key = 0;
for(int i = 1; i < n; ++i){
if(p[i] && p[i - 1]){
key = 1;
}
}
std::cout << (key ? (n == 2 ? x : std::min(x, y * 2)) : y) << '\n';
}else{
std::cout << (res / 2 * y) << '\n';
}
}
return 0;
}
T5:题意同T4，但不保证x >= y
分情况讨论：
1.x >= y时同T4
2.x < y时进行考虑，待思考。。。