A simple Blog for wyx I've been down the bottle hoping.
BZOJ3722【PA2014】Budowa 博弈 树形dp
发表于: | 分类: Oi | 评论:0 | 阅读:128

因为一个傻逼问题我花了一个下午在这道题上…………

首先就是去掉所有为0的点,剩下的点就能判断答案是 $Tak$ 还是 $Nie$

原因是所有的点都有奇数个儿子,两个人轮流放之后结果就是不变的

对于$n^2$算法,直接枚举每个为$0$的点然后暴力判断就行了

对于 $O(n)$ 算法,你可以算一下他有几个儿子选-2,几个选-1

然后你用-2的个数减去-1的个数,判断一下这个东西

如果>0显然不需要再放了

如果$=0$我们再放一个就行了

如果$=-1$,由于第一个人呢先放所以可以把这个树从$-1$改成$0$

这样虽然对于他没什么贡献,但是为他的父亲创造了一个机会,他的父亲的$-1$的个数减了一个

你需要找到若干条根到叶子的路径满足除了叶子刚才的那个差不是-1就是0

然后就是傻逼树形$dp$了

注意在判断格式问题的时候别忘了可能一个数字都没有,然后结果第二行输出0就行了

#include <stdio.h>
#include <iostream>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6+5;
const int M = N << 1;

int head[N];

inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

struct graph{
    int next,to;
    graph () {}
    graph (int _next,int _to)
    :next(_next),to(_to){}
}edge[M];

inline void add(int x,int y) {
    static int cnt = 0;
    edge[++cnt] = graph(head[x],y); head[x] = cnt;
    edge[++cnt] = graph(head[y],x); head[y] = cnt;
}

int col[N], stack[N], top, c[N];
bool vis[N];

inline int DFS(int x,int fa) {
    if(col[x] > 0) c[x] = 0;
    else if(col[x] == -1) return (c[x] = -1);
        else if(col[x] == -2) return (c[x] = 1);
        else return c[x];
    for(int i=head[x];i;i=edge[i].next) {
        if(edge[i].to != fa) {
            c[x] += DFS(edge[i].to,x);
        }
    }
    if(c[x] < 0) c[x] = -1;
    if(c[x] > 0) c[x] = 1;
    return c[x];
}

inline void DFS2(int x,int fa) {
    bool flag = false;
    int sum = 0;
    for(int i=head[x];i;i=edge[i].next) {
        if(edge[i].to != fa) {
            sum += c[edge[i].to];
            DFS2(edge[i].to,x);
            flag = 1;
        }
    }
    if(!flag) return;
    if(sum == 0 || sum == -1) vis[x] = 1;
}

inline void DFS3(int x,int fa) {
    bool flag = false;
    for(int i=head[x];i;i=edge[i].next) {
        if(edge[i].to != fa ) 
            if(vis[edge[i].to] || c[edge[i].to] == 0){
            DFS3(edge[i].to, x); flag = 1;
        } 
    }
    if(!flag && c[x] == 0) stack[++top] = x;
}

int main() {freopen("battle.in","r",stdin); freopen("battle.out","w",stdout);
    int n = read();
    for(int i=1;i<=n;++i) {
        col[i] = read();
        for(int j=1;j<=col[i];++j) add(i,read());
    }
    DFS(1,-1);
    if(c[1] == 1)  {
        for(int i=1;i<=n;++i) if(col[i] == 0) stack[++top] = i;
        printf("TAK %d\n", top);
        for(int i=1;i<top;++i) printf("%d ",stack[i]);
        if(top) cout << stack[top] << endl;
        return 0;
    }
    if(c[1] == -1) {
        puts("NIE");
        return 0;
    }
    DFS2(1,-1);
    DFS3(1,-1);
    sort(stack+1,stack+top+1);
    printf("TAK %d\n", top);
    for(int i=1;i<top;++i) printf("%d ",stack[i]);
    if(top) cout << stack[top] << endl;
}
Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP