A.Badge

https://qycode64.com/course/6a47850a69fcccaa3fd46be4/exam/6a5cb2a4b0fb7a5b2e6ffe3b/problem/CF1020B

题意：今天，老师逮到了n名学生在搞恶作剧,给一名学生打洞后，给pi的学生打洞，你不知道谁是老师逮到的第一个学生，但是你知道所有的数字pi。对于每一个a，如果第一个被逮到的学生是a，你的任务是找到谁会是徽章上面有两个洞的学生。

思路：从1到n遍历第一个被逮到的学生，c[]存储被打洞几次，输出被打洞2次的学生编号

#include<bits/stdc++.h>
using namespace std;
int p[1010],c[1010];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>p[i];
	for(int i=1;i<=n;i++){
		memset(c,0,sizeof(c));
		int j=i;
		while(1){
			c[j]++;
			if(c[j]==2){
				cout<<j<<" ";
				break;
			}
			j=p[j];
		}
	}
	return 0;
}

B.Nastya and Potions

https://qycode64.com/course/6a47850a69fcccaa3fd46be4/exam/6a5cb2a4b0fb7a5b2e6ffe3b/problem/CF1851E?lang=zh

题意：你有 n 种药剂，每种药剂可以直接买：花费c[i]金币，合成获得：用其他药剂作为材料混合而成（材料会被消耗） 对于每种药剂i，求出获得1份该药剂的最少花费。

思路：把合成配方建成树，用记忆化搜索得到第i种药剂所需要花费的最少金币数（最少金币数=min(直接购买，配方总和)），或用拓扑排序从叶子节点逐层得到药剂所需要花费的最少金币数

#include<bits/stdc++.h>
using namespace std;
vector<int>g[200005];
long long c[200005],f[200005],h[200005],v[200005];
long long dfs(int u){
	if(v[u])return f[u];
	v[u]=1;
	if(h[u]){
		f[u]=0;
		return 0;
	}
	if(g[u].empty()){
		f[u]=c[u];
		return f[u];
	}
	long long s=0;
	for(int i=0;i<g[u].size();i++){
		s+=dfs(g[u][i]);
	}
	f[u]=min(c[u],s);
	return f[u];
}
int main(){
	int t;
	cin>>t;
	while(t--){
		int n,k;
		cin>>n>>k;
		for(int i=1;i<=n;i++){
			g[i].clear();
			h[i]=0;
			v[i]=0;
		}
		for(int i=1;i<=n;i++)cin>>c[i];
		for(int i=1;i<=k;i++){
			int p;
			cin>>p;
			h[p]=1;
		}
		for(int i=1;i<=n;i++){
			int m;
			cin>>m;
			for(int j=1;j<=m;j++){
				int x;
				cin>>x;
				g[i].push_back(x);
			}
		}
		for(int i=1;i<=n;i++){
			dfs(i);
		}
		for(int i=1;i<=n;i++){
			cout<<f[i]<<" ";
		}
		cout<<"\n";
	}
	return 0;
}

C.Fox And Names

https://qycode64.com/course/6a47850a69fcccaa3fd46be4/exam/6a5cb2a4b0fb7a5b2e6ffe3b/problem/CF510C

题意：给你n个字符串，这些字符串在标准的字母顺序下可能不是递增的。现在你可以重新排列26个字母的顺序，问是否能使得这n个字符串在新的字母顺序下严格递增。如果可以，输出任意一种新的字母顺序，否则输出 "Impossible"。

思路：26 个字母作为节点，每个大小关系x<y变成一条有向边 x->y，问题转化为：是否存在拓扑排序如果存在拓扑排序，输出任意一个拓扑序；否则输出 Impossible。

#include<bits/stdc++.h>
using namespace std;
vector<int>g[30];
string s[110];
int rd[30];
queue<int>zx;
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>s[i];
	for(int i=2;i<=n;i++){
		string a=s[i-1], b=s[i];
		int len=min(a.size(), b.size());
		int f=0;
		for(int j=0;j<len;j++){
			if(a[j]!=b[j]){
				int x=a[j]-'a', y=b[j]-'a';
				g[x].push_back(y);
				rd[y]++;
				f=1;
				break;
			}
		}
		if(!f){
			if(a.size()>b.size()){
				cout<<"Impossible";
				return 0;
			}
		}
	}
	for(int i=0;i<26;i++){
		if(rd[i]==0)zx.push(i);
	}
	string ans="";
	while(!zx.empty()){
		int u=zx.front();
		zx.pop();
		ans+=char(u+'a');
		
		for(int i=0;i<g[u].size();i++){
			int v=g[u][i];
			rd[v]--;
			if(rd[v]==0)zx.push(v);
		}
	}
	if(ans.size()<26) cout<<"Impossible";
	else cout<<ans;
	return 0;
}

D.Mouse Hunt

https://qycode64.com/course/6a47850a69fcccaa3fd46be4/exam/6a5cb2a4b0fb7a5b2e6ffe3b/problem/CF1027D

题意：宿舍有n个房间，有一只老鼠，但不知道初始位置。老鼠每秒从房间 i 移动到房间 a[i]。你可以在一些房间放捕鼠器，每个房间放陷阱要花费 c[i]金币。老鼠一旦进入有陷阱的房间就会被抓住。保证无论老鼠从哪个房间开始，最终都会被抓住。求最小总花费。

思路：只要在环上放陷阱，老鼠无论从哪个房间开始：如果在环上 → 直接被抓住，如果在树枝上 → 最终会走到环上，被抓住对于每个环，选择环上花费最小的房间放陷阱。因为每个环都是独立的，老鼠进入哪个环取决于起点，所以每个环都必须有陷阱。

#include<bits/stdc++.h>
using namespace std;
long long c[200005],a[200005],zx[200005],v[200005];
queue<int>sq;
int main(){
	int n;
	long long ans=0;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>c[i];
	for(int i=1;i<=n;i++){
		cin>>a[i];
		zx[a[i]]++;
	}
	for(int i=1;i<=n;i++){
		if(zx[i]==0)sq.push(i);
	}
	while(!sq.empty()){
		int u=sq.front();
		sq.pop();
		v[u]=1;
		zx[a[u]]--;
		if(zx[a[u]]==0)sq.push(a[u]);
	}
	for(int i=1;i<=n;i++){
		if(!v[i]){
			long long u=i,mn=1e9;
			while(!v[u]){
				v[u]=1;
				mn=min(mn,c[u]);
				u=a[u];
			}
			ans+=mn;
		}
	}
	cout<<ans;
	return 0;
}