正方形(c++题解)

题目描述

给定一组不同长度的木棍，是否有可能将它们端对端地连接起来形成  个正方形?

输入格式

第1行输入包含N，即测试数据的数量。 每组测试数据第一个数为 ，即木棒的根数。之后有  个整数， 每个都给出了一根棍子的长度 。

输出格式

对于每种情况，如果可以形成正方形，则输出 yes 或 no，每个结果占  行。

样例

样例输入

复制3
4 1 1 1 1
5 10 20 30 40 50
8 1 7 2 6 4 4 3 5

样例输出

复制yes
no
yes

_____________________________________________________________________________

写作不易，点个赞呗!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 

_____________________________________________________________________________

#include <bits/stdc++.h> 
using namespace std; 
int a[100],v[100],n,len,cnt,z;
bool dfs(int s,int c,int l){
if(s>cnt)return true;
if(c==len)return dfs(s+1,0,1);
int g=0;
for(int i=l;i<=n;i++){
if(!v[i]&&c+a[i]<=len&&g!=a[i]){
v[i]=1;
if(dfs(s,c+a[i],i+1)) return true;
g=a[i];
v[i]=0;
if(c==0||c+a[i]==len) return false;
}
}
return false;
}
int main(){
cin>>z;
for(int c=1;c<=z;c++){
cin>>n;
int sum=0,ans=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
sum+=a[i];
ans=max(ans,a[i]);
}
sort(a+1,a+1+n);
reverse(a+1,a+n+1);
for(len=ans;len<=sum;len++){
if(sum%len)continue;
cnt=sum/len;
memset(v,0,sizeof(v));
if(dfs(1,0,1)) break;
}
if(len*4==sum)cout<<"yes\n";
else cout<<"no\n";
}
}

 

 

原文地址：https://blog.csdn.net/hb_zhyu/article/details/137709815

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！