A - Sherlock Bones Gym - 101350A-白红宇

A - Sherlock Bones Gym - 101350A

阅读量：4114 次

发布时间：2019-05-25

本文共 1386 字，大约阅读时间需要 4 分钟。

题意：The great dog detective Sherlock Bones is on the verge of a new discovery. But for this problem, he needs the help of his most trusted advisor -you- to help him fetch the answer to this case.

He is given a string of zeros and ones and length N.

Let F(x, y) equal to the number of ones in the string between indices x and yinclusively.

Your task is to help Sherlock Bones find the number of ways to choose indices (i, j, k) such that i < j < k, s_j is equal to 1, and F(i, j) is equal to F(j, k).

思路：这个题其实就可以转化为求区间的个数，其中区间内1的个数为奇数，其实思路还是挺好转化的，但是个人感觉代码写起来技巧性还是很强的。

先根据输入的串s求出区间内1个数的奇偶（根据异或），然后在倒着统计有奇数个1的区间个数，偶数个1的区间个数，最后统计总区间个数，在统计总区间个数的时候注意统计方法，同时注意对字符串的处理方式还有计数方式。

#include 
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        #include
         
          #include
          
           #include 
           
            #include 
            
             using namespace std;const int maxn=2e5+20;int per[maxn];int g[maxn][2];int main(){ int T; cin>>T; while(T--) { memset(per,0,sizeof(per)); memset(g,0,sizeof(g)); int n; cin>>n; string s; cin>>s; for(int i=0; i
             
              =0; i--) { if(per[i]==1) { g[i][1]=g[i+1][1]+1; g[i][0]=g[i+1][0]; } else { g[i][0]=g[i+1][0]+1; g[i][1]=g[i+1][1]; } } s="0"+s; int flag=0; long long ans=0; int last=n+1; for(int i=n; i>0; i--) { if(!flag) { if(s[i]=='1') { flag=1; last=i; } } else { if(per[i-1]==0) { ans+=g[last+1][1]; } else { ans+=g[last+1][0]; } if(s[i]=='1') { last=i; } } } cout<
              
               <

转载地址：http://zbgsi.baihongyu.com/

你可能感兴趣的文章