Codeforces Round #650 (Div. 3)

Codeforces Round #650 (Div. 3)

题目链接

题意：

给定01字串，若相邻的1之间0的个数大于等于k,是有效的社交距离。给定一个01字串，将其中的0变成1,还能保持有效的社交距离，求最多的变换次数。

思路：

如果只有零，那么在第一个位置添加一个1，然后顺序隔着一个k补一个0。如果有一，看能不能在第一个位置补0，然后顺序找1，每次找到1就重新开始数0然后数过足够的0之后就开始添0

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const int N=2e5+7;
const int mod=998244353;
const int inf=0x7fffffff;
const double pi=3.1415926535;
using namespace std;
char s[N];
int sum[N];
signed main()
{int t;cin>>t;while(t--){int n,k,cnt=0,i,l,r;cin>>n>>k;cin>>s+1;for(i=1;i<=n;i++){sum[i]=sum[i-1]+s[i]-'0';}i=1;while(i<=n){if(s[i]=='0'){if(i==1){r=min(n,i+k);if(sum[r]-sum[i]==0){s[i]='1';cnt++;i+=k;}}else if(i==n){l=max(1ll,i-k);if(sum[i-1]-sum[l-1]==0){s[i]='1';cnt++;i+=k;}}else{l=max(1ll,i-k),r=min(n,i+k);if(sum[i-1]-sum[l-1]==0&&sum[r]-sum[i]==0){s[i]='1';cnt++;i+=k;}}}i++;}cout<<cnt<<endl;}return 0;
}