题解：P17233 [Algo Beat Contest 017 B] 线性筛
EnjoySilence
·
·
题解
题目传送门
题意：给定一个长度为 n 的数组 a_1,a_2,\dots,a_n，每次进行一次如下操作：
- 将数组中下标为完全立方数的数字同时移除；
- 随后保持原有顺序重新编号。
求将数组清空的操作次数以及每次操作移除的数。
---
考虑对每一个 $1\le i\le n$ 计算出 $[1,i]$ 之间有多少个完全立方数，记为 $pre_i$；以及计算 $i$ 在第几轮操作被删除，记为 $cnt_i$。
首先，$pre_i$ 的转移显然，只需要判断 $i$ 是不是完全立方数再加上 $pre_{i-1}$ 即可，即：$pre_i=pre_{i-1}+\operatorname{is\_cube(i)}$，其中 $\operatorname{is\_cube}(i)=\begin{cases}1,& i是完全立方数\\ 0,& i不是完全立方数\end{cases}$。现在思考：如何计算 $cnt_i$？我们观察到：在进行一次操作后，下标为 $i$ 的数会位移到下标 $i-pre_i$，直到 $i-pre_i$ 是完全立方数为止，则在原数组中下标为 $i$ 的数在下标为 $i-pre_i$ 的数被删除后一轮紧接着被删除，即：$cnt_i=cnt_{i-pre_i}+1$，需要特判：如果 $i$ 是完全立方数，显然 $cnt_i=1$。
根据上面的方法进行递推，求出每一个 $pre_i,cnt_i$ 后，将原数组清空的操作次数显然为 $\max_{i=1}^n cnt_i$，然后对于所有 $1\le i\le n$，将 $a_i$ 在第 $cnt_i$ 轮输出即可。
[Submission](https://www.luogu.com.cn/record/291993250)