資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告