AtCoder Grand Contest 002题解

\(A\)

咕咕

int main(){

	cin>>a>>b;

	if(b<0)puts(((b-a+1)&1)?"Negative":"Positive");

	else if(a>0)puts("Positive");

	else puts("Zero");

	return 0;

}

\(B\)

模拟一下就行了

const int N=1e5+5;

int sz[N],ok[N],n,m,res;

int main(){

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

	scanf("%d%d",&n,&m);

	fp(i,1,n)sz[i]=1;ok[1]=1;

	for(R int x,y,i=1;i<=m;++i){

		scanf("%d%d",&x,&y);

		ok[y]|=ok[x],++sz[y],--sz[x];

		if(!sz[x])ok[x]=0;

	}

	fp(i,1,n)res+=ok[i];

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

	return 0;

}

\(C\)

考虑反过来，每一次连接两段绳子，且连接之后长度要大于等于\(L\)，那么第一次合并最长的两端，剩下的用这一段绳子去合并其他的就好了

//quming

#include<bits/stdc++.h>

#define R register

#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 cmin(T&a,const T&b){return a>b?a=b,1:0;}

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

using namespace std;

typedef long long ll;

const int N=1e5+5;

int a[N],n,L;

int main(){

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

	scanf("%d%d",&n,&L);

	fp(i,1,n)scanf("%d",&a[i]);

	R int pos=0;

	fp(i,1,n-1)if(a[i]+a[i+1]>=L){pos=i;break;}

	if(!pos)return puts("Impossible"),0;

	puts("Possible");

	fp(i,1,pos-1)printf("%d\n",i);

	fd(i,n-1,pos+1)printf("%d\n",i);

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

	return 0;

}

\(D\)

以边的序号为边权建出\(kruskal\)重构树，然后二分最大的序号，判断是否合法就行了

//quming

#include<bits/stdc++.h>

#define R register

#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 cmin(T&a,const T&b){return a>b?a=b,1:0;}

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

using namespace std;

const int N=5e5+5;

struct eg{int v,nx;}e[N];int head[N],tot;

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

int fa[N][25],sz[N],dep[N],ga[N],val[N],Log[N];

int n,m,q,nd,l,r,mid,ans;

inline int find(R int x){return ga[x]==x?x:ga[x]=find(ga[x]);}

void dfs(int u){

	sz[u]=(u<=n);

	for(R int i=1;dep[u]>>i;++i)fa[u][i]=fa[fa[u][i-1]][i-1];

	go(u)fa[v][0]=u,dep[v]=dep[u]+1,dfs(v),sz[u]+=sz[v];

}

inline int jump(R int u){

	fd(i,Log[dep[u]],0)if(fa[u][i]&&val[fa[u][i]]<=mid)u=fa[u][i];

	return u;

}

bool ck(R int u,R int v,R int p){

	u=jump(u),v=jump(v);

	return (u==v?sz[u]:sz[u]+sz[v])>=p;

}

int main(){

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

	scanf("%d%d",&n,&m);nd=n;

	fp(i,1,n)ga[i]=i;

	for(R int i=1,u,v,x,y;i<=m;++i){

		scanf("%d%d",&u,&v);

		u=find(u),v=find(v);

		if(u!=v)++nd,ga[u]=ga[v]=ga[nd]=nd,add(nd,u),add(nd,v),val[nd]=i;

	}

	Log[0]=-1;fp(i,2,nd)Log[i]=Log[i>>1]+1;

	dfs(nd);

	scanf("%d",&q);

	for(R int u,v,p;q;--q){

		scanf("%d%d%d",&u,&v,&p);

		l=1,r=m,ans=m;

		while(l<=r){

			mid=(l+r)>>1;

			ck(u,v,p)?(ans=mid,r=mid-1):l=mid+1;

		}

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

	}

	return 0;

}

\(E\)

如果我们把所有的\(a_i\)降序排序，那么我们可以画出一个网格图，其中第\(i\)列有\(a_i\)个格子，初始在\(1,1\)，第一个操作对应往右走，第二个操作对应往下走，那么走出边界的输

打表发现\((x,y)\)的答案和\((x+1,y+1)\)的答案相同，那么我们可以暴力找出最大的\((x,x)\)，然后计算这个格子的答案就行了

//quming

#include<bits/stdc++.h>

#define R register

#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 cmin(T&a,const T&b){return a>b?a=b,1:0;}

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

using namespace std;

const int N=1e5+5;

int a[N],n,m,las,pos,t;

int main(){

	scanf("%d",&n);

	fp(i,1,n)scanf("%d",&a[i]);

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

	fp(i,1,n)if(a[i]>=i)pos=i;else break;

	a[n+1]=0,t=1;fp(i,pos+1,n)if(a[i]==pos)t^=1;else break;

	puts(!(((a[pos]-pos+1)&1)&t)?"First":"Second");

	return 0;

}

\(F\)

对于每种颜色，我们把它变成一个无色的球和\(k-1\)个有颜色的球，那么发现，我们需要满足位置关系的只有这些无色的球和每个颜色第一次出现的位置（记为特殊位置），并且满足每一个前缀中无色球的个数都大于等于特殊位置的个数

那么我们倒着放球，设\(f_{i,j}\)表示放了后\(i\)个位置，且这\(i\)个位置中有\(j\)个特殊位置的方案数，那么后面放的总球数就是\(i+j\times (k-1)\)，转移的时候用组合数乘一下就可以了

//quming

#include<bits/stdc++.h>

#define R register

#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 cmin(T&a,const T&b){return a>b?a=b,1:0;}

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

using namespace std;

const int P=1e9+7;

inline void upd(R int &x,R int y){(x+=y)>=P?x-=P:0;}

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;

}

const int N=5005,M=5e6+5;

int f[N][N],fac[M],ifac[M],n,k;

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

inline void init(R int n=5e6){

	fac[0]=ifac[0]=1;fp(i,1,n)fac[i]=mul(fac[i-1],i);

	ifac[n]=ksm(fac[n],P-2);fd(i,n-1,1)ifac[i]=mul(ifac[i+1],i+1);

}

int main(){

	scanf("%d%d",&n,&k),--k;

	if(!k)return puts("1"),0;

	init();

	f[0][0]=1;

	fp(i,0,(n<<1)-1)fp(j,0,min(i,n))if(f[i][j]){

		if(j+1<=n)upd(f[i+1][j+1],mul(n-j,mul(f[i][j],C(i+j*(k-1)+k-1,k-1))));

		if((i+1-j)<=j)upd(f[i+1][j],f[i][j]);

	}

	printf("%d\n",f[n<<1][n]);

	return 0;

}

巴特西