[数据结构与算法]【PTA】团体程序设计天梯赛-练习集 25分的题

L2-001 紧急救援

题

题意：
求最短路的条数，和其中一条经过人数最多的最短路。
最后输出后者经过的城市编号。

题解：
先用dijkstra求出从起点开始到所有点的最短路，这要就得知从起点到终点的最短路。
接下来找最短路的条数：如果dist[j]=dist[i]+g[i][j]，说明这条路在最短路上。
每次保存人数和经过的城市编号，如果当前人数大于已经保存的人数则更新。

简单来说就是一个dijkstra+dfs。

#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
#define pb push_back
typedef long long ll;
const int N=500+10;
int n,m,s,d;
int a[N];
int g[N][N];
int dist[N];//从起点开始，到i的最短路
int st[N];
//求从s开始到每个点的最短路 
void dij()
{
	mem(dist,0x3f);		
	for(int i=0;i<n;i++)
	{
		dist[i]=g[s][i];
	}
	dist[s]=0;
	for(int i=0;i<n;i++)
	{
		int t=-1;
		for(int j=0;j<n;j++)
		{
			if(!st[j]&&(t==-1||dist[j]<dist[t]))
			{
				t=j;
			}									
		}
		st[t]=1;
			
		for(int j=0;j<n;j++)
		{
			dist[j]=min(dist[j],dist[t]+g[t][j]);
		}
	}	
} 
int minn,tiao,peo;
vector<int>ans,temp;
int done[N];
void dfs(int u,int w)
{
	if(u==d)
	{
		if(w>peo)
		{
			peo=w;
			ans=temp;
		}
		tiao++;
		return;
	}
	else
	{
		for(int i=0;i<n;i++)
		{
			//防止自己到自己，没有走过，在最短路径上 
			if(g[u][i]&&!done[i]&&dist[i]==dist[u]+g[u][i])
			{
				done[i]=1;
				temp.pb(i);
				dfs(i,w+a[i]);
				temp.pop_back();
				done[i]=0;
			} 
		}
	}
}
int main()
{
	cin>>n>>m>>s>>d;
	fir(i,0,n-1) cin>>a[i];
	
	mem(g,0x3f);
	for(int i=0;i<n;i++) g[i][i]=0;
	fir(i,1,m)
	{
		int a,b,c;scanf("%d%d%d",&a,&b,&c);
		g[a][b]=g[b][a]=min(g[a][b],c);
	}
	dij();
	
	//fir(i,0,n-1) cout<<dist[i]<<" ";
	
	minn=dist[d];
	tiao=0;
	done[0]=1;
	temp.pb(s);
	dfs(s,a[s]);	
	
	cout<<tiao<<" "<<peo<<endl;
	for(int i=0;i<ans.size();i++)
	{
		cout<<ans[i];
		if(i!=ans.size()-1) cout<<" ";
	}
	return 0;
}

L2-002 链表去重

题
千万不要结构体模拟链表，会累死。

这题可以观察出：
答案其实是：绝对值没有出现过的链表连在一起，和绝对值都出现过的链表连在一起。
所以可以分开存储。
注意，要判断没有相同绝对值出现的情况。（这里有2分）

#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
typedef long long ll;
const int N=1e6+10,M=1e4+10;
int a[N],ne[N],str[N];
int head,n;
int val[N];
int l1[N],l2[N],ne1[N],ne2[N];
int idx1,idx2;
int main()
{
	cin>>head>>n;
	fir(i,1,n)
	{
		int t;cin>>t;//直接int 到时候不满5位数就输出前导零 
		cin>>a[t]>>ne[t];
	}
	
	int p=head;
	
	while(p!=-1)
	{
		if(!val[abs(a[p])])
		{
			val[abs(a[p])]=1;
			l1[idx1++]=p;
		}
		else
		{
			l2[idx2++]=p;
		}
		p=ne[p];
	}
	for(int i=0;i<idx1-1;i++)
	{
		int num=l1[i];
		printf("%05d %d %05d\n",num,a[num],l1[i+1]);
	}
	printf("%05d %d -1\n",l1[idx1-1],a[l1[idx1-1]]);
	
	if(idx2)
	{
		for(int i=0;i<idx2-1;i++)
		{
			int num=l2[i];
			printf("%05d %d %05d\n",num,a[num],l2[i+1]);
		}
		printf("%05d %d -1\n",l2[idx2-1],a[l2[idx2-1]]);
	}
	return 0;
}

L2-003 月饼

题

贪心算法。
要全开double 不然有一个点过不了（2分）。

#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
typedef long long ll;
const int N=1000+10;
int n,sum;
struct node
{
	double num,mon;
	double a;
}a[N];

bool cmp(node a,node b)
{	
	return a.a>b.a;
}
int main()
{
	cin>>n>>sum;
	fir(i,1,n) cin>>a[i].num;
	fir(i,1,n) 
	{
		cin>>a[i].mon;
		a[i].a=(a[i].mon*1.0/a[i].num);
		//cout<<a[i].a<<" ";
	}
	
	double ans=0;
	sort(a+1,a+1+n,cmp);
	
	for(int i=1;i<=n;i++)
	{
		if(sum>a[i].num)
		{
			sum-=a[i].num;
			ans+=a[i].mon;
		}
		else
		{
			ans+=a[i].a*sum;
			break;
		}
	}
	cout.precision(2);
	cout<<fixed<<ans;
	return 0;
}

