凑平方数
题目 凑平方数
思路分析
这样不是很好暴力 ……
有个想法 能不能从平方数入手
既然预处理出来了所有的平方数 那试着把这些所有的平方数进行排列组合 最后如果满足0~9的所有数最多出现一次 就算一种合法方案？
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long LL;
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
for(LL i=1;i*i<9876543210LL;i++){
cout<<i*i<<endl;
}
return 0;
}
终端不会显示全部的输出（当输出过多时） 可以用下列命令将输出放入txt文件 进行检查
C:\code\c++\lanqiao>7th.exe > output.txt
数全提出来了 排列组合 dfs
……
程序没有输出并且返回了错误码 3221225725（在 Windows 环境中，这通常是因为访问违规或内存溢出导致的崩溃），这意味着可能存在几个问题。一是可能是代码中存在逻辑错误或效率问题导致内存消耗过大，二是可能是递归过深导致栈溢出。
爆系统栈了……
得想办法优化
首先 这些数不全是合法的 比如 100是个平方数 但就它本身而言 0就出现了两次 显然不满足 所以可以提前把这些数筛掉
其次 组合时 只需要单纯检查长度为10的字符串是否0~9只出现一次 无须考虑什么逗号
若长度大于10 或者 发现组合后不满足每个数只出现一次 就可以直接剪枝
只有长度恰好为10 且每数只出现一次的字符串才是合法方案
一个还算比较常规的dfs吧
代码实现
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long LL;
vector<LL> alls;
LL N,ans;
bool check(string s){
int vis[10]={0};
for(char c:s){
int t=c-'0';
vis[t]++;
if(vis[t]>1)
return false;
}
return true;
}
void dfs(int st,string num){
int len=num.length();
if(len>10 || !check(num))
return;
if(len==10 && check(num)){
ans++;
return;
}
for(int i=st;i<N;i++)
dfs(i+1,num+to_string(alls[i]));
}
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
for(LL i=0;i*i<9876543210LL;i++){
LL tmp=i*i;
if(check(to_string(tmp)))
alls.push_back(tmp);
}
N=alls.size();
dfs(0,"");
cout<<ans<<endl;
return 0;
}
💬 评论