P9391题解

· · 题解

数据好像水了？

本篇题解不是最优解法，仅供剪枝参考。

搜索+剪枝

对于每次输入的 a_i，我们考虑跳跃搜索求出有多少个珍珠没有被访问过，每次跳跃搜索进行一次标记。

如果搜索再次回到被标记的点时说明后面的点一定全部被标记过，在回溯时取消标记就可以大大减少使用 memset 的时间，时间复杂度大概为 O(nm)，最后暴力代码如下：

Code

#include<bits/stdc++.h>
#define ll long long
#define F(i,j,n) for(int i=j;i<=n;i++)
#define B(i,j,n) for(int i=j;i>=n;i--)
#define Tr(v,e) for(int v:e)
#define D double
#define ps push_back
#define Test ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
using namespace std;
const int N=1e6+10,NN=1e4+10;
ll n,m,k,x,y,u,v,w,cnt=0,ans=0,t=0,l,r,len,T;
ll mn=INT_MAX,mx=0,Mod,id=1;
string s1,s2;
ll a[N],b[N];
void dfs(ll id){
    if(!a[id]) ans++;//这个点没被访问
    a[id]=1;
    if(b[id]) return ;//已经标记过
    b[id]=1;
    dfs((id+x)%n);//因为是环，因此添加取模操作
    b[id]=0;//回溯时取消标记
}
int main(){
    cin>>n>>m;
    F(i,1,m){
        ans=0;
        cin>>x;
        dfs(1);
        cout<<ans<<" ";
    }
    return 0;
}

然后拿到部分分后再次考虑剪枝。

如果访问珠子数量已经达到 n 时，后面无论怎么搜索，珠子一定都被访问，因此直接后面输出 0 即可，大大减少了搜索的时间复杂度。

虽然以上思想已经得到满分，但是我们想到本题可以使用倍数对搜索进行优化。

当 a_i 搜索后它所有的倍数都不需要进行搜索，因为 a_i 是倍数的因子，倍数可以访问的点 a_i 全部可以访问。

所以加上特殊标记判断 a_i 是否是前面某一个数的倍数，如果是则不需要搜索，否则对 a_i 进行跳跃搜索再将其倍数打上特殊标记，最好情况下时间复杂度为 O(n)，代码如下：

#include<bits/stdc++.h>
#define ll int
#define F(i,j,n) for(int i=j;i<=n;i++)
#define B(i,j,n) for(int i=j;i>=n;i--)
#define Tr(v,e) for(int v:e)
#define D double
#define ps push_back
#define Test ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
using namespace std;
const int N=5e5+10,NN=1e4+10;
ll n,m,k,x,y,u,v,w,cnt=0,ans=0,t=0,l,r,len,T;
ll mn=INT_MAX,mx=0,Mod,id=1;
string s1,s2;
ll a[N],b[N],Can[N];
ll read(){
    ll s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') {s=s*10+ch-'0';ch=getchar();}
    return s*w;
}
inline void dfs(ll id,ll step){//同上
    if(!a[id]) ans++,cnt++;
    a[id]=1;
    if(b[id]) return ;
    b[id]=1;
    dfs((id+x)%n,step+1);
    b[id]=0;
}
inline void write(ll x){
    if(x<0) {putchar('-');x=-x;}
    if(x>9) write(x/10);
    putchar(x%10+'0');
} 

inline void print(ll n){
    F(i,1,n) write(0),putchar(' ');
    return ;
}
int main(){
    n=read(),m=read();
    F(i,1,m){
        ans=0;
        x=read();
        if(!Can[x]){//没有被特判过
            dfs(1,0);
            F(i,1,n/x) Can[x*i]=1;//倍数特判
            write(ans);
            putchar(' ');
        }   
        else write(0),putchar(' ');//被特判过，一定没有珠子没有被访问过
        if(cnt==n){
            print(m-i);
            return 0;
        }
    }
    return 0;
}