題目鏈接： http://acm.buaa.edu.cn/problem/439/
題意：給出一個數列。求有多少個區間[L,R]，使得區間之內的數字之和不大于K且區間內數字的抑或值不為0.
思路：首先計算抑或值為0的區間個數P，則答案為所有合法區間(即和不大于K)減去P。每次將前面一段和當前值抑或，設為X，記錄之前每個抑或值的個數，假設前面有個位置的抑或值也為X,設那個位置為a，當前位置為b，則[a+1,b]之間的數字的抑或值為0.然后就是和不大于K，每次累加，累加到當前和大于K的時候減去當前連續段的前面的數字。
map<i64,i64> hash;
i64 a[100005],K;
int n,C;
int main()
{
RD(C);
while(C--)
{
RD(n);
RD(K);
int i;
FOR0(i,n) RD(a[i]);
hash.clear();
hash[0]=0;
int tail=0;
i64 xorsum=0,xortail=0,sum=0,ans=0,all=0;
for(i=0;i<n;i++)
{
sum+=a[i];
xorsum^=a[i];
if(hash.find(xorsum)==hash.end()) hash[xorsum]=1;
else hash[xorsum]=hash[xorsum]+1;
while(sum>K)
{
sum-=a[tail];
xortail^=a[tail];
hash[xortail]=hash[xortail]-1;
tail++;
}
all+=i-tail+1;
if(tail==0) hash[0]++;
else hash[xortail]++;
if(tail<=i) ans+=hash[xorsum]-1;
if(tail==0) hash[0]--;
else hash[xortail]--;
}
PR(all-ans);
}
return 0;
}
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
