BZOJ3028:食物 生成函数
BZOJ3174:[Tjoi2013]拯救小矮人 贪心+dp

BZOJ2799:[Poi2012]Salaries 贪心

shinbokuow posted @ Jan 23, 2015 03:54:24 PM in BZOJ with tags 贪心 , 1648 阅读

思路:

我们维护以每一个节点为根的子树内部有多少个没有确定权值的点,另外,我们利用一个数组维护每个权值已经给了哪个节点.

我们从小到大遍历每个权值,若这个权值当前并没有确定给哪个节点,则将其压入栈中;否则我们在对应节点的子树中进行一系列确定操作:

我们维护栈中有多少个权值,以及有多少个自由权值.(这个是什么一会再说)

若未确定的节点数正好等于当前的自由权值数与栈中的权值总数,显而易见这些权值都应该分配给这棵子树.但是只有只有一个儿子的情况才能确定这个权值.所以我们不断在链上去找即可.这个过程可能确定了一些权值,随后我们将栈清空,并令自由权值的数目为0.因为他们只能被拘束在这颗子树内,而不能去别的地方.

若不然,我们将自由权值及栈中的权值分配给这棵子树所需要的数目,剩下的全部变成自由权值.

我们发现栈中的权值和自由权值很像,但是为什么不都搞成自由权值,而是非要维护一个栈呢?

这个问题显而易见:自由权值都是可以互相交换的(等价的),而栈中的元素显然不是!

于是\(O(n)\)水.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
 
namespace Fio{
    inline int getc(){
        static const int L=1<<15;static char buf[L],*S=buf,*T=buf;
        if(S==T){T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;}
        return*S++;
    }
    template<typename T>inline void Get(T&x){
        int c;while(!isdigit(c=getc()));x=c-'0';while(isdigit(c=getc()))x=(x<<1)+(x<<3)+c-'0';
    }
}
 
#define N 1000010
vector<int>v[N];
int pa[N],w[N];
int q[N],fr,ta,ins[N],size[N],stk[N],top,tot,sum;
int main(){
    int n;Fio::Get(n);
    register int i,j;
    for(i=1;i<=n;++i){
        Fio::Get(pa[i]),Fio::Get(w[i]);if(i==pa[i])w[i]=n;
        if(w[i])q[ta++]=i,ins[w[i]]=i;else v[pa[i]].push_back(i);
    }
    int u;
    while(fr<ta){
        u=q[fr++];
        for(j=0;j<v[u].size();++j)q[ta++]=v[u][j];
    }
    for(i=n-1;i>=0;--i){
        u=q[i];
        size[u]=1;
        for(j=0;j<v[u].size();++j)size[u]+=size[v[u][j]];
    }
    int tot=0;
    for(i=1;i<=n;++i){
        if(!(u=ins[i])){stk[++top]=i;continue;}
        int sum=0,ac=0,pretop=top;
        for(j=0;j<v[u].size();++j)sum+=size[v[u][j]];
        if(sum==tot+top){
            for(;v[u].size()==1&&top;u=v[u][0])
                ins[w[v[u][0]]=stk[top--]]=v[u][0],++ac,--sum;
            if(sum)tot=top=0;
        }
        else{
            if(sum)tot=tot+top-sum,top=0;
        }
    }
    for(i=1;i<=n;++i)printf("%d\n",w[i]);
    return 0;
}

 

DDD 说:
Jun 03, 2015 02:05:07 PM

请问程序中间那个没显示粗来的是什么。。。

Avatar_small
wyfcyx 说:
Jun 03, 2015 02:24:25 PM

@DDD: 什么东西没显示出来啊

DDD 说:
Jun 03, 2015 06:46:08 PM

@wyfcyx: 就是第47行FOR循环中间的那个

Avatar_small
wyfcyx 说:
Jun 04, 2015 08:07:08 PM

@DDD: 玛雅这是什么...让我看看代码

Avatar_small
wyfcyx 说:
Jun 04, 2015 08:09:05 PM

@wyfcyx: 现在换成了原汁原味的代码...这个bug是什么我也不太清楚...


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter