题解：P9328 [CCC 2023 S5] The Filter

XyaO · 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;
}