题目
https://codeforces.com/contest/1658/problem/F
长度n的0/1串
找多个不重叠子串满足
- 0/1比例和原串一致
- 长度和为m
范围
m <= n <= 2e5
1s
256MB
题解
Math
https://t.bilibili.com/646605883381383189
- 字符串拼成环
- 长度为m的1的个数,在相邻统计中变化最多为1, 所有的1个数和=m乘总的1的个数, 因此对于长度为m的1的个数 不会都大于目标也不会都小于目标,至少一个等于目标
长度为m的在原数组内则一个, 跨了原数组边界则两个
很明显不满足的我想到了,一个的很好做滑动窗口入门
但是我一直在想怎么证明 两个一定可以, 想了 单测大于小于, 全局不满足,但始终没想到 拼成环就容易搞了, 哎
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| #include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define pb push_back
char s[200010];
int n,m;
void work(){
scanf("%d %d",&n,&m);
scanf("%s",s);
int cnt1 = 0;
rep(i,0,n){
cnt1+=s[i] == '1';
}
if((cnt1 * m ) % n != 0){
printf("-1\n");
return ;
}
int x = (cnt1*m)/n;
int c = 0;
rep(i,0,m){
c += s[i]=='1';
}
rep(i,0,n){
if(c == x){
if(i <= n-m){
printf("1\n");
printf("%d %d\n",i+1,i+m);
}else{
printf("2\n");
printf("%d %d\n",1,m-(n-i));
printf("%d %d\n",i+1,n);
}
return ;
}
c += s[(i+m)%n]=='1';
c -= s[i]=='1';
}
}
int main(){
int t;
cin>>t;
while(t--)work();
return 0;
}
|
总结
Math啊 Math, 我怎么就想不出呢
看jiangly老哥的视频,他只想了15min
参考
官方题解