只是评测鸡波动吧
by 红黑树 @ 2023-11-12 22:40:48
没用快读,AC
```cpp
#include <bits/stdc++.h>
using namespace std;
int n,a[70],st,sum;
int nx[70];//下一根长度相等的木棍
bool vst[70];
bool cmp(int a,int b)
{
return a>b;
}
bool dfs(int num,int tar,int cnt,int last)
{
if(cnt==n)
{
if(num==tar)
{
cout<<tar;
exit(0);
}
else return false;
}
if(tar==num) num=0,last=0;
for(int i=last+1;i<=n;i++)
{
if(vst[i]) continue;
if(num+a[i]>tar)
{
i=nx[i]-1;
continue;
}
vst[i]=1;
if(dfs(num+a[i],tar,cnt+1,i)) return true;
vst[i]=0;
//对于失败的优化
if(tar-num==a[i]) return false;//如果这根最优方案失败,就不用考虑后面比它小的碎片
if(num==0) return false;//没有拼的棍子肯定用得上这个碎片,如果失败就不用看后面的
i=nx[i]-1;
}
return false;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i],st=max(st,a[i]),sum+=a[i];
sort(a+1,a+n+1,cmp);
//预处理每根木棍下一根长度不同的木棍,用于剪枝
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n+1;j++)
if(a[j]!=a[i])
{
nx[i]=j;
break;
}
// cout<<a[1];
for(int i=st;i<=sum;i++)
{
if((sum%i)!=0) continue;
dfs(0,i,0,0);
}
return 0;
}
```
用了快读,T了最后一个点
```cpp
#include <bits/stdc++.h>
using namespace std;
int n,a[70],sum;
int nx[70];//下一根长度相等的木棍
bool vst[70];
inline int read()
{
int f=1,num=0;
char c=getchar();
while(c<'0'||c>'9'){if(c='-') f=-1;c=getchar();}
while(c>='0'&&c<='9'){num=(num<<1)+(num<<3)+c-48;c=getchar();}
return f*num;
}
bool cmp(int a,int b)
{
return a>b;
}
void dfs(int num,int tar,int cnt,int last)
{
if(cnt==n)
{
if(num==tar)
{
printf("%d",tar);
exit(0);
}
else return;
}
if(tar==num) num=0,last=0;
for(int i=last+1;i<=n;++i)
{
if(vst[i]) continue;
if(num+a[i]>tar)
{
i=nx[i]-1;
continue;
}
vst[i]=1;
dfs(num+a[i],tar,cnt+1,i);
vst[i]=0;
//对于失败的优化
if(tar-num==a[i]) break;//如果这根最优方案失败,就不用考虑后面比它小的碎片
if(num==0) break;//没有拼的棍子肯定用得上这个碎片,如果失败就不用看后面的
i=nx[i]-1;
}
}
int main()
{
n=read();
for(int i=1;i<=n;++i)
a[i]=read(),sum+=a[i];
sort(a+1,a+n+1,cmp);
//预处理每根木棍下一根长度不同的木棍,用于剪枝
for(int i=1;i<=n;++i)
for(int j=i+1;j<=n+1;++j)
if(a[j]!=a[i])
{
nx[i]=j;
break;
}
// cout<<a[1];
for(int i=a[1];i<=sum;++i)
{
if((sum%i)!=0) continue;
dfs(0,i,0,0);
}
return 0;
}
```
by 2333? @ 2023-11-12 22:41:24
@[红黑树](/user/413140) 但是试了多次都很稳定,快读要慢7~8ms(
by 2333? @ 2023-11-12 22:43:15
额,你这个快读比 cin 还慢啊。你可以自己写个测试试一下。
by 红黑树 @ 2023-11-12 22:46:33
你可以读一个很大的文件,看看时间。
by 红黑树 @ 2023-11-12 22:47:19
@[红黑树](/user/413140) ![](https://cdn.luogu.com.cn/upload/image_hosting/eahgf3i6.png)
![](https://cdn.luogu.com.cn/upload/image_hosting/1yx61f4d.png)
by 2333? @ 2023-11-12 23:00:19
会不会洛谷的那个cin比你的快读快啊
by Lizichen_licis @ 2024-01-20 10:55:49
就是它的那个cin里面的程序和咱们那个 istream 不一样?
by Lizichen_licis @ 2024-01-20 10:56:23
我是scanf过的
by Lizichen_licis @ 2024-01-20 10:56:44