Fennec VS. Snuke --AtCoder
2024-09-05 04:43:05
题目描述
Fennec and Snuke are playing a board game.
On the board, there are N cells numbered 1 through N, and N−1 roads, each connecting two cells. Cell ai is adjacent to Cell bi through the i-th road. Every cell can be reached from every other cell by repeatedly traveling to an adjacent cell. In terms of graph theory, the graph formed by the cells and the roads is a tree.
Initially, Cell 1 is painted black, and Cell N is painted white. The other cells are not yet colored. Fennec (who goes first) and Snuke (who goes second) alternately paint an uncolored cell. More specifically, each player performs the following action in her/his turn:
Fennec: selects an uncolored cell that is adjacent to a black cell, and paints it black.
Snuke: selects an uncolored cell that is adjacent to a white cell, and paints it white.
A player loses when she/he cannot paint a cell. Determine the winner of the game when Fennec and Snuke play optimally.
On the board, there are N cells numbered 1 through N, and N−1 roads, each connecting two cells. Cell ai is adjacent to Cell bi through the i-th road. Every cell can be reached from every other cell by repeatedly traveling to an adjacent cell. In terms of graph theory, the graph formed by the cells and the roads is a tree.
Initially, Cell 1 is painted black, and Cell N is painted white. The other cells are not yet colored. Fennec (who goes first) and Snuke (who goes second) alternately paint an uncolored cell. More specifically, each player performs the following action in her/his turn:
Fennec: selects an uncolored cell that is adjacent to a black cell, and paints it black.
Snuke: selects an uncolored cell that is adjacent to a white cell, and paints it white.
A player loses when she/he cannot paint a cell. Determine the winner of the game when Fennec and Snuke play optimally.
Constraints
2≤N≤105
1≤ai,bi≤N
The given graph is a tree.
输入
Input is given from Standard Input in the following format:
N
a1 b1
:
aN−1 bN−1
N
a1 b1
:
aN−1 bN−1
输出
If Fennec wins, print Fennec; if Snuke wins, print Snuke.
样例输入
7
3 6
1 2
3 1
7 4
5 7
1 4
样例输出
Fennec
分析:本题最优策略是尽量堵住对手,BFS扫到最后发现谁占据的节点多,谁就会赢。
#include <iostream>
#include <string>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#define range(i,a,b) for(int i=a;i<=b;++i)
#define LL long long
#define rerange(i,a,b) for(int i=a;i>=b;--i)
#define fill(arr,tmp) memset(arr,tmp,sizeof(arr))
using namespace std;
int n,x,y,col[],cnt[];
vector<int> map[];
void init(){
cin>>n;
range(i,,n-){
cin>>x>>y;
map[x].push_back(y);
map[y].push_back(x);
}
col[]=,col[n]=;
}
void solve(){
queue<int>q;
q.push(),q.push(n);
while(!q.empty()){
int head=q.front();
q.pop();
++cnt[col[head]];
range(i,,map[head].size()-){
int tmp=map[head][i];
if(col[tmp])continue;
col[tmp]=col[head];
q.push(tmp);
}
}
cout<<(cnt[]<cnt[]?"Fennec":"Snuke")<<endl;
}
int main() {
init();
solve();
return ;
}
最新文章
- C#图片处理常见方法性能比较
- POJ 2965 The Pilots Brothers&#39; refrigerator
- C# 从CIL代码了解委托,匿名方法,Lambda 表达式和闭包本质
- [C++] C/C++结构体的区别
- Python中的join()函数split()函数
- 针对ASP.NET页面实时进行GZIP压缩优化的几款压缩模块的使用简介及应用测试!(附源码)
- ajax连接池和XMLHttpRequest
- sql server日期时间转字符串(转)
- ubuntu 10.04 下 samba 服务的配置
- Bandwidth内存带宽測试工具
- Windows下用Composer安装Laravel步骤(集成php环境用phpStudy2016版本)
- HTTP错误代码大全
- JNI的使用总结初篇
- 刨根问底HTTP和WebSocket协议
- (PMP)第2章-----项目运行环境
- Linux(lamp安装)
- ELK学习笔记之F5利用ELK进行应用数据挖掘系列(1)-HTTP
- 判断用户 是用的电脑还是手机 判断 是安卓还是IOS
- 【Beta阶段】第二次Scrum Meeting!
- stl string 使用(转载)