USACO 2019 Dec Gold 题解

2026年9月29日 · 阅读需 9 分钟

laieahoy

管理员

A. 集章活动 3

环上问题，首先肯定会考虑断环成链，这道题也不例外，于是先断环成链。

断环成链后，问题就变成了一个很经典的区间 DP 问题，我们可以设 $f[l][r][0/1][k]$ 为当前顺时针走了 $l$ ，逆时针走了 $r$ ，当前位置是顺/逆时针走来的，收集了 $k$ 枚印章时，最少需要多长时间，转移很简单，暂且不提。

但是我们发现，若是直接这样做，加上枚举断点的时间，时间复杂度为 $O(n^4)$ ，对于 $n\le 200$ 的数据，肯定是会超时的，所以我们需要优化。

观察转移，发现每次转移其实只需要用到 $0$ 至 $l$ 加上 $r+1$ 至 $n$ 与 $0$ 至 $l-1$ 加上 $r$ 至 $n$ 两段区间，换个角度，即每次扩展时只会向外扩展一个点，所以我们可以枚举当前区间经过了多少个点 $s$ ，那么转移只会从 $s-1$ 的状态中来，于是就可以用滚动数组优化了。而我们又发现，当 $s$ 固定后，如果知道 $l$ 或 $r$ 中任何一个量，都可以算出另外一个量，于是可以将 $l$ 或 $r$ 这一维优化掉，代码中是优化掉了 $r$ 。

点击展开代码

代码：

#include<iostream>
#include<algorithm>
#include<string.h>
using namespace std;
typedef long long ll;

const int N=205;
const ll inf=1e18;
int n,L,ans;
ll x[N],T[N];
ll f[N][N][2],lf[N][N][2];

int main()
{
	cin>>n>>L;
	for(int i=1;i<=n;i++) cin>>x[i];
	x[n+1]=L;
	for(int i=1;i<=n;i++) cin>>T[i];
	for(int l=0;l<=n;l++){
		for(int k=0;k<=n;k++){
			lf[l][k][0]=lf[l][k][1]=inf;
		}
	}
	lf[0][0][0]=lf[0][0][1]=0;
	for(int s=1;s<=n;s++){
		for(int l=0;l<=n;l++){
			for(int k=0;k<=n;k++){
				f[l][k][0]=f[l][k][1]=inf;
			}
		}
		for(int l=0;l<=s;l++){
			int r=n+1-(s-l);
			for(int k=0;k<=s;k++){
				if(l>=1){
					f[l][k][0]=min(lf[l-1][k][0]+x[l]-x[l-1],lf[l-1][k][1]+L-x[r]+x[l]);
					if(k&&lf[l-1][k-1][0]+x[l]-x[l-1]<=T[l]) f[l][k][0]=min(f[l][k][0],lf[l-1][k-1][0]+x[l]-x[l-1]);
					if(k&&lf[l-1][k-1][1]+L-x[r]+x[l]<=T[l]) f[l][k][0]=min(f[l][k][0],lf[l-1][k-1][1]+L-x[r]+x[l]);
				}
				if(r<=n){
					f[l][k][1]=min(lf[l][k][1]+x[r+1]-x[r],lf[l][k][0]+L-x[r]+x[l]);
					if(k&&lf[l][k-1][1]+x[r+1]-x[r]<=T[r]) f[l][k][1]=min(f[l][k][1],lf[l][k-1][1]+x[r+1]-x[r]);
					if(k&&lf[l][k-1][0]+L-x[r]+x[l]<=T[r]) f[l][k][1]=min(f[l][k][1],lf[l][k-1][0]+L-x[r]+x[l]);
				}
			}
		}
		for(int l=0;l<=n;l++){
			for(int k=0;k<=n;k++){
				lf[l][k][0]=f[l][k][0];
				lf[l][k][1]=f[l][k][1];
				if(min(f[l][k][0],f[l][k][1])<inf) ans=max(ans,k);
			}
		}
	}
	cout<<ans<<"\n";

	return 0;
}

B. Milk Pumping 牛奶运输

发现最后要求的答案只受两个量的影响：路径上的最小流量与路径长度。由于我们需要求使最终答案最大，所以要尽量使流量更大，路径更短。

同时处理两个量是很困难的，所以先固定一个量，若是固定路径长度显然是不好做的，但是若固定最小流量的话，其实就是跑一个有限制的最短路，发现这个限制对整个最短路算法的流程与正确性是没有影响的，所以我们可以枚举最小流量，再用 dijkstra 跑最短路，时间复杂度为 $O(N^2 logN)$ ，在 $N$ 只有 $1000$ 的情况下是能过的。

点击展开代码

代码：

#include<iostream>
#include<algorithm>
#include<string.h>
#include<queue>
#define x first
#define y second
using namespace std;
typedef pair<int,int> pii;

const int N=1005;
const double M=1000000;
int n,m,ma;
int e[N<<1],ne[N<<1],w[N<<1],d[N<<1],h[N],idx;
int dis[N];
bool vis[N];
int ans;

void add(int a,int b,int c,int f)
{
	e[idx]=b;
	ne[idx]=h[a];
	w[idx]=c;
	d[idx]=f;
	h[a]=idx++;
}

