欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

「雅礼集训 2017 Day2」水箱 并查集+树形DP

程序员文章站 2023-12-31 13:07:34
...

前言

好久没有写博客了,写一道雅礼毒瘤题来开开刀……CSDN都转变编辑器风格了,那我也顺便转换一下写作风格啦~

题目链接

水箱-LOJ

题目描述(改编)

有一个毒瘤,长得和水箱一样,可以装很多毒液。高度可以看做是正无穷,宽度为1,长度为n

这个毒瘤里面有 n1 个挡板,把毒瘤分成了 n 个小格。格子里已添加了一些毒液,毒液如果超过挡板就会溢出到其他格子里(就是说不会出现悬空毒液)(这很科学有没有)

现在告诉你每个挡板的高度和 m 个条件。每个条件形式如 (i,y,k),表示从左到右数的第i个格子中,在高度为 y+0.5 的地方是否有毒液,k=1 表示有,k=0 表示没有水,请求出这 m 个条件最多能同时满足多少个条件。本题有多组数据。

输入格式

第一行一个正整数 T,为数据组数。
第二行两个正整数 nm,中间用空格隔开。
接下来一行 n1 个整数,表示从左到右每一块挡板的高度。
接下来 m 行,每行三个整数 iyk,表示一个条件。

输出格式

T 行,每行对应一组数据的答案。

样例输入

2
3 4
3 4
1 3 1
2 1 0
2 2 0
3 3 1
2 2
2
1 2 0
1 2 1

样例输出

3
1

数据范围与提示

对于 20% 的数据,n,m16
对于另外 10% 的数据,只存在指明某处有水的条件;
对于另外 30% 的数据, n,m1000
对于 100% 的数据,n,m105,T5

题解

我只能说毒瘤出题人脑子里的毒瘤已经无法阻挡了。

PS: 为了讨论方便,以下内容中水箱即为毒瘤,水即为毒液

这道题其实思路特别巧妙……我们根据挡板的高度构造一棵树。这棵树有点类似于线段树,又有点类似于哈弗曼树(蒟蒻的理解,大犇勿喷)。我们以挡板从低到高的顺序开始,将挡板两端合并为一个节点,原来的两个节点变成儿子。描述不清楚,还是画图清楚一点……

「雅礼集训 2017 Day2」水箱 并查集+树形DP

我们可以使用并查集合并区间并建树,那么每一个节点其实就都代表了一个区间,而且还是一颗二叉树。你问我这样建树的作用?当然是树形DP啦!

对于一个区间,只可能有两种情况:1).没有溢出 2).溢出去了,我们分别讨论这两种情况

我们令 F[i] 表示编号为 i 的区间的水溢出去了最多可以满足多少条件,D[i] 表示编号为 i 的区间的水没有溢出了最多可以满足多少条件。注意,我们这里讨论的条件,只限于在这个区间中且高度在 i 的「管辖范围」内的条件。

「管辖范围」的意思是,这些条件完全不涉及到这个区间外的格子(比如上图中紫色区间中不讨论红色区间的条件(这个跟紫色区间没有关系啊喂),也不讨论深蓝色区间的水超过紫色区间范围的条件(比如溢出紫色区间左侧的挡板的情况,因为这样就要讨论黄色区间或者更多))。

换句话说,我们将溢出范围的条件归给父亲,如果连父亲都溢出来就归给祖父,以此类推,直到不会溢出为止(当然,最多是整个 [1,n] 区间啦)

那么我们只讨论在「管辖范围」内的情况。

首先,我们先看 D 数组,要求不溢出的条件数量,那么就分两种情况。
1.两个儿子都没有溢出,这样就相安无事,那么很显然的Di=ΣDsoni+empiempi表示属于 i 管辖的条件中k=0 的条件总数。
2.所有儿子都溢出了,但是都没有溢过 i 的上界,这个就要复杂一些,首先很显然的 Di 至少等于Di=ΣFsoni,现在考虑 i 管辖的条件。我们可以枚举一下现在溢出的高度,小于等于这个高度的 k=1 的条件都要加上,大于这个高度的 k=0 的条件都要加上。那么我们设置一个 sum=empi,然后按条件低到高枚举,遇到一个新的高度就加上 k=1 的个数,减去 k=0 的个数,然后所有的 sum 取一个最大值即可。

