CodeForces - 1353D
Constructing the Array
题目传送门：https://vjudge.net/contest/536385#problem/D
题意：给你一个全是0的数组，用1-n的数将这个数组填满，规则是从左至右筛选出0最多的子序列，然后如果子序列长度是奇数，就填在中间，如果长度是偶数，就填在中间偏左，让你输出填完的数组序列
题解：优先队列，我们需要时刻知道哪一段序列0最多，说白了插进去一个数，一段全是0的序列就会被分成2段，所以我们可以利用优先队列动态维护0序列的长度，优先处理0序列长的序列。
点击查看代码
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define all(x) (x).begin(), (x).end()
#define endl '\n'
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 2e5 + 10;
typedef struct node
{
int l, r;
bool operator<(const node &t) const
{
if (this->r - this->l != t.r - t.l)
return this->r - this->l < t.r - t.l;
else
return this->l > t.l;
}
} node;
priority_queue<node> q;
int a[N] = {0};
int main(void)
{
Zeoy;
int t;
cin >> t;
while (t--)
{
int n;
cin >> n;
q.push({1, n});
int num = 1;
while (q.size())
{
node t = q.top();
int l = t.l;
int r = t.r;
q.pop();
a[(l + r) / 2] = num++;
if (l != (l + r) / 2)
q.push({l, (l + r) / 2 - 1});
if (r != (l + r) / 2)
q.push({(l + r) / 2 + 1, r});
}
for (int i = 1; i <= n; ++i)
cout << a[i] << " ";
cout << endl;
}
return 0;
}
CodeForces - 1353E
periodic Garland
题目传送门：https://vjudge.net/contest/536385#problem/E
题意：给你一个字符串，0代表灯是灭的，1代表灯是亮的，现在给定k，使得每隔k个位置必须要有连续的亮的灯，或者没有灯亮，例如k=3，以下字符串是合法的"00010010", "1001001", "00010","0"，现在你可以用1花费使得0和1反转，问你最少需要多少花费能够把这个字符串变为合法的字符串。
题解：贪心，首先我们要知道i%k相等的位置一定距离相隔为k，所以我们只要去遍历[0,k-1]即i的余数，然后对i，i+k,i+2k,i+3k...这些位置进行操作，那我们怎么操作呢？
我们模拟一下：假设k=3，如果现在字符串是这个样，010010000，实际上我们根本不用去改变，现在本身就是最优解；如果0100000100，那么我们遍历到第一个1的时候发现使字符串合法的最小代价是1，就是让位置8的1变为0，当我们遍历到位置4的0的时候，使字符串合法的最小代价还是1，就是让位置8的1变为0，当我们遍历到位置8的1时，使字符串合法的最小代价还是1，要么让位置4的0变为1，要么让位置2的1变为0，我们仔细想想这是不是一个求最大字段和的问题，遇到1，sum++，遇到0，sum--，中间时刻维护sum的最大值，如果sum<0说明前面的和对后面已经产生不了贡献了，直接舍弃，这样的话sum其实就代表不需要被改变的最大值，答案就是1的数量减去sum的最大值。
点击查看代码
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define all(x) (x).begin(), (x).end()
#define endl '\n'
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 2e5 + 10;
int main(void)
{
Zeoy;
int t;
cin >> t;
while (t--)
{
int n, k;
cin >> n >> k;
string s;
cin >> s;
s = "*" + s;
int cnt = 0;
for (int i = 1; i <= n; ++i)
cnt += (s[i] == '1');
int ans = cnt;
for (int i = 0; i <= k - 1; ++i)
{
int sum = 0;
for (int j = i + 1; j <= n; j += k)
{
if (s[j] == '1')
sum++;
else
sum--;
if (sum < 0)
sum = 0;
ans = min(ans, cnt - sum);
}
}
cout << ans << endl;
}
return 0;
}