社区讨论

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 条回复,欢迎继续交流。

正在加载回复...