ABC #267 C、D、E、F

C - Index × A(Continuous ver.) (atcoder.jp)

考虑维护一个长度为m的滑动窗口，滑动窗口从左往右移动的过程中，维护\(\sum_{i=1}^Mi*B_i\)。

1. 右端点往后移动一格到位置i，对应res+=m*a[i]
2. 左端点往后移动一格到位置i，由于窗口中每个位置的编号都会减少1，所以需要减去的是一段连续和，假设s[i]=sum(a[1] to a[i])，则右移一格对应res-=s[r]-s[i-2]。

const int N=2e5+5;
typedef long long ll;
int n,m;
int a[N];
ll s[N];
ll res;

void del(int l,int r){
	res-=s[r]-s[l-1];
}

void add(int p,int k){
	res+=(ll)a[p]*k;
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		s[i]=s[i-1]+a[i];
	}
	
	ll ans=-1e18;
	for(int l=1,r=0;l<=n;del(l,r),l++){
		while(r-l+1<m && r<n){
			r++;
			add(r,r-l+1);
		}
		if(r-l+1==m)ans=max(ans,res);
	}
	
	cout<<ans<<endl;
	
	return 0;
}

D - Index × A(Not Continuous ver.) (atcoder.jp)

学魔怔了，想了一个\(O(N^3)\)的dp，在那优化了半天优化到\(O(N^2)\)。

当时dp的定义是：f[i][j]：前i个数中选择j个数并且选了i的所有方案，朴素的转移方程就是f[i][j]=max(f[t][j-1]+j*a[i]),t<i。然后发现dp过程中可以同时求出f[t][j-1]中的最大值，优化掉了一维。

const int N=2005;
typedef long long ll;
ll f[N][N];
ll g[N][N];
int n,m;
int a[N];

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	
	memset(f,-0x3f,sizeof(f)); memset(g,-0x3f,sizeof(g));
	f[0][0]=0;
	for(int i=0;i<=n;i++)g[i][0]=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m && j<=i;j++)g[i][j]=g[i-1][j];
		
		for(int j=1;j<=m && j<=i;j++){
			f[i][j]=max(f[i][j],g[i-1][j-1]+(ll)j*a[i]);
			g[i][j]=max(g[i][j],f[i][j]);
		}
	}
	
	ll ans=-1e18;
	for(int i=m;i<=n;i++)ans=max(ans,f[i][m]);
	cout<<ans<<endl;
	return 0;
}

其实可以直接定义：f[i][j]：前i个数中选择j个数的所有方案，转移的时候看a[i]选或者不选。实现的时候可以把第一位滚动掉。

typedef long long ll;
const int N=2005;
ll f[N];
int n,m;
int a[N];

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	
	memset(f,-0x3f,sizeof(f));
	f[0]=0;
	for(int i=1;i<=n;i++){
		for(int j=m;j>=1;j--){
			f[j]=max(f[j],f[j-1]+(ll)j*a[i]);
		}
	}

	cout<<f[m]<<endl;
	return 0;
}

E - Erasing Vertices 2 (atcoder.jp)

二分答案。

首先，可以预处理出删除每个点需要的代价s[i]。

二分删除所有点过程中的最大代价，我们需要将这个代价最小化，考虑如何写check函数。

假设二分的最大代价是mid：

1. 一开始，可以把所有s[i]<=mid的点都加入到栈中，并且打上标记，表示这些是可以删除的点。
2. 每次从栈顶取出一个点，把它删去，注意到删去一个点只会影响到它周边点的s[i]值，我们只需要暴力维护一下周边点的s[i]即可。
3. 维护周边点的s[i]的时候，如果该点不在栈中且s[i]<=mid，就把它加入栈中；如果该点在栈中，由于它的s[i]是单调减少的，所以无妨。
4. 最后看是否所有点都打上了标记即可。

