cmll02的博客

博客

2023 山东省队互唱 Round 1 B题 subtask3(log^2)做法

2023-06-12 13:37:57 By cmll02

考虑依次操作 $1,1,1,1,2,2,4,4,8,8,\cdots$。

维护一个 $sum$ 表示我们现在知道 $n$ 至少是 $sum+1$。

如果操作完变大那么直接更新 $sum$。

如果操作完变小了,把这次操作的数从 $sum$ 中减去,然后直接执行 $+sum$,然后重新从 $1$ 开始执行这个过程。

这样一轮是 $O(\log n)$ 的。每次操作 $sum$ 都不降。容易发现只要 $O(\log n)$ 次就能求得 $n$。

int add(long long x);
bool cmp(int i,int j);

int solve()
#define int long long
{
    int nw,pre=0;
    int sum=0;
    while(nw<2900)
    {
        int ps=sum;
        pre=nw=add(sum);
        for(int i=0;i<=30;i++)
        {
            int t=1<<(i==0?0:i-1);
            nw=add(t);
            if(cmp(nw,pre)==0)pre=nw,sum+=t;
            else {sum-=t;break;}
            nw=add(t);
            if(cmp(nw,pre)==0)pre=nw,sum+=t;
            else {sum-=t;break;}
        }pre=nw;
    }
    return sum+2;
#undef int
}

这个做法可以弄到期望 1log,需要大约 190 次操作,无法通过。

cmll02 Avatar