本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-06-18 22:18:48

题外话

做出来 ABCD
如果 C 题不犯 sb 错，这场就上 6kyu 了

A

略

B

略

C

填数独，爆搜！
复杂度：O(玄学)，反正是加剪枝过了

D

差分，$O(n)$
代码：

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	typedef long long ll;
	const int maxn=2e5+5;
	int n;
	int L[maxn],R[maxn];
	int cf[maxn];
	void main()
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%d%d",&L[i],&R[i]);
			cf[L[i]-1]--;
			cf[R[i]-1]++;
		}
		for(int i=200000;i>=1;i--)
		{
			cf[i]+=cf[i+1];
		}
		int lst=0;
		int r;
		bool flag=0;
		for(int i=1;i<=200000;i++)
		{
			if(cf[i])
			{
				if(!flag)
				{
					lst=i;
					flag=1;
				}
			}
			else
			{
				if(!flag)
				{
					continue;
				}
				else flag=0;
				r=i;
				printf("%d %d\n",lst,r); 
			}
		}
	}
}
int main()
{
	Main::main();
	return 0;
}

E

将 $i$ 连向 $x_i$，边权为 $c_i$
这样就构成了一颗基环树森林。
对于所有树上的点，肯定都能满足要求，先走 $i$ 再走 $x_i$ 就行了。
对于环上的点，例如：
$1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 1$
这样的，肯定要选一个点先走，那么这个点的上一个点就只能委屈了。
也就是要选取环上边权最小的边加入答案

此题结束

#include <bits\/stdc++.h>
using namespace std;
namespace Main
{
	typedef long long ll;
	const int maxn=2e5+5;
	int n;
	int x[maxn],c[maxn];
	int to[maxn];
	bool ins[maxn],vis[maxn];
	ll ans;
	void cir_ans(int u)
	{
		int start=u;
		int imin=0x3f3f3f3f;
		while(1)
		{
			imin=min(imin,c[u]);
			u=to[u];
			if(u==start)break;
		}
		ans+=(ll)imin;
	}
	void dfs(int u)
	{
		if(vis[u])
		{
			if(ins[u])
				cir_ans(u);
			return;
		}
		ins[u]=1;
		vis[u]=1;
		dfs(to[u]);
		ins[u]=0;
	}
	void main()
	{
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&x[i]);
		}
		for(int i=1;i<=n;i++)
		{
			scanf("%d",&c[i]);
		}
		for(int i=1;i<=n;i++)
		{
			to[i]=x[i];
		}
		for(int i=1;i<=n;i++)
		{
			if(!vis[i])
			{
				dfs(i);
			}
		}
		printf("%lld",ans);
	}
}
int main()
{
	Main::main();
	return 0;
}

F

In queue