正题

题目链接:https://www.luogu.com.cn/problem/P6499

题目大意

\(n\)个点的一棵树，开始有一个棋子在根处，开始先手选择一个点封锁，然后后手封锁棋子所在点然后移动一步到一个没有封锁的点，之后轮流进行。

先手不知道后手的移动，求先手有没有方法使得后手\(k\)步以内无法移动。

解题思路

后手无法走回头路所以要走到深度为\(k\)的节点，那么问题就变为了在\(k\)以内的每个深度选择一个节点切断，求能否使得树的深度不到达\(k\)。（显然第\(i\)步肯定是封锁深度为\(i\)的更优，因为如果选小于的后手已经跨过这个深度，选大的不如选它的父节点）。

然后n,k是400所以考虑状压dp。有一个结论就是如果\(n\leq k^2\)那么一定有解，因为如果\(n\leq k^2\)那么对于每个深度我们可以每次选择一个分叉的节点，然后去掉条路径一个没有分叉的边，这样每一次至少减少\(2k-1\)条边，然后深度(就是\(k\))减一，若干次以后就是\(k^2\)了。

这样就能把\(k\)缩到\(\sqrt n\)的复杂度，考虑状压。先在可能封锁的点上跑一个\(dfs\)序，然后设\(f_{i,s}\)表示目前决策到第\(dfn_i\)个点，每个深度被选择的情况为\(s\)是否合法。

然后如果选择一个点就直接跳到\(dfs\)序上该节点的子树末尾\(+1\)。然后强制选叶子就好了。

时间复杂度\(O(n2^{min\{k,\sqrt n\}})\)

code

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=410;

struct node{

    int to,next;

}a[N<<1];

int n,k,tot,cnt,ls[N],dep[N],dfn[N],ed[N];

bool mark[N],f[N][1<<20];

void addl(int x,int y){

    a[++tot].to=y;

    a[tot].next=ls[x];

    ls[x]=tot;return;

}

bool dfs(int x,int fa){

    dep[x]=dep[fa]+1;

    if(dep[x]+1==k)return mark[x]=1;

    for(int i=ls[x];i;i=a[i].next){

        int y=a[i].to;

        if(y==fa)continue;

        mark[x]|=dfs(y,x);

    }

    return mark[x];

}

void dfc(int x,int fa){

    if(!mark[x])return;dfn[cnt++]=x;

    for(int i=ls[x];i;i=a[i].next){

        int y=a[i].to;

        if(y==fa)continue;

        dfc(y,x);

    }

    ed[x]=cnt;return;

}

int main()

{

    scanf("%d%d",&n,&k);

    if(n<=k*k)return puts("DA")&0;

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

        int x,y;

        scanf("%d%d",&x,&y);

        addl(x,y);addl(y,x);

    }

    dep[0]=-2;dfs(1,0);dfc(1,0);

    int MS=(1<<k);f[1][0]=1;

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

        int x=dfn[i];

        for(int s=0;s<MS;s++){

            if(dep[x]!=k-1)f[i+1][s]|=f[i][s];

            if(!((s>>dep[x])&1))

                f[ed[x]][s|(1<<dep[x])]|=f[i][s];

        }

    }

    bool ans=0;

    for(int s=0;s<MS;s++)

        ans|=f[cnt][s];

    puts(ans?"DA":"NE");

    return 0;

}

巴特西

P6499-[COCI2016-2017#2]Burza【状压dp】

正题

题目大意

解题思路

code

最新文章

热门文章