2023年多校联训NOIP层测试5

HZOI - Isaac / 2023-08-07 / 原文

2023年多校联训NOIP层测试5

T1 糖果 \(10pts\)

首先考虑一些异或的性质:
- 归零率：\(a⊕a=0\)
- 恒等律：\(a⊕0=a\)
- 交换律：\(a⊕b=b⊕a\)
- 结合律: \(a⊕b⊕c=a⊕(b⊕c)=(a⊕b)⊕c\)
- 自反性(异或的逆运算为它本身): \(a⊕b⊕b=a\)
令 \(sum[i]\) 表示 \(a[0]⊕a[1]⊕a[2]...⊕a[n]\)，进行前缀和优化，然后进行分类讨论
- 若 \(sum[n]=0\) ，利用归零率，说明可以把这些糖果分成两段，使得每段糖果的美味度相同。
- 若 \(sum[n] \ne 0\) ，利用归零率和恒等率，若存在一个 \(l,r\) ，满足 \(1\le l<r \le n\) ，且 \(sum[l]==sum[n],sum[r]==0\) ,说明可以把这些糖果分成三段(分别是 \(1\) ~ \(l\) 和 \(l+1\) ~ \(r\) 和 \(r+1\) ~ \(n\) )，使得每段糖果的美味度相同。

枚举即可，复杂度\(O(Tn)\)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sort stable_sort
#define endl '\n'
int a[100010],sum[100010];
int main()
{
    int t,n,i,j,k,l,r; 
    cin>>t;
    for(i=1;i<=t;i++)
    {
        cin>>n;
        l=r=0;//初始化
        for(j=1;j<=n;j++)
        {
            cin>>a[j];
            sum[j]=sum[j-1]^a[j];
        }
        if(sum[n]==0)
        {
            cout<<"YES"<<endl;
        }
        else
        {
            for(j=1;j<=n;j++)
            {
                if(sum[j]==sum[n])
                {
                    l=j;
                    break;
                }
            }
            for(j=n;j>=1;j--)
            {
                if(sum[j]==0)
                {
                    r=j;
                    break;
                }
            }
            if(l!=0&&r!=0&&l<r)
            {
                cout<<"YES"<<endl;
            }
            else
            {
                cout<<"NO"<<endl;
            }
        }
    }
    return 0;
}