2021.05.05【NOIP提高B组】模拟 总结

T1

给你一棵树，要求增加最少的边权是的从根到每一个叶子的长度相等

不能改变原有的最大长度

这是一个贪心：尽可能往深度小的边增加

先预处理出 \(mx_i\) 表示从 \(i\) 到叶子的最大长度

然后 \(\text{dfs}\) ，传入一个 \(top\) 表示最大不能超过 \(top\)

对于一条边，分为两种情况

1. 是最大路径的边，只是 \(top\) 减少了这条边权
2. 不是最大路径的边，需要增加 \(top-mx_v-len_i\) ， \(top\) 变为 \(mx_v\)

#include<bits/stdc++.h>
using namespace std;
const int N=500005;
typedef long long LL;
int n,cnt,lst[N],nxt[N<<1],to[N<<1];
LL qz[N<<1],mx[N],ans;
inline void Ae(int fr,int go,int vl) {
	to[++cnt]=go,qz[cnt]=1LL*vl;
	nxt[cnt]=lst[fr],lst[fr]=cnt;
}
void pre(int u,int f) {
	for(int i=lst[u],v;i;i=nxt[i])
		if((v=to[i])^f) {
			pre(v,u);
			mx[u]=max(mx[u],mx[v]+qz[i]);
		}
}
void dfs(int u,int f,LL top) {
	for(int i=lst[u],v;i;i=nxt[i])
		if((v=to[i])^f) {
			if(mx[v]+qz[i]==mx[u])dfs(v,u,top-qz[i]);
			else ans+=top-mx[v]-qz[i],dfs(v,u,mx[v]);
		} 
}
int main() {
	scanf("%d",&n);
	for(int i=1,u,v,w;i<n;i++) {
		scanf("%d%d%d",&u,&v,&w);
		Ae(u,v,w),Ae(v,u,w);
	}
	pre(1,0);
	dfs(1,0,mx[1]);
	printf("%lld",ans);
}

T2

一个图中有 \(k\) 个关键点，现在需要从 1 到 \(n\) 往返一次，问在时间不超过 \(t\) 的前提下最多能经过多少关键点

满足经过关键点最多的同时时间最少，不能往返输出 \(-1\)

\(k\le 15\) 果断状压。

设 \(f_{s,i}\) 为过了关键点状态为 \(s\)，最后在 \(i\) 的最小时间

要经过起点和重点，于是把 1 和 \(n\) 加入关键点

因为走的最优方案肯定是走最短路，先预处理出关键点之间的最短路 \(dis\)

然后转移是 \(f_{s\cup j,j}=f_{s,i}+dis_{i,j}\)

最后处理答案，枚举状态 \(s\) ，枚举最后的点 \(i\) ，看 \(f_{s,i}+dis_{1,i}\le t\)

然后一波 \(lowbit\) 分解，一波比较

#include<bits/stdc++.h>
using namespace std;
const int N=10005,M=50005;
int n,m,K,T,cnt,p[25],x[N],lst[N],nxt[M<<1],to[M<<1],vis[N];
int D[N],dis[20][20],qz[M<<1],f[300005][20],ans1,ans2;
struct poi {
	int nw,vl; poi() { } poi(int _nw,int _vl):nw(_nw),vl(_vl) { }
	inline bool operator<(poi o) const { return o.vl<vl; }
};
priority_queue<poi>q;
inline void Ae(int fr,int go,int vl) {
	to[++cnt]=go,qz[cnt]=vl,nxt[cnt]=lst[fr],lst[fr]=cnt;
}
inline void dijk(int st) {
	memset(D,100,sizeof(D));
	memset(vis,0,sizeof(vis));
	D[st]=0,q.push(poi(st,0));
	register int u;
	while(!q.empty()) {
		u=q.top().nw,q.pop();
		if(vis[u])continue; vis[u]=1;
		for(int i=lst[u],v;i;i=nxt[i])
			if(D[u]+qz[i]<D[v=to[i]]) {
				D[v]=D[u]+qz[i];
				q.push(poi(v,D[v]));
			}
	}
}
int main() {
	for(int i=0;i<=20;i++)p[i]=1<<i;
	scanf("%d%d%d%d",&n,&m,&K,&T);
	for(int i=1,u,v,w;i<=m;i++) {
		scanf("%d%d%d",&u,&v,&w);
		Ae(u,v,w),Ae(v,u,w);
	}
	for(int i=1;i<=K;i++)scanf("%d",&x[i]);
	x[0]=1,x[++K]=n;
	for(int i=0;i<=K;i++) {
		dijk(x[i]);
		for(int j=0;j<=K;j++)
			dis[i][j]=D[x[j]];
	}
	memset(f,100,sizeof(f));
	f[1][0]=0;
	for(int s=0;s<p[K+1];s++)
		for(int i=0;i<=K;i++) if(s&p[i])
			for(int j=0;j<=K;j++) if(!(s&p[j]))
				f[s|p[j]][j]=min(f[s|p[j]][j],f[s][i]+dis[i][j]);
	ans2=2100000000;
	for(int s=0,tot,o;s<p[K+1];s++) {
		if((s&p[0]) && (s&p[K])) {
			tot=0,o=s;
			while(o)++tot,o-=o&-o;
			for(int i=0;i<=K;i++) {
				if(f[s][i]+dis[i][0]<=T) {
					if(tot>ans1)ans1=tot,ans2=f[s][i]+dis[i][0];
					else if(tot==ans1 && f[s][i]+dis[i][0]<ans2)
						ans2=f[s][i]+dis[i][0];					
				}
				
			}
		}
	}
	if(ans2>=2100000000)puts("-1");
	else printf("%d %d",ans1-2,ans2);
}

T3

题目大意：问对于 \(k\) 在 \(A\) 中异或最大值的位置，任意一个即可

板题！！！(对于我这种思维菜鸡来说)

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,m,tot,ch[N*80][2],id[N*80];
inline void ins(int p,int v) {
	register int u=0,s;
	for(int i=31;~i;i--) {
		s=v>>i&1;
		if(!ch[u][s])
			ch[u][s]=++tot;
		u=ch[u][s];
	}
	id[u]=p;
}
inline int ask(int v) {
	register int u=0,s;
	for(int i=31;~i;i--) {
		s=v>>i&1;
		if(ch[u][s^1])
			u=ch[u][s^1];
		else u=ch[u][s];
	}
	return id[u];
}
int main() {
	scanf("%d%d",&n,&m);
	for(int i=1,x;i<=n;i++) {
		scanf("%d",&x);
		ins(i,x);
	}
	for(int i=1,x;i<=m;i++) {
		scanf("%d",&x);
		printf("%d\n",ask(x));
	}
}

总结

1. 贪心要多想
2. 果断的决策： \(n\) 特别小一类的用状压
3. 板子一定不能挂