A
题意：
给定一个长度为n的数组，你可以任意交换两个距离为k的数，求最大的连续k个数组之和。
核心思路：这个我们直接暴力就好了，我们可以把那些距离为k的比较大的全都换到我们数组的前k个位置。然后求前k个位置的和就好了.
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int P = 133;
const int N = 1e6 + 10;
void solve()
{
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int i = 0;i < n;i++)
cin >> a[i];
for (int i = k;i < n;i++)
a[i % k] = max(a[i % k], a[i]);
LL ans = 0;
for (int i = 0;i < k;i++)
ans += a[i];
cout << ans << endl;
}
int main()
{
int T;
cin >> T;
while (T--)
{
solve();
}
}
B. Rule of League 模拟
题意：
有n个人战斗，战斗持续n-1次，第一次1和2战斗，第二次2和3战斗，第三次3和4战斗...最后一次n-1和n战斗。给定两个数x和y，表示每个人赢的场数为x和y。请构造出每一场获胜的人，若无解输出-1。
核心思路：这里就有细节了，分为以下几种情况：我们先交换位置令x最大
- 最大的都是0，显然无解
- y不为零，我们需要知道只要有比赛那么就必然会有人一场都无妨赢，所以y不等于0一定无解
- (n-1)%x,这个是很好理解的，就不解释了
然后接下来代码实现的时候我们可以使用k储存我们某个节点总共持续赢的次数。
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
typedef long long LL;
int P = 133;
const int N = 1e6 + 10;
int ans = 0x3fff;
void solve()
{
int n, x, y;
cin >> n >> x >> y;
if (x < y)
swap(x, y);
if (!x || y || (n - 1) % x)
{
cout << -1 << endl;
return;
}
int k = 0, now;
for (int i = 2; i <= n; ++i, --k) {
if (k == 0) {
k = x;
now = i;
}
cout << now << ' ';
}
cout << endl;
}
int main()
{
int T;
cin >> T;
while (T--)
{
solve();
}
}
C
题意：
给定一个数组，每次操作选定两个点l, r，如果a[l] + a[r]是奇数，那么a[r] = a[l]；否则a[l] = a[r]。目标是构造出一个不下降的序列，输出任意一组解使得操作次数不超过n。
核心思路：我们注意所给的条件，他只让我们输出任意一组解，所以我们只需要构造任意一组不下降的序列就好了。那怎么构造呢。我们可以先从首尾开始入手。先把首尾操作一下。那么第一项和最后一项就有那么几种情况。一定要注意我们的目的是把他们变为一样的序列，就是搞完之后每一个a[i]都相等
- 首尾都是奇数，每插入一个a[i]，如果a[i]是奇数就让他与最后一个数操作，如果是偶数就让他与第一个数操作。
- 首尾都是偶数，刚好相反。
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
typedef long long LL;
int P = 133;
const int N = 1e6 + 10;
int ans = 0x3fff;
int a[N], s[N];
int n;
void solve()
{
int n;
cin >> n;
int maxv = 0, minv = 1;
for (int i = 1;i <= n;i++)
{
cin >> a[i];
s[i] = a[i] & 1;//就是判断是不是奇偶
if (s[i] < minv)
minv = s[i];
if (s[i] > maxv)
maxv = s[i];
}
if (maxv == minv)//没操作之前就是全都是奇数或者全都是偶数.
{
cout << n - 1 << endl;
for (int i = n - 1;i >= 1;i--)
cout << i << " " << i + 1 << endl;
}
else
{
vector<pair<int, int>> ans;
if (a[1] != a[n])
{
ans.push_back({ 1,n });
if (s[1] != s[n])
a[n] = a[1];
else
a[1] = a[n];
}
if (a[1] & 1)//这里就只有首位是奇偶或者是偶奇的情况了
{
for (int i = 2;i <= n - 1;i++)
{
if (a[i] & 1)
{
ans.push_back({ i,n });
}
else
ans.push_back({ 1,i });
}
}
else
{
for (int i = 2;i <= n-1;i++)
{
if (a[i] & 1)
ans.push_back({ 1,i });
else
ans.push_back({ i,n });
}
}
cout << ans.size() << endl;
for (auto it : ans) cout << it.first << " " << it.second << endl;
cout << endl;
return;
}
}
int main()
{
int T;
cin >> T;
while (T--)
{
solve();
}
}
D1
题意：
给定两个01串，要求经过操作使得第一个串等于第二个串。可以选择两个位置翻转，如果两个位置距离为1，那么翻转的代价为x，距离大于1则代价为y。求最小代价。(其中x>y).
核心思路：我们一定要注意x>y,我们先考虑无解的情况，这个还是很显然的只要不相同的位置的个数不是偶数那么就一定无解。然后我们知道那个不相同的位置是偶数，所以我们在n>2的时候花费y一定是最优解。然后等于2的时候来一个特判就好了.
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
typedef long long LL;
int P = 133;
const int N = 2e5 + 10;
int a[N], b[N];
void solve()
{
int n, x, y;
cin >> n >> x >> y;
for (int i = 0;i < n;i++)
{
scanf("%1d", &a[i]);
}
for (int i = 0;i < n;i++)
scanf("%1d", &b[i]);
vector<int> ans;
int res = 0;
for (int i = 0;i < n;i++)
{
if (a[i] != b[i])
ans.push_back(i);
}
if (ans.size() % 2)
{
cout << -1 << endl;
return;
}
else
{
if (ans.size() == 2 && ans.front() + 1 == ans.back())
{
cout << min(x, 2 * y) << endl;
}
else
cout << ans.size() / (LL)2 * y << endl;
}
}
int main()
{
int T;
cin >> T;
while (T--)
{
solve();
}
}
D2
题意：
这个就是在第一问的情况下取消了x>y的条件。
核心思路：
- 当x<y我们还是采用第一种方式处理
- 当x>y,这里我们就需要注意了，我来举个例子，比如1 0 1,我们可以通过耗费\(2*x\)的代价变成0 0 0.回归主题，我们可以先把代价全都置为y,然后再想把拿些位置的代价替换为x可以实现代价最小。
假设第i个1在\(ans_{i}\)上面，那么对于这个1我们可以通过\(ans_i-ans_{i-1}\)次x将这两个1变为0.相比于一次y节省了\(y-x(p_i-p_{i-1})\).于是这一题我们就可以使用线性dp求解.
- 集合定义：dp[i]表示前i个元素通过把y替换成x所能节省的最多费用.
- 集合划分，可以划分尾第i个元素替换和不替换两种状态.
- 状态转移方程：\(dp[i]=max(dp[i-1],dp[i-2]+y-x(p_i-p_{i-1})\).
#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
typedef long long LL;
int P = 133;
const int N = 2e5 + 10;
LL a[N], b[N];
LL dp[N];
void solve()
{
LL n, x, y;
cin >> n >> x >> y;
for (int i = 0;i < n;i++)
{
scanf("%1d", &a[i]);
}
for (int i = 0;i < n;i++)
scanf("%1d", &b[i]);
vector<LL> ans;
LL res = 0;
for (int i = 0;i < n;i++)
{
if (a[i] != b[i])
ans.push_back(i);
}
if (ans.size() % 2)
{
cout << -1 << endl;
return;
}
if(x>=y)
{
if (ans.size() == 2 && ans.front() + 1 == ans.back())
{
cout << min(x, 2 * y) << endl;
}
else
cout << ans.size() / (LL)2 * y << endl;
}
else
{
dp[0] = 0;
for (int i = 1;i <= ans.size();i++)
{
dp[i] = dp[i - 1];//先由前面的值更新下,注意下下面的dp[i]=dp[i-]
if (i >= 2)
{
LL t = y - (LL)(ans[i - 1] - ans[i - 2]) * x;//要注意我们ans是从0开始的
dp[i] = max(dp[i], dp[i - 2] + t);
}
}
cout << (LL)y * ans.size() / 2 - dp[ans.size()]<<endl;
}
}
int main()
{
int T;
cin >> T;
while (T--)
{
solve();
}
}