1139 First Contact (30 分)

题目链接

https://pintia.cn/problem-sets/994805342720868352/problems/994805344776077312

AC代码

#include<bits/stdc++.h>
using namespace std;
struct node{
	int f1,f2;
};
unordered_map<int,int> gender,team;
unordered_map<int,vector<int>> f;
bool cmp(node x,node y){
	return x.f1!=y.f1?x.f1<y.f1:x.f2<y.f2;
}
int main()
{
	int n,m,k;
	cin>>n>>m;
	while(m--)
	{
		string s1,s2;
		int t1,t2,flag1=1,flag2=1;
		cin>>s1>>s2;
		if(s1[0]=='-') flag1=-1;
		if(s2[0]=='-') flag2=-1;
		t1=abs(stoi(s1));
		t2=abs(stoi(s2));
		gender[t1]=flag1;
		gender[t2]=flag2;
		f[t1].push_back(t2);
		f[t2].push_back(t1);
		team[t1*10000+t2]=team[t2*10000+t1]=1;
	}
	cin>>k;
	while(k--)
	{
		vector<node> ans;
		int t1,t2;
		cin>>t1>>t2;
		t1=abs(t1),t2=abs(t2);
		for(int i=0;i<f[t1].size();i++)
		{
			for(int j=0;j<f[t2].size();j++)
			{
				int f1=f[t1][i],f2=f[t2][j];
				if(f1==t2||f2==t1) continue;
				if(team[f1*10000+f2]&&gender[f1]==gender[t1]&&gender[f2]==gender[t2])
					ans.push_back({f1,f2}); 
			}
		}
		sort(ans.begin(),ans.end(),cmp);
		cout<<ans.size()<<endl;
		for(int i=0;i<ans.size();i++)
			printf("%04d %04d\n",ans[i].f1,ans[i].f2);
	}
}

注意事项

之所以在输入阶段大费周章采用字符串判断正负，就是为了对0000做判断，因为如果整数判断，0本身的正负无法确定（即-0000无法判断）
A爱B，但A、B不能是朋友（强烈吐槽，恋爱不都是从朋友到女（男）朋友吗，一见钟情除外。关键是题目里并没有相关的提示信息啊，哪位朋友如果能找到提示信息可以发在评论区里）

1142. Maximal Clique (25分)

题目链接

https://pintia.cn/problem-sets/994805342720868352/problems/994805343979159552

AC代码

#include<bits/stdc++.h>
using namespace std;
int a[205][205];
int main()
{
	int nv,ne,m,k,t;
	cin>>nv>>ne;
	while(ne--)
	{
		int t1,t2;
		cin>>t1>>t2;
		a[t1][t2]=a[t2][t1]=1;
	}
	cin>>m;
	while(m--)
	{
		int flag1=1,flag2=1,vis[nv+1]={0};
		fill(vis,vis+nv,0);
		cin>>k;
		if(k==0)
		{
			cout<<"Not a Clique"<<endl;
			continue;
		}
		vector<int> ans;
		for(int i=0;i<k;i++)
		{
			cin>>t;
			vis[t]=1;
			ans.push_back(t);
		}
		for(int i=0;i<k-1;i++)
		{
			for(int j=i+1;j<k;j++)
			{
				if(a[ans[i]][ans[j]]==0)
				{
					flag1=0;
					break;
				}
				if(flag1==0) break;
			}
		}
		if(flag1==0) cout<<"Not a Clique"<<endl;
		else
		{
			for(int i=1;i<=nv;i++)
			{
				if(vis[i]==0)
				{
					for(int j=0;j<k;j++)
					{
						if(a[i][ans[j]]==0)
							break;
						if(j==k-1) flag2=0;
					}
				}
				if(flag2==0) 
				{
					cout<<"Not Maximal"<<endl;
					break; 
				}
			}
			if(flag2==1) cout<<"Yes"<<endl; 
		}
		
	}
}

注意事项

flag1，flag2两个变量的判断顺序——要在第一个判断是否连通后，再进入maximal的判断
我自己的代码在设置判断点是否在待测数组的vis时，将范围设置为了nv，即vis[nv]={0}，但发现测试点2、3一直过不去，在将其改为vis[nv+1]={0}后，便可全部通过（测试了好久才找到，这是因为序号是从1到nv排序的）

1143 Lowest Common Ancestor (30 分)

题目链接

https://pintia.cn/problem-sets/994805342720868352/problems/994805343727501312

AC代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int m,n;
	cin>>m>>n;
	vector<int> pre(n);
	unordered_map<int,int> vis;
	for(int i=0;i<n;i++)
	{
		cin>>pre[i];
		vis[pre[i]]=1;
	}
	while(m--)
	{
		int x,y,root;
		cin>>x>>y;
		if(vis[x]==0&&vis[y]==0) 
		{
			printf("ERROR: %d and %d are not found.\n",x,y);
			continue;
		}
		else if(vis[x]==0||vis[y]==0)
		{
			printf("ERROR: %d is not found.\n",vis[x]==0?x:y);
			continue;
		}
		for(int i=0;i<n;i++)
		{
			root=pre[i];
			if((x<root&&y>root)||(x>root&&y<root)||x==root||y==root)
				break;	
		}	
		if((x<root&&y>root)||(x>root&&y<root))
			printf("LCA of %d and %d is %d.\n",x,y,root);
		else if(x==root)
			printf("%d is an ancestor of %d.\n",x,y);
		else if(y==root)
			printf("%d is an ancestor of %d.\n",y,x);
	}	
}