L2-004 这是二叉搜索树吗？（二叉搜索树性质+递归）

输入1：

7
8 6 5 7 10 8 11

输出1：

YES
5 7 6 8 11 10 8

输入2：

7
8 10 11 8 6 7 5

输出2：

YES
11 8 10 7 5 6 8

输入3：

7
8 6 8 5 10 9 11

输出3：

NO

参考：
L2-004 这是二叉搜索树吗？ （25 分）(二叉树的遍历)

要求二叉树的后序遍历，因此要递归地找左子树、右子树、根。
其中，根据二叉搜索树的性质可知，左子树都小于根，右子树大于等于根，以它为条件递归地找左右子树的边界即可。（不要硬模拟，太蠢了）

#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
#define pb push_back
typedef long long ll;
const int N=1e3+10;
int n,isM;
int a[N];
vector<int>ans;
void solve(int l,int r)
{
	if(l>r) return;
	
	/*
	利用二叉搜索树的性质：左子树小于根，右子树大于等于根
	找到左右子树的范围 
	*/
	int i=l+1,j=r;
	if(!isM)//不是镜像
	{
		while(i<=r&&a[i]<a[l]) i++;//找到的i是第一个不符合左子树要求的，则i是右子树的开头 
		while(j>l&&a[j]>=a[l]) j--;//找到的j是第一个不符合右子树要求的，则j是左子树的结尾 
		//这里注意范围，j从r开始，j要找的是左子树结尾，因此j不可能等于r 
	} 
	else //是镜像，则左子树大于等于 右子树小于 
	{
		while(i<=r&&a[i]>=a[l]) i++;
		while(j>=l&&a[j]<a[l]) j--;
	}
	if(j+1==i)//左子树的结尾+1应该是右子树的开头 
	{
		//接下来是递归左、右子树，再存根 这样才能得到后序遍历 
		solve(l+1,j);//左 
		solve(i,r);//右 
		ans.pb(a[l]);//l是根		
	}
}
int main()
{
	cin>>n;
	fir(i,1,n) cin>>a[i];
	isM=0;//先假设没有镜像 
	ans.clear();
	solve(1,n);
	if(ans.size()==n) 
	{
		puts("YES");
		for(int i=0;i<n;i++)
		{
			if(i) cout<<" ";
			cout<<ans[i];							
		}
	}
	else
	{
		ans.clear();
		isM=1;
		solve(1,n);
		if(ans.size()==n)
		{
			puts("YES");
			for(int i=0;i<n;i++)
			{
				if(i) cout<<" ";
				cout<<ans[i];				
			}
		}
		else puts("NO");
	}
	return 0;
}

L2-005 集合相似度（直接stl做）

题
第一次做的时候没有理解题意，直接跪了。

其实就是交集元素个数/并集元素个数。

21分版本：直接合并set，会T最后一个点

#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
typedef long long ll;
const int N=50+10;
int n;
set<int>a[N];
int main()
{
	cin>>n;
	fir(i,1,n)
	{
		int m;scanf("%d",&m);
		fir(j,1,m)
		{
			int t;scanf("%d",&t);
			a[i].insert(t);
		}
	}
	
	int m;cin>>m;
	while(m--)
	{
		int x,y;scanf("%d%d",&x,&y);
		double jiao,bing;
		
		set<int>temp;
		for(auto u:a[x])
		{
			temp.insert(u);
		}
		for(auto u:a[y])
		{
			temp.insert(u);
		}
		
		bing=temp.size();
		jiao=a[x].size()+a[y].size()-temp.size();
		
		double ans=jiao/bing;
		ans*=100;
		printf("%.2f%\n",ans);
//		cout.precision(2);
//		cout<<fixed<<ans<<"%"<<endl;
	}
	return 0;
}

用集合的函数直接做，25分版本：

#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
#define pb push_back
typedef long long ll;
const int N=1e5+10;
int n;
vector<set<int>>a;
int main()
{
	cin>>n;
	while(n--)
	{
		int m;cin>>m;
		set<int>temp;
		while(m--)
		{
			int x;cin>>x;
			temp.insert(x);
		}
		a.pb(temp);
	}
	cin>>n;
	while(n--)
	{
		int x,y;cin>>x>>y;
		x--,y--;//vector从0开始 
		int ans1,ans2;
		vector<int>tempp(4001);
		auto it=set_intersection(a[x].begin(),a[x].end(),a[y].begin(),a[y].end(),tempp.begin());
		ans1=it-tempp.begin();
		it=set_union(a[x].begin(),a[x].end(),a[y].begin(),a[y].end(),tempp.begin());
		ans2=it-tempp.begin();
		//cout<<ans1<<" "<<ans2<<endl;
		printf("%.2f%\n",ans1*1.0*100/ans2);
	}
	return 0;
}

其中，有三个函数（a、b两个数组必须是升序的）：

求交集：
auto it=set_intersection(a.begin(),a.end(),b.begin(),b.end(),c.begin());
把(vector类型的)a、b求交集，然后放入c中（从c.begin()开始放。）
返回的是指向末尾的迭代器，则it-c.begin()就是交集的元素个数。

求并集：
auto it=set_union(a.begin(),a.end(),b.begin(),b.end(),c.begin());

求集合差（在集合a中但不在集合b中的，既A-B的）：
auto it=set_difference(a.begin(),a.end(),b.begin(),b.end(),c.begin());

