自动搬运

查看原文

来自洛谷，原作者为

	XyaO **

搬运于2025-08-24 22:47:23，当前版本为作者最后更新于2025-03-10 10:55:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解

很妙的一道题。

首先为了减小精度误差，我们将所有数据乘上 $N$。

然后我们需要发现筛子的两个重要性质：

1. 所有筛子关于中心对称，所以点 $i$ 和点 $N-i$ 一定同被筛去或同时保留。
2. 若点 $x$ $(x<\dfrac{N}{3})$ 被第 $k$ 层的筛子筛去，那么点 $3x$ 必然被第 $k-1$ 层的筛子筛去，反之亦然。

性质一显而易见，性质二大家可以通过把第 $k-1$ 层的点和筛子看作是第 $k$ 层的点和筛子坐标扩大三倍而得到。

结合以上两条性质，构造函数 $f(x) = \min(x,N-x) \times 3$，可以证明 $x$ 和 $f(x)$ 的状态相同，因此我们对 $x$ 不断递归 $x \gets f(x)$：

• 如果 $x$ 会被筛去，那么在若干次递归后他必定会落在第一层的筛子内。
• 如果 $x$ 不会被筛去，那么每次递归查询的数形成的队列 $x,f(x),f(f(x)),f(f(f(x)))$...... 必定会出现循环节，只要在第一次某个数重复出现时跳出即可。

对于子任务 2，因为 $N \le 2 \times 10^5$，我们可以对每个点跑递归。但对于子任务 1 和 3，强行遍历各点必然超时，我们需要优化算法。

发现当 $N$ 很大时，前几层的筛子覆盖的范围相应地也会变得很大，那么我们可以先用靠前的筛子筛去大部分数，使得剩余的未确定的数的数量在一定的范围内，再对剩下的数跑递归即可。

时间复杂度 $O(能过)$，可以使用 unordered_map 记忆化搜索提高效率。

代码

#include<bits/stdc++.h>
#define mkp make_pair
using namespace std;
const int N=1e7;
unordered_map<int,int> mp;
int n,head,tail=1;
long long L,R;
double X[N],Y[N];
inline int dfs(int i)
{
	if(mp[i])return mp[i];
	if(i>L&&i<R)return mp[i]=1;
	mp[i]=2;
	return mp[i]=dfs(min(i,n-i)*3);
}
void Solve(double l,double r)
{
	if(r-l<1.0)
	{
		for(int i=ceil(l);i<=r;i++)
			if(dfs(i)==2)printf("%d\n",i);
		return;
	}
	double x=l+(r-l)/3,y=r-(r-l)/3;
	X[++tail]=l;Y[tail]=x;
	X[++tail]=y;Y[tail]=r;
}
signed main()
{
	cin>>n;
	L=n/3;R=(2ll*n-1)/3+1;
	X[1]=0.0;Y[1]=1.0*n;
	while(head<tail){head++;Solve(X[head],Y[head]);}
	return 0;
}