1 条题解

  • 0
    @ 2025-8-24 23:08:49

    自动搬运

    查看原文

    来自洛谷，原作者为

    avatar Wuyanru
    NOI2025 rp++ 喵~ | 不拿10级勾不改签名 | 我猜我是没机会改签名了

    搬运于2025-08-24 23:08:49，当前版本为作者最后更新于2025-01-25 19:00:13，作者可能在搬运后再次修改，您可在原文处查看最新版

    自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

    以下是正文

    莫名其妙被卡了好几天，然后莫名其妙想明白了，写篇题解。

    题目链接。

    题意

    现在有 nn 块蘑菇地，第 ii 块蘑菇地初始有 bib_i 个蘑菇，每天晚上一块地会长出 aia_i 个蘑菇。

    你每天早上可以选择一块地，并把这块地的所有蘑菇都拿走。

    对每一个 1≤k≤n1\le k\le n 求出，如果只有前 kk 天早上你可以拿蘑菇，最多能拿多少。

    n≤106n\le 10^6。

    题解

    首先有一些比较简单的观察。

    观察一：一块地不可能被采摘两次，因为如果被摘了两次，那么第一次采摘完全是可以省略掉的。

    此时这一块地拿到的总蘑菇量不变，你还可以拿多出来这一天去采一块别的蘑菇地，稳赚不亏。

    观察二：按照时间顺序，所有采摘的蘑菇地，aia_i 是递增的。

    这个也很好理解，因为如果你已经确定了采集哪些蘑菇地，那么 bb 的贡献就是确定的，你把 aia_i 大的换到后面让他多长一些肯定更优。

    那么这个时候就有一个 O(n2)O(n^2) 的暴力了。

    首先将所有蘑菇地按照 aia_i 升序进行排序，那么一定是先拿前面的再拿后面的。

    设 dpi,jdp_{i,j} 表示从前 ii 块蘑菇地里面，选出 jj 块地，作为前 jj 天采摘的目标，最多能有多少蘑菇。

    转移比较简单，直接枚举第 ii 块蘑菇地选不选就行。

    转移方程是 $dp_{i,j}=\max(dp_{i-1,j},dp_{i-1,j-1}+(j-1)a_i+b_i)$。

    那么考虑怎么优化这个东西呢，不妨想一想他有没有别的性质。

    考虑相邻两天，采集蘑菇地的变化。

    打个表或者自己瞎猜一下，都可以发现，第 ii 天与第 i+1i+1 天最优方案不同的地方，一定是恰好多采集了一块蘑菇地。

    而不会出现，去掉 22 块蘑菇地，再添加 33 块蘑菇地这种情况。

    为什么呢，假设 i+1i+1 天的最优方案，少了 kk 个蘑菇地而新添了 k+1k+1 个蘑菇地（特殊的，如果有多个最优方案，选择 kk 最小的那个）：

    图中的 00 表示蘑菇地两天的状态相同，++ 表示只有后一天选中，−- 表示只有前一天选中。

    若 k>0k>0，那么一定可以找到一对 +1+1 和 −1-1，使得他们中间只有 00，比如图中的绿色框内两块蘑菇地。

    考虑设当前的答案为 S1S_1，将这两块地有 +1,−1+1,-1 变成 0,00,0 的方案答案设为 S2S_2。

    如果有 S2≥S1S_2\ge S_1，说明 i+1i+1 天这个方案不是最优的，违背了我们的假设。

    这说明有 S1>S2S_1>S_2，这同样是矛盾的。

    因为如果 +1,−1+1,-1 这个方案更优，那么在第 ii 天的时候，这两块地就应该是现在 S1S_1 这个状态了，这说明第 ii 天的方案又不是最优的。

    这样，我们使用了反证法，证明第 i+1i+1 天恰好比第 ii 天多选了一块蘑菇地。

    那么这个时候我们又有一个 O(n2)O(n^2) 做法，对于每一天，直接枚举新选的蘑菇地是哪一块，然后选择增量最大的那个加入方案。

    这是一个非常好的性质，再看一下之前的 dp 转移。

    如果 dpi−1,j>dpi−1,j−1+(j−1)ai+bidp_{i-1,j}>dp_{i-1,j-1}+(j-1)a_i+b_i，这说明最优方案是不选 ii 这块蘑菇地。

    否则 dpi−1,j≤dpi−1,j−1+(j−1)ai+bidp_{i-1,j}\le dp_{i-1,j-1}+(j-1)a_i+b_i，这说明最优方案是选择 ii 这块蘑菇地。

    那么考虑我们刚刚的结论，可以发现一定存在一个 kk，满足对于 j<kj<k 的部分，最优方案是不选 ii，而对于 j≥kj\ge k 的部分，最优方案是选择 ii。

    那么这个 dp 就可以直接使用平衡树维护了，每一次直接在平衡树上二分找到 kk 的位置，然后分左右两侧分别转移。

    左边的转移是直接不变就行，右边需要整体加一个等差数列，然后中间需要额外插入一个点。

    这个做法是 O(nlog⁡n)O(n\log n) 的，显然太难写了，因为不仅需要区间加等差数列，还需要二分，你还得维护每一个子树的第一个和最后一个节点编号。

    所以我们考虑一个稍微好写一点的做法，我们直接去维护相邻两项 dp 的差。

    我们设 fpi,j=dpi−1,j−dpi−1,j−1fp_{i,j}=dp_{i-1,j}-dp_{i-1,j-1}，其中 j≥1j\ge 1，我们维护 fpi,jfp_{i,j} 的值。

    首先来考虑 kk 怎么找，可以发现 kk 是满足 dpi−1,j≤dpi−1,j−1+(j−1)ai+bidp_{i-1,j}\le dp_{i-1,j-1}+(j-1)a_i+b_i 的最小的 jj。

    而这个条件等价于 fpi−1,j≤(j−1)ai+bifp_{i-1,j}\le (j-1)a_i+b_i，这个条件可以直接在平衡树上二分。

    再写出 dpi,jdp_{i,j} 的转移式子：

    $$dp_{i,j}=\begin{cases}dp_{i-1,j}&j<k\\dp_{i-1,j-1}+(j-1)a_i+b_i&j\ge k\end{cases} $$

    那么我们就能写出 fpi,jfp_{i,j} 的转移式子

    $$fp_{i,j}=\begin{cases}fp_{i-1,j}&jk\end{cases} $$

    这样我们的平衡树就只需要维护区间加，而不是区间加等差数列了，并且由于这个二分只涉及到一个值，你也不需要记每一个子树的第一个或者最后一个点了，这实在是太牛了。

    时间复杂度 O(nlog⁡n)O(n\log n)。

    代码

    #include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
