Code Chef May Challenge 2019题解

\(REDONE\)

贡献可以拆成\(X(Y+1)+Y\)，那么一个数\(x\)的贡献对最终答案的贡献就是\(x(a_1+1)(a_2+1)...\)，那么最终答案肯定是\(\sum\limits_{i=1}^ni\prod\limits_{j=1}^{i-1}(j+1)\)最优

void init(){

	fac[0]=1;

	fp(i,1,1e6)fac[i]=mul(fac[i-1],i+1),ans[i]=add(ans[i-1],mul(i,fac[i-1]));

}

int main(){

//	freopen("testdata.in","r",stdin);

	init();

	for(int T=read();T;--T)n=read(),print(ans[n]);

	return Ot(),0;

}

\(MATCHS\)

直接辗转相除，假设\(n<m\)（如果\(n=m\)先手必胜），如果\(\left\lfloor{m\over n}\right\rfloor=1\)先后手必胜反一反，否则先手必胜，用\(SG\)函数就能证明

ll n,m;int flag;

int main(){

//	freopen("testdata.in","r",stdin);

	for(int T=read();T;--T){

		n=read(),m=read(),flag=1;

		if(n>m)swap(n,m);

		while(m%n&&m/n==1)flag^=1,m%=n,swap(n,m);

		puts(flag?"Ari":"Rich");

	}

	return 0;

}

\(WTBTR\)

先把坐标系旋转\(45\)度再扩大\(\sqrt{2}\)倍，那么只能选竖直或者水平的直线

易知最优方案一定是\(n-2\)条直线穿过\(n-2\)个点，剩下一条直线在剩下两个点的中间位置，所以只要求出平面最近点对就行了（这里的距离只有\(x\)或\(y\)的距离）。正确性可以用反证法证明。

int main(){

//	freopen("testdata.in","r",stdin);

	for(int T=read();T;--T){

		n=read(),ans=inf;

		for(R int i=1,x,y;i<=n;++i)x=read(),y=read(),a[i]=x-y,b[i]=x+y;

		sort(a+1,a+1+n),sort(b+1,b+1+n);

		fp(i,2,n)cmin(ans,a[i]-a[i-1]),cmin(ans,b[i]-b[i-1]);

		printf("%lf\n",ans*0.5);

	}

	return 0;

}

\(ADAROKS2\)

劲啊……

考虑一种涂法，我们不断涂副对角线，并保证涂的过程中没有矩形

第一条副对角线从\((1,1)\)开始，然后涂\((2,2),(3,3)\)……第二条副对角线从\((1,2)\)开始，第三条从\((1,4)\)开始……

所以我们该如何保证涂副对角线的过程中没有矩形呢？

我们令副对角线之间的距离依次增大，并记这个距离为\(a_i\)，那么有\(a_1=1,a_2=2,...\)，不难发现如果存在矩形就意味着有\(\sum\limits_{i=l}^ra_i=\sum\limits_{j=ll}^{rr}a_i\)，且\([l,r]\cap[ll,rr]=\varnothing\)

可以直接暴力把\(a_i\)预处理出来，然后后面染副对角线就行了

有个比较尴尬的问题就是如果\(n\leq 150\)左右黑色格子数会少于\(8n\)，因为左下角那个三角形是没有染的，我们暴力染一下

//minamoto

#include<bits/stdc++.h>

#define R register

#define inline __inline__ __attribute__((always_inline))

#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)

#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)

#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)

template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}

template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}

using namespace std;

char buf[1<<21],*p1=buf,*p2=buf;

inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}

int read(){

    R int res,f=1;R char ch;

    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);

    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');

    return res*f;

}

const int N=1e5+5;

int pos[N],n,tot;char mp[1005][1005];

bool ck(int x){

	pos[tot+1]=pos[tot]+x;

	fp(i,1,tot)fp(j,i,tot)fp(k,i+1,tot+1)if(pos[tot+1]-pos[k-1]==pos[j]-pos[i-1])return false;

	return true;

}

void init(){

	for(R int i=1;pos[tot]<2000;++i)

		if(ck(i))pos[++tot]=i,pos[tot]+=pos[tot-1];

	fd(i,tot,1)pos[i]-=pos[i-1];

}

