CF1109A Sasha and a Bit of Relax 题解

· · 题解

既然过了就写一篇题解吧。

题意已经有翻译了，就不必赘述。这里讲一些这道题的特点。

异或和

首先 x \oplus x = 0 以及 x \oplus 0 = x 这两个公式是必要的，而我们设

sum_1=a_l \oplus a_{l+1} ... \oplus a_{(l+r-1)/2} sum_2=a_{(l+r)/2} \oplus a_{(l+r+1)/2} ... \oplus a_{l+r}

由题意得 sum_1=sum_2 ，则有 sum_1 \oplus sum_2 =0

而异或运算满足加法性质，即 (a \oplus b) \oplus c = a \oplus (b \oplus c) 的性质。

那么我们需要查找的区间也就是满足 \bigoplus\limits_{i=l}^rval_i=0 的区间即可。我们又有 x \oplus x=0 那么对于一个区间满足上述式子，

记 sum_i 为该数列的异或前缀和，则有 sum_{l-1} \oplus sum_r =0 满足上述式子，也就是 sum_{l-1}=sum_r 的区间，用 map 来存储即可。

记得判断 (r-l+1)\mod 2=0 可以用位运算 (r-l+1)&1==0 来代替。

最后几个点比较大，记得开 long long 。否则会 WA

省略预处理代码
using namespace std;
const int MAXN=3e5+1;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
ll n,val,sum[MAXN];
ll res;
map<pair<ll,ll>,ll>M;
int main()
{
    // freopen("segment.in","r",stdin);
    // freopen("segment.out","w",stdout);
    read(n);
    ++M[make_pair(0,1)];
    for(int i=1;i<=n;++i)
    {
        read(val);
        sum[i]=sum[i-1]^val;
        ll x=!(i&1);
        res+=M[make_pair(sum[i],x)];
        ++M[make_pair(sum[i],x)];
    }
    printf("%lld",res);
    return 0;
}
/*
5
1 2 3 4 5
6
3 2 2 3 7 6

x^x=0
x^0=x
*/

上述代码是用 STL 库中的 map 写的，下面给出手写代码。因为其 val 值最大是 2^{20} 所以所有的异或和不会超过 2^{21}-1 所以数组开那么大就合适了。维护一个 bool 值表示当前位置是奇数还是偶数，然后加答案后统计该位置所对应的 (r-l+1) \mod 2 = 0 的位置后统计答案即可。

依然省略头文件
using namespace std;
const int MAXN=3e5+1;
const int MAXS=1<<21;
template<class T>
inline void read(T &x)
{
    x=0;
    char ch=gh(),t=0;
    while(ch<'0'||ch>'9') t|=ch=='-',ch=gh();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=gh();
    if(t) x=-x;
}
ll n,val,sum[MAXN];
ll res,ans[MAXS][2];
int main()
{
    // freopen("segment.in","r",stdin);
    // freopen("segment.out","w",stdout);
    read(n);
    ++ans[0][1];
    for(int i=1;i<=n;++i)
    {
        read(val);
        sum[i]=sum[i-1]^val;
        ll x=!(i&1);
        res+=ans[sum[i]][x];
        ++ans[sum[i]][x];
    }
    printf("%lld",res);
    return 0;
}
/*
5
1 2 3 4 5
6
3 2 2 3 7 6

x^x=0
x^0=x
*/

欢迎来蒟蒻的blog来 cue 。