template<typename A,const int N>
using aya=array<A,N>;
inline int read()
{
    int s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline ll lread()
{
    ll s=0,w=1;char ch;
    while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
mt19937 _rand(time(0)^clock());
struct node
{
    ll a,b;
}v[1000005];
int pri[1000005];
ll num[1000005];
ll tag[1000005];
int siz[1000005];
int ls[1000005];
int rs[1000005];
int n,rt,cnt;
inline void T(int p,ll y)
{
    num[p]+=y;
    tag[p]+=y;
}
inline void push_down(int p)
{
    if(ls[p]) T(ls[p],tag[p]);
    if(rs[p]) T(rs[p],tag[p]);
    tag[p]=0;
}
inline void push_up(int p)
{
    siz[p]=siz[ls[p]]+siz[rs[p]]+1;
}
int merge(int u,int v)
{
    if(!u||!v) return u|v;
    push_down(u),push_down(v);
    if(pri[u]>pri[v])
    {
        rs[u]=merge(rs[u],v);
        push_up(u);
        return u;
    }
    else
    {
        ls[v]=merge(u,ls[v]);
        push_up(v);
        return v;
    }
}
void split(int p,int &x,int &y,ll a,ll b,int bef)
{
    if(!p){ x=y=0;return ;}
    push_down(p);
    if(num[p]<=(bef+siz[ls[p]])*a+b)
    {
        y=p;
        split(ls[p],x,ls[y],a,b,bef);
        push_up(y);
    }
    else
    {
        x=p;
        split(rs[p],rs[x],y,a,b,bef+siz[ls[p]]+1);
        push_up(x);
    }
}
inline int New(ll v)
{
    cnt++;
    num[cnt]=v,tag[cnt]=0;
    ls[cnt]=rs[cnt]=0;
    siz[cnt]=1,pri[cnt]=_rand();
    return cnt;
}
ll ans;
void output(int p)
{
    if(!p) return ;
    push_down(p);
    output(ls[p]);
    ans+=num[p];printf("%lld\n",ans);
    output(rs[p]);
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++) v[i].a=lread(),v[i].b=lread();
    sort(v+1,v+n+1,[](node a,node b){ return a.a<b.a;});

    for(int i=1;i<=n;i++)
    {
        int x,y;
        split(rt,x,y,v[i].a,v[i].b,0);
        T(y,v[i].a);
        rt=merge(x,merge(New(siz[x]*v[i].a+v[i].b),y));
    }
    output(rt);
    return 0;
}
    • 1

    [PA 2016] 雨后的蘑菇 2 / Grzyby po deszczu 2

    信息

    ID
    11299
    时间
    5000ms
    内存
    512MiB
    难度
    6
    标签
    递交数
    0
    已通过
    0
    上传者
    1. 关于
    2. 联系我们
    3. 隐私
    4. 服务条款
    5. Language
    6. 主题
    3. Worker 0, 26ms