CF1719.

A. Chip Game

根据 \(n\) 和 \(m\) 的奇偶性判断即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
int t, n, m;
void solve() {
	n=read(), m=read();
	if(m%2==0) {
		if(n%2) puts("Burenka");
		else puts("Tonya");
	} else {
		if(n%2) puts("Tonya");
		else puts("Burenka");
	}
}
signed main() {
	t=read();
	while(t--) solve();
}

B. Mathematical Circus

如果 \(k\) 是奇数，那么奇数加奇数为偶数，最小是 \(2\)，而最小的偶数也是 \(2\)，因此只要将奇数 \(i\) 和偶数 \(i+1\) 配对即可。

否则，如果 \(k \equiv 2 \pmod 4\)，那么只要将一个模 \(4\) 为 \(2\) 的偶数加上 \(k\)，就一定是 \(4\) 的倍数，与任意奇数配对即可。

否则，一定有 \(4 \mid k\)，因此原来不是 \(4\) 的倍数的数无法转化成 \(4\) 的倍数，最终一定存在若干奇数无法配对。无解

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
const int N=2e5+5;
int t, n, k;
void solve() {
	n=read(), k=read();
	if(k&1) {
		puts("Yes");
		for(int i=1;i<=n;i+=2) printf("%lld %lld\n",i,i+1);
	} else if(k%4==2) {
		puts("Yes");
		bool cur=0;
		for(int i=1;i<=n;i+=2) {
			if(!cur) printf("%lld %lld\n",i+1,i);
			else printf("%lld %lld\n",i,i+1);
			cur^=1;
		}
	} else puts("No");
}
signed main() {
	t=read();
	while(t--) solve();
}

C. Fighting Tournament

很容易预处理出前 \(n\) 局比赛中，第 \(i\) 个人赢了的比赛。

注意到 \(\{a\}\) 是一个排列，那么比完前 \(n\) 局后，最终一定是能力为 \(n\) 的人在队头，且其他人不会再赢任何一场比赛，胜利者只会是他。

模拟这个过程即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
const int N=1e5+5;
int t, n, q, a[N];
vector<int> p[N];
deque<int> d;
#define pb push_back
#define pf push_front
void solve() {
	n=read(), q=read();
	d.clear();
	for(int i=1;i<=n;++i) a[i]=read(), d.pb(i), p[i].clear();
	for(int i=1;i<=n;++i) {
		int x=d.front(); d.pop_front();
		int y=d.front(); d.pop_front();
		if(a[x]<a[y]) swap(x,y);
		d.pf(x), d.pb(y);
		p[x].pb(i);
	}
	while(q--) {
		int x=read(), k=read();
		int ans=upper_bound(p[x].begin(),p[x].end(),k)-p[x].begin();
        // p[x]是有序的，可以二分查找
		if(a[x]==n&&k>n) ans+=k-n;
		printf("%lld\n",ans);
	}
}
signed main() {
	t=read();
	while(t--) solve();
}

D. Burenka and Traditions

虽然代价式子看起来复杂，但是不难发现，处理区间长度为 \(1,2\) 时，代价为 \(1\)，长度为 \(3,4\) 时，代价为 \(2\)，以此类推。因此可以看作，花费 \(1\) 的代价，处理 \(1\) 或 \(2\) 个数。

因此最多操作次数为 \(n\)，每个数异或上他自己。

设 \(f_i\) 为将 \([1,i]\) 变成全 \(0\) 的最小代价。

什么时候能同时处理两个数？当且仅当在 \(i\) 时，异或前缀和 \(S_i\) 已经出现过了，说明存在某个包含 \(i\) 的区间的异或和为 \(0\)。

设 \(S_j = S_i\)，那么\([j+1,i]\) 每个数都出现了偶数次，通过改变异或顺序就能得到两个相同的数，消去他们代价为 \(1\)。 \[ f_{j} + i - (j+1) + 1 - 1 = f_j - j + i - 1 \]

用std::map记录 \(S_j\) 对应的 \(f_j - j\) 即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
const int N=1e5+5;
int t, n, a[N];
set<int> st;
void solve() {
	n=read();
	for(int i=1;i<=n;++i) a[i]=read();
	int suf=0, ans=0;
	st.clear();
	for(int i=1;i<=n;++i) {
		if(!a[i]||st.count(a[i]^suf)) st.clear(), st.insert(0), suf=0;
		else st.insert(suf), suf^=a[i], ++ans;
	}
	printf("%lld\n",ans);
}
signed main() {
	t=read();
	while(t--) solve();
}

E. Fibonacci Strings

先递推斐波那契数列及其前缀和对应的项数。

对于字符总数 \(sum\)，如果它不是斐波那契数列的某项前缀和，那么无解。

否则找到它的项数 \(m\)，从大到小依次尝试用某一类字符取填充，如果当前最多的字符也达不到要求的个数，那么无解。使用大根堆维护。

如何处理相邻的字符不能相同？对于某一类字符的个数 \(x\)，满足 \(x > fib_i\)，那么填充完之后必然剩下 \(x-fib_i\) 个字符，将其延迟插入堆即可。

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int read() {
	int a=0, f=1; char c=getchar();
	while(!isdigit(c)) {
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)) a=a*10+c-'0', c=getchar();
	return a*f;
}
int t, n, s, f[105];
map<int,int> p;
void init() {
	f[1]=f[2]=1;
	s=2;
	p[1]=1, p[2]=2;
	for(int i=3;i<=100;++i) {
		f[i]=f[i-1]+f[i-2];
		s+=f[i];
		p[s]=i;
	}
}
void solve() {
	n=read();
	priority_queue<int> q;
	int sum=0;
	for(int i=1;i<=n;++i) {
		int x=read();
		sum+=x, q.push(x);
	}
	int m=p[sum];
	if(!m) { puts("NO"); return; }
	int t=-1;
	for(int i=m;i;--i) {
		if(q.empty()) { puts("NO"); return; }
		int x=q.top(); q.pop();
		if(x<f[i]) { puts("NO"); return; }
		if(t!=-1) q.push(t);
        // 延迟入堆，i=m时使用过的字符，到了i=m-2时才能使用
		t=x-f[i];
	}
	puts("YES");
}
signed main() {
	init();
	t=read();
	while(t--) solve();
}