L2-006 树的遍历（二叉树性质+递归）

参考：PTA 树的遍历 （25 分）

• 不是完全二叉树，所以要用map来存。因为它不是连续的。
• map[a]=b,用first表示a，second表示b
• 给了后序遍历和中序遍历：后序遍历知道每一个根，中序遍历能分出左右子树，按顺序找到的根就是层序遍历的答案。
• 递归 地找出根和左右子树范围（有规律可循）

#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
#define pb push_back
typedef long long ll;
const int N=30+10;
int n;
int hou[N],zhong[N];
map<int,int>ans;//ans[i]表示第i个答案
void solve(int l,int r,int ll,int rr,int a)//后序遍历的范围，中序遍历的范围，第a个答案
{
	if(r>=l&&rr>=ll)//没越界 
	{
		ans[a]=hou[r];//后序遍历的找根，按顺序找到的根即层序遍历的答案
		//在中序遍历中找根，分出左右子树 
		for(int i=ll;i<=rr;i++)
		{
			if(hou[r]==zhong[i])
			{
				//递归左子树 
				solve(l,i-ll+l-1,ll,i-1,a*2+1);
				//递归右子树
				solve(i-ll+l,r-1,i+1,rr,a*2+2); 
				return;
			}
		} 
	}
} 
int main()
{
	cin>>n;
	fir(i,1,n) cin>>hou[i];
	fir(i,1,n) cin>>zhong[i];
	solve(1,n,1,n,1);
	int f=0;
	for(auto x:ans)
	{
		if(f) cout<<" ";
		f++;
		cout<<x.second; 
	}
	return 0;
}

L2-007 家庭房产

题

一道改吐了的并查集大模拟。
参考：这个代码很清晰

解题思路：

1. 有n条输入，输入中会包括各种人，人的编号可能会重复（既在不同的输入中分别出现），但每次输入的房子信息是唯一的。所以我们遍历n次，累加房子的信息。
2. 题目中要求要输出家庭中最小的编号，那么我们其实可以在合并并查集的时候，让更小的祖先节点做祖先，这样其实该祖先节点的编号就是这个家庭的最小编号。
3. 由于人的编号会在不同的输入重复，所以我们在他每次出现时标记v[i]=1，然后遍历1e5，即人的编号的范围。
4. 房子只需要遍历n次，而得到人的编号要遍历1e5次，是因为房子的输入是唯一的。
5. 编号会有0000，所以遍历人的编号要从0开始。（不然会错3个点，这里改吐了）

ps：此题可以不路径压缩。

#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
#define pb push_back
typedef long long ll;
const int N=1e5+10,M=1e3+10;
int p[N];
void ini()
{
	fir(i,1,1e5) p[i]=i;
}
//int find(int x)
//{
//	if(x!=p[x]) p[x]=find(p[x]);
//	return p[x];
//}
int find(int x)
{
	int son=x,root;
	while(x!=p[x])//找祖先 
	{
		x=find(p[x]);
	}
	root=x;//根
	while(son!=p[son])//路径压缩 
	{
		int temp=p[son];
		p[son]=root;
		son=temp;
	}
	return x;
}
void merge(int a,int b)
{
	int aa=find(a),bb=find(b);
	if(aa<bb) p[bb]=aa;
	else p[aa]=bb;
}
struct node1
{
	int fa,mon,k,child[6],house,area,id;
}peo[M];
struct node
{
	int num,sumt,suma;//房产套数 房产面积
	double house,area;
	int flag;
	int id;
}ans[N];

bool cmp(node a,node b)
{
	if(a.area!=b.area) return a.area>b.area;
	else return a.id<b.id;
}
int n;
int v[N];//标记是否有人 
int main()
{
	ini();
	cin>>n;
	fir(i,1,n)
	{
		cin>>peo[i].id>>peo[i].fa>>peo[i].mon;
		v[peo[i].id]=1;
		if(peo[i].fa!=-1)
		{
			v[peo[i].fa]=1;
			merge(peo[i].id,peo[i].fa);
		}
		if(peo[i].mon!=-1)
		{
			v[peo[i].mon]=1;
			merge(peo[i].id,peo[i].mon);
		}
		cin>>peo[i].k;
		fir(j,1,peo[i].k)
		{
			cin>>peo[i].child[j];
			v[peo[i].child[j]]=1;
			merge(peo[i].id,peo[i].child[j]);
		}
		cin>>peo[i].house>>peo[i].area;
	}
	
	fir(i,1,n)//遍历每一个输入，带有房子 
	{
		int pa=find(peo[i].id);
		ans[pa].flag=1;
		ans[pa].sumt+=peo[i].house;
		ans[pa].suma+=peo[i].area;
		ans[pa].id=pa;
	}
	
	int cnt=0;
	fir(i,0,1e5)
	{
		if(v[i])//有人 
		{
			int pa=find(i);
			ans[pa].num++;
		}
		if(ans[i].flag) 
		{
			cnt++;			
		}
	}
	
	fir(i,0,1e5)
	{
		if(ans[i].flag)
		{
			ans[i].house=ans[i].sumt*1.0/ans[i].num;
			ans[i].area=ans[i].suma*1.0/ans[i].num;
		}
	}
	
	sort(ans,ans+1+100000,cmp);
	
	cout<<cnt<<endl;
	fir(i,0,cnt-1)
	{
		printf("%04d %d %.3f %.3f\n",ans[i].id,ans[i].num,ans[i].house,ans[i].area);
	}
	
	return 0;
}

