数字划分

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);
}

 

上一篇:$Poj1934\ Trip$ 线性$DP+$搜索


下一篇:2019/2/1Python LS1下午的数组(列表)