Gym101350 J Lazy Physics Cat

参考博客：https://blog.csdn.net/lengqiu2015/article/details/76855681#reply

题意

给出一个长度为n的01串我们定义F(x,y)是区间[x,y]内1的数量请你计算有多少三元组（i,j,k）满足i<j<k，s[j]是1而且F[i,j]等于F[j,k] n<=200000

分析

一开始一直在想怎么枚举j然后计算方案数，发现这样我只能写O(N^2),GG。

原来可以把题目转化一下，问这个串内有多少区间内有奇数个1（单独一个1或者1000或者0001这一类的都属于非法的）。

然后可以用dp来解决（好像也可以不用dp？）

dp[i][0]是以i为结尾的区间含有奇数个1的有多少

dp[i][1]是以i为结尾的区间含有偶数个1的有多少

那么转移就比较好想了：

如果i是1，那么dp[i][1]=dp[i-1][0],dp[i][0]=dp[i-1][1]+1(奇数变偶数，偶数变奇数)

如果i是0，那么dp[i][1]=dp[i-1][1],dp[i][0]=dp[i-1][0]+1

这样把所有的dp[i][0]加起来，再减掉非法的区间就可以了~

这个题要开long long。

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <iostream>

 using namespace std;

 const int maxn=+;

 char a[maxn];

 long long dp[maxn][];

 int n,T;

 long long ans;

 int main(){

     scanf("%d",&T);

     for(int t=;t<=T;t++){

         scanf("%d",&n);

         scanf("%s",a+);

         ans=;

         memset(dp,,sizeof(dp));

         if(a[]==''){

             dp[][]=;

             dp[][]=;

         }

         if(a[]==''){

             dp[][]=;

             dp[][]=;

         }

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

             if(a[i]==''){

                 dp[i][]=dp[i-][]+;

                 dp[i][]=dp[i-][];

             }else if(a[i]==''){

                 dp[i][]=dp[i-][];

                 dp[i][]=dp[i-][]+;

             }

         }

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

             ans+=dp[i][];

         }

         //下面去掉10000

         long long res=,all=;

         for(int i=n;i>=;i--){

             if(a[i]==''){

                 all+=res;

                 res=;

             }

             else

                 res++;

         }

         ans-=all;

         //下面去掉00001

         res=,all=;

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

             if(a[i]==''){

                 all+=res;

                 res=;

             }

             else

                 res++;

         }

         ans-=all;

         cout<<ans<<endl;

     }

     return ;

 }

巴特西

Gym101350 J Lazy Physics Cat

最新文章

热门文章