题意:Fennec和Snuke玩一个游戏,F在第一个点并且第一个点为黑色,S在第N个点并且第N个点为白色,然后给出一些点的相连,两个人轮流选择自己自己的颜色旁边相连并且没有上色的点进行涂色,谁最先没有色可以涂谁就输。问最后谁赢谁输。


题解:先dfs找到1到N这条链中间中间的下一个点并且保存位置为p,然后从第1个点开始再次dfs,如果遇到p点则停止dfs返回0,然后求dfs到点的和sum,如果sum>n-sum那么F赢,否则S赢。

(好菜啊需要两遍DFS,freeloop只需要一遍DFS就搞定,不愧是DIV1选手啊orz,后面附赠大神代码)


代码:

#include <iostream>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <sstream>
using namespace std;
 
typedef long long LL;
#define lowbit(x) ((x)&(-x))
#define INF 0x3f3f3f3f
#define memset(a,b) memset(a,b,sizeof(a))
#defineGE() printf(">----------\n")
#defineIN() freopen("in.txt","r",stdin)
#defineOUT() freopen("out.txt","w",stdout)
const int mod=1e9+7;
const LL inf=0x3f3f3f3f3f3f3f3f;
const double pi=acos(-1.0);
const double eps=1e-8;
const int maxn=100005;
 
int n, p;
vector<int> E[maxn];
int vis[maxn];
 
int dfs(int u, int step){
   vis[u]=1;
   if(u==n){
       int mid=step/2+1+step%2;
       if(step==mid)p=u;
       return mid;
   }
   for(int i=0;i<E[u].size();i++){
       int v=E[u][i];
       if(!vis[v]){
           int mid=dfs(v, step+1);
           if(mid&&step==mid&&!p)p=u;
           if(mid)return mid;
       }
   }
   return 0;
}
 
int dfs2(int u){
   vis[u]=1;
   if(u==p)return 0;
   int add=0;
   for(int i=0;i<E[u].size();i++){
       int v=E[u][i];
       if(!vis[v]){
           add+=dfs2(v);
       }
   }
   return add+1;
}
 
int main() {
   while(~scanf("%d", &n)){
       p=0;
       int u, v;
       for(int i=1;i<=n;i++)E[i].clear();
       for(int i=0;i<n-1;i++){
           scanf("%d%d", &u, &v);
           E[u].push_back(v);
           E[v].push_back(u);
       }
       memset(vis, 0);
       dfs(1, 1);
       memset(vis, 0);
       int sum=dfs2(1);
       printf("%s\n", sum>n-sum?"Fennec":"Snuke");
   }
   return 0;
}



freeloop代码:

#include <iostream>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <sstream>
using namespace std;
 
typedef long long LL;
#define lowbit(x) ((x)&(-x))
#define INF 0x3f3f3f3f
#define memset(a,b) memset(a,b,sizeof(a))
#defineGE() printf(">----------\n")
#defineIN() freopen("in.txt","r",stdin)
#defineOUT() freopen("out.txt","w",stdout)
const int mod=1e9+7;
const LL inf=0x3f3f3f3f3f3f3f3f;
const double pi=acos(-1.0);
const double eps=1e-8;
const int maxn=100005;
 
vector<int>G[maxn];
int dep[maxn], fa[maxn], siz[maxn];
void dfs(int x, int f){
   dep[x]=dep[f]+1;
   siz[x]=1;
   for (int i=0; i<G[x].size(); ++i) {
       int v=G[x][i];
       if (v==f) continue;
       dfs(v,x); fa[v]=x; siz[x]+=siz[v];
   }
}
int main(){
   int n, u, v;
   scanf("%d",&n);
   for (int i=1; i<n; ++i) scanf("%d%d",&u,&v), G[u].push_back(v), G[v].push_back(u);
   dfs(1,0);
   int x=(dep[n]-2)/2, p=n;
   for (int i=1; i<=x; ++i) p=fa[p];
   puts(n>(siz[p]<<1)?"Fennec":"Snuke");
   return 0;
}