专栏文章

题解：UVA10364 Square

___DAN__
UVA10364题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqr2xg5
此快照首次捕获于
2025/12/04 09:21
3 个月前
此快照最后确认于
2025/12/04 09:21
3 个月前
查看原文

题目传送门

正解(搜索剪枝)

当总长度不是四的倍数时不可行。
接着将长度和除以 44 ，得到每条边的长度 ll 。用一个变量 flagflag 代表当前是否有可行方案。之后暴力搜索，并定义四个变量 a,b,c,da,b,c,d ，分别代表四条边已有的长度。若木棒加上此边的长度超过了 ll ,则跳过（剪枝操作）。本条边加上木棍长度，进行下一步搜索，并回溯。若flag=1，（已有可行方案）则可以直接跳过以上操作。当木棍遍历结束，可直接判断 a=ba=b 且 b=cb=c 且 c=dc=d ，若等于则flag=1。最后输出。

代码展示

CPP
#include<bits/stdc++.h>
using namespace std;
int T,n,s;
int a[25],b[5];
int fl=0;
void dfs(int i){
	if(i==n+1){
		if(b[1]==b[2]&&b[2]==b[3]&&b[3]==b[4]) fl=1;
		return;
	}
	for(int j=1;j<=4;j++){
		if(b[j]+a[i]>s) continue;
		if(fl==0){
			b[j]+=a[i];
			dfs(i+1);
			b[j]-=a[i];
		}
		else break;
	}
}
int main(){
	cin>>T;
	while(T--){
		memset(b,0,sizeof(b));
		fl=0;
		s=0;
		cin>>n;
		for(int i=1;i<=n;i++){
			cin>>a[i];
			s+=a[i];
		}
		if(s%4!=0){
			cout<<"no"<<"\n"; 
			continue;	
		}
		s/=4;
		dfs(1);
		if(fl==1) cout<<"yes"<<"\n";
		else cout<<"no"<<"\n";
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...