L2-008 最长对称子串

题

1000的数据范围，可以暴力。

#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
#define pb push_back
typedef long long ll;
const int N=1e5+10;
string a;
int ans;
int main()
{
	getline(cin,a);
	ans=1;
	
	for(int i=0;a[i];i++)//中点 
	{
		//一个字符中轴 
		int j=i-1,k=i+1;
		int temp=1;//有中轴就是1 
		while(j>=0&&k<a.size())
		{
			if(a[j]!=a[k]) break;
			else
			{
				temp+=2;
				j--;k++;
			}
		}
		ans=max(ans,temp);
		
		//没有中轴也可以对称
		j=i,k=i+1;
		temp=0;//没中轴就是0 
		while(j>=0&&k<a.size())
		{
			if(a[j]!=a[k]) break;
			else
			{
				temp+=2;
				j--;k++;
			}
		}
		ans=max(ans,temp);
	}
	cout<<ans;
	return 0;
}

L2-009 抢红包（排序+模拟）

输入：

10
3 2 22 10 58 8 125
5 1 345 3 211 5 233 7 13 8 101
1 7 8800
2 1 1000 2 1000
2 4 250 10 320
6 5 11 9 22 8 33 7 44 10 55 4 2
1 3 8800
2 1 23 2 123
1 8 250
4 2 121 4 516 7 112 9 10

输出：

1 11.63
2 3.63
8 3.63
3 2.11
7 1.69
6 -1.67
9 -2.18
10 -3.26
5 -3.26
4 -12.32

代码：

#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
#define pb push_back
typedef long long ll;
const int N=1e4+10;
int n;
struct node
{
	double ans;
	int i,ge;
}ans[N];
bool cmp(node a,node b)
{
	if(a.ans!=b.ans) return a.ans>b.ans;
	else if(a.ge!=b.ge) return a.ge>b.ge;
	else return a.i<b.i;
}
int main()
{
	cin>>n;
	fir(i,1,n)
	{
		int k;cin>>k;
		int sum=0;
		while(k--)
		{
			int aa,bb;cin>>aa>>bb;
			sum+=bb;
			ans[aa].ans+=bb;
			ans[aa].ge++;
		}
		ans[i].ans-=sum;
	}
	fir(i,1,n)
	{
		ans[i].ans/=100;	
		ans[i].i=i;	
	}
	sort(ans+1,ans+1+n,cmp);
	fir(i,1,n) printf("%d %.2f\n",ans[i].i,ans[i].ans);
	return 0;
}

L2-010 排座位（并查集）

输入：

7 8 4
5 6 1
2 7 -1
1 3 1
3 4 1
6 7 -1
1 2 1
1 4 1
2 3 -1
3 4
5 7
2 3
7 2

输出：

No problem
OK
OK but...
No way

如果是朋友，就放入一个并查集里。

#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
#define pb push_back
typedef long long ll;
const int N=1e2+10;
int g[N][N];
int n,m,k;
int p[N];
void ini()
{
	for(int i=1;i<=100;i++) p[i]=i;
}
int find(int x)
{
	while(p[x]!=x) x=p[x];
	return p[x];
}
void merge(int a,int b)
{
	int aa=find(a),bb=find(b);
	p[aa]=bb;//认b作父 
}
int main()
{
	ini();
	cin>>n>>m>>k;
	while(m--)
	{
		int a,b,c;cin>>a>>b>>c;
		if(c==1)
		{
			merge(a,b);
		}
		else g[a][b]=g[b][a]=-1;
	}
	while(k--)
	{
		int a,b;cin>>a>>b;
		int fa=find(a),fb=find(b);	
		
		if(fa==fb)
		{
			if(g[a][b]!=-1) puts("No problem");
			else puts("OK but...");
		}	
		else
		{
			if(g[a][b]!=-1) puts("OK");
			else puts("No way");
		}		
	}
	
	return 0;
}

L2-011 玩转二叉树（二叉树性质+递归）

思路：
根据前序遍历找到根，根据中序遍历找到根的位置，从而分出左右子树。若根的下标为x，镜像即左子树的下标为x2+2，右子树下标为x2+1；
参考：L2-011. 玩转二叉树-PAT团体程序设计天梯赛GPLT（柳神，牛！）
代码：

#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
#define pb push_back
typedef long long ll;
const int N=30+10;
int n,z[N],q[N];
map<int,int>ans;
void levelorder(int l,int r,int root,int now)//中序遍历范围，前序位置（代表根），当前位置（代表答案） 
{
	if(r>=l)
	{
		for(int i=l;i<=r;i++)
		{
			if(z[i]==q[root])//找到根 
			{
				ans[now]=z[i];
				levelorder(l,i-1,root+1,now*2+2);
				levelorder(i+1,r,root+1+i-l,now*2+1);
				return;
			}
		}
	}
}
int main()
{
	cin>>n;
	fir(i,1,n) cin>>z[i];
	fir(i,1,n) cin>>q[i];
	levelorder(1,n,1,1);
	int f=0;
	for(auto x:ans)
	{
		if(f) cout<<" ";
		f++;
		cout<<x.second;
	}
	return 0;
}

L2-012 关于堆的判断（堆的模拟）

输入：

5 4
46 23 26 24 10
24 is the root
26 and 23 are siblings
46 is the parent of 23
23 is a child of 10

输出：

F
T
F
T

