Preface

最近国庆在外面玩的有点high啊，欠了一篇AT和两篇CF没写，今天先浅浅写一下这场

当时10.2号在外面玩得有点晚了，到寝室刚好比赛开始，晚饭都没吃就开干了

主要是C写的太久了，而且挂了一发之后看了好久才发现\(n=3\)的情形没处理好

然后40min做D没做出来，鉴定为纯纯的FW（话说原来ARC这么难的吗，感觉比以前的一些AGC还难）

A - Repdigit Number

送分题，暴力枚举每一种情况判断即可

#include<cstdio>
#define RI register int
#define CI const int&
using namespace std;
int n,m,md,mn=-1;
inline void print(CI d,CI n)
{
	for (RI i=1;i<=n;++i) putchar(d+'0');
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%d%d",&n,&m),j=1;j<=9;++j)
	{
		int cur=0; for (i=1;i<=n;++i)
		if ((cur=(10LL*cur+j)%m)==0)
		{
			if (i>mn||(i==mn&&j>md)) mn=i,md=j;
		}
	}
	if (~mn) print(md,mn); else puts("-1");
	return 0;
}

B - Two LIS Sum

一眼猜结论题，不难发现我们将\(A\)排成\(1,2,\cdots,n\)时答案一定不会变劣，因此在此基础上求出\(B\)的LIS即可

#include<cstdio>
#include<iostream>
#define RI register int
#define CI const int&
using namespace std;
const int N=300005;
int n,a[N],x,b[N],cur,ans;
class Tree_Array
{
	private:
		int bit[N];
	public:
		#define lowbit(x) (x&-x)
		inline void add(int x,CI y)
		{
			for (;x<=n;x+=lowbit(x)) bit[x]=max(bit[x],y);
		}
		inline int get(int x,int ret=0)
		{
			for (;x;x-=lowbit(x)) ret=max(ret,bit[x]); return ret;
		}
		#undef lowbit
}T;
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 (i=1;i<=n;++i) scanf("%d",&x),b[a[i]]=x;
	for (i=1;i<=n;++i) cur=T.get(b[i]),T.add(b[i],cur+1),ans=max(ans,cur+1);
	return printf("%d",ans+n),0;
}

C - Avoid Prime Sum

又是比较显然的构造题，不难发现奇数+奇数、偶数+偶数的和一定为合数，因此我们考虑尽可能地让奇数之间，偶数之间尽量邻近在一起

因此就有一个naive的想法，根据\(n\)的奇偶性把棋盘分成两个部分（如下图），每个部分各自填奇数和偶数，然后只要考虑交界处的情况了

偶数的情况比较容易，只要找到一个奇数且不是质数的数然后拆分一下即可，但奇数时要讨论最中间的奇数要和两个偶数之和为合数

可能我的实现比较渣，代码量挺大，而且还需要特判\(n=3\)的情况（话说我\(n=3\)的情况手玩玩不出来最后还是暴枚出来的）

后来看了眼官方sol发现可以直接用\(3\)的倍数来构造，这样大大降低了代码复杂度

