AtCoder Grand Contest 001 题解

传送门

\(A\)

咕咕咕

const int N=505;

int a[N],n,res;

int main(){

	scanf("%d",&n);

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

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

	fp(i,1,n)res+=a[(i<<1)-1];

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

	return 0;

}

\(B\)

考虑递归，记\(las\)表示画的上一个三角形的边长，\(now\)为现在的三角形的边长，如果\(now|las\)，则再走\(las*2-las\)就可以到终点，否则我们可以走\(now\)的整数倍次，也就是说取个模，然后再计算下一个\(las\)和\(now\)就行了，复杂度为\(O(\log n)\)

建议画图理解

ll n,x,res,las,now,t;

int main(){

	scanf("%lld%lld",&n,&x);

	res=n,las=n-x,now=x;

	while(now){

		if(las%now==0){res+=(las<<1)-now;break;}

		res+=(las/now*now)<<1,t=now,now=las%now,las=t;

	}

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

	return 0;

}

\(C\)

记\(f_{u,i}\)表示考虑\(u\)的子树内，且\(u\)子树内未被删去的点中深度最深的点里\(u\)的距离为\(i\)，此时子树内剩余的点数最多为多少，转移只用合法的状态转移就是了

//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=2005;

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

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

int f[N][N],g[N],mx[N],n,res,k;

void dfs(int u,int fa){

	memset(f[u],0xef,sizeof(f[u]));

	f[u][0]=1;

	go(u)if(v!=fa){

		dfs(v,u),memcpy(g,f[u],(max(mx[u],mx[v]+1)+1)<<2);

		fp(i,0,mx[u])fp(j,0,mx[v])if(i+j+1<=k)

			cmax(g[max(i,j+1)],f[u][i]+f[v][j]);

		cmax(mx[u],mx[v]+1),memcpy(f[u],g,(mx[u]+1)<<2);

	}

}

int main(){

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

	for(R int i=1,u,v;i<n;++i)scanf("%d%d",&u,&v),add(u,v),add(v,u);

	dfs(1,0);

	fp(i,1,n)fp(j,0,min(mx[i],k))cmax(res,f[i][j]);

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

	return 0;

}

\(D\)

首先如果奇数的个数超过\(2\)就无解了，具体可以把回文串的相同看做连边，至少得连成一棵生成树，奇数的话中间的点就无法连边了，所以奇数大于\(2\)就\(gg\)