bool cck(R int i,R int j){

	fp(k,1,n)fp(l,1,n)if(i!=k&&j!=l)

		if((mp[k][j]=='O')+(mp[i][l]=='O')+(mp[k][l]=='O')==3)return false;

	return true;

}

int main(){

//	freopen("testdata.in","r",stdin);

	init();

	int res;

	for(int T=read();T;--T){

		n=read(),res=0;

		fp(i,1,n)fp(j,1,n)mp[i][j]='.';

		for(R int i=1,j=1;i<=n;i+=pos[j++])

			for(R int x=1,y=i;y<=n;++x,++y)mp[x][y]='O',++res;

		for(R int i=1;i<=n&&res<8*n;++i)

			for(R int j=1;j<=i&&res<8*n;++j)

				if(mp[i][j]!='O'&&cck(i,j))mp[i][j]='O',++res;

		fp(i,1,n){

			fp(j,1,n)putchar(mp[i][j]);

			putchar('\n');

		}

	}

	return 0;

}

\(BINARY\)

我们可以看做是\(1\)不断往左跳，那么我们只要知道每个\(1\)往左跳了多少次就可以了，要注意不能跳过界

所以现在问题就是该如何计算一个\(1\)在这\(z\)秒里有多少秒是往左跳的，有多少秒是停下来的

考虑每一个极长的\(1\)的联通块，对于开头的那个\(1\)，它是第\(1\)秒就开始跳了的，对于第\(i\)个\(1\)，它是从第\(i\)秒才开始向左跳的。如果我们用一个队列来表示一个跳和停地状态，\(q[i]=0\)表示停下，\(q[i]=1\)表示跳跃，那么这个极长联通块中没加入一个\(1\)都会令\(q[++t]=0\)并使\(++h\)，只要保证\(t-h+1=z\)，动态维护这个区间的和就好了

然而跳跃的情况该如何考虑呢？设这个极长联通块到前一个极长联通块之间的\(0\)的个数为\(p\)，那么以当前的极长联通块中第一个点为例，它会连续往左跳\(p\)秒，此时有可能前一个联通块中所有点都已经跳完了，那么它可以继续跳。否则它就必须停下来等一下之后才能继续跳。如果以我们之前的那个\(q\)为例，可以发现一次往后加了\(0\)点的时候，会把\(q\)中的最后一个\(1\)变成\(0\)。那么我们只要对\(1\)开一个链表，记录一下上一个\(1\)的位置就行了

然后没有然后了

//minamoto

#include<bits/stdc++.h>

#define R register

#define inline __inline__ __attribute__((always_inline))

#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)

#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)

#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)

template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}

template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}

using namespace std;

char buf[1<<21],*p1=buf,*p2=buf;

inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}

int read(){

    R int res,f=1;R char ch;

    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);

    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');

    return res*f;

}

inline int getop(){R char ch;while((ch=getc())>'9'||ch<'0');return ch-'0';}

char sr[1<<22];int K=-1;

inline void Ot(){fwrite(sr,1,K+1,stdout),K=-1;}

const int N=1e6+5;

int a[N],b[N],q[N<<1],las[N<<1],n,z,h,t,tl,now,tot;

int main(){

//	freopen("testdata.in","r",stdin);

	for(int T=read();T;--T){

		n=read(),z=read();

		fp(i,1,n)a[i]=getop(),b[i]=0;

		tl=t=now=tot=0,h=1;fp(i,1,z)q[++t]=1,++now;

		fp(i,1,n){

			if(a[i]==1)b[max(++tot,i-now)]=1,q[++t]=0,las[t]=tl,tl=t,now-=q[h++];

			else if(tl>=h)q[tl]=1,++now,tl=las[tl];

		}

		fp(i,1,n)sr[++K]=b[i]+'0',sr[++K]=' ';

		sr[++K]='\n';

	}

	return Ot(),0;

}

\(TREDEG\)

强行二合一……

首先我们把无根树转化为\(prufer\)序列，那么无根树的总数就是\(n^{n-2}\)，只要计算总的贡献就行了。对于\(n\leq 100000\)的数据答案就是

