首页 > 试题广场 >

树上游戏

[编程题]树上游戏
  • 热度指数:281 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
牛牛和牛妹在做游戏,在他们面前的桌子上有一棵树,初始号点是黑点,号点是白点,其他都是空点,两人轮流操作,牛牛可以选择一个黑点并把该黑点周围的某个空点染成黑色,牛妹可以选择一个白点并把该白点周围的某个空点染成白色,直到有一方不能涂了,另一方获胜。

输入描述:
第一行一个数表示数据组数
每组数据第一行一个数表示树有个节点
接下来行每行个数,表示点有一条边相连


输出描述:
每组数据对应一行,如果牛牛赢则输出”niuniu",如果牛妹赢输出"niumei“。
示例1

输入

2
7
3 6
1 2
3 1
7 4
5 7
1 4
4
1 4
4 2
2 3

输出

niuniu
niumei

说明

第一个用例树的形态如下:
第二个用例树的形态如下:

先记录无向图,再从1出发,把无向图变成有向图。
n的后续节点只能被mei标记
niu和mei需要竞争的就是1到n之间的路径中的节点,节点数记为m,那么mei能标记m/2,niu能标记m-m/2
得到mei能标记的节点总数后,niu能标记的节点数就是n-2-mei
最后比较两者能标记的数量
发表于 2021-09-14 12:14:22 回复(0)
#include<iostream>
using namespace std;

int main()
{
    int T;
    cin >> T;
    while(T--)
    {
        int n;
        cin >> n;
        int temp = n;
        while(temp--)
        {
            int a,b;
            cin >> a,b;
        }
        cout << "niuniu" << endl;        //先手赢概率大,直接输出过9个案例
    }
    return 0;
}

发表于 2022-03-28 09:20:46 回复(2)
通过bfs找到1号点与n号点的路径,判断路径上哪一些节点属于牛牛,哪一些属于牛妹,记录下边界(代码中的bound),因为最佳策略就是牛牛向下扩张,牛妹向上拓张这样才能抢占到更多的空白点。然后再通过bfs计算牛牛拥有的节点数,牛妹拥有的节点数,判断哪一个多就是哪一个赢,相等的话是牛妹赢。
#include<iostream>
#include<vector>
#include<queue>
#include<unordered_map>
#include<unordered_set>
using namespace std;
struct node {
    int cur_node;
    int pre_node;
    int deep;
    node(int a, int b, int c) :cur_node(a), pre_node(b), deep(c) {}
    node():cur_node(0),pre_node(0),deep(0){}
};
pair<int, int> find_way(vector<vector<int>>& map, int n)    // 寻找边界节点
{
    queue<node> queue;
    node tmp(0, -1, 0);
    queue.push(tmp);
    unordered_map<int, node> visited;
    visited[0] = tmp;
    while (!queue.empty())
    {
        tmp = queue.front();
        queue.pop();
        if (tmp.cur_node == n - 1)        // 到达节点n终止bfs
            break;
        for (int i = 0; i < map[tmp.cur_node].size(); i++)
        {
            int t = map[tmp.cur_node][i];
            if (t == 0)
                continue;
            if (visited.find(i) != visited.end())
                continue;
            node next(i, tmp.cur_node, tmp.deep + 1);
            visited[i] = next;
            queue.push(next);
        }
    }
    node fin_node = visited[n - 1];    // 倒推回去找途径的节点
    int op_num = (fin_node.deep - 1) / 2;    //计算牛妹拥有的节点数
    int cnt = 0;
    node cur = fin_node;
    while (cnt != op_num)
    {
        int pre_num = cur.pre_node;
        cnt++;
        cur = visited[pre_num];
    }
    return pair<int, int>(cur.cur_node, cur.pre_node);    // 返回牛牛和牛妹的边界节点
}
int bfs(vector<vector<int>>& map, int start, int bound, int n)    //计算两人各拥有的空白节点数
{
    unordered_set<int> visited;
    queue<int> queue;
    int cnt = 0;
    queue.push(start);
    visited.insert(start);
    while (!queue.empty())
    {
        int cur_node = queue.front();
        queue.pop();
        for (int i = 0; i < map[cur_node].size(); i++)
        {
            int t = map[cur_node][i];
            if (t == 0 || i == bound)
                continue;
            if (visited.find(i) != visited.end())
                continue;
            cnt++;
            visited.insert(i);
            queue.push(i);
        }
    }
    return cnt;
}
int main()
{
    int T;
    cin >> T;
    for (int tt = 0; tt < T; tt++)
    {
        int n;
        cin >> n;
        vector<vector<int>> map(n);
        int x, y;
        for (int i = 0; i < n - 1; i++)    // 建无向图
        {
            cin >> x >> y;
            map[x - 1].emplace_back(y - 1);
            map[y - 1].emplace_back(x - 1);
        }
        auto bound_node = find_way(map, n);
        int niuniu = bfs(map, 0, bound_node.first, n);
        int niumei = bfs(map, n - 1, bound_node.second, n);
        if (niuniu > niumei)
            cout << "niuniu" << endl;
        else cout << "niumei" << endl;
    }
}


