Preface

AGC好难啊，从C题开始就一点不会了，感觉以前OI时候的AGC没那么变态的啊，也许是我变菜好多了吧

A - i i's

考虑先放一个这样的序列：

\[n,n-1,n,n-1,n\cdots,n-1,n,n-2 \]

这样就把\(n,n-1\)都用完了，同时还用了个\(n-2\)，然后考虑从大到小地把剩下的数插入空隙中

每次暴枚找到所有合法的插入位置即可，复杂度\(O(n^3)\)但远远跑不满，可以通过

#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_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=1005;
int n; vector <int> ans;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%d",&n),i=1;i<=2*n-1;++i)
	if (i&1) ans.push_back(n); else ans.push_back(n-1);
	for (ans.push_back(n-2),i=n-2;i>=1;--i)
	{
		vector <int> tmp; int cnt=i-(i==n-2);
		for (tmp.push_back(ans[0]),j=1;j<ans.size();++j)
		{
			if (cnt&&abs(ans[j-1]-i)<=2&&abs(ans[j]-i)<=2) --cnt,tmp.push_back(i);
			tmp.push_back(ans[j]);
		}
		ans=tmp;
	}
	//for (i=1;i<ans.size();++i) assert(abs(ans[i]-ans[i-1])>=1&&abs(ans[i]-ans[i-1])<=2);
	for (int x:ans) printf("%d ",x);
	return 0;
}

B - Red and Blue Spanning Tree

XJB乱搞就过了

首先不难发现可以把边分成三类，根据这条边的颜色和它的端点同色的数量为\(2/1/0\)划分，不难发现第三类边对于颜色的限制是没用的，只能起到把图连通的作用

考虑如果没有第一类边的话我们需要至少\(n\)条第二类边才能满足每个点的颜色要求，而这是显然不合法的，因此第一类边必须要存在

同时稍微手玩一下会发现选第一类边一定比选第二类边来的优，因为在不成环的情况下第一类边的贡献至少也是\(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_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,m,x[N],y[N],c[N],col[N],fa[N],vis[N]; char s[N],ch[10];
vector <pi> v[N]; vector <int> ans;
inline int getfa(CI x)
{
	return x!=fa[x]?fa[x]=getfa(fa[x]):x;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d%d",&n,&m),i=1;i<=m;++i)
	scanf("%d%d%s",&x[i],&y[i],ch),c[i]=ch[0]=='R',v[x[i]].push_back(pi(y[i],i)),v[y[i]].push_back(pi(x[i],i));
	for (scanf("%s",s+1),i=1;i<=n;++i) fa[i]=i,col[i]=s[i]=='R';
	for (i=1;i<=m;++i) if (c[i]==col[x[i]]&&c[i]==col[y[i]]&&getfa(x[i])!=getfa(y[i]))
	ans.push_back(i),fa[getfa(x[i])]=getfa(y[i]),vis[x[i]]=vis[y[i]]=1;
	queue <int> q; for (i=1;i<=n;++i) if (vis[i]) q.push(i);
	while (!q.empty())
	{
		int now=q.front(); q.pop();
		for (auto [to,id]:v[now])
		if (!vis[to]&&c[id]==col[to]&&getfa(now)!=getfa(to))
		ans.push_back(id),vis[to]=1,q.push(to),fa[getfa(now)]=getfa(to);
	}
	for (i=1;i<=n;++i) if (!vis[i]) return puts("No"),0;
	for (i=1;i<=m;++i) if (getfa(x[i])!=getfa(y[i]))
	fa[getfa(x[i])]=getfa(y[i]),ans.push_back(i);
	puts("Yes"); for (auto x:ans) printf("%d ",x);
	return 0;
}

C - Erase and Divide Game

好有意思的题

首先考虑如果给出的数不是区间而是单独的值该怎么做，考虑这两种操作的本质

我们不妨把所有数扔进从低位到高位的0/1Trie中，不难发现每次操作就是往当前这个点的子树里走一步，先不能走的人就输了

而这道题的问题就在于给出的数是一段区间，而一段区间内的数在0/1Trie上的分布是很散的，我们很难显式地把0/1Trie建出来

考虑一种更本质的做法，我们求出每个点的SG函数，用\(0\)代表空点，\(1\)代表必胜态，\(2\)代表必败态，合并两个点时要注意空点的情况需要特别考虑

初始时我们所有给出的区间的SG函数都是\(1\)，剩下的其它区间都是\(0\)，我们考虑一步步地模拟合并的过程

对于从0/1Trie的第\(60\)层合并到第\(59\)层时，我们对于一个数\(x\)，只要看\(x+2^{59}\)的SG函数即可，然后合并后我们得到的仍然是\(O(n)\)级别的区间，再处理向上的合并即可

这部分的实现可以用类似于归并排序的写法，具体实现看代码，复杂度\(O(n\log V)\)

#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_map>
#define int long long
#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 trs[3][3]={{0,1,1},{1,2,1},{1,1,1}};
struct ifo
{
	int l,r,tp;
	inline ifo(CI L=0,CI R=0,CI TP=0)
	{
		l=L; r=R; tp=TP;
	}
}; vector <ifo> o; int t,n,l,r,lst;
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	for (scanf("%lld",&t);t;--t)
	{
		RI i,j; for (scanf("%lld",&n),lst=-1,i=1;i<=n;++i)
		{
			scanf("%lld%lld",&l,&r);
			if (lst+1<=l-1) o.push_back(ifo(lst+1,l-1,0));
			o.push_back(ifo(l,r,1)); lst=r;
		}
		o.push_back(ifo(lst+1,(1LL<<60)-1,0));
		for (j=60;j>=1;--j)
		{
			vector <ifo> L,R; int mid=1LL<<j-1;
			for (auto [l,r,tp]:o)
			{
				if (r<mid) L.push_back(ifo(l,r,tp));
				else if (l>=mid) R.push_back(ifo(l-mid,r-mid,tp));
				else L.push_back(ifo(l,mid-1,tp)),R.push_back(ifo(0,r-mid,tp));
			}
			int p=0,q=0; o.clear(); while (p<L.size()&&q<R.size())
			{
				if (L[p].r<=R[q].r) o.push_back(L[p]); else o.push_back(R[q]);
				o.back().tp=trs[L[p].tp][R[q].tp];
				if (L[p].r==o.back().r) ++p; else L[p].l=o.back().r+1;
				if (R[q].r==o.back().r) ++q; else R[q].l=o.back().r+1;
			}
		}
		puts(o.back().tp==1?"Takahashi":"Aoki"); o.clear();
	}
	return 0;
}