\[Ans=[x^{n-2}]\left(\sum_{i=0}^\infty {(d_i+1)^k\over d_i!}x^i\right)^n
\]

直接多项式快速幂就行了

然后是\(k=1\)的情况，此时\(n\leq 2000000\)，直接多项式快速幂显然会爆炸

那就换个方法数吧

\[\begin{aligned}
Ans
&=(n-2)!\prod_{\sum d_i=n-2}\left({d_i+1\over d_i!}\right)\\
&=(n-2)!\prod_{\sum d_i=n-2}\left({1\over d_i!}+{1\over (d_i-1)!}\right)\\
\end{aligned}
\]

我们把括号里的给拆出来，那么假设有\(x\)项\({1\over (d_i-1)!}\)，\(n-x\)项\({1\over d_i!}\)，那么\(\sum d_i=n-2-x\)，且我们枚举这\(n\)个里面那些是\(d_i-1\)，方案数还需要乘上一个\({n\over x}\)

于是总的方案数为

\[\begin{aligned}
Ans
&=(n-2)!\sum_{k=0}^{n-2}{n\choose k}\prod_{\sum d_i=n-2-k}{1\over d_i!}\\
&=\sum_{k=0}^{n-2}{n\choose k}(n-2)^{\underline{k}}(n-2-k)!\prod_{\sum d_i=n-2-k}{1\over d_i!}\\
&=\sum_{k=0}^{n-2}{n\choose k}(n-2)^{\underline{k}}n^{n-2-k}\\
\end{aligned}
\]

直接\(O(n)\)计算就行了

//minamoto

#include<bits/stdc++.h>

#define R register

#define inline __inline__ __attribute__((always_inline))

#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)

#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)

#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)

template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}

template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}

using namespace std;

char buf[1<<21],*p1=buf,*p2=buf;

inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}

int read(){

    R int res,f=1;R char ch;

    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);

    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');

    return res*f;

}

const int N=(1<<18)+5,P=998244353,M=2e6+5;

inline void swap(R int &x,R int &y){R int t=x;x=y,y=t;}

inline int add(R int x,R int y){return x+y>=P?x+y-P:x+y;}

inline int dec(R int x,R int y){return x-y<0?x-y+P:x-y;}

inline int mul(R int x,R int y){return 1ll*x*y-1ll*x*y/P*P;}

int ksm(R int x,R int y){

	R int res=1;

	for(;y;y>>=1,x=mul(x,x))(y&1)?res=mul(res,x):0;

	return res;

}

int lg[N],r[21][N],rt[2][N],lim,d;

int fac[M],ifac[M],inv[M];

void init(){

	fp(d,1,18){

		fp(i,1,(1<<d)-1)r[d][i]=(r[d][i>>1]>>1)|((i&1)<<(d-1));

		lg[1<<d]=d;

	}

	fac[0]=inv[0]=ifac[0]=fac[1]=inv[1]=ifac[1]=1;

	fp(i,2,2e6){

		fac[i]=mul(fac[i-1],i),

		inv[i]=mul(P-P/i,inv[P%i]),

		ifac[i]=mul(ifac[i-1],inv[i]);

	}

	for(R int t=(P-1)>>1,i=1,x,y;i<262144;i<<=1,t>>=1){

		x=ksm(3,t),y=ksm(332748118,t),rt[0][i]=rt[1][i]=1;

		fp(k,1,i-1)

			rt[1][i+k]=mul(rt[1][i+k-1],x),

			rt[0][i+k]=mul(rt[0][i+k-1],y);

	}

}

void NTT(int *A,int ty){

	fp(i,0,lim-1)if(i<r[d][i])swap(A[i],A[r[d][i]]);

	R int t;

	for(R int mid=1;mid<lim;mid<<=1)

		for(R int j=0;j<lim;j+=(mid<<1))

			fp(k,0,mid-1)

				A[j+k+mid]=dec(A[j+k],t=mul(rt[ty][mid+k],A[j+k+mid])),

				A[j+k]=add(A[j+k],t);

	if(!ty){

		t=inv[lim];

		fp(i,0,lim-1)A[i]=mul(A[i],t);

	}

}

