HDU 5379 Mahjong tree

题意：在一棵有n个节点的树上放编号从1到n的麻将，要求每个点的儿子节点之间的编号连续，每棵子树内的编号连续。

解法：手推一组样例之后就可以得到如下结论然后从根节点一边讨论一边搜就好了。

当一个节点只有一个儿子的时候，如果儿子是叶子节点则只有一种放法，如果儿子不是叶子节点则有两种放法。

当一个节点有两个儿子的时候，一定有两种放法。

当一个儿子有三个儿子及以上的时候，假设有k个儿子，如果非叶子节点m的个数为0则有k!种放法，如果m为1，则有2 × (k - 1)!种放法，如果m为2，则有2 × (k - 2)!种放法，如果m > 2则不存在合法情况。

将所有情况相乘即为答案。

代码：

代码是队友写的……这么鬼畜的变量名才不是我起的呢233

哦对了……要手动扩栈不然会RE

#pragma comment(linker, "/STACK:102400000,102400000")

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <set>

#include <map>

#include <vector>

#include <limits.h>

using namespace std;

typedef long long LL;

#define MAXN 100010//1e5

const LL mod = (LL)1e9 + 7;

int t, n, cas;

vector<int> edge[MAXN];

bool vis[MAXN];

LL ans;

LL A[MAXN];

void init() {

    for(int i = 0; i <= n; i++) {

        edge[i].clear();

    }

    edge[0].push_back(1);

    edge[1].push_back(0);

    memset(vis, false, sizeof vis);

    vis[0] = true;

    ans = 1LL;

}

void DFS(int u) {

    int len = edge[u].size();

    if((len == 1 && u != 0) || ans == 0LL) return ;

    if(len - 1 == 1 || u == 0) {

        for(int i = 0; i < len; i++) {

            int v = edge[u][i];

            if(!vis[v]) {

                if(edge[v].size() - 1 > 0) {

                    ans = (ans * 2LL) % mod;

                    vis[v] = true;

                    if(ans == 0LL) return;

                    DFS(v);

                }

            }

        }

    } else if(len - 1 == 2) {

        ans = (ans * 2LL) % mod;

        for(int i = 0; i < len; i++) {

            int v = edge[u][i];

            if(vis[v]) continue;

            vis[v] = true;

            if(ans == 0LL) return;

            DFS(v);

        }

    } else if(len - 1 >= 3) {

        vector<int> son;

        int cnt = 0;

        int dayu0 = 0;

        for(int i = 0; i < len; i++) {

            int v = edge[u][i];

            if(vis[v]) continue;

            son.push_back(v);

            if(edge[v].size() - 1 > 0) dayu0++;

        }

        cnt = son.size();

        if(dayu0 == 0) {

            ans = (ans * A[cnt]) % mod;

        } else if(dayu0 == 1) {

            ans = (ans * 2LL) % mod;

            ans = (ans * A[cnt - 1]) % mod;

        } else if(dayu0 == 2) {

            ans = (ans * 2LL) % mod;

            ans = (ans * A[cnt - 2]) % mod;

        } else {

            ans = 0LL; return ;

        }

        for(int i = 0; i < cnt; i++) {

            int v = son[i];

            vis[v] = true;

            if(ans == 0LL) return ;

            DFS(v);

        }

    }

}

int main() {

    scanf("%d", &t);

    A[1] = 1LL;

    for(LL i = 2; i <= 100000LL; i++) {

        A[i] = A[i - 1] * i % mod;

    }

    while(t--) {

        scanf("%d", &n);

        init();

        int u, v;

        for(int i = 0; i < n - 1; i++) {

            scanf("%d%d", &u, &v);

            edge[u].push_back(v);

            edge[v].push_back(u);

        }

        DFS(0);

        printf("Case #%d: %I64d\n", ++cas, ans);

    }

    return 0;

}

巴特西

HDU 5379 Mahjong tree

最新文章

热门文章