T1

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

不能改变原有的最大长度

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

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

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

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

是最大路径的边，只是 \(top\) 减少了这条边权
不是最大路径的边，需要增加 \(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));

	}

}

总结

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

巴特西

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

T1

T2

T3

总结

最新文章

热门文章

巴特西

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

T1

T2

T3

总结

最新文章

热门文章

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