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代码

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn=1e5+;

 int n,m;

 char s[maxn];

 queue<int >q;

 int F()///将0变成1的最大长度

 {

     while(!q.empty())

         q.pop();

     int cnt=;

     int pre=;

     int ans=;

     int cur=m;

     for(int i=;i <= n;++i)

     {

         if(s[i] == '')

             cnt++;

         else if(cur > )

         {

             cur--;

             cnt++;

             q.push(cnt-pre);///cnt-pre:两个0之间的1的个数+1

             pre=cnt;

         }

         else if(!q.empty())///反悔操作

         {

             int tmp=q.front();

             q.pop();

             cnt -= tmp;

             pre -= tmp;

             cnt++;

             q.push(cnt-pre);

             pre=cnt;

         }

         else

             cnt=;

         ans=max(ans,cnt);

     }

     return ans;

 }

 int Solve()

 {

     int ans=F();

     for(int i=;i <= n;++i)///0,1互换，重用F()

         s[i]=s[i] == '' ? '':'';

     ans=max(ans,F());

     return ans;

 }

 int main()

 {

 //    freopen("C:\\Users\\hyacinthLJP\\Desktop\\in&&out\\contest","r",stdin);

     int test;

     scanf("%d",&test);

     while(test--)

     {

         scanf("%d%d",&n,&m);

         scanf("%s",s+);

         printf("%d\n",Solve());

     }

     return ;

 }

•思路2（暴力）

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

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn=1e5+;

 int n,m;

 char s[maxn];

 int F()

 {

     int ans=;

     int e=;

     int cur=m;

     for(int i=;i <= n;++i)

     {

         e=max(e,i);

         while(e <= n)

         {

             if(s[e] == '')

             {

                 if(cur > )

                     cur--;

                 else

                     break;

             }

             e++;

         }

         ///以i位置为左端点，经过m次操作，最远到达e-1位置

         ans=max(ans,e-i);

         if(s[i] == '')

             cur=min(,m);

     }

     return ans;

 }

 int Solve()

 {

     int ans=F();

     for(int i=;i <= n;++i)

         s[i]=(s[i] == '') ? '':'';

     ans=max(ans,F());

     return ans;

 }

 int main()

 {

 //    freopen("C:\\Users\\hyacinthLJP\\Desktop\\in&&out\\contest","r",stdin);

     int test;

     scanf("%d",&test);

     while(test--)

     {

         scanf("%d%d",&n,&m);

         scanf("%s",s+);

         printf("%d\n",Solve());

     }

     return ;

 }

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

待写

巴特西

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

F.Black&White

•题意

•思路1（反悔操作）

•AC代码

•思路2（暴力）

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

最新文章

热门文章