CF974 Review

(以后比较简单的题就不写了)

A B C

skip

D

个人写了 \(O(n\log n)\) 的类模拟算法，能过，但不能做到 $O(n) $ 。

考虑什么时候一段 \([st,st+d-1]\) 的时间会和某一段区间有重合，也就是我自己写的算法的核心思想其实。

那就是 $st+d-1\ge l_i \quad st\le r_i $ ，变形一下就可以得到 \(l_i-d+1\le st\le r_i\) ，也就是会对所有满足开头 \(st\) 在上述范围内的答案产生 \(+1\) 的贡献，那么直接进行差分数组区间加就可以了。

E

仍然是普通的最短路，但是到了某些节点之后（有马），就可以使得之后的前进过程都只消耗 \(w/2\) 的代价，并且是两个人同时出发，最后在一点汇合（可以停下等待）。

后者非常好解决，我们只需要跑两次最短路，然后枚举中间汇合的点就好了。

那么如何处理前者？就要用到分层最短路。

对于任何一个有马的节点，我们都向更高一层建一条边，而更高一层的所有边权都是底层对应的一半。最后的最短路就是两张图取一个 min 就行。

#include<bits/stdc++.h>
#define int long long 
using namespace std;
template<typename T>inline void re(T &x)
{
	x=0;int f=1;char c=getchar();
	while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
	while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
	x*=f;
}
template<typename T>inline void wr(T x)
{
	if(x<0)putchar('-'),x=-x;
	if(x>9)wr(x/10);
	putchar(x%10^48);
}
int n,m,h;
struct Edge
{
	int u,v,w,nex;
}e[2000010];
int tote,head[400010],vis[400010];
inline void add(int u,int v,int w)
{
	e[++tote].u=u,e[tote].v=v,e[tote].w=w;
	e[tote].nex=head[u],head[u]=tote;
}
struct Node
{
	int x,dis;
};
bool operator <(Node a,Node b)
{
	return a.dis>b.dis;
}
const int inf=1e15+1;
int dis1[400010],disn[400010];
inline void dj()
{
	for(register int i=1;i<=2*n;++i)dis1[i]=inf,vis[i]=0;
	dis1[1]=0;
	priority_queue<Node> q;
	q.push(Node{1,0});
	while(q.size())
	{
		int x=q.top().x;q.pop();
		if(vis[x])continue;
		for(int i=head[x];i;i=e[i].nex)
		{
			int v=e[i].v,w=e[i].w;
			if(dis1[x]+w<dis1[v])
			{
				dis1[v]=dis1[x]+w;
				q.push(Node{v,dis1[v]});
			}
		}
		vis[x]=1;
	}
	
	for(register int i=1;i<=2*n;++i)disn[i]=inf,vis[i]=0;
	disn[n]=0;
	priority_queue<Node> q1;
	q1.push(Node{n,0});
	while(q1.size())
	{
		int x=q1.top().x;q1.pop();
		if(vis[x])continue;
		for(int i=head[x];i;i=e[i].nex)
		{
			int v=e[i].v,w=e[i].w;
			if(disn[x]+w<disn[v])
			{
				disn[v]=disn[x]+w;
				q1.push(Node{v,disn[v]});
			}
		}
		vis[x]=1;
	}
	
}	
inline void pre()
{
	tote=0;
	memset(head,0,sizeof(head));
	re(n),re(m),re(h);
	int tmp;
	for(register int i=1;i<=h;++i)
	{
		re(tmp);
		add(tmp,tmp+n,0);
	}
	for(register int i=1;i<=m;++i)
	{
		int u,v,w;
		re(u),re(v),re(w);
		add(u,v,w),add(v,u,w);
		add(u+n,v+n,w/2),add(v+n,u+n,w/2);
	}
	dj();
//	puts("display:");
//	for(register int i=1;i<=n;++i)printf("%lld ",dis1[i]);
//	printf("\n");
//	for(register int i=1;i<=n;++i)printf("%lld ",disn[i]);
//	printf("\n");
}
inline void solve()
{
	int ans=1e15+2;
	for(register int i=1;i<=n;++i)
	{
		if(dis1[i]==inf||disn[i]==inf)continue;
		ans=min(ans,max(min(dis1[i],dis1[i+n]),min(disn[i],disn[i+n])));
	}
	if(ans==1e15+2)puts("-1");
	else wr(ans),putchar('\n');
}
signed main()
{
	int T;
	cin>>T;
	while(T--)
	{
		pre();
		solve();
	}
	return 0;
}

F

一道很基础的树形dp，当时前四道题交了六发罚时心态爆炸没看后面了。

实际上我也不知道我能不能做出来，虽然这个树形dp确实贴脸上了。

定义 \(dp[x][0/1]\) 为当前点 \(x\) 选/不选，能得到的以 \(x\) 为根的子树的最大价值。

由于考虑的是一个树形结构，所以如果要选择当前节点，我们只用考虑它向下的影响，因为之后我们会在他的计算他的父亲时考虑它向上的影响。

当然还需要注意的就是我们只会统计维修过的节点，因此如果一个节点的状态是没有维修，也就是 \(dp[x][0]\) ，那么附近的节点是不会对它产生 \(-c\) 的影响的，所以只有当一条边连接的两个点状态都是 \(1\) 的时候才会考虑 \(c\) ，而且是 \(-2*c\) 。转移过程如下（直接贴代码了）：

#include<bits/stdc++.h>
#define int long long 
using namespace std;
int T,n,c;
const int N=2e5+10;
vector<int> e[N];
int a[N],dp[N][2];
inline void dfs(int x,int fa)
{
	int s1=0,s0=0;
	for(auto v:e[x])
	{
		if(v==fa)continue;
		dfs(v,x);
		s1+=max(dp[v][1]-2*c,dp[v][0]);
		s0+=max(dp[v][1],dp[v][0]);
	}
	dp[x][1]=max(dp[x][1],s1+a[x]);
	dp[x][0]=max(dp[x][0],s0);
}
inline void pre()
{
	cin>>n>>c;
	for(register int i=1;i<=n;++i)cin>>a[i],dp[i][0]=dp[i][1]=0,e[i].clear();
	for(register int i=1;i<=n-1;++i)
	{
		int u,v;
		cin>>u>>v;
		e[u].push_back(v),e[v].push_back(u);
	}
}
signed main()
{
	cin>>T;
	while(T--)
	{
		pre();
		dfs(1,0);
		cout<<max(dp[1][1],dp[1][0])<<endl;
	}
	return 0;
}

F G

还没改（估计鸽了