题解：CF1852A Ntarsis' Set

TBSF_0207 · 2025-10-20 16:09:47 · 题解

与 k 无关的 \Theta(n) 做法。

首先 10^{1000} 足够大，不妨把初始集合视为 \N_+。

模拟赛出了这个的强化版，k\le 10^9，我们考虑怎么解决这个问题。首先观察到如果 a_1\neq 1 答案一定为 1。不妨逆推，我们发现顺着推很简单，如果经过若干轮都没有被淘汰，每一轮每个数 x 的 pos_x 就会经过如下转移：pos_x\leftarrow pos_x -i，其中 a_i 为最后一个 <pos_x 的数。

相应地，逆推只需要 pos_x\leftarrow pos_x+i，其中 a_i 为最后一个 <pos_x +i 的数，即 a_{i+1}\geq pos_x + i。显然递推过程中找到的 i 是单调不降的（理解：相当于每次抽出没被删掉的放在前面，只需找到每次被放在前面的推导出抽出时的位置，显然这是唯一且递增的），但是可能会有多个相同且冗余的 i，每次都对 pos_x 执行 +i 的操作。

考虑加速这一过程。让 pos_x 直接加到边界 a_{i+1}-1 且不能做超过 k 步所需的步数为 p=\min(k,\lfloor\frac{a_{i+1}-1-pos_x}{i}\rfloor)，那么 pos_x\leftarrow pos_x+p\times i 即可，这样对于每个 i 都只会做 \Theta(1) 次。最后如果 pos_x>a_n 且 k\neq 0，pos_x\leftarrow pos_x + k\times n 就可以逆推出初始的 pos_x 值。

时间复杂度 \Theta(n)。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5+5;
int n,k,a[N];
int main(){
    int Tn;scanf("%d",&Tn);
    while(Tn--){
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        if(a[1]!=1){printf("1\n");continue;}
        LL Pos=1;
        for(int i=1;i<n;i++)
            if(Pos<=a[i+1]-i){
                int p=min(k,(int)(a[i+1]-1-Pos)/i);
                Pos+=p*i;k-=p;
            }
        Pos+=1ll*k*n;
        printf("%lld\n",Pos);
    }
    return 0;
}