凑平方数（dfs提高，set，字符串）

#include<iostream>
#include<string>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
long long shu[20];
int ai[10]={0,1,2,3,4,5,6,7,8,9};
set<string> jj;

void dfs(int cur,int num)
{
    if(cur==10)
    {
            long long shu2[20];
        for (int i = 0; i<num; i++)
            shu2[i] = shu[i];//将存储的数字赋值
        sort(shu2, shu2 + num);//排序
        string xu;

        for (int i = 0; i<num; i++)
        {
            while (shu2[i])
            {
                int a = shu2[i] % 10;
                shu2[i] = shu2[i] / 10;
                char b = a + '0';
                xu = xu + b;
            }
            xu += '-';
        }

        for (int i = 0; i < num; i++)
            cout << shu[i] << " ";
        cout << endl;

        jj.insert(xu);



        return;
    }
    if(ai[cur]==0)//如果第一个表示0 那么直接进行下一个数字
    {
        shu[num]=0;
        dfs(cur+1,num+1);
    }
    else
    {
        long long sum=0;
        for(int i=cur;i<10;i++)
        {
            sum=sum*10+ai[i];
            double son=sqrt(sum);
            if(son==(int)son)
            {
                shu[num]=sum;
                dfs(i+1,num+1);
            }
        }
    }
}

int main()
{
        do
        {
            memset(shu,0,sizeof(shu));
            dfs(0,0);
        }while(next_permutation(ai,ai+10));   
    cout<<jj.size()<<endl;
    return 0;
}

这是大佬的代码

下面是我的

#include<iostream>
#include<algorithm>
#include<iostream>
#include<set>
#include<string.h>
#include<math.h>
using namespace std;
typedef long long LL;
int qqq;
LL ans2[20];LL ans[100];int a[10]={0,1,2,3,4,5,6,7,8,9};
char ans3[20];int ans5[100];

set<string> ss;

void dfs(int step,int cnt){

	if(step==10){
		for(int i=0;i<cnt;i++) cout<<ans[i]<<"&"<<" ";
		for(int i=0;i<cnt;i++) ans5[i]=ans[i]; 
		sort(ans5,ans5+cnt);
//		int tcnt=0;
//		for(int i=0;i<cnt;i++){
//			while(ans5[i]){
//			ans2[tcnt++]=ans5[i]%10;
//			ans5[i]/=10;	
//			}
//
//		}
       string xu;

        for (int i = 0; i<cnt; i++)
        {
            while (ans5[i])
            {
                int a = ans5[i] % 10;
                ans5[i] = ans5[i] / 10;
                char b = a + '0';
                xu = xu + b;
            }
            xu += '-';
        }

//		for(int i=0;i<tcnt;i++){
//			ans3[i]=ans2[i]+'0';
//		}
//		for(int i=0;i<tcnt;i++) cout<<ans3[i]<<"*"<<" ";
//		cout<<endl;
//		cout<<ans[2]<<"*"<<endl;
		ss.insert(xu);
		qqq++;
		return;
	}
	if(a[step]==0){
		ans[cnt]=0;
		dfs(step+1,cnt+1);
	}
	else{
	LL sum=0;
	for(int k=step;k<=9;k++){
		sum=sum*10+a[k];
		double tans=sqrt(sum);
//		cout<<sum<<"^%^"<<endl;
		if(tans==(int)tans){
			ans[cnt]=sum;
			dfs(k+1,cnt+1);
		}
	}
	}
}


int main(){
	qqq=0;
	do{
		memset(ans,0,sizeof(ans));
		dfs(0,0);
	}while(next_permutation(a,a+10));
		
	cout<<qqq<<" "<<ss.size()<<endl; 
}

思路一开始没有想到。一位一位的搜，搜到平方数存起来。最后处理的时候先排序，然后转换成char型并在每一个数后面加一个“-”。最后将这个字符串放到set中去重。

凑平方数（dfs提高，set，字符串）

全站热榜