A. XORinacci

题意： f(0) = a, f(1) = b, f(n) = f(n-1)^f(n-2), 求f(n)
思路： 每三个数字一个循环

/* Algorithm: Author: anthony1314 Creat Time: Time Complexity: */

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <stack>
#include <cmath>
#include <deque>
#include <queue>
#include <list>
#include <set>
#include <map>
#define line printf("---------------------------\n")
#define mem(a, b) memset(a, b, sizeof(a))
#define pi acos(-1)
using namespace std;
typedef long long ll;
typedef double db;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int maxn = 2000+10;

void add(int &x, int y){
	x = (x + y) % mod;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int a, b, n, t;
	for(cin>>t; t; t--) {
		cin>>a>>b>>n;
		if(n % 3 == 0)cout<<a<<endl;
		else if(n % 3 == 1) cout<<b<<endl;
		else cout<<(a^b)<<endl;
	}

	return 0;
}

B. Uniqueness

题意： 你可以删除长度不超过2000的数字中的任意一段，使得剩下的数字每个数字都唯一，请问最小的删除的长度
思路： 先对所有的数字离散化，然后枚举符合的左端点，根据左端点枚举符合的右端点，取最小值

/* Algorithm: Author: anthony1314 Creat Time: Time Complexity: */

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <stack>
#include <cmath>
#include <deque>
#include <queue>
#include <list>
#include <set>
#include <map>
#define line printf("---------------------------\n")
#define mem(a, b) memset(a, b, sizeof(a))
#define pi acos(-1)
using namespace std;
typedef long long ll;
typedef double db;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int maxn = 2000+10;

void add(int &x, int y){
	x = (x + y) % mod;
}
int a[maxn], b[maxn], vis[maxn];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n, ans = 1e9;
	cin>>n;
	for(int i = 1; i <= n; i++){
		cin>>a[i], b[i] =a[i];
	}
	sort(b + 1, b + 1 + n);
	for (int i = 1; i <= n; i++){
		a[i] = lower_bound(b + 1, b + 1 + n, a[i]) - b;
	}
	for(int i = 0; i <= n; i++){//0 表示前面的全部截掉 
		mem(vis, 0);
		bool ok = 1;
		for(int j = 1; j <= i & ok; j++){
			if(vis[a[j]]){
				ok = 0;
			}else {
				vis[a[j]] = 1;
			}
		}
		if(!ok){//1~i 有重复的数字 
			break; 
		}
		int r = i;
		for(int j = n; j > i; j--){
			if(vis[a[j]]){
				r = j;
				break;
			}else {
				vis[a[j]] = 1;
			}
		}
		ans = min(ans, r-i);
	}
	cout<<ans<<endl;
	return 0;
}

C. Magic Grid

题意： 你要构造一个n*n的矩阵，使得每一行每一列都异或和相同，数字为0到 n^2 -1

思路： 将 n * n 的矩阵构造出若干个4 * 4的矩阵 ,连续的四个自然数异或和为0，4个相差为4的自然数也为0

0 1 2 3 
4 5 6 7 
8 9 10 11
12 13 14 15 

/* Algorithm: Author: anthony1314 Creat Time: Time Complexity: */

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <stack>
#include <cmath>
#include <deque>
#include <queue>
#include <list>
#include <set>
#include <map>
#define line printf("---------------------------\n")
#define mem(a, b) memset(a, b, sizeof(a))
#define pi acos(-1)
using namespace std;
typedef long long ll;
typedef double db;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int maxn = 2000+10;

void add(int &x, int y) {
	x = (x + y) % mod;
}
int a[maxn][maxn];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin>>n;
	int x = 0;
	for(int i = 0; i < n; i += 4) {
		for(int j = 0; j < n; j += 4) {
			for(int ii = 0; ii < 4; ii++) {
				for(int jj = 0; jj < 4; jj++) {
					a[i+ii][j+jj] = x++;
				}
			}
		}
	}
	for(int i = 0; i < n; i++) {
		for(int j = 0; j < n; j++) {
			if(j == n-1) cout<<a[i][j]<<endl;
			else cout<<a[i][j]<<" ";
		}
	}

	return 0;
}

D.Restore Permutation

题意： 给出一个排列处理后的结果，每一位为该数字前面比他小的数字的和现在要你还原该排列
思路： 线段树查询，首先线段树预处理，我是理解成把1到i的前缀和先做好，然后从后往前查询该点的和为一到i的那个数的前缀和，每次查询完都更新一下，不知道这种写法叫什么，听群里dalao说叫线段树持久化？？

/* Algorithm: Author: anthony1314 Creat Time: Time Complexity: */

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <stack>
#include <cmath>
#include <deque>
#include <queue>
#include <list>
#include <set>
#include <map>
#define line printf("---------------------------\n")
#define mem(a, b) memset(a, b, sizeof(a))
#define pi acos(-1)
using namespace std;
typedef long long ll;
typedef double db;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;
const int maxn = 200000+10;

void add(int &x, int y) {
	x = (x + y) % mod;
}
ll sum[maxn], tree[maxn<<2];
int a[maxn];
void update(int root, int l, int r, int pos, int val) {
	tree[root] += val;
	if(l == r) return ;
	int mid = (l + r)>>1;
	if(pos <= mid) {
		update(root<<1, l, mid, pos, val);
	} else {
		update(root<<1|1, mid+1, r, pos, val);
	}
}
int query(int root, int l, int r, ll k) {
	if(l == r) {
		return l;
	}
	int mid = (l + r) / 2;
	if(k >= tree[root<<1]) {
		return query(root<<1|1, mid+1, r, k-tree[root<<1]);
	} else {
		return query(root<<1, l, mid, k);
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin>>n;
	for(int i = 1; i <= n; i++) {
		cin>>sum[i];
		update(1, 1, n, i, i);
	}
	for(int i = n; i > 0; i--) {
		a[i] = query(1, 1, n, sum[i]);
		update(1, 1, n, a[i], -a[i]);
	}
	for(int i = 1; i <= n; i++) {
		cout<<a[i]<<" ";
	}
	return 0;
}

E.F 待补