<<点个赞吧

$\huge\color{Gold}{暑假每日一题2022}\color{black}{题解集合}$

算法

DFS+剪枝

C++ 代码

#include<bits/stdc++.h>
#pragma GCC optimize(3)
using namespace std;
int n,ans;
int a[10011];
bool b[10011];
bool isqrt(int m){  
    int i=sqrt(m);
    return m==i*i;
}
void dfs(int now,int last){
    if(now>=n){ 
        ans++;
        return;
    }
    for(int i=1;i<=n;i++){
        if(i>1&&a[i]==a[i-1]&&!b[i-1]) continue;        
        if(b[i]) continue;
        if(isqrt(last+a[i])){
            b[i]=true;
            dfs(now+1,a[i]);
            b[i]=false;         
        }
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){
        if(i>1&&a[i]==a[i-1]) continue;
        b[i]=true;
        dfs(1,a[i]);
        b[i]=false;
    }
    cout<<ans;
    return 0;
}