2019年湘潭大学程序设计竞赛（重现赛）F.Black&White

F.Black&White

•题意

　　操作 m 次后，求连续的1或连续的0的最大值，每次操作只能反转一个位置；

•思路1（反悔操作）

　　定义队列q：依次存放两个零之间的1的个数+1；

　　首先求解1最大的连续值；

　　假设 n=15 , m=3 , s如下图所示；

　　

　　①来到第一个0位置，m=3>0，反转，m--，q.push(3)，cnt=3；

　　②来到第二个0位置，m=2>0，反转，m--，q.push(2)，cnt=5；

　　③来到第三个0位置，m=1>0，反转，m--，q.push(1)，cnt=6；

　　④来到第四个0位置，m=0，没法反转这个0，需要删除前面的一次操作来反转当前的位置；

　　删除哪个操作呢？

　　当然是最早的那次操作了，即将第一个零位置反转回0，并将当前位置反转；

　　将第一个0位置反转回0后，图示紫圈①对答案就没有贡献了，需要删掉 cnt=6-3=3；

　　 q.push(3)，cnt=6；

　　其余同理；

　　综上：

　　①m > 0，直接进行反转操作，并记录将此位置反转后，此位置与其前一个零之间的连续的1的个数；

　　②m = 0，反悔操作，将最早的一次反转操作删除，反转此位置，并记录；

　　求解连续的 0 位置，只需将 s 中的 0,1 互换，然后在跑一边上述代码即可；

　　输出两者的最大值；

•AC代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1e5+50;
 4 
 5 int n,m;
 6 char s[maxn];
 7 
 8 queue<int >q;
 9 int F()///将0变成1的最大长度
10 {
11     while(!q.empty())
12         q.pop();
13 
14     int cnt=0;
15     int pre=0;
16     int ans=0;
17     int cur=m;
18     for(int i=1;i <= n;++i)
19     {
20         if(s[i] == '1')
21             cnt++;
22         else if(cur > 0)
23         {
24             cur--;
25             cnt++;
26             q.push(cnt-pre);///cnt-pre:两个0之间的1的个数+1
27             pre=cnt;
28         }
29         else if(!q.empty())///反悔操作
30         {
31             int tmp=q.front();
32             q.pop();
33             cnt -= tmp;
34             pre -= tmp;
35             cnt++;
36             q.push(cnt-pre);
37             pre=cnt;
38         }
39         else
40             cnt=0;
41         ans=max(ans,cnt);
42     }
43     return ans;
44 }
45 int Solve()
46 {
47     int ans=F();
48     for(int i=1;i <= n;++i)///0,1互换，重用F()
49         s[i]=s[i] == '1' ? '0':'1';
50     ans=max(ans,F());
51     return ans;
52 }
53 int main()
54 {
55 //    freopen("C:\Users\hyacinthLJP\Desktop\in&&out\contest","r",stdin);
56     int test;
57     scanf("%d",&test);
58     while(test--)
59     {
60         scanf("%d%d",&n,&m);
61         scanf("%s",s+1);
62         printf("%d
",Solve());
63     }
64     return 0;
65 }

View Code

•思路2（暴力）

　　枚举每个位置，判断从以当前位置为开始，经过 m 次操作最长的连续的 1 的个数；

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1e5+50;
 4 
 5 int n,m;
 6 char s[maxn];
 7 
 8 int F()
 9 {
10     int ans=0;
11     int e=1;
12     int cur=m;
13     for(int i=1;i <= n;++i)
14     {
15         e=max(e,i);
16         while(e <= n)
17         {
18             if(s[e] == '0')
19             {
20                 if(cur > 0)
21                     cur--;
22                 else
23                     break;
24             }
25             e++;
26         }
27         ///以i位置为左端点，经过m次操作，最远到达e-1位置
28         ans=max(ans,e-i);
29         if(s[i] == '0')
30             cur=min(1,m);
31     }
32     return ans;
33 }
34 int Solve()
35 {
36     int ans=F();
37     for(int i=1;i <= n;++i)
38         s[i]=(s[i] == '1') ? '0':'1';
39     ans=max(ans,F());
40     return ans;
41 }
42 int main()
43 {
44 //    freopen("C:\Users\hyacinthLJP\Desktop\in&&out\contest","r",stdin);
45     int test;
46     scanf("%d",&test);
47     while(test--)
48     {
49         scanf("%d%d",&n,&m);
50         scanf("%s",s+1);
51         printf("%d
",Solve());
52     }
53     return 0;
54 }

View Code

•思路3（二分+前缀和）

待写