关于调整函数：
要从下往上调整，这样只有/2一种方法。
若是从上往下调整有两种方法，答案就不唯一了。

#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
#define pb push_back
typedef long long ll;
const int N=1e3+10;
int a[N],n,m;
void adjust(int x)
{	
	while(x>=2)
	{
		if(a[x]<a[x/2]) swap(a[x],a[x/2]);
		x/=2;
	}
}
int main()
{
	cin>>n>>m;
	fir(i,1,n)
	{
		cin>>a[i];
		adjust(i);
	}
	while(m--)
	{
		int num1;cin>>num1;
		string str1;cin>>str1;
		if(str1=="is")
		{
			string str2;cin>>str2>>str2;
			if(str2=="root")
			{
				if(a[1]==num1) puts("T");
				else puts("F");
			}
			else if(str2=="parent")
			{
				string t;cin>>t;int num2;cin>>num2;
				int f=0;
				for(int i=1;i<=n;i++)
				{
					if(a[i]==num2&&a[i/2]==num1) f=1;
				}
				if(f) puts("T");
				else puts("F");
			}
			else if(str2=="child")
			{
				string t;cin>>t;int num2;cin>>num2;
				int f=0;
				for(int i=1;i<=n;i++)
				{
					if(a[i]==num1&&a[i/2]==num2) f=1;
				}
				if(f) puts("T");
				else puts("F");
			}
		}
		else
		{
			string temp;
			int num2;cin>>num2;cin>>temp>>temp;
			int f=0;
			for(int i=1;i<=n;i++)
			{
				if(a[i]==num1&&a[i+1]==num2&&a[i/2]==a[(i+1)/2]) f=1;
				else if(a[i]==num2&&a[i+1]==num1&&a[i/2]==a[(i+1)/2]) f=1;
			}
			if(f) puts("T");
			else puts("F");
		}
	}
	return 0;
}

L2-013 红色警报

输入：

5 4
0 1
1 3
3 0
0 4
5
1 2 0 4 3

输出：

City 1 is lost.
City 2 is lost.
Red Alert: City 0 is lost!
City 4 is lost.
City 3 is lost.
Game Over.

由题知，此题是求连通性的。由于每失去一个城市，这个城市会分离出来，单独成为一个连通度。因此，若这次的连通度大于上次的连通度+1，则改变了连通性。

#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
typedef long long ll;
const int N=500+10;
int n,m;
int g[N][N],v[N];
int now;
void dfs(int u,int v[])
{
	v[u]=1;
	fir(i,0,n-1)
	{
		if(g[u][i]&&!v[i]) dfs(i,v);
	}
}
int judge()
{
	mem(v,0);
	int ans=0;
	for(int i=0;i<n;i++)
	{
		if(!v[i]) 
		{
			ans++;
			dfs(i,v);
		}
	}
	return ans;
}
int main()
{
	cin>>n>>m;
	fir(i,1,m) 
	{
		int a,b;cin>>a>>b;
		g[a][b]=1;
		g[b][a]=1;
	}
	now=judge();
	int t;cin>>t;
	fir(j,1,t)
	{
		int temp;cin>>temp;
		fir(i,0,n-1)
		{
			g[i][temp]=0;
			g[temp][i]=0;
		}
		int cnt=judge();
	
		if(now+1<cnt) printf("Red Alert: City %d is lost!\n",temp);
		else printf("City %d is lost.\n",temp);
		now=cnt;
	}
	if(t==n) printf("Game Over.");
	return 0;
}

L2-014 列车调度（set的巧妙应用）

输入：

9
8 4 2 5 3 9 1 6 7

输出：

4

参考：柳神的巧妙代码
set的函数

#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
#define pb push_back
typedef long long ll;
const int N=1e5+10;
set<int>s;
/*
相当于用一个元素来代表这一条队伍
该元素是这条队伍的最小值 
*/ 
int main()
{
	int n;cin>>n;
	s.insert(0);
	while(n--)
	{
		int t;cin>>t;
		if(t<*s.rbegin())//t比s中最大的值小 
		{
			s.erase(*s.upper_bound(t));
			//找到大于t的第一个元素的迭代器 删除这个值	相当于排在这个值后面 取代了这条队伍的最小值		
		}
		s.insert(t); 
	}
	cout<<s.size()-1;
	return 0;
}

L2-015 互评成绩（模拟）

输入：

6 5 3
88 90 85 99 60
67 60 80 76 70
90 93 96 99 99
78 65 77 70 72
88 88 88 88 88
55 55 55 55 55

输出：

87.667 88.000 96.000

代码：

#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
#define pb push_back
typedef long long ll;
const int N=1e4+10;
int n,m,k; 
vector<double>a;
bool cmp(double a,double b)
{
	return a>b;
}
int main()
{
	cin>>n>>m>>k;
	fir(i,1,n)
	{
		int maxn=-1,minn=0x3f3f3f3f;
		int sum=0;
		fir(j,1,m)
		{
			int t;cin>>t;sum+=t;
			maxn=max(maxn,t);
			minn=min(minn,t);
		}
		sum-=maxn;
		sum-=minn;
		a.pb(sum*1.0/(m-2));
	}
	sort(a.begin(),a.end(),cmp);
	for(int i=k-1;i>=0;i--)
	{
		if(i!=k-1) cout<<" ";
		printf("%.3f",a[i]);
	}
	return 0;
}

L2-016 愿天下有情人都是失散多年的兄妹