然后就是 F 数组了,这就很简单了,只需要 ΣFi=Fsoni+allempi 就可以了,all 是管辖的条件总数,allempi 就是 k=1 的个数。直观上理解就是儿子全都溢出,然后自己也全都溢满。

然后最终答案就是 Dfull,就是整个区间的 D

至此就完成了,但其实有很多细节,就不一一赘述了……

Code:

#include<vector>
#include<cstdio>
#include<cstring>
#include<climits>
#include<algorithm>
using namespace std;
#define N 200005
int T,n,m,dt,bel[N],tip[N],bot[N],emp[N];
int fa[20][N],son[N][2],f[N],d[N];
pair<int,int>h[N];
vector<pair<int,bool> >g[N];
template<class type>
inline void Read(type &a)
{
    a=0;bool f=0;char c;
    while(c=getchar(),c<'0'||c>'9')f|=(c=='-');
    while(c>='0'&&c<='9')a=a*10+c-'0',c=getchar();
    if(f)a=-a;
}
template<class type>
inline void Write(type a)
{
    if(a<0)putchar('-'),a=-a;
    if(a>9)Write(a/10);
    putchar(a%10+'0');
}
template<class type>inline type Ckmax(type &a,const type b){return a=max(a,b);}
template<class type>inline type Ckmin(type &a,const type b){return a=min(a,b);}
int Getbel(int a)
{
    if(!bel[a])return a;
    return bel[a]=Getbel(bel[a]);
}
void Init()
{
    Read(n);Read(m);
    for(int i=1;i<n;i++)
    {
        Read(h[i].first);
        h[i].second=i;
    }
    bot[0]=INT_MAX;
    sort(h+1,h+n);dt=n;
    memset(bel,0,sizeof(bel));
    for(int i=1;i<=n;i++)
        fa[0][i]=bot[i]=son[i][0]=son[i][1],tip[i]=i;
    for(int i=1;i<n;i++)
    {
        int a=Getbel(h[i].second);
        int b=Getbel(h[i].second+1);
        bot[++dt]=h[i].first;
        fa[0][dt]=0;
        fa[0][tip[a]]=dt;
        fa[0][tip[b]]=dt;
        son[dt][0]=tip[a];
        son[dt][1]=tip[b];
        bel[b]=a;
        tip[a]=dt;
    }
    for(int i=1;i<=dt;i++)g[i].clear();
    for(int i=1;i<=18;i++)
        for(int j=1;j<=dt;j++)
            fa[i][j]=fa[i-1][fa[i-1][j]];
}
void Insert()
{
    int x,hei,type;
    memset(emp,0,sizeof(emp));
    for(int i=1;i<=m;i++)
    {
        Read(x);Read(hei);Read(type);
        for(int j=18;j>=0;j--)
            if(bot[fa[j][x]]<=hei)
                x=fa[j][x];
        g[x].push_back(make_pair(hei,type));
        emp[x]+=!type;
    }
    for(int i=1;i<=dt;i++)
        sort(g[i].begin(),g[i].end());
}
void Solve()
{
    memset(f,0,sizeof(f));
    memset(d,0,sizeof(d));
    int S,T,sum,sz,tmp;
    for(int i=1;i<=dt;i++)
    {
        if(!g[i].empty())
        {
            sz=g[i].size();
            S=0;
            d[i]=sum=emp[i]+(i>n?f[son[i][0]]+f[son[i][1]]:0);
            while(S<sz)
            {
                T=S;
                tmp=(g[i][T].second?1:-1);
                while(T+1<sz&&g[i][T+1].first==g[i][T].first)
                    ++T,tmp+=(g[i][T].second?1:-1);
                sum+=tmp;
                Ckmax(d[i],sum);
                S=T+1;
            }
            f[i]=sum;
        }
        if(i>n)
        {
            Ckmax(d[i],emp[i]+d[son[i][0]]+d[son[i][1]]);
            Ckmax(f[i],f[son[i][0]]+f[son[i][1]]);
        }
    }
    Write(d[dt]);
    putchar(10);
}
int main()
{
    Read(T);
    while(T--)
    {
        Init();
        Insert();
        Solve();
    }
}

上一篇:

下一篇: