https://pintia.cn/problem-sets/994805046380707840/problems/1111914599412858887
C++版本一
题解:LCA
25分满分题解:
1、map映射分配ID,只要给名分配就行了;
2、起源人的姓相同不算是同一个家族;
3、数据存在性别为女的节点有子节点,此时子节点作为起源人处理;
4、存在多个起源人
5、并查集路径压缩
6、嫡系亲属不论相隔多少代都不能结婚(LCA没有这个问题)
7、log2()函数可能存在精度问题
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=200000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-2;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum,tot;
int pre[N];//并查集
bool vis[N];//DFS标记
int dep[N];//深度
int dp[N][21];//ST
char str1[30],str2[30],str3[30],str4[30],fa[N][30],son[N][30];
bool sex[N];//性别
int lg[N];
map<string,int>mp,mp1;//映射
vector<int>G[N];//图
int find(int x){return pre[x]==x?x:pre[x]=find(pre[x]);}//并查集find()
void marge(int u,int v){//并查集marge
int tu=find(u);
int tv=find(v);
if(tu!=tv){
pre[tu]=tv;
}
}
void dfs(int u){//DFS
vis[u]=1;//cout<<u<<endl;
for(int i=0,j=G[u].size();i<j;i++){
int v=G[u][i];
if(!vis[v]){
dep[v]=dep[u]+1;
dp[v][0]=u;
dfs(v);
}
}
}
void init(){//初始化
for(int i=1;i<N;i++){
G[i].clear();
pre[i]=i;
}
memset(vis,0,sizeof(vis));
memset(dep,0,sizeof(dep));
memset(dp,0,sizeof(dp));
mp.clear();
}
int LCA(int x,int y){//最近公共祖先
if(dep[x]<dep[y])
swap(x,y);
while(dep[x]>dep[y])
x=dp[x][lg[dep[x]-dep[y]]];
if(x==y)
return x;
for(int i=lg[dep[x]]+EXP;i>=0;i--){
if(dp[x][i]!=dp[y][i])
x=dp[x][i],y=dp[y][i];
}
return dp[x][0];
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
//while(t--){
scanf("%d",&n);
init();
for(int i=1;i<=n;i++){
cin>>str1>>str2;
int len=strlen(str2);
mp1[str1]=i;
if(str2[len-1]=='m'){
sex[i]=0;
}else if(str2[len-1]=='f'){
sex[i]=1;
}else if(str2[len-1]=='n'){
sex[i]=0;
}else if(str2[len-1]=='r'){
sex[i]=1;
}
strcpy(son[i],str1);
strcpy(fa[i],str2);
}
for(int i=1;i<=n;i++){
u=i;int len=strlen(fa[i]);
if(fa[i][len-1]=='n'){
fa[i][len-4]='\0';
v=mp1[fa[i]];
if(sex[v]==0){//女爸爸问题
marge(u,v);
G[u].push_back(v);
G[v].push_back(u);
}
}else if(fa[i][len-1]=='r'){
fa[i][len-7]='\0';
v=mp1[fa[i]];
if(sex[v]==0){
marge(u,v);
G[u].push_back(v);
G[v].push_back(u);
}
}
}
for (int i = 1; i <= n; ++i)
lg[i] = lg[i - 1] + (1 << lg[i - 1] + 1 == i);//log2
for(int i=1;i<=n;i++){
if(pre[i]==i){
dfs(i);//搜图
}
}
for(int i=0;i<20;i++){
for(int j=1;j<=n;j++){
dp[j][i+1]=dp[dp[j][i]][i];//ST
}
}
scanf("%d",&m);
for(int i=1;i<=m;i++){
cin>>str1>>str2>>str3>>str4;
u=mp1[str1];
v=mp1[str3];
//名字不存在
if(mp1[str1]==0||mp1[str3]==0){
cout<<"NA"<<endl;
continue;
}
//性别相同
if(sex[u]==sex[v]){
cout<<"Whatever"<<endl;
}else{
//无公共祖先
if(find(u)!=find(v)){
cout<<"Yes"<<endl;
continue;
}
//最近公共祖先
int lca=LCA(u,v);
//cout<<lca<<" "<<u<<" "<<v<<endl;
//cout<<dep[lca]<<" "<<dep[u]<<" "<<dep[v]<<endl;
if(dep[u]-dep[lca]<4||dep[v]-dep[lca]<4){//五代以内
cout<<"No"<<endl;
}else{
cout<<"Yes"<<endl;
}
}
}
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
C++版本二
模拟
https://blog.csdn.net/qq_40946921/article/details/88934369
#include<iostream>
#include<map>
#include<string>
using namespace std;
struct Peoson {
char sex;
string father;
};
map<string, Peoson> people;
int judge(string a, string b) {
int i = 1, j;
for (string A = a; !A.empty(); A = people[A].father, i++) {
j = 1;
for (string B = b; !B.empty(); B = people[B].father, j++) {
if (i >= 5 && j >= 5) break; //双方都超出5代之后,不需要继续寻找(测试点6 运行超时)
if (A == B && (i < 5 || j < 5)) //五代内出现共同祖先,返回false(测试点3、6答案错误)
return 0;
}
}
return 1;
}
int main() {
int n, m;
string str, a, b;
cin.sync_with_stdio(false);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a >> b;
if (b.back() == 'n') //儿子
people[a] = { 'm',b.substr(0,b.size() - 4) };
else if (b.back() == 'r') //女儿
people[a] = { 'f',b.substr(0, b.size() - 7) };
else people[a].sex = b.back(); //其他人
}
cin >> m;
for (int i = 0; i < m; i++) {
cin >> a >> str >> b >> str; //姓氏没有用
if (people.find(a) == people.end() || people.find(b) == people.end()) printf("NA\n");
else if (people[a].sex == people[b].sex) printf("Whatever\n");
else printf("%s\n", judge(a, b) ? "Yes" : "No");
}
return 0;
}
C++版本三
题解:https://blog.csdn.net/weixin_43264529/article/details/88925108
样例图解
第一次查 10、11号节点,最近公共父节点为0号节点,0到10和11的距离均为4,成立,输出Yes;
第二次查 14、10号节点,最近公共父节点为3号节点,3到10和11的距离均为3,不成立,输出No;
第三次查8,6号节点,最近公共父节点为0号节点,0到8的距离均为3,0到和6的距离为2,不成立,输出No;
第四五次查询性别相同,输出Whatever
第六次查询,信息不存在,输出NA。
记下每一个人的父节点,然后找最近公共父节点,再检查最近公共父节点到两个人之间的距离是否都大于3。
#include <bits/stdc++.h>
using namespace std;
bool judge(vector<int> &F, int s1, int s2)
{
int n = F.size();
vector<int> count(n, 0);
vector<int> dist1(n, 0);
vector<int> dist2(n, 0);
int t ;
count[s1]++;
count[s2]++;
while(F[s1] != -1)
{
t = F[s1];
count[t]++;
dist1[t] = dist1[s1] + 1;
if(t == s2) //直系祖宗...太乱了,直接false,不加这个,会有两个点过不去
return false;
s1 = t;
}
while(F[s2] != -1)
{
t = F[s2];
count[t]++;
dist2[t] = dist2[s2] + 1;
if(count[t] > 1)
{
if(dist2[t]>=4 && dist1[t] >= 4)
return true;
else
return false;
}
s2 = t;
}
return true;
}
int main()
{
int n;
cin >> n;
string f1, f2;
vector<bool> sex(n);
vector<vector<string> > record(n);
map<string, int> M; //给每个人编号
vector<int> F(n, -1); //父节点编号
int cnt = 0;
for(int i=0;i<n;i++) //编号
{
cin >> f1 >> f2;
M.insert(make_pair(f1, cnt));
int l = f2.size();
if(f2[l-1] == 'm' || f2[l-1] == 'n')
sex[cnt] = 1; //男
else
sex[cnt] = 0;
cnt++;
record[i].push_back(f1);
record[i].push_back(f2);
}
string par;
for(int i=0;i<n;i++) //找父节点
{
f1 = record[i][0];
f2 = record[i][1];
int len = f2.size();
if(f2[len-1] != 'r' && f2[len-1] != 'n') //老祖宗
continue;
if(sex[M[f1]] == true)
par = f2.substr(0, len-4);
else
par = f2.substr(0, len-7);
F[M[f1]] = M[par];
}
int m;
cin >> m;
string t1,t2;
for(int i=0;i<m;i++)
{
cin >> f1 >> f2 >> t1 >> t2;
if(M.find(f1) == M.end() || M.find(t1) == M.end() )
{
cout << "NA" << endl;
continue;
}
if(sex[M[f1]] == sex[M[t1]])
{
cout << "Whatever" << endl;
continue;
}
if(judge(F, M[f1], M[t1]))
{
cout << "Yes" << endl;
}
else
cout << "No" << endl;
}
return 0;
}
24分
一个女爸爸问题
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=200000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-2;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum,tot;
int pre[N];//并查集
bool vis[N];//DFS标记
int dep[N];//深度
int dp[N][21];//ST
char str1[30],str2[30],str3[30],str4[30],fa[N][30],son[N][30];
bool sex[N];//性别
int frist[N];//父节点
int lg[N];
map<string,int>mp;//映射
vector<int>G[N];//图
int find(int x){return pre[x]==x?x:pre[x]=find(pre[x]);}//并查集find()
void marge(int u,int v){//并查集marge
int tu=find(u);
int tv=find(v);
if(tu!=tv){
pre[tu]=tv;
}
}
void dfs(int u){//DFS
vis[u]=1;
for(int i=0,j=G[u].size();i<j;i++){
int v=G[u][i];
if(!vis[v]){
dep[v]=dep[u]+1;
dp[v][0]=u;
dfs(v);
}
}
}
void init(){//初始化
for(int i=1;i<N;i++){
G[i].clear();
pre[i]=i;
}
memset(vis,0,sizeof(vis));
memset(dep,0,sizeof(dep));
memset(dp,0,sizeof(dp));
cnt=0;
tot=0;
mp.clear();
}
int LCA(int x,int y){//最近公共祖先
if(dep[x]<dep[y])
swap(x,y);
while(dep[x]>dep[y])
x=dp[x][lg[dep[x]-dep[y]]];
if(x==y)
return x;
for(int i=lg[dep[x]]+EXP;i>=0;i--){
if(dp[x][i]!=dp[y][i])
x=dp[x][i],y=dp[y][i];
}
return dp[x][0];
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
//while(t--){
scanf("%d",&n);
n*=2;
init();
for(int i=1;i<=n/2;i++){
cin>>str1>>str2;
int len=strlen(str2);
bool sex0=0;//性别判断
if(str2[len-1]=='m'){
str2[len-1]='\0';
sex0=0;
}else if(str2[len-1]=='f'){
str2[len-1]='\0';
sex0=1;
}else if(str2[len-1]=='n'){
str2[len-4]='\0';
sex0=0;
}else if(str2[len-1]=='r'){
str2[len-7]='\0';
sex0=1;
}
if(!mp[str1]){
mp[str1]=++tot;
}
if(!mp[str2]){
mp[str2]=++tot;
}
u=mp[str1];
v=mp[str2];
sex[u]=sex0;
//sex[v]=0;
strcpy(son[i],str1);
strcpy(fa[i],str2);
//cout<<str2<<v<<sex[v]<<endl;
}
for(int i=1;i<=n/2;i++){
u=mp[son[i]];
v=mp[fa[i]];frist[u]=v;
if(sex[v]==0){
marge(u,v);
G[u].push_back(v);
G[v].push_back(u);
}
}
for (int i = 1; i <= tot; ++i)
lg[i] = lg[i - 1] + (1 << lg[i - 1] + 1 == i);
for(int i=1;i<=tot;i++){
if(pre[i]==i){
dfs(i);
}
}
//cout<<"2"<<endl;
for(int i=0;i<20;i++){
for(int j=1;j<=tot;j++){
dp[j][i+1]=dp[dp[j][i]][i];
}
}
scanf("%d",&m);
for(int i=1;i<=m;i++){
cin>>str1>>str2>>str3>>str4;
u=mp[str1];
v=mp[str3];
int fu=mp[str2];
int fv=mp[str4];
//名字不存在
if(mp[str1]==0||mp[str2]==0||mp[str3]==0||mp[str4]==0||frist[u]!=fu||frist[v]!=fv){
cout<<"NA"<<endl;
continue;
}
//性别相同
if(sex[u]==sex[v]){
cout<<"Whatever"<<endl;
}else{
//无公共祖先
if(find(u)!=find(v)){
cout<<"Yes"<<endl;
continue;
}
//最近公共祖先
int lca=LCA(u,v);
//cout<<lca<<" "<<u<<" "<<v<<endl;
//cout<<dep[lca]<<" "<<dep[u]<<" "<<dep[v]<<endl;
if(dep[u]-dep[lca]<4||dep[v]-dep[lca]<4){//五代以内
cout<<"No"<<endl;
}else{
cout<<"Yes"<<endl;
}
}
}
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}
22分(满分25分)真的不会了
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=200000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum,tot;
int pre[N];
bool vis[N];
int dep[N];
int dp[N][21];
char str1[30],str2[30],str3[30],str4[30];
bool sex[N];
int frist[N];
map<string,int>mp;
vector<int>G[N];
int find(int x){return pre[x]==x?x:pre[x]=find(pre[x]);}
void marge(int u,int v){
int tu=find(u);
int tv=find(v);
if(tu!=tv){
pre[tu]=tv;
}
}
void dfs(int u){
vis[u]=1;
for(int i=0,j=G[u].size();i<j;i++){
int v=G[u][i];
if(!vis[v]){
dep[v]=dep[u]+1;
dp[v][0]=u;
dfs(v);
}
}
}
void init(){
for(int i=1;i<N;i++){
G[i].clear();
pre[i]=i;
}
memset(vis,0,sizeof(vis));
memset(dep,0,sizeof(dep));
memset(dp,0,sizeof(dp));
cnt=0;
tot=0;
mp.clear();
}
int LCA(int x,int y){
if(dep[x]<dep[y])
swap(x,y);//cout<<x<<" "<<dp[1][0]<<endl;
while(dep[x]>dep[y])
x=dp[x][(int)log2(dep[x]-dep[y])];
if(x==y)
return x;
for(int i=log2(dep[x]);i>=0;i--){
if(dp[x][i]!=dp[y][i])
x=dp[x][i],y=dp[y][i];
}
return dp[x][0];
}
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//ios::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
//scanf("%d",&t);
//while(t--){
scanf("%d",&n);
n*=2;
init();
for(int i=1;i<=n/2;i++){
cin>>str1>>str2;
int len=strlen(str2);
bool sex0=0;
if(str2[len-1]=='m'){
str2[len-1]='\0';
sex0=0;
}else if(str2[len-1]=='f'){
str2[len-1]='\0';
sex0=1;
}else if(str2[len-1]=='n'){
str2[len-4]='\0';
sex0=0;
}else if(str2[len-1]=='r'){
str2[len-7]='\0';
sex0=1;
}
if(!mp[str1]){
mp[str1]=++tot;
}
if(!mp[str2]){
mp[str2]=++tot;
}
u=mp[str1];
v=mp[str2];
sex[u]=sex0;
sex[v]=0;
frist[u]=v;
marge(u,v);
G[u].push_back(v);
G[v].push_back(u);
//cout<<str2<<v<<endl;
}
for(int i=1;i<=n;i++){
if(pre[i]==i){
dfs(i);
}
}
//cout<<"2"<<endl;
for(int i=0;i<20;i++){
for(int j=1;j<=n;j++){
dp[j][i+1]=dp[dp[j][i]][i];
}
}
scanf("%d",&m);
for(int i=1;i<=m;i++){
cin>>str1>>str2>>str3>>str4;
u=mp[str1];
v=mp[str3];
int fu=mp[str2];
int fv=mp[str4];
if(mp[str1]==0||mp[str2]==0||mp[str3]==0||mp[str4]==0||frist[u]!=fu||frist[v]!=fv){
cout<<"NA"<<endl;
continue;
}
if(sex[u]==sex[v]){
cout<<"Whatever"<<endl;
}else{
if(find(u)!=find(v)){
cout<<"Yes"<<endl;
continue;
}
int lca=LCA(u,v);
//cout<<lca<<" "<<u<<" "<<v<<endl;
//cout<<dep[lca]<<" "<<dep[u]<<" "<<dep[v]<<endl;
if(dep[u]-dep[lca]<4||dep[v]-dep[lca]<4){
cout<<"No"<<endl;
}else{
cout<<"Yes"<<endl;
}
}
}
//}
#ifdef DEBUG
printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
//cout << "Hello world!" << endl;
return 0;
}