void Inv(int *a,int *b,int len){

	if(len==1)return b[0]=ksm(a[0],P-2),void();

	Inv(a,b,len>>1);static int A[N],B[N];

	lim=(len<<1),d=lg[lim];

	fp(i,0,len-1)A[i]=a[i],B[i]=b[i];

	fp(i,len,lim-1)A[i]=B[i]=0;

	NTT(A,1),NTT(B,1);

	fp(i,0,lim-1)A[i]=mul(A[i],mul(B[i],B[i]));

	NTT(A,0);

	fp(i,0,len-1)b[i]=dec(add(b[i],b[i]),A[i]);

	fp(i,len,lim-1)b[i]=0;

}

void Ln(int *a,int *b,int len){

	static int A[N],B[N];

	fp(i,1,len-1)A[i-1]=mul(a[i],i);A[len-1]=0;

	Inv(a,B,len);lim=(len<<1),d=lg[lim];

	fp(i,len,lim-1)A[i]=B[i]=0;

	NTT(A,1),NTT(B,1);

	fp(i,0,lim-1)A[i]=mul(A[i],B[i]);

	NTT(A,0);

	fp(i,1,len-1)b[i]=mul(A[i-1],inv[i]);b[0]=0;

	fp(i,len,lim-1)b[i]=0;

}

void Exp(int *a,int *b,int len){

	if(len==1)return b[0]=1,void();

	Exp(a,b,len>>1);

	static int A[N];Ln(b,A,len);

	lim=(len<<1),d=lg[lim];

	A[0]=dec(a[0]+1,A[0]);

	fp(i,1,len-1)A[i]=dec(a[i],A[i]);

	fp(i,len,lim-1)A[i]=b[i]=0;

	NTT(A,1),NTT(b,1);

	fp(i,0,lim-1)b[i]=mul(b[i],A[i]);

	NTT(b,0);

	fp(i,len,lim-1)b[i]=0;

}

void ksm(int *a,int *b,int len,int k){

	static int A[N];

	Ln(a,A,len);

	fp(i,0,len-1)A[i]=mul(A[i],k);

	Exp(A,b,len);

}

int n,k,ans;

inline int C(R int n,R int m){return 1ll*fac[n]*ifac[m]%P*ifac[n-m]%P;}

int dfs(int pos,int now){

	if(pos==n+1)return now==n-2?1:0;

	int res=0;

	fp(i,0,n-2-now)res=add(res,mul(dfs(pos+1,now+i),mul(1,ifac[i])));

	return res;

}

int calc1(){

	int res=0;

	int iv=ksm(n,P-2);

	for(R int i=0,p=ksm(n,n-2),tmp=n-2;i<=n-2;p=mul(p,mul(iv,tmp--)),++i)

		res=add(res,1ll*fac[n]*ifac[i]%P*ifac[n-i]%P*p%P);

	return res;

}

int A[N],B[N];

int calc2(){

	int len=1;while(len<=n-2)len<<=1;

	fp(i,0,len-1)A[i]=mul(ksm(i+1,k),ifac[i]);

	ksm(A,B,len,n);

	return mul(B[n-2],fac[n-2]);

}

int main(){

//	freopen("testdata.in","r",stdin);

	init();

	for(int T=read();T;--T){

		n=read(),k=read();

		ans=(k==1)?calc1():calc2();

		ans=mul(ans,ksm(ksm(n,n-2),P-2));

		printf("%d\n",ans);

	}

	return 0;

}

\(ADAPWN\)

我们可以把一次操作看成删除一个点，那么这道题就可以看做是一个二分图，选出最少的点删掉，使得剩下的点之间没有边相连，也就是一个最小点覆盖

不过这里有一个问题，就是有一些点是不可能被删掉的，所以它们是不能被选在最小点覆盖里的。我们强制它们不删，那么所有和它们有边相连的点都要被强制删掉

然后就是如何求二分图最小点覆盖了……鉴于咱对二分图一无所知，可以看看\(fcw\)巨巨的总结

没了

//minamoto

