剪枝剪错了,在二分查找后,你把 $ln$ 写成了 $lst$。应该是如果当前这一根木棍能刚好把剩下长度拼完,但匹配失败,才退出循环。说实话我不理解为啥这些错了不是 WA 而是 TLE。真的不会导致漏解吗?
by wujingfey @ 2023-10-18 15:33:12
@[26946z2111](/user/928342) 帮你改好了,最慢的一个点 $180ms$
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,a[110],len,sm,nxt[110];
bool flag[110],Flag;
void dfs(int k,int lst,int ln){
if(Flag)return;
if(ln==0){
if(k==sm){
Flag=1;
return;
}
int q;
for(int i=1;i<=n;i++){
if(!flag[i]){
q=i;
break;
}
}
flag[q]=1;
dfs(k+1,q,len-a[q]);
flag[q]=0;
return;
}
int l=lst+1,r=n;
while(l<r){
int mid=(l+r)>>1;
if(a[mid]<=ln)r=mid;
else l=mid+1;
}
for(int i=l;i<=n;i++){
if(!flag[i]&&ln-a[i]>=0){
flag[i]=1;
dfs(k,i,ln-a[i]);
flag[i]=0;
if(Flag)return;
if(a[i]==ln||len==ln)return;
i=nxt[i];
}
}
}
bool cmp(int x,int y){return x>y;}
int main(){
cin>>n;
int sum=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
sum+=a[i];
}
sort(a+1,a+n+1,cmp);
for(int i=n;i>=1;--i){
if(a[i]!=a[i+1]){
nxt[i]=i;
}
else nxt[i]=nxt[i+1];
}
for(len=a[1];len<=sum;len++){
if((len>sum/2&&len<sum)||sum%len!=0)continue;
sm=sum/len;
flag[1]=1;
dfs(1,1,len-a[1]);
flag[1]=0;
if(Flag){
cout<<len;
break;
}
}
return 0;
}
```
by wujingfey @ 2023-10-18 15:35:16
@[wujingfey](/user/637073) 感谢救急!10月21号就要比赛了,临时抱抱佛脚
by 26946z2111 @ 2023-10-18 21:39:58