Preface

懒狗闪总好久没打CF了，而且桂林回来后也没摸过键盘了，今天打的那叫一个手生

本来都不知道今天晚上有比赛，后面ztc叫我打我想着反正不熄灯就小号摆着打

最后赛后10min写出E题就很难受，感觉状态正常点就能出5个题了（或者来个2h15min的场就好了）

A. Treasure Chest

签，刚开始没看见\(x,y>0\)还以为有两边，以为要大分讨，后面发现我是傻逼

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
int t,x,y,k;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		scanf("%d%d%d",&x,&y,&k);
		if (x>=y) printf("%d\n",x); else
		{
			if (x+k>=y) printf("%d\n",y); else printf("%d\n",x+k+2*(y-(x+k)));
		}
	}
	return 0;
}

B. Points and Minimum Distance

不难发现将所有数从小到大排序后，令第\(i\)个点的坐标为\((a_i,a_{i+n})\)一定是最优的

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=205;
int t,n,a[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i; for (scanf("%d",&n),i=1;i<=2*n;++i) scanf("%d",&a[i]);
		sort(a+1,a+2*n+1); printf("%d\n",a[n]-a[1]+a[2*n]-a[n+1]);
		for (i=1;i<=n;++i) printf("%d %d\n",a[i],a[i+n]);
	}
	return 0;
}

C. Torn Lucky Ticket

这题思路不难，但实现的话有一些细节的说

我实现的时候选择钦定后面计算的串长度一定大于等于前面的串，这样我们就可以把要分出去的部分直接计算了，剩下的就是开个桶统计了

代码看似很长，其实都是复制粘贴的，因为要做两个方向以及把所有串reverse一遍再做一次

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int n,a[N],len[N],pfx[N][7],rpfx[N][7],bkt[7][50]; LL ans; char s[10];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%d",&n),i=1;i<=n;++i)
	{
		scanf("%s",s+1); len[i]=strlen(s+1);
		for (j=1;j<=len[i];++j) pfx[i][j]=pfx[i][j-1]+s[j]-'0';
		for (j=1;j<=len[i];++j) rpfx[i][j]=rpfx[i][j-1]+s[len[i]-j+1]-'0';
	}
	auto S=[&](CI id,CI l,CI r)
	{
		return pfx[id][r]-pfx[id][l-1];
	};
	for (memset(bkt,0,sizeof(bkt)),i=1;i<=n;++i)
	{
		for (j=1;j<=len[i];++j) if ((j+len[i])%2==0)
		{
			int t=(j+len[i])/2-j,fr=S(i,1,t),bk=S(i,t+1,len[i]);
			if (bk-fr>=0) ans+=bkt[j][bk-fr];
		}
		++bkt[len[i]][S(i,1,len[i])];
	}
	for (memset(bkt,0,sizeof(bkt)),i=n;i>=1;--i)
	{
		for (j=1;j<len[i];++j) if ((j+len[i])%2==0)
		{
			int t=(j+len[i])/2-j,fr=S(i,1,t),bk=S(i,t+1,len[i]);
			if (bk-fr>=0) ans+=bkt[j][bk-fr];
		}
		++bkt[len[i]][S(i,1,len[i])];
	}
	auto R=[&](CI id,CI l,CI r)
	{
		return rpfx[id][r]-rpfx[id][l-1];
	};
	for (memset(bkt,0,sizeof(bkt)),i=1;i<=n;++i)
	{
		for (j=1;j<=len[i];++j) if ((j+len[i])%2==0)
		{
			int t=(j+len[i])/2-j,fr=R(i,1,t),bk=R(i,t+1,len[i]);
			if (bk-fr>=0) ans+=bkt[j][bk-fr];
		}
		++bkt[len[i]][R(i,1,len[i])];
	}
	for (memset(bkt,0,sizeof(bkt)),i=n;i>=1;--i)
	{
		for (j=1;j<len[i];++j) if ((j+len[i])%2==0)
		{
			int t=(j+len[i])/2-j,fr=R(i,1,t),bk=R(i,t+1,len[i]);
			if (bk-fr>=0) ans+=bkt[j][bk-fr];
		}
		++bkt[len[i]][R(i,1,len[i])];
	}
	return printf("%lld",ans+n),0;
}

