Codeforces Round #642 (Div. 3)
https://codeforc.es/contest/1353
A. Most Unstable Array
题意:
构造一个长为 n 的序列,序列和为 m ,问相邻两数之差绝对值的和的最大值
思路见代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3 + 10;
int main()
{
int n, t, m;
scanf("%d", &t);
while(t--)
{
scanf("%d%d", &n, &m);
if(n == 1)
{
cout<<0<<'\n';
}
else if(n == 2)
{
cout<<m<<'\n';
}
else
{
cout << 2 * m << '\n';
}
}
return 0;
}
B. Two Arrays And Swaps
题意:
最多把 b 数组的数置换到 a 数组 k 次,求最终 a 数组和的最大值
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 35;
int a[N], b[N];
int main()
{
int n, k, t;
scanf("%d", &t);
while(t--)
{
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; ++i)
{
scanf("%d", &a[i]);
}
for(int i = 1; i <= n; ++i)
{
scanf("%d", &b[i]);
}
sort(a + 1, a + n + 1);
sort(b + 1, b + n + 1, greater<int>());
int ans = 0;
for(int i = 1; i <= n; ++i)
{
if(i <= k && b[i] > a[i])
ans += b[i];
else
ans += a[i];
}
cout<<ans<<'\n';
}
return 0;
}
C. Board Moves
题意:
一个 n * n 的方格板,每个格子中都有一个数字,每一步可以将一个格子中的数字移动到某个与它相邻的格子中,现将所有数字移动到一个格子中,问最少多少步
思路:
很明显,都移到最中间的格子里
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 5;
ll a[N];
void init()
{
for(ll i = 1; i < N; ++i)
{
a[i] = i * i + a[i - 1];
}
}
int main()
{
init();
int t, n;
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
ll ans = 8 * a[(int)(n / 2)];
cout<<ans<<'\n';
}
return 0;
}
D. Constructing the Array
题意:
将数字 1 ~ n 按顺序放到 n 个位置上,每次选择长度最长且最靠左的空白的中间(奇数长度的空白选中间,偶数长度的空白选中间靠左的一个)
思路:
用优先队列存储数列的空白段
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
struct node
{
int id, len;
node(){};
node(int idd, int lenn):id(idd), len(lenn){}
bool operator < (const node &a)const
{
if(len != a.len)
return len < a.len;
else
return id > a.id;
}
};
int a[N];
int main()
{
int n, t;
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
priority_queue<node>q;
q.push(node(1, n));
for(int i = 1; i <= n; ++i)
{
node tmp = q.top();
q.pop();
int l = tmp.id;
int r = tmp.id + tmp.len - 1;
int pos;
if(tmp.len & 1)
{
pos = (l + r) / 2;
}
else
{
pos = (l + r - 1) / 2;
}
a[pos] = i;
if(tmp.len > 1)
{
q.push(node(pos + 1, tmp.len - pos + tmp.id - 1));
}
if(tmp.len > 2)
{
q.push(node(tmp.id, pos - tmp.id));
}
}
for(int i = 1; i <= n; ++i)
{
cout<<a[i];
if(i < n)
cout<<' ';
}
cout<<'\n';
}
return 0;
}
E. K-periodic Garland
题意:
修改原字符串一些位置上的状态,使得任意两个 1 之间的距离都是 k ,求最少修改次数
思路:
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5;
int main()
{
int t, n, k;
char s[N];
scanf("%d", &t);
while(t--)
{
scanf("%d%d", &n, &k);
scanf("%s", s);
int sum = 0;
for(int i = 0; i < n; ++i)
{
sum += s[i] - '0';
}
int tmp, maxx = 0;
for(int i = 0; i < k; ++i)
{
tmp = 0;
for(int j = i; j < n; j += k)
{
tmp += 2 * (s[j] - '0') - 1;
if(tmp < 0)
tmp = 0;
maxx = max(maxx, tmp);
}
}
cout<<sum - maxx<<'\n';
}
return 0;
}