失眠网 > Sasha and a Bit of Relax K倍区间 (前缀和异或前缀和计数思维)

Sasha and a Bit of Relax K倍区间 (前缀和异或前缀和计数思维)

时间：2020-03-28 18:17:28

(29条消息) CodeForces - 1109A Sasha and a Bit of Relax(思维+异或和，好题)_Frozen_Guardian的博客-CSDN博客

Sasha and a Bit of Relax - CodeForces 1109A - Virtual Judge ()

题意:思路:很容易想到前缀和,且这是一道计数题,不需要知道具体的每对情况,所以这里我选择考虑以区间右端点来记录每一种情况,想要构成r-l+1为偶数,那么区间的左右端点必然是同奇偶的,那么我们记录区间右端点的时候,每个右端点都可以和之前所有同奇偶的l组合成一个答案,记录答案即可

ans可能爆int

cnt[0][0]初始化为1:偶数的情况可以和左区间为0的情况组成一组答案,所以一开始只要出现了前缀异或为0的偶数右端点的时候是有答案的,所以提前初始化为1

#include<bits/stdc++.h>#define x first#define gcfx main#define y second#define mak make_pair#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)#define debug(a) cout<<a<<'\n'#define endl '\n'#define umap unordered_mapusing namespace std;typedef long long LL;typedef unsigned long long ULL;typedef pair<int,int> PII;const int N=3e5+10,M=1,inf=0x3f3f3f3f,mod=1e9+7;int n;LL a[N];LL cnt[2][(1<<20)+10];int gcfx(){IOS;cin>>n;int sum=0;LL res=0;cnt[0][0]=1;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++){sum=sum^a[i];res+=cnt[i%2][sum];cnt[i%2][sum]++;}cout<<res<<endl;return 0;}

1230. K倍区间 - AcWing题库

解法如上

#include<bits/stdc++.h>using namespace std;const int N=1e5+10;typedef long long LL;int n,k;LL a[N],cnt[N],s[N];int main(){cin>>n>>k;cnt[0]=1;long long res=0;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) s[i]=s[i-1]+a[i];for(int i=1;i<=n;i++){res+=cnt[s[i]%k];cnt[s[i]%k]++;}cout<<res<<endl;return 0;}