【题解】10-4提高组模拟

图论题做爽了（还说考的知识点要均匀……）

A.『MGOI』Simple Round I | C. 魔法禁林

lnk

纯纯最短路。

// Problem:Luogu P9504 『MGOI』Simple Round I | C. 魔法禁林

#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e4+10;
struct edge
{
	int v,w;
};
vector <edge> g[MAXN];
int n,m,s,t;
struct node
{
	int u,mag,sur;
	bool operator <(const node a)const
	{
		if(mag==a.mag)return sur>a.sur;
		return mag>a.mag;
	}
};
priority_queue <node> q;
int dis[MAXN][510];
bool vis[MAXN][510];
void solve()
{
	q.push({t,0,0});
	memset(dis,0x3f,sizeof(dis));
	dis[t][0]=0;
	while(!q.empty())
	{
		node front=q.top();
		q.pop();
		int u=front.u,sur=front.sur;
		vis[u][sur]=0;
		if(sur>100)continue;
		for(auto tmp:g[u])
		{
			int v=tmp.v,w=tmp.w;
			if(dis[v][sur+1]>dis[u][sur]+w/(sur+1))
			{
				if(!vis[v][sur+1])
					vis[v][sur+1]=1,q.push({v,dis[v][sur+1],sur+1});
				dis[v][sur+1]=dis[u][sur]+w/(sur+1);
			}
		}
	}
}
int main()
{
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		g[u].push_back({v,w});
		g[v].push_back({u,w});
	}
	solve();
	int ans=0x3f3f3f3f;
	for(int i=0;i<=100;i++)ans=min(ans,dis[s][i]);
	cout<<ans;
	return 0;
}

B. [USACO22FEB] Email Filing S

lnk

这道题是模拟和贪心，根据题目所说就能做出来了（感觉还是有点难度）

// Problem:Luogu P8188 [USACO22FEB] Email Filing S

#include<bits/stdc++.h>
using namespace std;
const int N=100010,M=10010;
set<int>sce;
queue<int>q[M];
int T,n,m,K,f[N],c[N],top,st[N];

int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=x*10+ch-'0';
		ch=getchar();
	}
	return x*f;
}

void init()
{
	top=0;
	sce.clear();
	for(int i=1;i<=m;i++)
		while(!q[i].empty())q[i].pop();
	memset(c,0,sizeof(c));
}

bool check()
{
	int j=1,t;
	set<int>::iterator it;
	for(int i=1;i<=m;i++)
	{
		t=i+K-1;
		if(t<=m)
		{
			c[t]-=q[t].size();
			while(!q[t].empty())
			{
				int x=q[t].front();
				q[t].pop();
				sce.erase(x);
			}
		}
		while(c[i])
		{
			int x=(j<=n)?j:st[top--];
			if(sce.size()==K)
			{
				if(j<=n)
				{
					it=sce.begin();
					st[++top]=*it;
					q[f[*it]].pop();
					sce.erase(*it);
				}
				else
					return 0;
			}
			if(f[x]<=t)
				c[f[x]]--;
			else
			{
				sce.insert(x);
				q[f[x]].push(x);
			}
			if(j<=n)j++;
		}
	}
	return 1;
}

int main()
{
	T=read();
	while(T--)
	{
		m=read();
		n=read();
		K=read();
		init();
		for(int i=1;i<=n;i++)
		{
			f[i]=read();
			c[f[i]]++;
		}
		check()?puts("YES"):puts("NO");
	}
	return 0;
}

C. [POI 2012] RAN-Rendezvous

听li_cat大佬说是基环树（？）分成三种情况

• 在同一个基环树上且在同一个节点的子树下，答案是LCA（用倍增）
• 在同一个基环树但是在不同节点的子树下，答案是两点所在树的根节点其中的一个
• 不在同一个基环树上，答案$-1$

#include<bits/stdc++.h>
const int MAXN=500010;
using namespace std;
int indeg[MAXN],n,m,wcc[MAXN],anc[MAXN][21],dep[MAXN],cirlen[MAXN],cirid[MAXN],cirpos[MAXN],tot;
vector <int> g[MAXN];
queue <int> q;
void dfs(int u,int f,int rt,int d)
{
	dep[u]=d;wcc[u]=rt;
	for(int i=0;i<g[u].size();i++)
	{
		int v=g[u][i];
		if(indeg[v]||v==f)continue;
		dfs(v,u,rt,d+1);
	}
}
void pre()
{
	for(int p=1;p<=19;p++)
		for(int i=1;i<=n;i++)
			anc[i][p]=anc[anc[i][p-1]][p-1];
}
int lca(int x,int y)
{
	if(dep[x]<dep[y])swap(x,y);
	int tmp=dep[x]-dep[y];
	for(int i=19;i>=0;i--)if(tmp>>i&1)x=anc[x][i];
	if(x==y)return y;
	for(int i=19;i>=0;i--)
	{
		if(anc[x][i]!=anc[y][i])x=anc[x][i],y=anc[y][i];
	}
	return anc[x][0];
}
void circle(int u,int id,int az)
{
	if(cirpos[u])return;
	cirid[u]=id;cirlen[id]++;cirpos[u]=az;
	circle(anc[u][0],id,az+1);
}
bool check(int a,int b,int c,int d)
{
	if(max(a,b)!=max(c,d))return max(a,b)<max(c,d);
	if(min(a,b)!=min(c,d))return min(a,b)<min(c,d);
	return a>=b;
}
signed main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		int u;scanf("%d",&u);
		g[u].push_back(i);
		anc[i][0]=u;
		indeg[u]++;
	}
	for(int i=1;i<=n;i++)if(!indeg[i])q.push(i);
	while(!q.empty())
	{
		int u=q.front();q.pop();
		int v=anc[u][0];
		indeg[v]--;
		if(!indeg[v])q.push(v);
	}
	for(int i=1;i<=n;i++)
	{
		if(indeg[i])
		{
			dfs(i,0,i,0);
			if(!cirpos[i])circle(i,++tot,1);
		}
	}
	pre();
	while(m--)
	{
		int u,v;scanf("%d%d",&u,&v);
		if(cirid[wcc[u]]!=cirid[wcc[v]])
		{
			cout<<-1<<' '<<-1<<endl;
		}
		else if(wcc[u]==wcc[v])
		{
			int LCA=lca(u,v);
			cout<<dep[u]-dep[LCA]<<' '<<dep[v]-dep[LCA]<<endl;
		}
		else
		{
			int t1=wcc[u],t2=wcc[v];
			int ans1=dep[u]+(cirpos[t2]-cirpos[t1]+cirlen[cirid[t1]])%cirlen[cirid[t1]];
			int ans2=dep[v]+(cirpos[t1]-cirpos[t2]+cirlen[cirid[t1]])%cirlen[cirid[t1]];
			if(check(dep[u],ans2,ans1,dep[v]))cout<<dep[u]<<' '<<ans2<<endl;
			else cout<<ans1<<' '<<dep[v]<<endl;
		}
	}
	return 0;
}

D.[蓝桥杯 2024 省研究生组] 植物生命力

lnk

由于线段树/树状数组，先搁这