洛谷P1084 疫情控制 [noip2012] 贪心+树论+二分答案 (还有个小bugQAQ

时间：2023-03-09 05:44:05
洛谷P1084 疫情控制 [noip2012] 贪心+树论+二分答案 (还有个小bugQAQ

正解:贪心+倍增+二分答案

解题报告:

正好想做noip的题目然后又想落实学长之前讲的题?于是就找上了这题

其实之前做过,70,然后实在细节太多太复杂就不了了之,现在再看一遍感觉又一脸懵了...

从标签就可以发现是个很麻烦考虑的点很多的问题,所以分开按步骤梳理我觉得应该会好些qwq

帕1,贪心

首先最最基本的思想要想到趴?就是贪心,就是,如果我不能跑到首都,我肯定是尽量往上跑;然后如果能跑到首都就先跑到首都再想怎么分配

帕2,倍增

已经发现是要往上提了,自然考虑倍增,于是写个函数预处理掉倍增这事儿

void dfs1(int u,int fafa)
{
    for(int i=head[u];i;i=edge[i].next)
        ]=u;d[edge[i].to][]=edge[i].wei;dis[edge[i].to]=dis[u]+edge[i].wei;dfs1(edge[i].to,u);}
}
inline void pre()
{
    dfs1(,);
    rp(i,,)
        rp(j,,n)fa[j][i]=fa[fa[j][i-]][i-],d[j][i]=d[j][i-]+d[fa[j][i-]][i-];
}
//分了俩段,结构更好看qwq

这是代码

帕3,二分

可以发现这个显然是个能二分的自然是想到二分

于是就写个check函数

然后这题就结束了

不存在的这题最麻烦的地方就在这个check函数趴?

然后接下来几个帕都是港这个check函数

关于check函数:

帕1,上提

通过之前预处理出的倍增往上走就是了

inline int stp(int u,int lim)
{my(i,,)if(fa[u][i] && d[u][i]<=lim)lim-=d[u];[i],u=fa[u][i];return u;}
//lim:二分的那个时间

这还是代码

帕2,判断是否到首都

如果没到首都就让它呆哪儿,到了首都登记下它还能走多久

rp(i,,m)
{
    int upup=stp(arm[i],limit);
    )vis[upup]=;
    else army[++cnt].sid=ff[i],army[cnt].tim=limit-dis[arm[i]];
}
//判断:如果不能到就停哪儿,能到就登记下(就像之前贪心所说

这又是代码

帕3,处理首都的亲崽有几个还没驻扎

再写个函数,判断有几个崽没被驻扎,登记下来(如果都被驻扎了就可以直接GG了退出掉

(对了我登记那儿忘复制来了但是又懒得编辑了就这样,自己去整个程序里看就是了,就在dfs后面qwq

void dfs2(int u)
{
    ,orzgoldgenius=;
    for(int i=head[u];i;i=edge[i].next)
    {
        ])
        {
            orzgoldgenius=;
            dfs2(edge[i].to);
            ;
        }
    }
    vis[u]=orzcjk&orzgoldgenius;
}
dfs2();

这双是代码

帕4,分配

把登记了的到了首都的发配给没有被驻扎的崽子们那儿去(关于这里的处理似乎有争议啊...等下港qwq   争议被抹掉了没有争议

不过关于分配细节挺多的要注意下嗷

        sort(army+,army+cnt+);sort(ned+,ned+cjk+,cmp);
    rp(i,,cjk)
    {
        if(!vis[ned[i]])
        {
            )return false;
            )
            {
                if(army[now].tim<dis[ned[i]] && now!=cnt)
                {
                    vis[army[now].sid]=true;
                    if(ned[i]==army[now].sid)break;
                    ++now;
                }
                else
                {
                    if(now==cnt)break;
                    if(army[now].sid!=ned[i] && (!vis[army[now].sid]))
                    {
                        vis[army[now].sid]=true;
                        ++now;
                    }
                    else break;
                }
            }
            if(now==cnt)if(army[now].tim<dis[ned[i]] && army[now].sid!=ned[i])return false;
            vis[ned[i]]=true;++now;
        }
    }
    return true;

这叒是代码

然后就真滴讲完辽,二分什么的太套路了懒得放

最后放程序

overrrr

#include<bits/stdc++.h>
using namespace std;
#define rp(i,x,y) for(register int i=x;i<=y;++i)
#define my(i,x,y) for(register int i=x;i>=y;--i)
#define mp make_pair
#define pi pair<int,int>

