这一刻的救赎感！ || solution - CF1452F

littlebug · 2025-09-24 11:56:53 · 题解

你懂不懂看到 \tt \color{#00B027} Accepted 那一刻的救赎感啊喂！！！

思路是比较容易的，但是细节比较多。

记 a:b 为用 a 次操作可以使 \le x 的元素增加 b 个，它的的比值为 \frac a b。

贪心。

分析一下可以发现，对一个 \le 2^x 的元素操作，结果一定是 1:1；对一个 >2^x 的元素操作，令这个元素为 2^{x+i}，那么在一直分解直到 2^x 的过程中，结果为 2^i-1 : 2^i。

所以先操作 2^{x+i} 一定是更优的，而且不难发现一定是从小到大按顺序操作，这样可以使比值尽量大。

直到剩余的 k 不够 2^i 的时候，就不能完全操作 2^{x+i} 了，这时候就可能有两种操作：

操作 \le 2^x 的元素，即操作 1:1。
不完全操作 2^{x+i}。

可以发现后者的结果是不确定的。

但是可以发现一个元素操作后变成编号小 1 的两个元素，这可以形成一个递归的结构，所以考虑递归地解决。

因为 2^{x+i} 的 2^i-1 : 2^i 会被分解成 2^{i-1} : 2^{i-1} , 2^{i-1}-1 : 2^{i-1}，所以这个标记是可以往下传递的。且贪心地，一定会先走左子树再走右子树（因为如果右子树没走，那么左子树是走不了的），于是可以判一下左子树的贡献与 k 的大小关系，然后递归到子问题。

大体思路就是这样，然后就是递归部分的细节了。

下面给出调代码的过程，应该是能踩的坑我都踩到了。

WA on #2 Q5：忘记考虑在把一个数分解成若干个 2^x 之后，又会产生新的 1:1。

10 1
947459 389393 330193 923905 586112 633984 879912 105167 467236 366443
2 4 304758765

299128961

WA on #2 Q151：只考虑了 1:1 个数 \ge k 的情况，忘记 1:1 个数 <k 但是当前处理的比值 >1 的情况。
```
10 1
370768 691341 211969 220375 136028 842276 746582 112475 578010 670433
2 0 283765227
```
```
279777044
```
WA on #14 Q9559：草我第二步的时候怎么操作次数忘加了，怎么这还能过这么多点。还有就是递归边界的答案脑抽算错了。
```
10 1
4 1 5 1 4 0 2 0 0 2
2 1 269
```
```
252
```
WA on #32 Q6515：不可以在非边界的时候直接把 1:1 做掉，因为最后可能会出现 4:2 , 1:2 这种情况，当 4:2 必选的时候，显然 1:2 比 1:1 更优。
```
10 1
0 1 1 0 0 0 1 0 1 1
2 1 7
```
```
7
```
WA on #32 Q1：套取数据的代码忘删了！

代码：

// === / 走吧 就算我们无法让大雨停下 还有我 陪你在雨里放肆奔跑啊 / ===

int n,Q,a[N],b[N];

int d,c;
il int dfs(int k,int x,int y)
{
    if(x>=y && c>=k) return k;
    if(y<=2)
    {
        int ans=0;
        x>y && (ans+=c,k-=c,c=0);
        k && (ans+=x);
        return ans;
    }

    int _k=k;
    if((_k-=y>>1)<=0) return dfs(k,x-(y>>1)+1,y>>1);
    else return c+=(y>>1)*((1<<d)-1),(x-(y>>1)+1)+dfs(_k,(y>>1)-1,y>>1);
}

il int sol(int x,int k)
{
#define chk if(k<=0) return ans

    // no sol
    int ccc=0; rep(i,0,n-1) if((ccc+=a[i]*(1<<i))>=k) break;
    if(ccc<k) return -1;

    int ans=0,tmp;

    // qwq
    k-=gsum(a,a+x+1);
    chk;

    // first x+i
    bool enough;
    rep(i,x+1,n-1)
    {
        tmp=min(a[i],k/(1<<i-x)),enough=tmp!=a[i];
        ans+=((1<<i-x)-1)*tmp,k-=(1<<i-x)*tmp;
        a[i]-=tmp,a[x]+=(1<<i-x)*tmp;
        if(enough) break;
    }
    chk;

    // then <=i
    int c0=0;
    rep(i,0,x)
    {
        c0+=((1<<i)-1)*a[i],a[i]=0;
        if(c0>=k) return ans+k;
    }
    chk;

    // 
    int y;
    rep(i,x+1,n-1) if(a[i]) {y=i;break;}
    return c=c0,d=x,ans+dfs(k,(1<<y-x)-1,1<<y-x);
}

il void solve()
{
    read(n,Q),_::r(b-1,n);

    int op,x,k,cnt2=0;
    while(Q--)
    {
        read(op,x,k);
        if(op==1) {b[x]=k; continue;}
        memcpy(a,b,sizeof(b));
        write(sol(x,k),'\n');
    }
}

华风夏韵，洛水天依！