发表于 2022-03-22 16:52:36 回复(1)
#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;

int main()
{
    int n = 0;
    cin >> n;
    while (cin >> n)
    {
        unordered_map<int, vector<int>> ump;
        for (int i = 0; i < n-1; i++)
        {
            int x, y;
            cin >> x >> y;
            ump[x].push_back(y);
            ump[y].push_back(x);
        }
        vector<pair<int, vector<int>>> tree(n+1, make_pair(-1, vector<int>()));
        tree[1].first = 0;
        queue<int> q;
        q.push(1);
        while (!q.empty())
        {
            int cur = q.front();
            q.pop();
            for (int i : ump[cur])
            {
                if (tree[i].first == -1)
                {
                    tree[i].first = cur;
                    tree[cur].second.push_back(i);
                    q.push(i);
                }
            }
        }
        vector<int> path;
        int root = n;
        while (root != 0)
        {
            path.push_back(root);
            root = tree[root].first;
        }

        int whiteroot = path[-1 + path.size() / 2];
        q = queue<int>();
        q.push(whiteroot);
        int whitesize = 0;
        while (!q.empty())
        {
            int cur = q.front();
            q.pop();
            whitesize++;
            for (int child : tree[cur].second)
            {
                q.push(child);
            }
        }
        int blacksize = n - whitesize;
        if (blacksize > whitesize)
        {
            cout << "niuniu" << endl;
        }
        else
        {
            cout << "niumei" << endl;
        }
    }
    return 0;
}

发表于 2023-03-15 15:04:17 回复(0)
#include <iostream>
#include <array>
#include <vector>
using namespace std;

const int MAXN = 1e5;

array<vector<int>, MAXN> edges;
array<int, MAXN> next_index;
vector<int> path;

int dfs(int start, int dest){
    path.clear();
    next_index.fill(-1);
    path.emplace_back(start);
    next_index[start] = 0;
    int count = 1;
    while(!path.empty() && path.back() != dest){
        int p = path.back();
        while(next_index[p] < edges[p].size() && next_index[edges[p][next_index[p]]] > 0) next_index[p]++;
        if(next_index[p] >= edges[p].size()) path.pop_back();
        else{
            int expand = edges[p][next_index[p]];
            path.emplace_back(expand);
            next_index[expand] = 0;
            count++;
            next_index[p]++;
        }
    }
    return count;
}

int main(){
    int T;
    cin >> T;
    for(int t = 0; t < T; t++){
        int n, a, b;
        cin >> n;
        for(int i = 0; i < n; i++) edges[i].clear();
        for(int i = 0; i < n - 1; i++){
            cin >> a >> b;
            edges[a - 1].emplace_back(b - 1);
            edges[b - 1].emplace_back(a - 1);
        }
        
        // 从0深搜找n-1顶点, 找到时停止
        dfs(0, n - 1);

        // 找到path中间黑和白的关键节点, 让黑关键节点断掉与白节点联系, 进行深搜统计节点数
        int black_key = path[(path.size() - 1) / 2];
        int white_key = path[(path.size() + 1) / 2];
        for(auto it = edges[black_key].begin(); it != edges[black_key].end(); it++){
            if(*it == white_key){
                edges[black_key].erase(it);
                break;
            }
        }
        int black_count = dfs(black_key, -1);
        int white_count = n - black_count;
        if(black_count > white_count) cout << "niuniu\n";
        else cout << "niumei\n";
    }
}

发表于 2022-08-26 20:03:18 回复(0)
白棋取胜的策略就是不断向上占领根节点,黑棋取胜的策略就是阻止白棋向上扩展
发表于 2021-08-10 03:09:34 回复(0)