输入：

24
00001 M 01111 -1
00002 F 02222 03333
00003 M 02222 03333
00004 F 04444 03333
00005 M 04444 05555
00006 F 04444 05555
00007 F 06666 07777
00008 M 06666 07777
00009 M 00001 00002
00010 M 00003 00006
00011 F 00005 00007
00012 F 00008 08888
00013 F 00009 00011
00014 M 00010 09999
00015 M 00010 09999
00016 M 10000 00012
00017 F -1 00012
00018 F 11000 00013
00019 F 11100 00018
00020 F 00015 11110
00021 M 11100 00020
00022 M 00016 -1
00023 M 10012 00017
00024 M 00022 10013
9
00021 00024
00019 00024
00011 00012
00022 00018
00001 00004
00013 00016
00017 00015
00019 00021
00010 00011

输出：

Never Mind
Yes
Never Mind
No
Yes
No
Yes
No
No

注意：
在输入一个ID的父母时是知道父母的性别的， 此时要把父母的性别记录了。 否则会只通过0、2这两个点。
若不记录父母的性别，那么之后的判断到父母就有可能出现：两个没有记录性别的初始化值相等，输出Never Mind的情况。

代码：

#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
#define pb push_back
typedef long long ll;
const int N=1e5+10;
int g[N];//gender 1男-1女 
int f[N],m[N];//father mother
int n,k;
void ini()
{
	for(int i=0;i<10000;i++)
	{
		f[i]=-1;
		m[i]=-1;
	}
}
int v[N];
struct node
{
	int ans,num;
};
void bfs(int x)
{
	queue<node>q;
	v[x]++;
	q.push({x,1});
	while(q.size())
	{
		auto t=q.front();
		q.pop();
		
		if(t.num<5)
		{
			int t1=f[t.ans],t2=m[t.ans];
			if(t1!=-1)
			{
				q.push({t1,t.num+1});
				v[t1]++;
			}
			if(t2!=-1)
			{
				q.push({t2,t.num+1});
				v[t2]++;
			}
		}
	}
}
int main()
{
	ini();
	cin>>n;
	fir(i,1,n)
	{
		int t;cin>>t;
		char ch;cin>>ch;
		if(ch=='M') g[t]=1;
		else g[t]=-1;
		cin>>f[t]>>m[t];
		g[f[t]]=1;//记录父母的性别
		g[m[t]]=-1;
	}
	cin>>k;
	while(k--)
	{
		int a,b;cin>>a>>b;
		if(g[a]==g[b]) 
		{
			puts("Never Mind");
			continue;
		}
		mem(v,0);
		bfs(a);
		bfs(b);
		int flag=0;
		for(int i=0;i<100000;i++)
		{
			if(v[i]==2)
			{
				flag=1;break;
			}
		}
		if(flag) puts("No");
		else puts("Yes");
	}
	return 0;
}

L2-019 悄悄关注（模拟）

输入1：

10 GAO3 Magi Zha1 Sen1 Quan FaMK LSum Eins FatM LLao
8
Magi 50
Pota 30
LLao 3
Ammy 48
Dave 15
GAO3 31
Zoro 1
Cath 60

输出1：

Ammy
Cath
Pota

输入2：

11 GAO3 Magi Zha1 Sen1 Quan FaMK LSum Eins FatM LLao Pota
7
Magi 50
Pota 30
LLao 48
Ammy 3
Dave 15
GAO3 31
Zoro 29

输出2：

Bing Mei You

代码：

#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define pb push_back
#define ll long long
const int N=1e4+10;
int n,m;
map<string,int>gz;
struct node
{
	string name;
	int zan;
}p[N];
vector<string>s;
int main()
{
	cin>>n;
	fir(i,1,n)
	{
		string a;cin>>a;
		gz[a]=1;//关注了 
	}
	cin>>m;
	int sum=0;
	fir(i,1,m)	
	{
		string a;int b;cin>>a>>b;
		sum+=b;
		p[i]={a,b};
	}
	double pj=sum*1.0/m;
	fir(i,1,m)
	{
		if(p[i].zan>pj&&gz[p[i].name]==0)
		{
			s.pb(p[i].name);
		}
	}
	if(s.empty())
	{
		cout<<"Bing Mei You";
	}
	else
	{
		sort(s.begin(),s.end());
		for(auto x:s) cout<<x<<endl;
	}
	return 0;
}

L2-020 功夫传人（模拟）

输入：

10 18.0 1.00
3 2 3 5
1 9
1 4
1 7
0 7
2 6 1
1 8
0 9
0 4
0 3

输出：

404

代码：

#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
#define pb push_back
typedef long long ll;
const int N=1e5+10;
double a[N],z,r,ans,rr;
int n;
vector<int> s[N];//存徒弟 
int d[N];//得道 
struct node
{
	int num;
	double ans;
};
void bfs()
{
	queue<node>q;
	q.push({0,z});
	while(q.size())
	{
		auto t=q.front();
		q.pop();
		
		if(s[t.num].size())//有徒弟 没得道
		{
			for(int i=0;i<s[t.num].size();i++)
			{
				int temp=s[t.num][i];
				a[temp]=a[t.num]*rr;
				q.push({temp,a[temp]});
			}
		} 
		else
		{
			ans+=(a[t.num]*d[t.num]);
		}
	}
}
int main()
{
	cin>>n>>z>>r;
	rr=100-r;
	rr*=0.01;
	a[0]=z;
	fir(i,0,n-1)
	{
		int k;cin>>k;
		if(k)
		{
			fir(j,1,k)
			{
				int t;cin>>t;
				s[i].pb(t); 
			}
		}
		else
		{
			int t;cin>>t;
			d[i]=t;//负数表示得道
		}
	}
	bfs();
	cout<<(int)ans;
	return 0;
}

