数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物
数学
英语
经济学
心理学
社会学
时尚学
法学C++ 程序，找出单元着色游戏获胜者
假设有两个数组 A 和 B，每个数组都有 N 个元素。假设 Amal 和 Bimal 在一个棋盘上进行游戏，棋盘的单元格编号从 1 到 N，有 N-1 条路。道路连接两个单元格。所以，第 i 条道路连接 A[i] 和 B[i]。可以通过多次移动到相邻单元格，从每个单元格到达其他每个单元格。初始时，第 1 个单元格标为黑色，第 N 个单元格标为白色。其他单元格没有颜色。Amal 先玩，他们交替进行。Amal 选择一个与黑色单元格相邻的未着色单元格，并将其涂成黑色。Bimal 选择一个与白色单元格相邻的未着色单元格，并将其涂成白色。如果玩家无法涂色一个单元格，则该玩家失败。我们必须找到获胜者。
因此，如果输入是 A = [3, 1, 3, 7, 5, 1]；B = [6, 2, 1, 4, 7, 4]，则输出将是 Amal，因为如果 Amal 先将单元格 2 涂成黑色，无论 Bimal 如何移动，他都会获胜。
步骤
要解决这个问题，我们将遵循以下步骤：
N := 99999 Define one adjacency list adjList Define three large arrays p, d, and ssz Define a function dfs(), this will take nd, par, dep, p[nd] := par d[nd] := dep ssz[nd] := 1 for each node i in adjList[nd], do if i XOR par is non-zero, then: dfs(i, nd, dep + 1) ssz[nd] := ssz[nd] + ssz[i] From the main method, do the following: n := size of A for initialize i := 1, when i < n, update (increase i by 1), do: u := A[i - 1], v := B[i - 1] insert v at the end of adjList[u] insert u at the end of adjList[v] dfs(1, 1, 0) nd := n for initialize i := 0, when i < (d[n] - 1) / 2, update (increase i by 1), do: nd := p[nd] return if 2 * ssz[nd] >= n, then "Bimal", otherwise "Amal"
示例
让我们看看以下实现以更好地理解 -
#include <bits/stdc++.h>
using namespace std;
int N = 99999;
vector<vector<int>> adjList(N);
vector<int> p(N), d(N), ssz(N);
void dfs(int nd, int par, int dep){
p[nd] = par;
d[nd] = dep;
ssz[nd] = 1;
for (int i : adjList[nd]){
if (i ^ par){
dfs(i, nd, dep + 1);
ssz[nd] += ssz[i];
}
}
}
string solve(vector<int> A, vector<int> B){
int n = A.size();
for (int i = 1; i < n; i++){
int u = A[i - 1], v = B[i - 1];
adjList[u].push_back(v);
adjList[v].push_back(u);
}
dfs(1, 1, 0);
int nd = n;
for (int i = 0; i < (d[n] - 1) / 2; i++)
nd = p[nd];
return (2 * ssz[nd] >= n ? "Bimal" : "Amal");
}
int main(){
vector<int> A = { 3, 1, 3, 7, 5, 1 };
vector<int> B = { 6, 2, 1, 4, 7, 4 };
cout << solve(A, B) << endl;
}输入
{ 3, 1, 3, 7, 5, 1 }, { 6, 2, 1, 4, 7, 4 }输出
Amal
更新于： 2022-03-03
496 次浏览
广告