d375 - 10364 - Square
題目描述
題目給定一組棍子的長度，要求判斷這些棍子是否能組成一個正方形。正方形的邊長必須是所有棍子長度總和的四分之一，且每根棍子都必須被使用，且不能折斷。
解題思路
首先，檢查所有棍子長度總和是否能被 4 整除。如果不能，則不可能組成正方形，直接輸出 "no"。如果能被 4 整除，則計算正方形的邊長。接著，檢查是否有單根棍子的長度大於邊長，如果有的話，則不可能組成正方形，直接輸出 "no"。
如果以上條件都滿足，則使用回溯法 (Backtracking) 嘗試找到兩個邊長之和等於總長度的一半的邊。找到其中一邊後，再嘗試用剩下的棍子組成另一邊。dfsf 函數用於尋找第一條邊，dfs 函數用於尋找第二條邊。us 陣列用於標記棍子是否已被使用。jd 陣列用於標記是否成功找到邊。
在尋找邊的過程中，使用貪心策略，從最長的棍子開始嘗試，以減少回溯的次數。
複雜度分析
- 時間複雜度: O(2^M)，其中 M 是棍子的數量。在最壞的情況下，需要嘗試所有可能的棍子組合。
- 空間複雜度: O(M)，主要用於儲存棍子的長度、使用狀態和回溯所需的堆疊空間。
程式碼
#include <iostream>
#include <algorithm>
using namespace std;
int ac,a[25],us[25],v[4],n,m,tot,t2,t4,ma,ta,jd[2];
void dfs(int tp,int it,int r){
//++ta;
if(r==0||jd[tp]){
jd[tp]=1;
return;
}
for(int i=it+1;i<m;++i){
if(us[i]==tp&&r>=a[i]){
us[i]+=2;
dfs(tp,i,r-a[i]);
us[i]-=2;
}
}
}
void dfsf(int it,int r){
//++ta;
if(ac)return;
if(r==0){
jd[0]=jd[1]=0;
dfs(0,-1,t4);
if(jd[0]==0)return;
dfs(1,-1,t4);
if(jd[1])ac=1;
return;
}
for(int i=it+1;i<m;++i){
if(r>=a[i]){
us[i]=1;
dfsf(i,r-a[i]);
us[i]=0;
}
}
}
bool cmp(int x,int y){
return (x<y)? 0:1;
}
int main(){
cin.tie(0);cout.tie(0); ios::sync_with_stdio(false);
cin >> n;
while(n--){
cin >> m;
ac=tot=ma=0;
for(int i=0;i<m;++i){
cin >> a[i];
tot+=a[i];
ma=max(a[i],ma);
}
if(tot%4==0&&ma<=tot/4){
t2=tot/2;
t4=t2/2;
sort(a,a+m,cmp);
us[0]=1;
dfsf(0,t2-a[0]);
us[0]=0;
if(ac)
cout << "yes\n";
else
cout << "no\n";
}
else{
cout << "no\n";
}
}
//cout << "Total : " << ta ;
}
//Total : 860250675
//Total : 530330080
//Total : 530238312
//Total : 4719815
//Total : 941062
//Total : 833298