社区讨论
求助,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 条回复,欢迎继续交流。
正在加载回复...