D. XOR Construction

想到就很简单的一个题

首先不难发现令\(b_1=x\)，\(a_i\)的前缀异或和数组为\(pfx_i\)，则\(b_i=x\oplus pfx_{i-1}\)

那么我们可以先求出所有的\(pfx_i\)，现在的问题就变成找一个合适的\(x\)使得给这些数都异或上\(x\)后得到的是一个\(0\sim n-1\)的排列

先来考虑个必要条件，我们可以先枚举某个二进制位\(k\)，求出\(0\sim n-1\)在这一位上\(1\)的个数，然后再求出\(pfx_0\sim pfx_{n-1}\)在这一位上\(1\)的个数

很显然如果二者相等则\(x\)的第\(k\)位为\(0\)，否则第\(k\)位为\(1\)

而由于保证一定有解，我们这样确定出来的符合必要性的答案就一定满足要求

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=200005;
int n,a[N],pfx[N],c[30][2],t[30][2];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%d",&n),i=1;i<n;++i) scanf("%d",&a[i]),pfx[i]=pfx[i-1]^a[i];
	//for (i=1;i<=n;++i) printf("%d%c",pfx[i]," \n"[i==n]);
	for (i=0;i<n;++i) for (j=0;j<30;++j) ++t[j][(i>>j)&1];
	for (i=1;i<=n;++i) for (j=0;j<30;++j) ++c[j][(pfx[i]>>j)&1];
	int st=0; for (i=0;i<30;++i) if (t[i][0]!=c[i][0]) st|=(1<<i);
	for (i=1;i<=n;++i) printf("%d ",st^pfx[i-1]);
	return 0;
}

E. Infinite Card Game

思路啥的都很自然的一个题，不过由于码力退化了（就是不写好写的拓扑排序）花了1h也没写完，太菜太菜

首先考虑双方的最优策略都很显然，当对方出了某张牌后，我方的最优策略一定是找一张能干掉对方的牌中防御力最大的牌

那么我们可以给双方的每张牌都找一张（或不存在）对方的牌，表示当我方出了这张牌后对方会出的牌，就可以得到一个博弈的转移图

不难发现可以在上面跑一个类似于对抗搜索的东西，当一个点没有出点时就是必胜态，而当一个点的所有后继都是必胜态时它就是必败态

而这道题比较特殊因为有平局状态的存在，那么我们先暴力搜出图中所有的环将它们的状态置为平局，并在对抗搜索的过程中将所有后继状态为平局的点的状态也置为平局即可

而找一张牌的后继状态很显然可以给两个数组分别排序后two points处理，同时要注意将牌面相同的牌合成一个不然可能会出现某些问题的说

