Wannafly挑战赛4

A

签到

B

题意

给一个数列，这个数列中所有区间长度在[L,R]之间并且为偶数的异或和之和 

分析

卡我两天啊，一直都不知道怎么算，看了代码模拟出这种方法才想明白

切入点：按位（二进制位）考虑贡献，枚举每个区间的右端点，我们只要统计出左端点，考虑这一位（二进制位）的贡献，左端点要满足与右端点位置奇偶性不同，用一个前缀xor，算出前i个数，二进制位的奇偶情况，然后根据题意在[L,R]区间，修改一下就好

#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn = 1e5 + 10;
const ll mod = 1e9 + 7;
int a[maxn];
int cnt[2][2];
int n, l, r;

int main()
{
    scanf("%d%d%d", &n, &l ,&r);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        a[i]^=a[i-1];
    }
    if(l&1) l++;
    if(r&1) r--;
    if(l>r)
    {
        cout<<0<<endl;
        return 0;
    }
    ll sum=0;
    for(int i = 0; i <= 31; i++)
    {
        ll ans=0;
        memset(cnt, 0 , sizeof(cnt));
        for(int j = l; j <= n; j++)
        {
            cnt[j&1][(a[j-l]>>i)&1]++;
            ans+=cnt[j&1][!((a[j]>>i)&1)];
           // ans%=mod;
            if(j>=r)
                cnt[j&1][(a[j-r]>>i)&1]--;
        }
        sum = ((sum+(1ll*ans)*(1<<i))%mod)%mod;
        sum%=mod;
    }
    printf("%lld
", (sum+mod)%mod);
    return 0;

}

C.割草机

直接模拟即可，vector大法好

设置一个每行的标记即可