AtCoder Beginner Contest 209（D，E）
D(树,lca)
这个题给出\(n\)个点，\(n-1\)条边，有两个人，一个人在\(c\)点，一个人在\(d\)点，两人以相同的速度朝着对方走来（并且都是按照最短路的走法），问这两个人相遇是在点上，还是在路上
这一题意很好知道，就是判断这两点之间的最短距离的奇偶性
然后我就一个一个地去求最短路了，结果毫不意外的超时了
但是这个我感觉就是这个最短路迷惑了我
其实这道题告诉我们总共有\(n-1\)条路了，我们就应该知道这个在没有重边的情况下是一棵树，而且每一条边的距离都是一样的，那么对于这样的一棵树来说，好像两点之间的距离就直接是可求的，即\(dis_c+dis_d-2\times dis_{lca(c,d)}\)
然后这个\(2\times dis_{lca(c,d)}\)不会影响奇偶性，那么奇偶性就看\(dis_c+dis_d\)了
所以我们只需要知道\(dis_c\)和\(dis_d\)的和即可
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
using namespace std;
#define int long long
#define LL long long
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define mem(a,b) memset((a),(b),sizeof(a))
const double eps=1e-9;
const int maxn=2e5+10;
const int mod=1e9+7;
int n,q;
vector<int>g[maxn];
int dis[maxn];
void dfs(int u,int fa)
{
dis[u]=dis[fa]+1;
for (auto v:g[u])
{
if(v==fa) continue;
dfs(v,u);
}
return ;
}
signed main()
{
cin>>n>>q;
for (int i=1;i<n;i++)
{
int u,v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
dfs(1,0);
while (q--)
{
int x,y;
cin>>x>>y;
int flag=dis[x]+dis[y];
if(flag&1)
{
cout<<"Road\n";
}
else
{
cout<<"Town\n";
}
}
system ("pause");
return 0;
}
E（博弈，拓扑，图）
这个题意大致就是两个人，每次都必须选择上一个人选择的一个字符串的最后三个字符作为最前面三个字符的字符串，知道某人找不到这样的字符串，那么这个人就输了（类似于词语接龙）
这个题乍一看看不出什么规律，只能根据最原始的判断方法，第一步都不能找到成功的解法，先手必败，对于后面的步骤，如果下一步先手是必败，那么这一步必胜，如果这一步只能到达必败的状态，那么这一步也是必败
然后这个题还会存在平局，那就就意味着这个题出现了环，（刚好拓扑排序里面没有访问到的就是环）
然后我们就直接以上规律求出解
但是每次输入的字符串要怎么转化成边呢
我们可以对于一个字符串，最主要的就是前三个字符\(pre\)和后三个字符\(suf\)，我们首先把这两个字符转化成\(hash\)值，然后我们可以建造反图，如果是最开始的，那么就意味着它后面没有可选字符串了，可以得知最开始的一部分字符串的状态，然后这些字符串通过拓扑排序来寻找它其他字符的状态
具体可看代码
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include<cmath>
#include <unordered_map>
#include <array>
#include <cstring>
using namespace std;
#define int long long
#define LL long long
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define inf 1e18
#define INF 1e18
#define mem(a,b) memset((a),(b),sizeof(a))
const double eps=1e-9;
const int maxn=2e5+10;
const int mod=1e9+7;
int n;
vector<int>g[maxn];
int in[maxn];
int star[maxn];
int ans[maxn];
set<int>id;
int get(string s)
{
int res=0;
for (int i=0;i<s.size();i++)
{
int now=0;
if(s[i]>='a'&&s[i]<='z')
{
now=s[i]-'a';
}
else
{
now=s[i]-'A'+26;
}
res=res*52+now;
}
return res;
}
signed main()
{
cin>>n;
for (int i=1;i<=n;i++)
{
string s;
cin>>s;
string pre=s.substr(0,3);
string suf=s.substr(s.size()-3,3);
int u=get(suf),v=get(pre);
id.insert(u);
id.insert(v);
g[u].push_back(v);
in[v]++;
star[i]=u;
ans[u]=-1;
}
queue<int>q;
for (auto x:id)
{
if(in[x]==0)
{
q.push(x);
ans[x]=0;
}
}
while (!q.empty())
{
int u=q.front();
q.pop();
for (auto v:g[u])
{
if(ans[v]==-1)
{
in[v]--;
if(ans[u]==0)
{
ans[v]=1;
q.push(v);
}
else if(in[v]==0)
{
ans[v]=0;
q.push(v);
}
}
}
}
for (int i=1;i<=n;i++)
{
if(ans[star[i]]==-1)
{
cout<<"Draw\n";
}
else if(ans[star[i]]==1)
{
cout<<"Aoki\n";
}
else
{
cout<<"Takahashi\n";
}
}
system ("pause");
return 0;
}