AtCoder Grand Contest 009 题解

为啥这场题目少一点啊……

(A)

易知增加的数前面肯定比后面大，那么我们倒着做，然后维护一下最小要加多少就可以了

typedef long long ll;
const int N=1e5+5;
int a[N],b[N],n;ll sum;
int main(){
	scanf("%d",&n);
	fp(i,1,n)scanf("%d%d",&a[i],&b[i]);
	fd(i,n,1)sum=(a[i]+sum+b[i]-1)/b[i]*b[i]-a[i];
	printf("%lld
",sum);
	return 0;
}

(B)

把(a_i)当做(i)的父亲，那么问题可以转化为对于(u)，使每一个儿子的深度分别增加(1,2,3,...)，最终使深度最深的点深度最小。那么我们对于每一个(u)把它的所有儿子按深度从大到小排序之后分别加上(1,2,3...)即可

//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 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;
const int N=1e5+5;
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 d[N],st[N],top,n;
inline bool cmp(const int &x,const int &y){return d[x]>d[y];}
void dfs(int u){
	d[u]=0;
	go(u)dfs(v);
	top=0;go(u)st[++top]=v;
	sort(st+1,st+1+top,cmp);
	fp(i,1,top)cmax(d[u],d[st[i]]+i);
}
int main(){
	scanf("%d",&n);
	for(R int fa,i=2;i<=n;++i)scanf("%d",&fa),add(fa,i);
	dfs(1);
	printf("%d
",d[1]);
	return 0;
}

(C)

先考虑暴力的(dp)，设当前在位置(k)，已经算出了(f_{k,i})表示当前位置(k)选则放在(A)中，且上一个放在(B)中的位置为(i)的方案数，(g_{k,i})表示当前位置(k)选则放在(B)中，且上一个放在(A)中的位置为(i)的方案数

如果(a_{k+1}-a_kgeq A)，那么(f_{k,i})可以转移到(f_{k+1,i})。如果(a_{k+1}-a_igeq B)，那么(f_{k,i})可以转移到(g_{k+1,k})

(g)的转移同理

那么仔细考虑，发现每一次转移只会让某一个前缀清零，或者更新(f_{k+1,k})和(g_{k+1,k})，那么我们对于(f,g)分别记下第一个不为(0)的位置，以及对于每一个(k)记下它放在(A/B)中时前一个数最大的位置是多少，那么一次转移就可以看做是前缀清零和区间查询，树状数组维护即可

//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 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;
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;
}
typedef long long ll;
const int N=1e5+5;
int n,ma,mb,la[N],lb[N];ll A,B,a[N];
struct bit{
	int c[N];
	inline void chg(R int x,R int y){for(++x;x<=n+1;x+=x&-x)upd(c[x],y);}
	inline int qwq(R int x){R int res=0;for(++x;x;x-=x&-x)upd(res,c[x]);return res;}
	inline int query(R int l,R int r){return l>r?0:dec(qwq(r),qwq(l-1));}
}f,g;
int main(){
	scanf("%d%lld%lld",&n,&A,&B);
	fp(i,1,n)scanf("%lld",&a[i]);
	for(R int i=1,ia=0,ib=0;i<=n;++i){
		while(ia<n&&a[ia+1]<=a[i]-A)++ia;
		while(ib<n&&a[ib+1]<=a[i]-B)++ib;
		la[i]=ia,lb[i]=ib;
	}
	ma=mb=0,f.chg(0,1),g.chg(0,1);
	fp(i,2,n){
		R int df=g.query(mb,la[i]),dg=f.query(ma,lb[i]);
		f.chg(i-1,df),g.chg(i-1,dg);
		if(a[i]-a[i-1]<A)ma=i-1;
		if(a[i]-a[i-1]<B)mb=i-1;
	}
	printf("%d
",add(f.query(ma,n),g.query(mb,n)));
	return 0;
}

(D)

挺巧妙的，想不到啊~~

首先如果我们采用点分的话，很容易发现上界是(O(log n))级别的，不过这样并不一定最优

我们考虑给每个点编号，如果同时有两个点(u,v)的编号为(k)，那么它们的路径上至少要有一个点的编号大于(k)

那么就分成两种情况讨论，如果(u)的两个不同子树中同时有(k)，则(u)的编号必须大于(k)

如果(u)的某个子树中有(k)且那个(k)到(u)的路径上没有其它大于(k)的点，则(u)不能取(k)

那么直接树形(dp)即可，具体细节看代码

//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 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;
const int N=1e5+5;
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,res;
void dfs(int u,int fa){
	R int s=0;
	go(u)if(v!=fa)dfs(v,u),s|=(f[u]&f[v]),f[u]|=f[v];
	if(!f[u])return f[u]=1,void();
	R int c=0;
	while((1<<c)<=s||(f[u]>>c&1))++c;
	f[u]=((f[u]>>c|1)<<c),cmax(res,c);
}
int main(){
	scanf("%d",&n);
	for(R int i=1,u,v;i<n;++i)scanf("%d%d",&u,&v),add(u,v),add(v,u);
	dfs(1,0);
	printf("%d
",res);
	return 0;
}

(E)

这题是真的神仙啊……

首先我们把它转化为一棵(k)叉树，其中每个点有(k)个叶子，总共有(n+m)个叶节点，其中有(n)个黑色（权值为(1)）和(m)个白色（权值为(0)），每一个节点的权值为它所有儿子的平均值，那么根节点的权值就是最终的答案

我们发现，如果一个黑色节点(i)的深度为(d_i)，那么根节点最终的答案就是(x_1=sum k^{-d_i})

那么我们再设所有白色节点的权值为(1)，然后把这一部分的贡献记为(x_0)，那么就有一个很显然的结论是(x_0+x_1=1)。那么一个方案合法，当且仅当(x_0)和(x_1)都合法且(x_0+x_1=1)

这个条件的充分性显然，而必要性的话，我们就要证明如果(x_0+x_1=1)必定有合法解。首先如果(sum k^{-d_i}=1)，那么深度最深的点的个数必定是(k)的倍数（否则它们的和不可能是整数），我们把这些点合并为深度(-1)的点，一直合并下去直到最后只剩一个点，说明这样肯定合法

我们把(x_1)转化为一个(k)进制小数((0.a_1a_2a_3a_4....a_l))，其中(a_l eq 0)，那么要保证(x_1)和(1-x_1)都合法。先来考虑(x_1)，如果进位的话，可以看做是在这(l)个位置上加上总共(n)个(1)。然而加上进位的话似乎就比较辣手了，考虑到一次进位会使(k)个(1)变为(1)个(1)，相当于总数减去(k-1)，那么如果(x_1)合法则有(sum a_iequiv npmod{k-1})，反之如果这两个同余，我们一定可以构造出(x_1)，所以这就是充要条件

然后还得保证(1-x_1)合法，我们可以把(1)给(k)进制分解成一个(b_1=k-1,b_2=k-1,b_3=k-1,...,b_l=k)的数，那么(x_0)的第(i)位(c_i)就可以看做(k-1-a_i)，除了第(l)位。因为我们强制(x_1)的第(l)位不为(0)，所以(x_0)的第(l)位也不为(0)，那么我们强制(c_l)先放一个数，然后再(--m)，那么(c_l)也等于(k-1-a_i)了，这样这个条件和(x_1)的就差不多了

综上所述，一个(x_1)合法当且仅当满足以下条件

[egin{aligned} & sum_{i=1}^l a_ileq n\ & sum_{i=1}^l a_iequiv npmod{k-1}\ & sum_{i=1}^l (k-1)-a_ileq m\ & sum_{i=1}^l (k-1)-a_iequiv mpmod{k-1}\ end{aligned} ]

设(f[i][j])表示(x_1)有(i)位，且所有位置的和为(j)的方案数，这个可以直接(O(n^2)dp)算出，如果对应的(x_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 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;
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=2005;
int f[2][N],s[N],n,m,k,t,l,res;
inline int min(R int x,R int y){return x<y?x:y;}
int main(){
	scanf("%d%d%d",&n,&m,&k),l=(n+m-1)/(k-1),--m;
	f[0][0]=1,t=0;
	for(R int i=1;i<=l;++i,t^=1){
		s[0]=f[t][0];
		fp(j,1,n)s[j]=add(s[j-1],f[t][j]);
		fp(j,0,min(n,k-1))f[t^1][j]=s[j];
		fp(j,k,n)f[t^1][j]=dec(s[j],s[j-k]);
		fp(j,1,n)if(j%(k-1)==n%(k-1)&&i*(k-1)-j<=m&&(i*(k-1)-j)%(k-1)==m%(k-1))
			upd(res,dec(f[t^1][j],f[t][j]));
	}
	printf("%d
",res);
	return 0;
}