(打表找规律+前缀异或和)MORE XOR

待我称王封你为后i 2022-02-16 14:02 212阅读 0赞

题目链接：[https://nanti.jisuanke.com/t/38230][https_nanti.jisuanke.com_t_38230]

比赛的时候也在推规律，可惜手动推错了~再者推出来还要用前缀异或和来解决，不然时间复杂度太高，会TLE.

之前不知道用前缀异或和，首先做个小题目：[（前缀异或和）51nod 2128 前缀异或][51nod 2128]

//队友写的打表代码
    #include <bits/stdc++.h>
    using namespace std;
    const int maxn=1e5+10;
    int s[maxn],p[maxn]={0};
    int f(int l,int r)
    {
        int x=0;
        for(;l<=r;l++){
            x^=s[l];
            p[s[l]]++;
        }
    
        return x;
    }
    int g(int l,int r)
    {
        int x=0;
        for(int i=l;i<=r;i++)
            for(int j=i;j<=r;j++)
                x^=f(i,j);
        return x;
    }
    int w(int l,int r)
    {
        int x=0;
        for(int i=l;i<=r;i++)
            for(int j=i;j<=r;j++)
                x^=g(i,j);
        return x;
    }
    int main()
    {
        freopen("in.txt","r",stdin);
        int t;
        scanf("%d",&t);
        while(t--){
            int n,q;
            scanf("%d",&n);
            for(int i=1;i<=n;i++)
                scanf("%d",&s[i]);
            scanf("%d",&q);
            while(q--){
                int l,r;
                memset(p,0,sizeof(p));
                scanf("%d %d",&l,&r);
                //printf("%d\n",w(l,r));
                w(l,r);
                printf("q=%d ",20-q);
                for(int i=1;i<=n;i++)
                    if(p[i])
                    printf("%d:%d  ",i,p[i]%2);
                printf("\n");
            }
        }
        return 0;
    }
    /*
    输入数据：
    1
    20
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
    20
    1 1
    1 2
    1 3
    1 4
    1 5
    1 6
    1 7
    1 8
    1 9
    1 10
    1 11
    1 12
    1 13
    1 14
    1 15
    1 16
    1 17
    1 18
    1 19
    1 20
    
    */

打表可以看出是以4为周期的，0表示这个数不参与异或，1表示这个数要参与异或。

mod4余1:1000

mod4余2:1100

mod4余3:0100

mod4余0:0000

题目AC代码：

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=1e5+10;
    int a[maxn];
    
    
    int main(){
    	int t;
    	scanf("%d",&t);
    	while(t--){
    		int n,q,l,r;
    		scanf("%d",&n);
    		for(int i=1;i<=n;i++){
    			scanf("%d",&a[i]);
    		}
    		for(int i=5;i<=n;i++){
                a[i]^=a[i-4];   //因为答案是4为周期的，所以我们将mod4余数相等的相异或
    		}
    		scanf("%d",&q);
    		while(q--){
    			scanf("%d%d",&l,&r);
    			int res=0;
    			if((r-l+1)%4==1){
    				res^=a[r];
                    if(l>4) res^=a[l-4];  //1000
    			}else if((r-l+1)%4==2){
                    res^=a[r]^a[r-1];
                    if(l>=3) res^=a[l-3];  //1100
                    if(l>=4) res^=a[l-4];
    			}else if((r-l+1)%4==3){   //0100
    				res^=a[r-1];
    				if(l>=3) res^=a[l-3];
    			}
    			printf("%d\n",res);
    		}
    	}
    
    
    	return 0;
    }

[https_nanti.jisuanke.com_t_38230]: https://nanti.jisuanke.com/t/38230
[51nod 2128]: https://blog.csdn.net/qq_37275680/article/details/89435205