L2-023 图着色问题（dfs）

输入：

6 8 3
2 1
1 3
4 6
2 5
2 4
5 4
5 6
3 6
4
1 2 3 3 1 2
4 5 6 6 4 5
1 2 3 4 5 6
2 3 4 2 3 4

输出：

Yes
Yes
No
No

注意：颜色数要严格相等！如果用到的颜色小于颜色数K，也是No！

#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
#define pb push_back
typedef long long ll;
const int N=500+10;
int n,m,k;
bool g[N][N];//是否连通
int c[N];//颜色 
int vis[N],v[N];
int ans;
void dfs(int u)
{
	if(ans) return;
	if(v[u]) return;
	v[u]=1;
	for(int i=1;i<=n;i++)
	{
		if(g[u][i])
		{
			if(c[u]==c[i]) 
			{
				ans=1;return;
			}
			else 
			{
				if(!v[i]) dfs(i);
			}					
		}
	}
}
int main()
{
	cin>>n>>m>>k;
	fir(i,1,m)
	{
		int a,b;cin>>a>>b;
		g[a][b]=g[b][a]=1;
	}
	int t;cin>>t;
	while(t--)
	{
		mem(c,0);
		mem(vis,0);
		fir(i,1,n) 
		{
			cin>>c[i];
			vis[c[i]]=1;
		}
		int f=0;
		for(int i=1;i<=n;i++)
		{
			if(vis[i]) f++;
		}
		if(f!=k) //颜色数量必须与k相同！！ 
		{
			puts("No");
			continue;
		}
		ans=0;
		mem(v,0);//dfs
		for(int i=1;i<=n;i++)
		{
			if(!v[i]) dfs(i);
		}
		if(ans) puts("No");
		else puts("Yes");
	}
	return 0;
}

L2-024 部落

输入：

4
3 10 1 2
2 3 4
4 1 5 7 8
3 9 6 4
2
10 5
3 7

输出：

10 2
Y
N

题解：一个并查集。

#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
typedef long long ll;
const int N=1e4+10;
int p[N];
int find(int x)
{
	if(x!=p[x]) p[x]=find(p[x]);
	return p[x];
}
int v[N],ans;
int n;
set<int>siz;
int main()
{
	//输入 
	cin>>n;
	for(int i=1;i<=1e4;i++) p[i]=i;
	ans=0;
	fir(i,1,n)
	{
		int m;scanf("%d",&m);
		int head;scanf("%d",&head);
		int headd=find(head);
		v[head]=1;
		fir(i,2,m)
		{
			int x;scanf("%d",&x);
			v[x]=1;
			int xx=find(x);
			if(xx!=headd) 
			{
				p[xx]=headd;
			//	ans++;
			}
		}
	}
	//求有多少人和多少部落 
	int peo=0;
	fir(i,1,1e4) 
	{
		if(v[i]) 
		{
			peo++;
			int ii=find(i);
			siz.insert(ii);
		}		
	}
	cout<<peo<<" "<<siz.size()<<endl;
	//求是否在一个并查集内 
	int m;cin>>m;
	fir(i,1,m)
	{
		int a,b;cin>>a>>b;
		int aa=find(a),bb=find(b);
		if(aa!=bb) puts("N");
		else puts("Y");
	}
	return 0;
}

L2-030 冰岛人（模拟）

输入：

15
chris smithm
adam smithm
bob adamsson
jack chrissson
bill chrissson
mike jacksson
steve billsson
tim mikesson
april mikesdottir
eric stevesson
tracy timsdottir
james ericsson
patrick jacksson
robin patricksson
will robinsson
6
tracy tim james eric
will robin tracy tim
april mike steve bill
bob adam eric steve
tracy tim tracy tim
x man april mikes

输出：

Yes
No
No
Whatever
Whatever
NA

模拟题。通过姓=父亲的名来找父亲。注意读题：

所谓“五代以内无公共祖先”是指两人的公共祖先（如果存在的话）必须比任何一方的曾祖父辈分高。

也就是说，若公共祖先要比其中一个人的曾祖父辈分低，则有公共祖先。
即：循环的时候一层是遍历所有，一层是遍历到曾祖父。

代码：

