题解：P17233 [Algo Beat Contest 017 B] 线性筛

· · 题解

一开始想模拟乱搞，因为有效删除不会很多，但遍历一次成本太高，总复杂度奔平方了，不行。

既然直接模拟不行，就反向思考，看每个下标会在第几轮被删除。

考虑打表看一下规律，此处以 n=30 为例，数字为在原数组中的下标：

 1: 1, 8, 27
 2: 2, 10, 30
 3: 3, 12
 4: 4, 14
 5: 5, 16
 6: 6, 18
 7: 7, 20
 8: 9, 22
 9: 11, 24
10: 13, 26
11: 15, 29
12: 17
13: 19
14: 21
15: 23
16: 25
17: 28

不难发现随轮数增加，纵向存在一些比较规律的递推关系，变化量看起来是 \lfloor\sqrt[3]x\rfloor。

注：这个变化量是因为在前 x 个数中，每一轮删除的数量是 \lfloor\sqrt[3]x\rfloor，相当于是下标前移到更贴近完全立方数的位置，直至被删除。

那么思路就逐渐成型了，设 r[i] 表示下标为 i 的位置会在第几轮被删除，则有：

int n, a[maxn], r[maxn]; // r[i]:原数列中第i个位置上的数在第几轮被删除

void solve()
{
    int n; cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
    }

    int k = 1; // 当前位置的立方根
    int cnt = 0; // 总操作次数

    for(int i = 1; i <= n; i ++){ // 枚举每个位置
        while((k+1)*(k+1)*(k+1) <= i) k ++; // k=floor(i^(1/3))，因为 1^3,2^3...k^3均<=i
        if(k*k*k == i){
            r[i] = 1; // 本身是完全立方数，第一轮就被删除
        }
        else{
            r[i] = r[i-k] + 1; // 本轮不被删除，经过一次操作后位置变为 x-k
        }
        cnt = max(cnt, r[i]);
    }

    vector<vector<int>> ans(cnt+1);
    for(int i = 1; i <= n; i ++){
        ans[r[i]].push_back(i);
    }

    cout << cnt << '\n';
    for(int k = 1; k <= cnt; k ++){
        for(int i : ans[k]){
            cout << a[i] << ' ';
        }
        cout << '\n';
    }
}