题解：CF1774F1 Magician and Pigs (Easy Version)

这个玩意直接维护不好搞，考虑转化第三个操作。

如果没有

3

操作，肯定要动态维护前几个操作中，

2

操作的总贡献

w

。而对于一个

3

操作，剩余血量为

x

的猪猪将会分裂成两头猪猪，这两头猪猪的血量分别为

x,x-w

，随后

w

变为原先的两倍。

我们考虑这样转化题意：对于每头猪，遇到

3

操作的时候可以选择是否将当前血量

-w

，求使得这头猪猪血量

>0

的方案数，并对所有猪求方案数的和。

F1 好像可以直接平衡树维护，但我懒，不想写平衡树。而且平衡树没法做 F2。

令

V

为

x

值域的最大值，即

10^9

。考虑到：

如果 $3$ 操作的 $w\geq V$ ，则这个 $3$ 操作无效。
如果 $3$ 操作的 $w=0$ ，则把在这个 $3$ 操作之前生成的所有猪猪，答案乘以 $2$ 。
反之，剩余情况的 $3$ 操作只有 $\log V$ 次，因为每次 $3$ 操作会让 $w$ 乘以 $2$ 。

那就直接暴力处理这

\log V

次第三种

3

操作就行。具体计算答案的时候，把这些

3

操作插入 vector，记录第

i

个三类

3

操作的

w

为

W_i

，则

2W_i\leq W_{i+1}

，问题可以类比拆二进制位来做。

时间复杂度

\Theta(n\log V)

。

CPP

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
#define pii pair<int,int>
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define ro(i,r,l) for(int i=r;i>=l;i--)
const int N=8e5+5,INF=1e9,M=998244353;
int n,op[N],val[N];
vector<int>e;
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    int w=0,c=1,rs=0;
    fo(i,1,n){
        cin>>op[i];
        if (op[i]<3)
            cin>>val[i];
        if (op[i]==2)
            w=min(INF,w+val[i]);
        if (op[i]==3){
            val[i]=w;
            w=min(INF,w*2);
        }
    }
    w=0;
    ro(i,n,1){
        if (op[i]==1){
            int x=val[i]-w;
            if (x<=0)
                continue;
            int p=e.size();
            for (auto i:e){
                p--;
                if (x>i){
                    x-=i;
                    (rs+=(1ll<<p)*c%M)%=M;
                }
            }
            (rs+=c)%=M;
        }
        else if (op[i]==2)
            w=min(INF,w+val[i]);
        else{
            if (!val[i])
                c=c*2%M;
            else if (val[i]!=INF)
                e.push_back(val[i]);
        }
    }
    cout<<rs<<'\n';
    return 0;
}

题解：CF1774F1 Magician and Pigs (Easy Version)

文章操作

相关推荐

评论

题解：CF1774F1 Magician and Pigs (Easy Version)