同类型题目 天梯赛 L2-016 愿天下有情人都是失散多年的兄妹 个人题解
思路:
1.本题有4个输出,性别相同和人名是否出现过很好判断,主要就是判断五代内是否存在公共祖先。
2.首先,我们根据题目要求,可以通过哈希表将字符串映射到有序点上,依次建图。
3.这里建图是孩子指向双亲。
4.然后就是主要的判断五代内是否存在公共祖先。
判断五代内是否存在公共祖先:
1.首先,在本题中,双方并不保证是同辈份。
2.所以假设A的第十三代祖先是B的第四代祖先,二者也不可以谈恋爱。(题目要求就是这样)。
3.这里题目要求是五代以内,所以第五代就不算了。
4.所以我们可以做两次判断,每次跑两个dfs。
5.第一个dfs标记A的所有祖先,第二个dfs看B的五代以内是否存在公共祖先。
6.然后在调换做一遍。
注意:
1.要先判断人名是否存在在根据性别判断。
2.因为我这里先判断了性别,但如果是没出现过的人名,他们的性别都是保持初始化状态。
3.就是一样的,会触发Whatever答案的错判。
#include <bits/stdc++.h>
#include <ext/rope>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
#define fi first
#define se second
typedef long long LL;
const int N = 1e5 + 10;
// const int R = 999997;
const int Base = N / 2;
const int M = 1e6 + 10;
// const int P = 1 << 10;
const LL INF = 0x3f3f3f3f3f3f3f3fll;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef pair<double, double> PDD;
typedef pair<PII, int> PIII;
typedef pair<LL, int> PLI;
typedef pair<int, string> PIS;
typedef pair<double, int> PDI;
typedef pair<string, int> PSI;
typedef pair<string, string> PSS;
const double eps = 1e-4;
const int mod = 1e9 + 7;
int n, k;
int m;
int Q;
// rope<int> r;
tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> treap;
int h[N];
int e[M];
int sex[N];
int ne[M];
int idx;
int cnt;
unordered_map<string, int> mp;
unordered_map<string, bool> q;
bool st[N];
bool flag;
void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx++;
}
void dfs1(int u, int num)
{
if (num >= 3)
{
return;
}
st[u] = true;
// cout << u << endl;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
// if (j == 8)
// {
// cout << u << endl;
// }
if (!st[j])
{
st[j] = true;
dfs1(j, num + 1);
}
else
{
// cout << st[j] << endl;
// cout << num << endl;
// cout << u << endl;
// cout << j << endl;
flag = true;
return;
}
}
}
void dfs2(int u)
{
// if (num >= 3)
// {
// return;
// }
st[u] = true;
// cout << u << endl;
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
// if (j == 8)
// {
// cout << u << endl;
// }
if (!st[j])
{
st[j] = true;
dfs2(j);
}
else
{
// cout << st[j] << endl;
// cout << num << endl;
// cout << u << endl;
// cout << j << endl;
flag = true;
return;
}
}
}
void solve()
{
scanf("%d", &n);
vector<PSS> query(n + 1);
memset(h, -1, sizeof h);
for (int i = 1; i <= n; i++)
{
string a, b;
cin >> a >> b;
query[i] = {a, b};
q[a] = true;
mp[a] = ++cnt;
}
for (int i = 1; i <= n; i++)
{
string a, b;
a = query[i].fi;
b = query[i].se;
// cout << a << endl;
int t = b.find("sson");
if (t != b.npos)
{
sex[mp[a]] = 1;
string str = b.substr(0, b.size() - 4);
add(mp[a], mp[str]);
}
else
{
t = b.find("sdottir");
if (t != b.npos)
{
sex[mp[a]] = 2;
string str = b.substr(0, b.size() - 7);
add(mp[a], mp[str]);
}
else
{
char c = b.back();
if (c == 'm')
{
sex[mp[a]] = 1;
}
else
{
sex[mp[a]] = 2;
}
}
}
// cout << sex[mp[a]] << endl;
}
scanf("%d", &m);
while (m--)
{
string a, b, c, d;
cin >> a >> b >> c >> d;
// cout << a << endl;
// cout << sex[mp[a]] << ' ' << sex[mp[c]] << endl;
if (!q.count(a) || !q.count(c))
{
puts("NA");
continue;
}
if (sex[mp[a]] == sex[mp[c]])
{
puts("Whatever");
continue;
}
memset(st, 0, sizeof st);
// cout << mp[a] << ' ' << mp[b] << endl;
// st[mp[a]] = true;
// st[mp[b]] = true;
// cout << st[8] << endl;s
flag = false;
dfs1(mp[a], 0);
// cout << st[8] << endl;
dfs2(mp[c]);
if (flag)
{
puts("No");
continue;
}
// cout << st[8] << endl;
memset(st, 0, sizeof st);
dfs1(mp[c], 0);
// cout << st[8] << endl;
dfs2(mp[a]);
if (!flag)
{
puts("Yes");
}
else
{
puts("No");
}
}
}
int main()
{
int t = 1;
// scanf("%d", &t);
// int a = 1;
// for (int i = 1; i <= 26; i++)
// {
// a = (a << 1) + 1;
// }
// cout << a << endl;
// float t = 134217727;
// int cnt = 200;
// printf("%.16lf", t);
// while (cnt--)
// {
// t = t * 2 + a;
// printf("%.16f\n", t);
// }
// getchar();
while (t--)
{
// cout << (2563 % 11) << endl;
// cout << t << endl;
solve();
// cout << (((float)1) << 63) << endl;
// cout << '\0' << endl;
// cout << f(4);
// cout<<(25 >> 5)
// cout << gcd(31415, 14142);//
// cout << (28284 / 11) << endl;
}
return 0;
}
/*
* __----~~~~~~~~~~~------___
* . . ~~//====...... __--~ ~~
* -. _|// |||\\ ~~~~~~::::... /~
* ___-==_ _-~o~ \/ ||| \\ _/~~-
* __---~~~.==~||\=_ -_--~/_-~|- |\\ \\ _/~
* _-~~ .=~ | \\-_ '-~7 /- / || \ /
* .~ .~ | \\ -_ / /- / || \ /
* / ____ / | \\ ~-_/ /|- _/ .|| \ /
* |~~ ~~|--~~~~--_ \ ~==-/ | \~--===~~ .\
* ' ~-| /| |-~\~~ __--~~
* |-~~-_/ | | ~_ _-~ /\
* / \ __ \/~ __
* _--~ _/ | .-~~____--~-/ ~~==.
* ((->/~ '.|||' -_| ~~-/ , . _||
* -_ ~\ ~~---l__i__i__i--~~_/
* _-~-__ ~) \--______________--~~
* //.-~~~-~_--~- |-------~~~~~~~~
* //.-~~~--\
* ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
*
* 神兽保佑 永无BUG
*/
/**
* ┏┓ ┏┓+ +
* ┏┛┻━━━┛┻┓ + +
* ┃ ┃
* ┃ ━ ┃ ++ + + +
* ████━████+
* ◥██◤ ◥██◤ +
* ┃ ┻ ┃
* ┃ ┃ + +
* ┗━┓ ┏━┛
* ┃ ┃ + + + +Code is far away from
* ┃ ┃ + bug with the animal protecting
* ┃ ┗━━━┓ 神兽保佑,代码无bug
* ┃ ┣┓
* ┃ ┏┛
* ┗┓┓┏━┳┓┏┛ + + + +
* ┃┫┫ ┃┫┫
* ┗┻┛ ┗┻┛+ + + +
*/