,M=;
,fa[N][],d[N][],dis[N],ned[N],ff[N];
struct ed{int to,next,wei;}edge[M];
struct alive{int sid,tim;}army[N];
bool vis[N];
bool operator <(alive x,alive y){return x.tim<y.tim;}

inline int read()
{
    ;;
    '))ch=getchar();
    ;
    )+(x<<)+(ch^'),ch=getchar();
    return y?x:-x;
}
inline void add(int x,int y,int z){edge[++tot].to=y;edge[tot].next=head[x];edge[tot].wei=z;head[x]=tot;}
void dfs1(int u,int fafa)
{
    for(int i=head[u];i;i=edge[i].next)
        ]=u;d[edge[i].to][]=edge[i].wei;dis[edge[i].to]=dis[u]+edge[i].wei;dfs1(edge[i].to,u);}
}
void dfs2(int u)
{
    ,orzgoldgenius=;
    for(int i=head[u];i;i=edge[i].next)
    {
        ])
        {
            orzgoldgenius=;
            dfs2(edge[i].to);
            ;
        }
    }
    vis[u]=orzcjk&orzgoldgenius;
}
inline void pre()
{
    dfs1(,);
    rp(i,,)
        rp(j,,n)fa[j][i]=fa[fa[j][i-]][i-],d[j][i]=d[j][i-]+d[fa[j][i-]][i-];
}
inline ,)if(fa[u][i] && d[u][i]<=lim)lim-=d[u][i],u=fa[u][i];return u;}
inline bool cmp(int x,int y){return dis[x]<dis[y];}
bool jud(int limit)
{
    ;memset(vis,,sizeof(vis));
    rp(i,,m)
    {
        int upup=stp(arm[i],limit);
        )vis[upup]=;
        else army[++cnt].sid=ff[i],army[cnt].tim=limit-dis[arm[i]];
    }
    dfs2();
    ,now=;
    ];i;i=edge[i].next)if(!vis[edge[i].to])ned[++cjk]=edge[i].to;
    sort(army+,army+cnt+);sort(ned+,ned+cjk+,cmp);
    rp(i,,cjk)
    {
        if(!vis[ned[i]])
        {
            )return false;
            )
            {
                if(army[now].tim<dis[ned[i]] && now!=cnt)
                {
                    vis[army[now].sid]=true;
                    if(ned[i]==army[now].sid)break;
                    ++now;
                }
                else
                {
                    if(now==cnt)break;
                    if(army[now].sid!=ned[i] && (!vis[army[now].sid]))
                    {
                        vis[army[now].sid]=true;
                        ++now;
                    }
                    else break;
                }
            }
            if(now==cnt)if(army[now].tim<dis[ned[i]] && army[now].sid!=ned[i])return false;
            vis[ned[i]]=true;++now;
        }
    }
    return true;
}
inline ,))x=fa[x][i];return x;}

int main()
{
    n=read();rp(i,,n-){int t1=read(),t2=read(),t3=read();add(t1,t2,t3);add(t2,t1,t3);}
    pre();
    m=read();rp(i,,m)arm[i]=read(),ff[i]=getf(arm[i]);
    while(l<=r)
    {
        ;
        ;
        ;
        }
    !=l)printf("%d\n",l);
    else printf("-1\n");
    ;
}

这,依然是代码(...我是不是有点无聊啊233333333

啊森气！我重载运算符的时候把'<'重载成'>'了,然后调了一晚上...最近效率太太太低了我都想扇自己耳巴子了...

upd:18/11/03

　　总算A了?但是有个事儿我真的没懂...这样的,就是我想剪一波枝?然后我就想着鸭,如果我一个城市读入了很多次其实我是不用重复算的对趴,然后如果一个城市的爹的祖宗已经读入了我也不用重复算了它的爹了直接返回ff[i]就成了对趴?

　　　　　　哇我觉得这个思路真实好到爆炸了?然后我就成功90了?然后我删了那个剪枝就A了?

　　　　　　什么鬼啊你家祖宗还带变的嘛???什么玩意儿啊...实力哭爆了...我我我我调了半小时就因为这玩意儿?

　　　　　　哦我还发现我最近经常调试调很久,,,代码半小时debug三天就是我了:(

再放个辛酸的提交记录  不放了,蓝瘦

所以到底为什么会这样啊???我觉得我这波剪枝不可能错啊???什么鬼嘛QAQ