自动搬运

查看原文

来自洛谷，原作者为

	Light_az florr.io 同名 || 莱特阿哲

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

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

以下是正文

数据好像水了？

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

搜索+剪枝

对于每次输入的 $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;
}