D. Constructing the Array
题目大意: 给定一个长度为n的全为0的字符串, 每次找出一个长度最大的全为0子区间(如果多个区间长度均为最大值, 则选择最左区间), 若区间长度为奇数, 则将(a[frac{l+r}{2}] := i), 为偶数, 则(a[frac{l+r-1}{2}] := i)
解题思路: 将问题划分为若干个子区间递归求解. 用pair维护每个点的权值以及坐标. 对任意一段全0区间上的中间点, 其权值应为这个点所在区间的左端点减去右端点的差值. 之后对所有点按照权值从小到大进行排序, 最后对排序后的点从1~n赋值即可. 用一个res数组记录答案可以避免pair嵌套pair的情况.
/*
* @Author: Hellcat
* @Date: 2020-05-26 14:30:06
* D. Constructing the Array
* https://codeforces.com/contest/1353/problem/D
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5 + 10;
pair<int, int> a[N];
int res[N];
void build(int l, int r) {
if(l > r) return;
int mid = l+r>>1;
a[mid].first = l - r;
a[mid].second = mid;
build(l, mid-1), build(mid+1, r);
}
int main() {
int T; cin>>T;
while(T--) {
int n; cin>>n;
build(1, n);
sort(a+1, a+n+1);
for(int i = 1; i <= n; i++)
res[a[i].second] = i;
for(int i = 1; i <= n; i++)
cout<<res[i]<<" ";
puts("");
}
}
E. K-periodic Garland
题目大意: 给定一个长度为(n)((1 le n le 10^6))的01字符串, 可以将任意多个0(或1)改为1(或0), 或者不修改. 求出使得字符串满足相邻2个1距离为(k)((1 le k le n)).
解题思路: 找到字符串中的所有1, 遍历0~k个位置, 从中选择一个作为起点, 以k为周期检查相应位置是否为1, 将总共1的个数减去检查到的1的个数即为答案.
/*
* @Author: Hellcat
* @Date: 2020-05-25 14:47:14
*/
#include <bits/stdc++.h>
using namespace std;
int main() {
int T; cin>>T;
while(T--) {
int n, k; cin>>n>>k;
string s; cin>>s;
int cnt = 0;
for(auto i : s) cnt += i=='1';
int ans = cnt;
for(int i = 0; i < k; i++) {
int diff = 0;
for(int j = i; j < n; j += k) {
if(s[j] == '1') diff++;
else diff--;
diff = max(diff, 0);
ans = min(ans, cnt - diff);
}
}
cout<<ans<<endl;
}
}