社区讨论
0分求助
灌水区参与者 3已保存回复 3
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 3 条
- 当前快照
- 1 份
- 快照标识符
- @locc392v
- 此快照首次捕获于
- 2023/10/30 11:22 2 年前
- 此快照最后确认于
- 2023/11/04 23:05 2 年前
题目描述
给定一组不同长度的木棍,是否有可能将它们端对端地连接起来形成1个正方形?
输入格式
第1行输入包含N,即测试数据的数量。 每组测试数据第一个数为M,即木棒的根数。之后有M个整数, 每个都给出了一根棍子的长度li。
输出格式
对于每种情况,如果可以形成正方形,则输出yes或no,每个结果占1行。
数据范围与提示
4 <= M <= 20
1 <= li <= 100000
我的代码:
CPP#include <bits/stdc++.h>
using namespace std;
int times[2000005],len[25],n;
bool ck[25];
void clear()
{
memset(times,0,sizeof(times));
memset(len,0,sizeof(len));
}
void dfs(int k,int cnt,int last)
{
if(k==n+1) return;
for(int i=last+1;i<=n;i++)
{
if(!ck[i])
{
times[cnt+len[i]]++;
ck[i]=1;
dfs(k+1,cnt+len[i],i);
ck[i]=0;
}
}
}
int main()
{
int s;
scanf("%d",&s);
for(int i=1;i<=s;i++)
{
clear();
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&len[i]);
dfs(1,0,0);
for(int i=1;i<=2000005;i++)
if(times[i]>=4)
{
printf("yes\n");
break;
}
printf("no\n");
}
}
我是大聪明 样例过了(明天看回复)
回复
共 3 条回复,欢迎继续交流。
正在加载回复...