w星球的长老交给小明一个任务:
1,2,3...16 这16个数字分为两组。
要求:
这两组数字的和相同,
并且,两组数字的平方和也相同,
并且,两组数字的立方和也相同。
请你利用计算机的强大搜索能力解决这个问题。
并提交1所在的那个分组的所有数字。
这些数字要从小到大排列,两个数字间用一个空格分开。
即类似:1 4 5 8 ... 这样的答案。
注意,只提交这一组数字,不要填写任何多余的内容。
----------------------------------------
笨笨有话说:
只要一个组的成员确定了,另一个组的成员也就确定了。枚举一个组的成员就可以了。
凭直觉,两个组的成员数目不会差太多吧。
歪歪有话说:
既然求 1 所在的那个组,那只要枚举剩余的成员就可以了。
貌似都是8个成员的可能性很大啊。
答案:
dfs,参数为和,平方和,立方和,剩下的和,剩下的平方和,剩下的立方和,由于按顺序,所以last用来保证按顺序选取。
代码:
#include <iostream> #include <vector> using namespace std; bool vis[17] = {true,true}; vector<int> ans(1,1); void dfs(int last,int s1,int s2,int s3,int ls1,int ls2,int ls3) { if(s1 > ls1 || s2 > ls2 || s3 > ls3) return; if(s1 == ls1 && s2 == ls2 && s3 == ls3) { for(int i = 0;i < ans.size();i ++) { cout<<ans[i]<<' '; } cout<<endl; return; } for(int i = last;i <= 16;i ++) { if(vis[i]) continue; vis[i] = true; ans.push_back(i); dfs(i + 1,s1 + i,s2 + i * i,s3 + i * i * i,ls1 - i,ls2 - i * i,ls3 - i * i * i); ans.pop_back(); vis[i] = false; } } int main() { int a = 0,b = 0,c = 0; for(int i = 2;i <= 16;i ++) { a += i; b += i * i; c += i * i * i; } dfs(2,1,1,1,a,b,c); }