D - Red and Blue Chips

妙妙计数题

考虑判定一个RB序列是否可以被得到，不妨从后往前考虑

如果当前位置是R，则序列顶端一定得是一个R，并且我们需要拿掉这个R

否则如果当前位置是B，它顶端可以放的是任意东西，但下方一定是B，此时我们可以把序列从某个B的位置分裂

如果某次在遇到R时拿不出R了则该状态不合法，否则总存在一种方案可以构造出该序列

而每次遇到B的分裂策略显然满足贪心性，我们把每个B分裂的方案能带来的R的数量从大到小排序，这样一定是最优的

不过要注意初始时上面的R是不参与排序的，因为它们一开始就可以被取出来

因此不妨先统计出每个B前面的R的个数\(c_1,c_2,\cdots,c_k\)，而初始序列相当于给定了序列\(d_1,d_2,\cdots,d_k\)，我们需要计数满足以下限制的序列\(c\)的个数：

\(k\)和原序列中B的数目相同
\(\sum_{i=1}^k c_i\)和原序列中R的数目相同
讲\(c_2,c_3,\cdots,c_k\)排序后，\(\forall s\in[1,k],\sum_{i=1}^s c_i\ge \sum_{i=1}^s d_i\)

这个计数问题就很trivial了，我们从大到小把数加入，设\(f_{i,j,k}\)表示当前加入的最大数为\(i\)，一共选了\(j\)个数，这些数的和为\(k\)的方案数

转移系数其实就是多重全排列的式子，总复杂度\(O(n^3\log 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_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=305,mod=998244353;
int n,d[N],R,B,f[N][N][N],fact[N],ifac[N]; char s[N];
inline void inc(int& x,CI y)
{
	if ((x+=y)>=mod) x-=mod;
}
inline int quick_pow(int x,int p=mod-2,int mul=1)
{
	for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;
}
inline void init(CI n)
{
	RI i; for (fact[0]=i=1;i<=n;++i) fact[i]=1LL*fact[i-1]*i%mod;
	for (ifac[n]=quick_pow(fact[n]),i=n-1;i>=0;--i) ifac[i]=1LL*ifac[i+1]*(i+1)%mod;
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j,k,l; for (scanf("%d%s",&n,s+1),i=n;i>=1;--i)
	if (s[i]=='B') ++B; else ++d[B],++R;
	for (i=1;i<=B;++i) d[i]+=d[i-1];
	for (init(n),i=d[1];i<=R;++i) f[R+1][1][i]=fact[B-1];
	for (i=R;i>=0;--i) for (j=1;j<=B;++j) for (k=d[j];k<=R;++k)
	for (l=0;j+l<=B&&k+i*l<=R;++l)
	{
		if (k+i*l<d[j+l]) break;
		inc(f[i][j+l][k+i*l],1LL*f[i+1][j][k]*ifac[l]%mod);
	}
	return printf("%d",f[0][B][R]),0;
}