题目描述
B B B 经常与 A A A 一起玩游戏。今天,他们在一棵树上玩游戏。 A A A 有 m 1 m1 m1 块石子, B B B 有 m 2 m2 m2 块石子,游戏一开始,所有石头放在树的节点处,除了树根。
A A A 先移动石子。然后两人轮流移动,每次移动只能选择自己的一个石子,而且只能从当前位置移到父亲节点处,游戏过程中允许一个节点处放多个石子。
谁先把自己所有的石子移到树根处谁就失败了,假设两人都是非常聪明,游戏过程中都使用最优策略,给定石子起始位置,要你计算出谁是赢家。
为了简化题目,假设树根为 0 0 0。
输入格式
输入包含多组测试数据。
第一行输入
T
T
T 表示测试数据组数。
接下来每组测试数据第一行输入
3
3
3 个整数
n
n
n,
m
1
m1
m1,
m
2
m2
m2,
n
n
n 为树的节点个数。
接下来
n
−
1
n - 1
n−1 行,每行包含两个整数
x
,
y
x,y
x,y
(
0
≤
x
,
y
<
n
)
(0 \le x, y < n)
(0≤x,y<n),表示树中有一条边连接
x
x
x 和
y
y
y。
接下来
m
1
m1
m1 行,每行一个整数,表示
A
A
A 的石子的位置。
接下来
m
2
m2
m2 行,每行一个整数,表示
B
B
B 的石子的位置。
输出格式
对于每组数据,输出 A A A 或 B B B 表示 A A A 或 B B B 赢了。
数据范围
对于
30
%
30\%
30% 的数据,
1
≤
n
≤
10
1 \le n \le 10
1≤n≤10,
1
≤
m
1
,
m
2
≤
n
1 \le m1, m2 \le n
1≤m1,m2≤n。
对于
100
%
100\%
100% 的数据,
1
≤
n
≤
1
0
4
1 \le n \le 10^4
1≤n≤104,
1
≤
m
1
,
m
2
≤
1
0
4
1 \le m1,m2 \le 10^4
1≤m1,m2≤104。
样例
输入:
2
3 1 1
0 1
2 0
1
2
3 2 1
0 1
1 2
2 2
2
输出:
B
A
思路
首先一眼看上去,似乎是个博弈题,但其实只是简单的树。
石子只能移到其根节点,且根节点只有一个,因此每个石子移到根节点的距离就能求出来。
将
A
A
A 和
B
B
B 的每个石子离根节点的距离求出来相加,进行比较。
A A A 为先手,只有 s u m A > s u m B sum_A > sum_B sumA>sumB 时, A A A 才能赢,否则 B B B 赢。
比如 s u m A = s u m B = 1 sum_A = sum_B = 1 sumA=sumB=1, A A A 先走, B B B 再走, A A A 就不能走了, B B B 赢。
代码
#include<bits/stdc++.h>
using namespace std;
int T;
int n, m1, m2;
int dep[100010];//深度
int a[100010], b[100010];
vector<int> v[100010];//图
//x:当前节点 y:父亲节点 z:当前节点深度
void dfs(int x, int y, int z){
dep[x] = z;
for(auto i : v[x]){
if(i == y){//父亲
continue;
}
dfs(i, x, z + 1);
}
}
int main(){
scanf("%d", &T);
while(T --){
//多组数据清空
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
memset(dep, 0, sizeof(dep));
scanf("%d %d %d", &n, &m1, &m2);
for(int i = 1; i < n; ++ i){
int x, y;
scanf("%d %d", &x, &y);
v[x].push_back(y);
v[y].push_back(x);
}
//将 a和b 每个位置的石子个数统计出来,方便以后计算
for(int i = 1; i <= m1; ++ i){
int x;
scanf("%d", &x);
a[x] ++;
}
for(int i = 1; i <= m2; ++ i){
int x;
scanf("%d", &x);
b[x] ++;
}
//dfs 计算每个节点的深度
dfs(0, -1, 0);
int sum1 = 0, sum2 = 0;
for(int i = 1; i <= n; ++ i){
sum1 += a[i] * dep[i];
}
for(int i = 1; i <= n; ++ i){
sum2 += b[i] * dep[i];
}
if(sum1 > sum2){
printf("A\n");
}
else{
printf("B\n");
}
//v 在清空时注意要把 0 清了
for(int i = 0; i <= n; ++ i){
v[i].clear();
}
}
return 0;
}
本站资源均来自互联网,仅供研究学习,禁止违法使用和商用,产生法律纠纷本站概不负责!如果侵犯了您的权益请与我们联系!
转载请注明出处: 免费源码网-免费的源码资源网站 » [图论]游戏
发表评论 取消回复