7.18 number of square arrays

Topic link

The number of square arrays

Question making

30min too 3/10
The reason for the error is that repeated permutations are not considered , This is also the focus of this topic

Code and solution

This problem is actually pruning a full arrangement
In order to satisfy the question ： The first condition of pruning is

1. Need to satisfy the complete square
2. Non repeating numbers are required

The first one is easy to satisfy , The second point is to consider, such as
1 1 2 （1 2 3） Serial number in brackets
The arrangement of the numbers above is ：
1 1 2 （1 2 3）
1 1 2 （2 1 3）
Such repetition can be solved in this way ：
Default for the same , Be sure to put the small serial number in front , If you traverse to a certain number , But it is the same as its value, but the number in front of it has not been used , At this time, this number cannot be used .
Then sort by logarithm first , In this way, the same numbers will be put together
if((a[i]==a[i-1]&&e[i-1]==1))

#include<iostream>
#include<cmath>
#include<algorithm>

using namespace std;


/*  First row full arrangement , Prune in the process of full arrangement  */
const int N=15;
int n;
int a[N];
int e[N];
int q[N];
long long ans=0;

int judge(int x){
    
	// Used to judge x Is it a complete square 
	if(sqrt(x)==(int)sqrt(x)) 
		return 1;
	return 0;
}

void dfs(int q[], int layer){
    
	
	if(layer==n){
    
		ans++;
		return ;
	}
	
	for(int i=1;i<=n;i++){
    
		if(e[i]==0&&judge(q[layer]+a[i])){
    
			if((a[i]==a[i-1]&&e[i-1]==1))
				continue;
				e[i]=1;
				q[layer+1]=a[i];
				dfs(q,layer+1);
				e[i]=0;	
		}
	}
}



int main(){
    
	
	cin>>n;
	
	for(int i=1;i<=n;i++)
		cin>>a[i];
		
	sort(a+1,a+1+n);
	
	
	for(int i=1;i<=n;i++){
    
		q[1]=a[i];
		e[i]=1;
		dfs(q,1);
		e[i]=0;
	}
	
	cout<<ans<<endl;
	
	return 0;
}

Postscript

Playing football