#include<cstdio>
#include<iostream>
#include<algorithm>
#define RI register int
#define CI const int&
using namespace std;
const int N=1005;
const int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int n,a[N][N],tar,odd[N],even[N],spo=-1,spe,arr[N]; bool vis[N*N];
inline bool is_prime(CI n)
{
	for (RI i=2;i*i<=n;++i)
	if (n%i==0) return 0; return 1;
}
inline bool check(CI t)
{
	for (RI i=1;i<=n;++i)
	{
		odd[i]=i; even[i]=t-i; if ((t-i)&1) swap(odd[i],even[i]);
		if (i!=1&&!is_prime(even[i]+1)) spo=odd[i],spe=even[i];
	}
	return ~spo;
}
inline void sp_solve(void)
{
	RI i,j,k; for (i=1;i<=9;++i) arr[i]=i;
	do
	{
		for (k=0,i=1;i<=3;++i) for (j=1;j<=3;++j) a[i][j]=arr[++k];
		bool flag=1; for (i=1;i<=3&&flag;++i) for (j=1;j<=3&&flag;++j) for (k=0;k<4&&flag;++k)
		{
			int ii=i+dx[k],jj=j+dy[k]; if (ii<1||ii>3||jj<1||jj>3) continue;
			if (is_prime(a[i][j]+a[ii][jj])) flag=0;
		}
		if (flag) return;
	} while (next_permutation(arr+1,arr+10));
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j,k; if (scanf("%d",&n),n==3) sp_solve(); else
	{
		if (n&1)
		{
			for (i=2*n+1;i<=n*n;i+=2)
			if (!is_prime(i)&&check(i)) break;
			a[(n+1)/2][(n+1)/2]=1; a[(n+1)/2+1][(n+1)/2]=even[1];
			a[(n+1)/2][(n+1)/2+1]=spe; a[(n+1)/2-1][(n+1)/2+1]=spo;
			vis[1]=vis[even[1]]=vis[spe]=vis[spo]=1;
			for (i=j=1;i<(n+1)/2;++i)
			{
				if (odd[++j]==spo) ++j; vis[a[(n+1)/2][i]=odd[j]]=1;
			}
			for (i=(n+1)/2+2;i<=n;++i)
			{
				if (odd[++j]==spo) ++j; vis[a[(n+1)/2-1][i]=odd[j]]=1;
			}
			for (i=j=1;i<(n+1)/2;++i)
			{
				if (even[++j]==spe) ++j; vis[a[(n+1)/2+1][i]=even[j]]=1;
			}
			for (i=(n+1)/2+2;i<=n;++i)
			{
				if (even[++j]==spe) ++j; vis[a[(n+1)/2][i]=even[j]]=1;
			}
			for (k=1,i=1;i<(n+1)/2-1;++i) for (j=1;j<=n;++j)
			{
				while (vis[k]) k+=2; vis[a[i][j]=k]=1;
			}
			for (i=1;i<=(n+1)/2;++i)
			{
				while (vis[k]) k+=2; vis[a[(n+1)/2-1][i]=k]=1;
			}
			for (k=2,i=(n+1)/2+2;i<=n;++i) for (j=1;j<=n;++j)
			{
				while (vis[k]) k+=2; vis[a[i][j]=k]=1;
			}
			for (i=(n+1)/2+1;i<=n;++i)
			{
				while (vis[k]) k+=2; vis[a[(n+1)/2+1][i]=k]=1;
			}
		} else
		{
			for (i=2*n+1;i<=n*n;i+=2)
			if (!is_prime(i)) { check(i); break; }
			for (i=1;i<=n;++i) vis[a[n/2][i]=odd[i]]=1,vis[a[n/2+1][i]=even[i]]=1;
			for (k=1,i=1;i<n/2;++i) for (j=1;j<=n;++j)
			{
				while (vis[k]) k+=2; vis[a[i][j]=k]=1;
			}
			for (k=2,i=n/2+2;i<=n;++i) for (j=1;j<=n;++j)
			{
				while (vis[k]) k+=2; vis[a[i][j]=k]=1;
			}
		}
	}
	for (i=1;i<=n;++i) for (j=1;j<=n;++j) printf("%d%c",a[i][j]," \n"[j==n]);
	return 0;
}

D - Simultaneous Sugoroku

当时比赛的时候想的方向有点偏了，结果G了

首先我们直接考虑所有的\([1,10^6]\)的pieces，然后可以发现一个重要的性质：

对于\(t,-t\)两个位置的pieces，它们如果到达原点那时间必然时相同的，若无法到达最后的位置关于原点对称

初始时所有的pieces都在一个半轴上，不难发现在每次移动后就可能会出现正负半轴上都有pieces的情况

但我们利用上面的性质，总是可以把其中那个pieces数量较少的半轴上的pieces全部合并到另一个半轴上去，具体地我们可以连一条边在这两个点之间（可以看下图帮助理解）

然后每次有piece到达原点的时候统计答案即可，最后所有点之间构成了一个森林，更新答案即可

#include<cstdio>
#include<vector>
#define RI register int
#define CI const int&
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
const int N=1000005;
int n,m,x[N],d[N]; pair <int,int> ans[N]; vector <int> v[N]; bool vis[N];
inline void DFS(CI now)
{
	vis[now]=1; for (int to:v[now]) if (!vis[to])
	{
		if (ans[now].fi==1) ans[to]=ans[now]; else ans[to]=mp(0,-ans[now].se); DFS(to);
	}
}
int main()
{
	//freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
	RI i,j; for (scanf("%d%d",&n,&m),i=1;i<=n;++i) scanf("%d",&x[i]);
	for (i=1;i<=m;++i) scanf("%d",&d[i]);
	for (i=1;i<=1000000;++i) ans[i].first=-1; int l=1,r=1000000,mid,sum=0;
	for (i=1;i<=m;++i)
	{
		if (l>r) break; if (l+sum>0) sum-=d[i]; else sum+=d[i]; mid=-sum;
		if (mid<l||mid>r) continue; ans[mid]=mp(1,i);
		if (mid-l<=r-mid)
		{
			for (j=l;j<mid;++j) v[2*mid-j].pb(j); l=mid+1;
		} else
		{
			for (j=mid+1;j<=r;++j) v[2*mid-j].pb(j); r=mid-1;
		}
	}
	for (i=l;i<=r;++i) ans[i]=mp(0,i+sum);
	for (i=1;i<=1000000;++i) if (!vis[i]&&~ans[i].fi) DFS(i);
	for (i=1;i<=n;++i) printf("%s %d\n",ans[x[i]].fi?"Yes":"No",ans[x[i]].se);
	return 0;
}