typedef long long ll;
const int N=2e5+5,M=2*N;
int n,m;
int a[N];
ll s[N],f[N];
int e[M],ne[M];
int h[N],idx;
int stk[N],vis[N],top;

void adde(int x,int y){
	e[idx]=y; ne[idx]=h[x]; h[x]=idx++;
}

bool check(ll gap){
	top=0;
	memcpy(f,s,sizeof(f));
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++)
	 	if(f[i]<=gap){
	 		stk[++top]=i;
	 		vis[i]=1;
	 	}
	 	
	while(top){
		int u=stk[top--];
		for(int i=h[u];~i;i=ne[i]){
			int v=e[i];
			f[v]-=a[u];
			if(f[v]<=gap && !vis[v]){
				stk[++top]=v;
				vis[v]=1;
			}
		}
	}
	
	for(int i=1;i<=n;i++)
		if(!vis[i])return 0;
		
	return 1;
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	
	int x,y;
	memset(h,-1,sizeof(h));
	for(int i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		adde(x,y); adde(y,x);
	}
	
	for(int i=1;i<=n;i++){
		for(int j=h[i];~j;j=ne[j]){
			int v=e[j];
			s[i]+=a[v];
		}
	}
	
	ll l=0,r=2e14+1;
	while(l<r){
		ll mid=(l+r)>>1;
		if(check(mid))r=mid;
		else l=mid+1;
	}
	cout<<l<<endl;
	return 0;
}

F - Exactly K Steps (atcoder.jp)

树的直径，k级祖先。

根据树的直径的性质，我们可以知道距离树上任意一点u最远的点一定是直径的端点，因此问题就转化成了：从直径的其中一个端点为根，找到u的k级祖先。

直径的两个端点可以用两遍dfs求出。

k级祖先考虑用栈+离线+dfs的方法来求：用栈维护当前dfs从跟到u的路径上的点，可以知道如果u存在k级祖先，stack[top-k]就是满足条件的一个。

const int N=2e5+5,M=2*N;
int n,q;
int e[M],ne[M];
int h[N],idx;
int d1,d2,ma;
int dep[N];
struct que{
	int x,k;
}qz[N];
vector<int>w[N],ans[N];
int stk[N],top;

void adde(int x,int y){
	e[idx]=y; ne[idx]=h[x]; h[x]=idx++;
}

void dfs_far(int u,int fa,int &d){
	dep[u]=dep[fa]+1;
	if(dep[u]>ma){
		d=u; ma=dep[u];
	}
	
	for(int i=h[u];~i;i=ne[i]){
		int v=e[i];
		if(v==fa)continue;
		dfs_far(v,u,d);
	}
}

void dfs_anc(int u,int fa){
	stk[++top]=u;
	for(int i=0;i<w[u].size();i++){
		int k=w[u][i];
		if(top>k)ans[u][i]=stk[top-k];
	}

	for(int i=h[u];~i;i=ne[i]){
		int v=e[i];
		if(v==fa)continue;
		dfs_anc(v,u);
	}
	
	top--;
}

int main(){
	scanf("%d",&n);
	int x,y;
	memset(h,-1,sizeof(h));
	for(int i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		adde(x,y); adde(y,x);
	}
	
	dfs_far(1,0,d1);
	memset(dep,0,sizeof(dep)); ma=0;
	dfs_far(d1,0,d2);
	
	scanf("%d",&q);
	for(int i=1;i<=q;i++){
		scanf("%d%d",&x,&y);
		w[x].push_back(y);
		qz[i]={x,(int)w[x].size()-1};
	}
	for(int i=1;i<=n;i++)ans[i].resize((int)w[i].size());
	
	dfs_anc(d1,0);
	dfs_anc(d2,0);

	for(int i=1;i<=q;i++){
		int val=ans[qz[i].x][qz[i].k];
		if(!val)printf("%d\n",-1);
		else printf("%d\n",val);
	}
	
	return 0;
}