否则的话我们把奇数放到两边，并把最两边分别\(+1-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 N=1e5+5;

int st[N],a[N],id[N],tt,n,m,top;

inline void Ot(){printf("%d\n",top);fp(i,1,top)printf("%d%c",st[i]," \n"[i==top]);}

int main(){

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

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

	fp(i,1,m){

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

		if(a[i]&1)id[++tt]=i;

	}

	if(tt>2)return puts("Impossible"),0;

	if(tt>0)swap(a[1],a[id[1]]);if(tt>1)swap(a[m],a[id[2]]);

	fp(i,1,m)printf("%d%c",a[i]," \n"[i==m]);

	if(m==1){

		st[++top]=1;

		if(a[1]-1)st[++top]=a[1]-1;

	}else{

		--a[1],++a[m];

		fp(i,1,m)if(a[i])st[++top]=a[i];

	}

	return Ot(),0;

}

\(E\)

好吧的确还是比较菜……

我们把\({a_i+b_i+a_j+b_j\choose a_i+a_j}\)变成从\((-a_i,-b_i)\)走到\((a_j,b_j)\)的方案数，那么可以直接通过\(O(MAX^2)\)的\(dp\)算出\(\sum_{i=1}^n\sum_{j=1}^n{a_i+b_i+a_j+b_j\choose a_i+a_j}\)，减掉多算的就行了

//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=2e5+5,M=5005,S=2005;

int a[N],b[N],fac[N],ifac[N],f[M][M],xmx,ymx,n,res;

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

void init(int n){

	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(){

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

	scanf("%d",&n);

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

	init((xmx+ymx)<<1);

	fp(i,1,n)++f[S-a[i]][S-b[i]];

	fp(i,S-xmx,S+xmx)fp(j,S-ymx,S+ymx)if(f[i][j])upd(f[i+1][j],f[i][j]),upd(f[i][j+1],f[i][j]);

	fp(i,1,n)upd(res,f[S+a[i]][S+b[i]]);

	fp(i,1,n)res=dec(res,C((a[i]+b[i])<<1,a[i]<<1));

	printf("%d\n",mul(res,(P+1)>>1));

	return 0;

}

\(F\)

很妙的转化

我们设一个新的序列\(Q\)，其中\(Q_{P_i}=i\)，那么操作可以变成“如果\(|Q_i-Q_{i+1}|\geq k\)，则可以交换\(Q_i\)和\(Q_{i+1}\)”，我们需要让\(1\)这个元素在最左边，在满足这个条件的时候让\(2\)在最左边，在满足这个条件时让\(3\)在最左边……

假设在\(Q\)中存在\(i,j\)满足\(i<j\)且\(|Q_i-Q_j|<k\)，那么在\(Q\)中\(Q_i\)在\(Q_j\)左边，任意次操作之后\(Q_i\)也一定还在\(Q_j\)的左边

此时我们可以从\(Q_i\)向\(Q_j\)连一条边，易知连完边之后的图一定是一个\(DAG\)，那么我们找到这个\(DAG\)最小的拓扑序就好了

然而这样的话边数会爆炸

考虑优化，若存在\(i,j\)满足\(i<j\)且\(j-i<k\)且\(P_j<P_i\)，则在图中会连边\(j,i\)，若\(i\)满足\(i=\min(l,P_l>P_j,l\in[j-k+1,j-1])\)，则对于任意\(l\)，必定有连边\((j,l)\)，同时也必定有连边\((i,l)\)！那么我们只需要连边\((j,i)\)，即可满足拓扑的要求了。对于\(j\)的右边同样如此

用线段树优化即可

//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=1e6+5,inf=0x3f3f3f3f;

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

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

inline int min(R int x,R int y){return x<y?x:y;}

struct node;typedef node* ptr;

struct node{

	ptr lc,rc;int mn;

	inline void upd(){mn=min(lc->mn,rc->mn);}

}E[N<<2],*nd=E,*rt;

priority_queue<int,vector<int>,greater<int> >q;int deg[N],pos[N],id[N],n,k;

void build(ptr &p,int l,int r){

	p=++nd;if(l==r)return p->mn=inf,void();

	int mid=(l+r)>>1;

	build(p->lc,l,mid),build(p->rc,mid+1,r);

	p->upd();

}

void update(ptr p,int l,int r,int x,int v){

	if(l==r)return p->mn=v,void();

	int mid=(l+r)>>1;

	x<=mid?update(p->lc,l,mid,x,v):update(p->rc,mid+1,r,x,v);

	p->upd();

}

int res;

void query(ptr p,int l,int r,int ql,int qr){

	if(ql<=l&&qr>=r)return cmin(res,p->mn),void();

	int mid=(l+r)>>1;

	if(ql<=mid)query(p->lc,l,mid,ql,qr);

	if(qr>mid)query(p->rc,mid+1,r,ql,qr);

}

int main(){

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

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

	for(R int i=1,x;i<=n;++i)scanf("%d",&x),pos[x]=i;

	build(rt,1,n);

	for(R int i=n,l,r;i;--i){

		l=max(pos[i]-k+1,1),r=pos[i]-1,res=inf;

		if(l<=r)query(rt,1,n,l,r);if(res!=inf)add(pos[i],pos[res]),++deg[pos[res]];

		l=pos[i]+1,r=min(pos[i]+k-1,n),res=inf;

		if(l<=r)query(rt,1,n,l,r);if(res!=inf)add(pos[i],pos[res]),++deg[pos[res]];

		update(rt,1,n,pos[i],i);

	}

	fp(i,1,n)if(!deg[i])q.push(i);

	for(R int u,i=1;i<=n;++i){

		u=q.top(),q.pop(),id[u]=i;

		go(u)if(!--deg[v])q.push(v);

	}

	fp(i,1,n)printf("%d\n",id[i]);

	return 0;

}