Preface

AGC好难啊，这场补完最近就没啥比赛好补了，接下来去训练下专题吧

像C题这种美妙的人类智慧题感觉以我的脑子一辈子也想不出来www

A - Mex Game

对于任意一段前缀，我们可以求出对应的每个人的操作次数以及每个人拥有的位置数

考虑Alice的最优策略一定是从小到大地放入Bob对应的格子所对的下标，Bob同理

因此只要检验一下谁的格子还有剩余即可

#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,CA,CB; char s[N];
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; if (scanf("%d%s",&n,s+1),s[1]=='A') ++CA; else ++CB;
	for (i=2;i<=n+1;++i)
	{
		if (s[i]=='A') ++CA; else ++CB;
		int OA=i/2,OB=(i-1)/2;
		puts(CA-OB>0?"Alice":"Bob");
	}
	return 0;
}

B - Insert 1, 2, 3, ...

刚开始想假了写了个线段树上二分，后面发现就是个傻逼题

首先考虑当左端点确定时，合法的右端点的取值一定是连续的一段，这就提示我们考虑如何对于每个左端点快速求出右端点

手玩一下会发现如果我们把所有无法被表示的下标扔到一个栈里，只要每次看一下能否在这次操作中把栈顶元素表示掉即可

总复杂度\(O(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=500005;
int n,a[N],stk[N],top; LL ans;
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i; for (scanf("%d",&n),i=1;i<=n;++i) scanf("%d",&a[i]);
	for (stk[top=1]=n+1,a[n+1]=-1,i=n;i>=1;--i)
	{
		stk[++top]=i; int lst=1;
		while (a[stk[top]]==lst) --top,++lst;
		ans+=stk[top]-i;
	}
	return printf("%lld",ans),0;
}

C - Add Mod Operations

人类智慧题，完全想不到的说

首先把无解的情况判掉，显然当出现\(\exist i,j\in[1,n],a_i=a_j\and b_i\ne b_j\)这种情况就一定不合法，否则均可以构造解

然后我们可以对\(a_i\)升序排序，考虑如果每次操作\(y=\max(a)+x\)，那么总可以把序列中最大的元素变成\(0\)并将其它元素加上\(x\)

考虑先依照此法操作\(n\)次，这样我们得到的序列形如：\(0,x_n,x_n+x_{n-1},\cdots,\sum_{i=3}^n x_i,\sum_{i=2}^n x_i\)

不难发现相邻两项间的差值总是正的，那么如果\(b\)满足单调不降且\(b_1=0\)那么就可以确定一组\(\{x_n\}\)

但如果不满足的话我们也有方法，不妨搞一个很大的数\(\infty\)，然后令\(b'_i=b_i+(i-1)\times \infty\)，这样\(\{b'\}\)就是单调不降的

我们只需要在最后一次操作做一遍\(x_{n+1}=b_1,y_{n+1}=\infty\)即可

但题目要求的是操作次数要\(\le n\)，这样就得考虑怎么样可以省下一次操作，不难发现其实最后操作\(n\)次的序列中并没有\(x_1\)，这就提醒我们从这里入手

考虑把原来操作的\(x_1\)修改为\(x_1-a_1\)，这样在操作\(n-1\)次后的序列就形如：\(\sum_{i=1}^{n-1} x_i,0,x_{n-1},\cdots,\sum_{i=3}^{n-1} x_i,\sum_{i=2}^{n-1} x_i\)

不妨修改\(b'_1=b_1+(n-1)\times \infty,b'_i=b_i+(i-1)\times \infty (i\in[2,n])\)，这样最后一次操作\(x_n=b_2,y_n=\infty\)即可

实现中取\(\infty =2\times 10^9+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 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 N=1005,INF=2e9+1;
int n,a[N],b[N],x[N],y[N]; pi d[N];
inline void work(CI x,CI y)
{
	for (RI i=1;i<=n;++i) a[i]=(a[i]+x)%y;
}
signed main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%lld",&n),i=1;i<=n;++i) scanf("%lld",&a[i]);
	for (i=1;i<=n;++i) scanf("%lld",&b[i]),d[i]=pi(a[i],b[i]);
	for (i=1;i<=n;++i) for (j=i+1;j<=n;++j)
	if (a[i]==a[j]&&b[i]!=b[j]) return puts("No"),0;
	sort(d+1,d+n+1); n=unique(d+1,d+n+1)-d-1;
	for (i=1;i<=n;++i) a[i]=d[i].fi,b[i]=d[i].se;
	if (n==1) return printf("Yes\n1\n%lld %lld\n",(b[1]-a[1]+INF)%INF,INF),0;
	x[1]=b[1]-b[n]+INF-a[1]; x[n]=b[2]; y[n]=INF;
	for (i=2;i<=n-1;++i) x[i]=b[n-i+2]-b[n-i+1]+INF;
	for (i=1;i<=n-1;++i) y[i]=a[n-i+1]+x[i],work(x[i],y[i]);
	for (printf("Yes\n%lld\n",n),i=1;i<=n;++i) printf("%lld %lld\n",x[i],y[i]);
	return 0;
}

Postscript

感觉以后AGC先放放不补了，以我现在的水平AGC的妙处都体会不太到，后面的题目是一点做不了