void dijkstra(int x,int lim)
{
	priority_queue<pii,vector<pii>,greater<pii>> heap;
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof vis);
	dis[x]=0;
	heap.push({0,x});
	while(heap.size()){
		pii t=heap.top();
		heap.pop();
		int u=t.y;
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=h[u];~i;i=ne[i]){
			int v=e[i],ww=w[i],f=d[i];
			if(dis[v]>dis[u]+ww&&f>=lim){
				dis[v]=dis[u]+ww;
				heap.push({dis[v],v});
			}
		}
	}
}

int main()
{
	memset(h,-1,sizeof h);
	cin>>n>>m;
	for(int i=1,a,b,c,f;i<=m;i++){
		cin>>a>>b>>c>>f;
		ma=max(ma,f);
		add(a,b,c,f),add(b,a,c,f);
	}
	for(int lim=0;lim<=ma;lim++){
		dijkstra(1,lim);
		ans=max(ans,(int)((double)lim/(double)dis[n]*M));
	}
	cout<<ans<<"\n";

	return 0;
}

C. Milk Visits 牛奶拜访

判断一个数在一条路径中是否出现过，就是看这个数在这段路径中的出现次数是否大于 $0$ ，所以我们设某个数 $c$ 在从根到点 $x$ 的路径中出现次数为 $cnt[x][c]$ ，那么对于每个询问 ${u,v,c}$ ，即询问 $u$ 到 $v$ 的路径上 $c$ 出现多少次，我们可以用如下方式计算每个询问路径的信息。

ans=cnt[u][c]+cnt[v][c]-cnt[lca(u,v)][c]-cnt[fa[lca(u,v)][c]

可是这样的话空间会爆，需要考虑优化。

注意到，对于每个询问，我们会用到计算中的只有 $u$ ， $v$ ， $lca(u,v)$ ， $fa[lca(u,v)]$ 这几个点，所以实际是不需要记录每个点的 $cnt$ 的全部信息的，只需要知道到这个点时，某个颜色出现了多少次，因为我们可以将询问挂到点上，后续 dfs 遍历到某个点时再计算挂到这个点上的询问，具体地，我们对于 $u$ ， $v$ ，在这两个点上存 ${c,+1,id}$ ，表示遍历到这两个点时，需要在第 $id$ 个询问上加当前点到根的路径上 $c$ 的出现次数，而在另外两个点上存 ${c,-1,id}$ ，含义类似。

现在的问题就是如何知道遍历到某个点当前点到根的路径上 $c$ 的出现次数，由于我们知道，每进入一个点，它的子树中每个点到根的路径上这个点所对应的数字出现次数就会加 $1$ ，而出这个点后，即已经遍历完它的子树后，它的贡献就消失了，所以我们可以维护一个全局桶 $cnt$ ，在进入一个点 $u$ 时 $cnt[type[u]]$ 加 $1$ ，出这个点时 $cnt[type[u]]$ 减 $1$ 。

详见代码。

点击展开代码

代码：

#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
#include<cmath>
using namespace std;

const int N=1e5+5,LOG=20;
int n,m;
int t[N];
int e[N<<1],ne[N<<1],h[N],idx;
int ans[N];
int f[N],dfn[N],cnt;
int st[N][30];
struct node{int c,x,id;};
vector<node> op[N];
int sum[N];

void add(int a,int b)
{
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx++;
}

void dfs(int u,int fa)
{
	dfn[u]=++cnt;
	st[cnt][0]=fa;
	f[u]=fa;
	for(int i=h[u];~i;i=ne[i]){
		int v=e[i];
		if(v==fa) continue;
		dfs(v,u);
	}
}

int get(int a,int b)
{
	return dfn[a]<dfn[b]?a:b;
}

int get_lca(int a,int b)
{
	if(a==b) return a;
	a=dfn[a],b=dfn[b];
	if(a>b) swap(a,b);
	int d=log2(b-a);
	return get(st[a+1][d],st[b-(1<<d)+1][d]);
}

void dfs2(int u)
{
	sum[t[u]]++;
	for(auto i:op[u]){
		ans[i.id]+=i.x*sum[i.c];
	}
	for(int i=h[u];~i;i=ne[i]){
		int v=e[i];
		if(v==f[u]) continue;
		dfs2(v);
	}
	sum[t[u]]--;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	memset(h,-1,sizeof h);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>t[i];
	for(int i=1,a,b;i<n;i++){
		cin>>a>>b;
		add(a,b),add(b,a);
	}
	dfs(1,0);
	for(int i=1;i<=LOG;i++){
		for(int j=0;j+(1<<i)-1<=n;j++){
			st[j][i]=get(st[j][i-1],st[j+(1<<(i-1))][i-1]);
		}
	}
	for(int i=1,a,b,c;i<=m;i++){
		cin>>a>>b>>c;
		int l=get_lca(a,b);
		op[a].push_back({c,1,i});
		op[b].push_back({c,1,i});
		op[l].push_back({c,-1,i});
		op[f[l]].push_back({c,-1,i});
	}
	dfs2(1);
	for(int i=1;i<=m;i++){
		if(ans[i]>0) cout<<1;
		else cout<<0;
	}
	cout<<"\n";

	return 0;
}

A. 集章活动 3​

B. Milk Pumping 牛奶运输​

C. Milk Visits 牛奶拜访​

A. 集章活动 3

B. Milk Pumping 牛奶运输

C. Milk Visits 牛奶拜访