题解 P3942 将军令

题解

首先看到这题 \(k=1\) 时，就是一道小胖守皇宫，那么由 \(k=1\) 联想到 \(k=2...20\) 发现可以树形 \(DP\)

但转移方程太难想，不太适合考场做。

考虑贪心：

对所有节点先按深度由大到小排序，对于每一个未覆盖的节点，我们选择他的第 \(k\) 级祖先。

证明：

对于一个节点，我们选他的第 \(k\) 级祖先，这样布置可以覆盖最大的范围，同时因为我们是按深度在搜，所以这样决策无后效性。

对于按深度排序，可以先 \(dfs\) 再排，后直接一个 \(bfs\)

Code:

#include<bits/stdc++.h>

#define ri register signed

#define p(i) ++i

using namespace std;

namespace IO{

    char buf[1<<21],*p1=buf,*p2=buf;

    #define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++

    template<typename T>inline void read(T &x) {

        ri f=1;x=0;char ch=gc();

        while(ch<'0'||ch>'9') {if (ch=='-') f=0;ch=gc();}

        while(ch>='0'&&ch<='9') {x=(x<<1)+(x<<3)+(ch^48);ch=gc();}

        x=f?x:-x;

    }

}

using IO::read;

namespace nanfeng{

    #define cmax(x,y) ((x)>(y)?(x):(y))

    #define cmin(x,y) ((x)>(y)?(y):(x))

    #define FI FILE *IN

    #define FO FILE *OUT

    static const int N=1e5+7;

    int que[N],first[N],vis[N],fa[N],dep[N],t=1,n,k,tt,ans;

    struct edge{int v,nxt;}e[N<<1];

    inline void add(int u,int v) {

        e[t].v=v;

        e[t].nxt=first[u];

        first[u]=t++;

    }

    inline void bfs() {

        int hd=1,tl=0,tot=0;

        que[p(tl)]=1;

        while(hd<=tl) {

            int x=que[hd++];

            dep[p(tot)]=x;

            for (ri i(first[x]),v;i;i=e[i].nxt) {

                if (fa[v=e[i].v]||v==1) continue;

                fa[que[p(tl)]=e[i].v]=x;

            }

        }

    }

    void dfs(int x,int fa,int dis){

        vis[x]=1;

        if (dis==k) return;

        for (ri i(first[x]),v;i;i=e[i].nxt) if ((v=e[i].v)!=fa) dfs(v,x,dis+1);

    }

    inline int find(int x) {

        for (ri i(1);i<=k;p(i)) {

            x=fa[x];

            if (!x) return 1;

        }

        return x;

    }

    inline int main() {

        // FI=freopen("nanfeng.in","r",stdin);

        // FO=freopen("nanfeng.out","w",stdout);

        read(n),read(k),read(tt);

        for (ri i(1);i<n;p(i)) {

            int u,v;read(u),read(v);

            add(u,v);add(v,u);

        }

        bfs();

        for (ri i(n);i;--i) {

            if (vis[dep[i]]) continue;

            p(ans);

            int f=find(dep[i]);

            dfs(f,0,0);

        }

        printf("%d\n",ans);

        return 0;

    }

}

int main() {return nanfeng::main();}

巴特西

题解 P3942 将军令

题解

最新文章

热门文章