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

microsoft_vs_code · 2026-08-10 18:25:06 · 题解

注意到题解区没有使用链表的题解，这里提供一个链表模拟的题解。

观察题目，发现在每一次删除 i^3 过后，下一次删除的下标会右移 i 个依旧存在的点。

我们用链表来维护每一个点的前驱和后继，在每一次查询过后，暴力地去将下一次要删除的位置往后跳 i 次。

每一个点都只会被删一次，也就是说删点的总时间复杂度是 O(n) 的。

一次最多删 n^{\frac{1}{3}} 个点，而每一个删点在删完所有点以后一共最多会暴力跳 n 次，所以暴力跳点的最坏时间复杂度为 O(n^{\frac{4}{3}})。

所以最坏时间复杂度为 O(n^{\frac{4}{3}})，但实际上，并不是所有点都会跳满 n 次，所以远远跑不满。

Code:

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define fr(a, b, c) for (c = a; c <= b; ++c)
#define rf(a, b, c) for (c = a; c >= b; --c)
#define I using
#define AK namespace
#define LUOGU std
#define I_AK_CSP                  \
    ios_base::sync_with_stdio(0); \
    cin.tie(0)
#define MAXN 1000101
#define MAXM 100
#define llabs(x) ((x < 0) ? -x : x)
I AK LUOGU;
ll read()
{
    char a = getchar();
    ll ans = 0, f = 1;
    while (a < '0' || a > '9')
    {
        if (a == '-')
            f = -1;
        a = getchar();
    }
    while (a >= '0' && a <= '9')
    {
        ans = (ans << 3) + (ans << 1) + (a - '0');
        a = getchar();
    }
    return ans * f;
}
void write(ll x)
{
    if (x < 0)
    {
        x = -x;
        putchar('-');
    }
    if (x / 10)
    {
        write(x / 10);
    }
    putchar(x % 10 + '0');
}
ll n, m, a[MAXN], i, j, cnt, ans, pre[MAXN], nxt[MAXN], d[MAXN];
vector<ll> v[MAXN];
int main()
{
    I_AK_CSP;
    n = read();
    fr(1, n, i)
    {
        a[i] = read();
        //预处理前驱和后继
        pre[i] = i - 1;
        nxt[i] = i + 1;
    }
    nxt[n + 1] = n + 1;
    //预处理第一次删除的位置
    for (i = 1; i * i * i <= n; i++)
    {
        d[i] = i * i * i;
    }
    m = i - 1;
    while (cnt < n)
    {
        //统计答案
        ans++;
        fr(1, m, i)
        {
            if(d[i] > n)
                break;
            //统计答案
            cnt++;
            v[ans].push_back(d[i]);
            //删点
            nxt[pre[d[i]]] = nxt[d[i]];
            pre[nxt[d[i]]] = pre[d[i]];
        }
        m = i - 1;
        //跳点
        fr(1, m, i)
        {
            fr(1, i, j)
            {
                d[i] = nxt[d[i]];
            }
        }
    }
    //输出答案
    write(ans);
    fr(1, ans, i)
    {
        putchar('\n');
        for (auto j : v[i])
        {
            write(a[j]);
            putchar(' ');
        }
    }
    return 0;
}