题目大意是:
不重复不遗漏的使用0-9,拼凑成若干个完全平方数(0除了单独成数之外不可位于开头),询问一共有多少种拼法。
当时在考场我被第一题炸的有点懵逼,导致这题也思考了好久。
一开始我的思路是穷举0-9,然后拆分检验,后来发现复杂度过高且实现太难。
上了个厕所之后才反应过来要打表,于是思路修改为:
获取完全平方数表,因为要不重复,所以这个数最大不可能超过1e10,所以只要存储并按位拆分1e10以内的完全平方数即可。
接下来就只需要走递归的套路了,检验,添加,继续尝试,失败还原。
代码如下:
#include <iostream> #include <vector> using namespace std; typedef long long ll; vector<ll> nlist; vector<vector<ll>> el; ll nowl[10]; ll times; //打平方数表 void getnlist() { for (ll i = 0; i < 100000; i++) { ll temp = i*i; ll tl[10]; memset(tl, 0, sizeof(tl)); while (temp > 0) { //验重 if (tl[temp % 10]) break; tl[temp % 10]++; temp /= 10; } if (temp) continue; nlist.push_back(i*i); vector<ll> tempel; for (ll j = 0; j < 10; j++) { tempel.push_back(tl[j]); } el.push_back(tempel); } } //尝试添加表中第id号数字 void testadd(int id) { int tempnow[10]; for (int i = 0; i < 10; i++) { tempnow[i] = nowl[i]; if (tempnow[i] && el[id][i]) return; else tempnow[i] += el[id][i]; } bool acflag = true; for (int i = 0; i < 10; i++) { if (tempnow[i] == 0) { acflag = false; break; } } if (acflag) { times++; return; } for (int i = 0; i < 10; i++) nowl[i] = tempnow[i]; for (int j = id + 1; j < el.size(); j++) { testadd(j); } for (int i = 0; i < 10; i++) { nowl[i] -= el[id][i]; } } int main() { getnlist(); //0可以单独作为平方数 el[0][0] = 1; for (int i = 0; i < el.size(); i++) { testadd(i); } cout << times << endl; return 0; }
最终答案:300