#include<bits/stdc++.h>

#define R register

#define inline __inline__ __attribute__((always_inline))

#define fp(i,a,b) for(R int i=(a),I=(b)+1;i<I;++i)

#define fd(i,a,b) for(R int i=(a),I=(b)-1;i>I;--i)

#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)

template<class T>inline bool cmax(T&a,const T&b){return a<b?a=b,1:0;}

template<class T>inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}

using namespace std;

char buf[1<<21],*p1=buf,*p2=buf;

inline char getc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}

int read(){

    R int res,f=1;R char ch;

    while((ch=getc())>'9'||ch<'0')(ch=='-')&&(f=-1);

    for(res=ch-'0';(ch=getc())>='0'&&ch<='9';res=res*10+ch-'0');

    return res*f;

}

int read(char *s){

	R int len=0;R char ch;while((ch=getc())!='O'&&ch!='.');

	for(s[++len]=ch;(ch=getc())=='O'||ch=='.';s[++len]=ch);

	return s[len+1]='\0',len;

}

const int N=205,M=2e4+5;

struct eg{int v,nx;}e[M];int head[M<<2],tot;

inline void add(R int u,R int v){e[++tot]={v,head[u]},head[u]=tot;}

char mp[N][N];int id[N][N],px[M],py[M],to[M],vis[M],bl[M],now[M],ok[M];

int n,cnt,tim,res;

bool dfs(int u){

	vis[u]=tim;

	go(u)if(vis[v]!=tim){

		vis[v]=tim;

		if(!to[v]||dfs(to[v]))return to[v]=u,true;

	}

	return false;

}

int main(){

//	freopen("testdata.in","r",stdin);

	for(int T=read();T;--T){

		n=read(),cnt=tot=res=0;

		fp(i,1,n){

			read(mp[i]);

			fp(j,1,n)if(mp[i][j]=='O')id[i][j]=++cnt,px[cnt]=i,py[cnt]=j,bl[cnt]=(i&1);

		}

		fp(i,1,n+1)mp[n+1][i]=0;

		fp(i,1,cnt)to[i]=vis[i]=head[i]=now[i]=ok[i]=0;

		fp(i,1,n)fp(j,1,n)if(mp[i][j]=='O'&&mp[i-1][j-1]!='O'&&mp[i-1][j+1]!='O'){

			now[id[i][j]]=1;

			if(mp[i+1][j+1]=='O')now[id[i+1][j+1]]=2;

			if(mp[i+1][j-1]=='O')now[id[i+1][j-1]]=2;

		}

		fp(i,1,cnt)res+=(now[i]==2);

		for(R int i=1;i<=n;i+=2)fp(j,1,n)if(mp[i][j]=='O'&&!now[id[i][j]]){

			if(mp[i-1][j-1]=='O'&&!now[id[i-1][j-1]])add(id[i][j],id[i-1][j-1]);

			if(mp[i-1][j+1]=='O'&&!now[id[i-1][j+1]])add(id[i][j],id[i-1][j+1]);

			if(mp[i+1][j-1]=='O'&&!now[id[i+1][j-1]])add(id[i][j],id[i+1][j-1]);

			if(mp[i+1][j+1]=='O'&&!now[id[i+1][j+1]])add(id[i][j],id[i+1][j+1]);

		}

		tim=0;

		fp(i,1,cnt)if(!now[i]){

			++tim;

			if(dfs(i))++res;

		}

		fp(i,1,cnt)if(to[i])ok[to[i]]=1;

		++tim;

		fp(i,1,cnt)if(!now[i]&&bl[i]&&!ok[i])dfs(i);

		fp(i,1,cnt)if(!now[i]&&bl[i]&&vis[i]!=tim)now[i]=2;

		fp(i,1,cnt)if(!now[i]&&!bl[i]&&vis[i]==tim)now[i]=2;

		printf("%d\n",res);

		fd(i,cnt,1)if(now[i]==2){

			int x=px[i],y=py[i];

			printf("%d %d %c\n",x,y,mp[x-1][y-1]=='O'?'L':'R');

		}

	}

	return 0;

}

剩下的慢慢补……

巴特西