2019 ICPC南昌邀请赛比赛 K. MORE XOR （思维+打表+异或可惜的题）

本文主要是介绍2019 ICPC南昌邀请赛比赛 K. MORE XOR （思维+打表+异或可惜的题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Given a sequence of nn numbers a_1, a_2, \cdots, a_na1,a2,⋯,an and three functions.

Define a function f(l,r)f(l,r) which returns \oplus a[x]⊕a[x] (l \le x \le rl≤x≤r). The \oplus⊕ represents exclusive OR.

Define a function g(l,r)g(l,r) which returns \oplus f(x,y)(l \le x \le y \le r)⊕f(x,y)(l≤x≤y≤r).

Define a function w(l,r)w(l,r) which returns \oplus g(x,y)(l \le x \le y \le r)⊕g(x,y)(l≤x≤y≤r).

You are also given a number of xor-queries. A xor-query is a pair (i, ji,j) (1 \le i \le j \le n1≤i≤j≤n). For each xor-query (i, j)(i,j), you have to answer the result of function w(l,r)w(l,r).

Input

Line 11: t (1 \le t \le 20)t(1≤t≤20).

For each test case:

Line 11: n (1 \le n \le 100000)n(1≤n≤100000).

Line 22: nn numbers a_1, a_2, \cdots, a_n (1 \le a_i \le 10^9)a1,a2,⋯,an(1≤ai≤109).

Line 33: q (1 \le q \le 100000)q(1≤q≤100000), the number of xor-queries.

In the next qq lines, each line contains 22 numbers i, ji,j representing a xor-query (1 \le i \le j \le n)(1≤i≤j≤n).

It is guaranteed that sum of nn and q \le 10^6q≤106.

Output

For each xor-query (i, j)(i,j), print the result of function w(i,j)w(i,j) in a single line.

样例输入复制

样例输出复制

题意:

函数f(l,r)为⊕ai(i∈[l,r])

函数g(l,r) 为⊕f(x,y)(x,y∈[l,r])

函数w(l,r) 为⊕g(x,y)(x,y∈[l,r])

给出q个询问(l,r)要求输出w(l,r)

分析:

对于g(l,r),多列几下我们可以找到规律:

如果r-l为奇数,则g(l,r)=0

如果r-l为偶数,则g(l,r)=l^(l+2)^.......^r

然后根据以上特点,打表找规律

区间长度len与答案关系

len mod 4 = 1时，把mod 4 = 1的位置异或起来
len mod 4 = 2时，把mod 4 = 1和2的位置异或
len mod 4 = 3时，mod 4 = 2的位置异或
len mod 4 = 0时，答案为0

官方题解

#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
#define PI acos(-1)
#define eps 1e-9
#define mp(x,y) make_pair(x,y)
const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
#define LOCALconst int MAXN = 100000+10;
int n;
int a[MAXN];void solve()
{int q;scanf("%d", &q);int l, r;while( q-- ){scanf("%d %d", &l, &r);int all = r-l+1;int ans;if( all%4 == 0 ){ans = 0;}else if( all%4 == 1 ){if( l >= 4 ) ans = a[r]^a[l-4];else ans = a[r];}else if( all%4 == 2 ){if( l >= 3 ) ans = a[r]^a[l-3];else ans = a[r];if( l >= 4 ) ans ^= a[r-1]^a[l-4];else ans ^= a[r-1];}else{if( l >= 3 ) ans = a[r-1]^a[l-3];else ans = a[r-1];}printf("%d\n", ans);}
}int main(int argc, char * argv[]) 
{int t;scanf("%d", &t);while( t-- ){scanf("%d", &n);for(int i = 1; i <= n; i++ ){scanf("%d", &a[i]);if( i >= 4 ){a[i] ^= a[i-4];}}solve();}return 0;
}

队友打表代码

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<iomanip>
#include<list>
#include<map>
#include<queue>
#include<sstream>
#include<stack>
#include<string>
#include<set>
#include<vector>
using namespace std;
#define PI acos(-1.0)
#define pppp cout<<endl;
#define EPS 1e-8
#define LL long long
#define ULL unsigned long long     //1844674407370955161
#define INT_INF 0x3f3f3f3f      //1061109567
#define LL_INF 0x3f3f3f3f3f3f3f3f //4557430888798830399
// ios::sync_with_stdio(false);
// 那么cin, 就不能跟C的 scanf，sscanf, getchar, fgets之类的一起使用了。
const int dr[]={0, 0, -1, 1, -1, -1, 1, 1};
const int dc[]={-1, 1, 0, 0, -1, 1, -1, 1};
int read()//输入外挂
{int ret=0, flag=0;char ch;if((ch=getchar())=='-')flag=1;else if(ch>='0'&&ch<='9')ret = ch - '0';while((ch=getchar())>='0'&&ch<='9')ret=ret*10+(ch-'0');return flag ? -ret : ret;
}
bool check(int x)
{int tem=sqrt(x);if(tem*tem==x)return true;return false;
}
int a[1000];
int main()
{//freopen("D:\\chnegxubianji\\inORout\\in.txt", "r", stdin);//freopen("D:\\chnegxubianji\\inORout\\out.txt", "w", stdout);for(int len=0;len<=20;++len){cout<<"区间长度："<<len+1;memset(a,0,sizeof(a));int i=6;//i表示起点int y=len+i;for(;i<=y;++i){ for(int j=i;j<=y;++j){if((j-i)%2==1)continue;else{for(int k=i;k<=j;k+=2)a[k]++;}}}printf("  [1,%d]  ",y);for(i=1;i<=y;++i){if(a[i]%2==1)cout<<i<<" ";}cout<<endl;}return 0;
}

这篇关于2019 ICPC南昌邀请赛比赛 K. MORE XOR （思维+打表+异或可惜的题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！