#include<cstdio>
#include<iostream>
#include<utility>
#include<vector>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<set>
#include<array>
#include<random>
#include<bitset>
#include<ctime>
#include<limits.h>
#include<assert.h>
#include<unordered_set>
#include<unordered_map>
#define RI register int
#define CI const int&
#define mp make_pair
#define fi first
#define se second
#define Tp template <typename T>
using namespace std;
typedef long long LL;
typedef long double LDB;
typedef unsigned long long u64;
typedef __int128 i128;
typedef pair <int,int> pi;
typedef vector <int> VI;
typedef array <int,3> tri;
const int N=600005;
struct ifo
{
	int atk,def,id;
}a[N],b[N]; int t,n,m,suf[N],idx,nxt[N],vis[N],pre[N],cnt[N],ans[N],tim[N]; map <pi,int> rst;
inline void DFS1(CI now,CI CLK)
{
	vis[now]=1; tim[now]=CLK; if (!nxt[now]) return;
	if (!vis[nxt[now]]) pre[nxt[now]]=now,DFS1(nxt[now],CLK); else
	{
		if (tim[nxt[now]]!=CLK) return;
		for (int x=now;x!=nxt[now];x=pre[x])
		ans[x]=-2; ans[nxt[now]]=-2;
	}
}
inline int DFS2(CI now)
{
	if (ans[now]!=-1) return ans[now];
	if (DFS2(nxt[now])==-2) return ans[now]=-2;
	if (!nxt[now]) return ans[now]=1;
	return ans[now]=DFS2(nxt[now])^1;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%d",&t);t;--t)
	{
		RI i,j; scanf("%d",&n); idx=0; rst.clear();
		for (i=1;i<=n;++i) cnt[i]=0;
		for (i=1;i<=n;++i) scanf("%d",&a[i].atk);
		for (i=1;i<=n;++i) scanf("%d",&a[i].def);
		for (i=1;i<=n;++i)
		{
			if (rst.count(pi(a[i].atk,a[i].def))) ++cnt[rst[pi(a[i].atk,a[i].def)]];
			else cnt[rst[pi(a[i].atk,a[i].def)]=++idx]=1;
		}
		n=0; for (auto [it,id]:rst) ++n,a[n].atk=it.fi,a[n].def=it.se,a[n].id=id;
		scanf("%d",&m); idx=n; rst.clear();
		for (i=1;i<=m;++i) cnt[n+i]=0;
		for (i=1;i<=m;++i) scanf("%d",&b[i].atk);
		for (i=1;i<=m;++i) scanf("%d",&b[i].def);
		for (i=1;i<=m;++i)
		{
			if (rst.count(pi(b[i].atk,b[i].def))) ++cnt[rst[pi(b[i].atk,b[i].def)]];
			else cnt[rst[pi(b[i].atk,b[i].def)]=++idx]=1;
		}
		m=0; for (auto [it,id]:rst) ++m,b[m].atk=it.fi,b[m].def=it.se,b[m].id=id;
		for (i=1;i<=n+m;++i) nxt[i]=vis[i]=pre[i]=0,ans[i]=-1;
		auto cmp_atk=[&](const ifo& A,const ifo& B)
		{
			return A.atk<B.atk;
		};
		auto cmp_def=[&](const ifo& A,const ifo& B)
		{
			return A.def<B.def;
		};
		sort(a+1,a+n+1,cmp_def); sort(b+1,b+m+1,cmp_atk);
		for (suf[m]=m,i=m-1;i>=1;--i)
		if (b[suf[i+1]].def>b[i].def) suf[i]=suf[i+1]; else suf[i]=i;
		for (i=j=1;i<=n;++i)
		{
			while (j<=m&&a[i].def>=b[j].atk) ++j;
			if (j<=m) nxt[a[i].id]=b[suf[j]].id;
		}
		sort(a+1,a+n+1,cmp_atk); sort(b+1,b+m+1,cmp_def);
		for (suf[n]=n,i=n-1;i>=1;--i)
		if (a[suf[i+1]].def>a[i].def) suf[i]=suf[i+1]; else suf[i]=i;
		for (i=j=1;i<=m;++i)
		{
			while (j<=n&&b[i].def>=a[j].atk) ++j;
			if (j<=n) nxt[b[i].id]=a[suf[j]].id;
		}
		//for (i=1;i<=n;++i) printf("%d%c",nxt[i]," \n"[i==n]);
		//for (i=n+1;i<=m;++i) printf("%d%c",nxt[i]," \n"[i==m]);
		for (i=1;i<=n+m;++i) if (!vis[i]) DFS1(i,i);
		for (i=1;i<=n+m;++i) DFS2(i);
		int win=0,draw=0,lose=0;
		for (i=1;i<=n;++i)
		{
			if (ans[i]==-2) { draw+=cnt[i]; continue; }
			if (ans[i]==1) win+=cnt[i]; else lose+=cnt[i];
		}
		printf("%d %d %d\n",win,draw,lose);
	}
	return 0;
}