#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
#define pb push_back
//#define first fi
//#define second se
typedef long long ll;
const int N=1e5+10;
map<string,pair<string,int>>mp;//名 姓 性别 
int n;
bool judge(string m1,string m2)
{
	//姓==父名
	int i=1,f=0;
	for(string a=m1;a!="";a=mp[a].first)
	{		
		int j=1;
		for(string b=m2;b!="";b=mp[b].first)
		{
			/*
			所谓“五代以内无公共祖先”
			是指两人的公共祖先（如果存在的话）
			必须比任何一方的曾祖父辈分高。
			曾祖父辈分==4
			*/
			if(j>=5&&i>=5) break;
			if(a==b&&(i<5||j<5)) 
			{
				return 1;
			}
			j++;
		}	
		//if(i>=5) break;
		i++;		
	} 
	
	return 0;
}
int main()
{
	cin>>n;
	fir(i,1,n)
	{
		string a,b;
		cin>>a>>b;//名 姓 
		if(b.back()=='f'||b.back()=='m')
		{
			mp[a].first="";
			if(b.back()=='f') mp[a].second=0;
			else mp[a].second=1;
		}
		else if(b.back()=='n')
		{
			mp[a].first=b.substr(0,b.size()-4);
			mp[a].second=1;
		}
		else if(b.back()=='r')
		{
			mp[a].first=b.substr(0,b.size()-7);
			mp[a].second=0;
		}
	}
	int m;cin>>m;
	while(m--)
	{
		string m1,x1,m2,x2;
		cin>>m1>>x1>>m2>>x2;
		if(mp.find(m1)==mp.end()||mp.find(m2)==mp.end()) puts("NA");
		else if(mp[m1].second==mp[m2].second) puts("Whatever");
		else if(judge(m1,m2)) puts("No");
		else puts("Yes");
 	}
	return 0;
}

L2-032 彩虹瓶（模拟+栈）

输入：

7 5 3
7 6 1 3 2 5 4
3 1 5 4 2 6 7
7 6 5 4 3 2 1

输出：

YES
NO
NO

代码：

#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
#define pb push_back
typedef long long ll;
const int N=1e3+10;
int n,m,k;
int main()
{
	cin>>n>>m>>k;
	while(k--)
	{
		stack<int>s;		
		int now=1,flag=1;
		fir(i,1,n)
		{
			int t;cin>>t;
			if(t==now) 
			{
				now++;//每次now变了都可以出一波 
				while(s.size()&&s.top()==now&&flag)
				{
					s.pop();now++;
				}
			}
			else
			{
				s.push(t);
				if(s.size()>m)
				{
					flag=0;
				}
			}
		}
		while(s.size()&&s.top()==now&&flag)
		{
			s.pop();now++;
		}
		if(s.empty()) puts("YES");
		else puts("NO");		
	}
	return 0;
}

L2-035 完全二叉树的层序遍历（二叉树概念+递归）

参考：柳神：L2-035 完全二叉树的层序遍历 (25 分)-PAT 团体程序设计天梯赛 GPLT
代码：

#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define mem(a,x) memset(a,x,sizeof(a));
#define pb push_back
typedef long long ll;
const int N=30+10;
int n,a[N],ans[N],cnt;
void solve(int idx)
{
	if(idx>n) return;//完全二叉树的性质
	//后序遍历的顺序：左右根 
	solve(idx*2);//左 
	solve(idx*2+1);//右 
	ans[idx]=a[cnt++];
}
int main()
{
	cin>>n;
	fir(i,1,n) cin>>a[i];
	cnt=1;
	solve(1);
	fir(i,1,n) 
	{
		if(i!=1) cout<<" ";
		cout<<ans[i];
	}
	return 0;
}

L2-036 网红点打卡攻略（模拟+读题！！）

输入：

6 13
0 5 2
6 2 2
6 0 1
3 4 2
1 5 2
2 5 1
3 1 1
4 1 2
1 6 1
6 3 2
1 2 1
4 5 3
2 0 2
7
6 5 1 4 3 6 2
6 5 2 1 6 3 4
8 6 2 1 6 3 4 5 2
3 2 1 5
6 6 1 3 4 5 2
7 6 2 1 3 4 5 2
6 5 2 1 4 3 6

输出：

3
5 11

这题给了我一个深刻的教训：要认真读题。
此题是模拟题，只需判断输入的方案是否合法（即：是否经过所有点，要经过的路径是否存在，经过的点是否有且仅经过一次），而非什么最短路。（我竟然把它理解成为dfs+dijsktra）
如题：

你的任务就是从一大堆攻略中，找出那个能在每个网红点打卡仅一次、并且路上花费最少的攻略。

所以这道题是在给出的攻略中找一个最优，而非总体找最优值。

ps：memset的函数背错了，也浪费了很多时间。所以要记熟了再用缩写…

#include<bits/stdc++.h>
using namespace std;
#define fir(i,a,n) for(int i=a;i<=n;i++)
#define pb push_back
#define ll long long
#define mem(a,x) memset(a,x,sizeof(a))
const int N=200+10;
int n,m,g[N][N];
int v[N];//visited
struct node
{
	int i,ans;
};
vector<node>anss;
bool cmp(node a,node b)
{
	if(a.ans!=b.ans) return a.ans<b.ans;
	else return a.i<b.i;
}
int main()
{
	cin>>n>>m;
	fir(i,1,m)
	{
		int a,b,c;cin>>a>>b>>c;
		g[a][b]=c;
		g[b][a]=c;
	}
	
	int k;cin>>k;
	fir(i,1,k)
	{
		int kk;cin>>kk;
		int now=0,sum=0,flag=0;
		if(kk!=n) flag=1;
		mem(v,0);
		fir(j,1,kk)
		{
			int temp;cin>>temp;
			if(g[now][temp]&&!v[temp])
			{
				sum+=g[now][temp];
				v[temp]=1;
			}
			else  flag=1;								
			now=temp;			
		}
		if(g[now][0]) sum+=g[now][0];
		else flag=1;
		if(!flag) anss.pb({i,sum});
	}
	cout<<anss.size()<<endl;
	sort(anss.begin(),anss.end(),cmp);
	cout<<anss[0].i<<" "<<anss[0].ans;
	return 0;
}