社区讨论

求助,next数组哪里错了

P1120[CERC 1995] 小木棍参与者 3已保存回复 2

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mi6xmdo9
此快照首次捕获于
2025/11/20 12:29
4 个月前
此快照最后确认于
2025/11/20 12:29
4 个月前
查看原帖
CPP
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,vis[70],x;
int l[70],tot,lsum,lmax=0,next[70];
bool flag=false;
bool cmp(int x,int y){return x>y;}
void dfs(int u,int sum,int now,int length){
	if(now>length||(sum==tot&&now!=length))return;
	if(now==length){
		now=0;
		if(sum==tot){
			flag=true;
			return;
		}
	}
	for(int i=u;i<=tot;i++){
    //这里循环从u开始也导致结果错误
		if(!vis[i]){
			vis[i]=1;
			dfs(i,sum+1,now+l[i],length);
			vis[i]=0;
			i=next[i];
		}
	}
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		if(x<=50){
			tot++;
			lsum+=x;
			lmax=max(lmax,x);
			l[tot]=x;
		}
	}
	sort(l+1,l+tot+1,cmp);
	for(int i=tot+1;i>=1;i--){
		if(l[i-1]!=l[i])next[i-1]=i;
		else next[i-1]=next[i];
	}
	for(int i=lmax;i<=lsum/2;i++){
		if(!(lsum%i)){
			vis[1]=1;
			dfs(1,1,l[1],i);
			vis[1]=0;
			if(flag){
				printf("%d\n",i);
				return 0;
			}
		}
	}
	printf("%d\n",lsum);
	return 0;
}

回复

2 条回复,欢迎继续交流。

正在加载回复...