題目鏈接： http://acm.buaa.edu.cn/problem/439/
題意：給出一個(gè)數(shù)列。求有多少個(gè)區(qū)間[L,R]，使得區(qū)間之內(nèi)的數(shù)字之和不大于K且區(qū)間內(nèi)數(shù)字的抑或值不為0.
思路：首先計(jì)算抑或值為0的區(qū)間個(gè)數(shù)P，則答案為所有合法區(qū)間(即和不大于K)減去P。每次將前面一段和當(dāng)前值抑或，設(shè)為X，記錄之前每個(gè)抑或值的個(gè)數(shù)，假設(shè)前面有個(gè)位置的抑或值也為X,設(shè)那個(gè)位置為a，當(dāng)前位置為b，則[a+1,b]之間的數(shù)字的抑或值為0.然后就是和不大于K，每次累加，累加到當(dāng)前和大于K的時(shí)候減去當(dāng)前連續(xù)段的前面的數(shù)字。
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;
}
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫(xiě)作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
