A30951. 势均力敌用 n （> 2） 个不同的个位数字组成一个 n 位数，显然有 n! 个不同的结果。可以证明，这 n! 个数字可以被分为势均力敌的两组 —— 即平方和相等、且个数也相等的两组。本题就请你用程序验证一下这个结论。因为本题是一道简单题，所以规模很小，只考虑 n ≤ 4 的情况。（2 < n ≤ 4），随后一行给出 n 个不…
填空题
中等
知识点
题目描述
势均力敌
用 n （> 2） 个不同的个位数字组成一个 n 位数，显然有 n! 个不同的结果。可以证明，这 n! 个数字可以被分为势均力敌的两组 —— 即平方和相等、且个数也相等的两组。
本题就请你用程序验证一下这个结论。
因为本题是一道简单题，所以规模很小，只考虑 n ≤ 4 的情况。
时间限制：4000 内存限制：262144
输入
输入第一行给出正整数 n（2 < n ≤ 4），随后一行给出 n 个不同的、在区间 [1, 9] 内的个位数字，其间以空格分隔。
输出
将所有组成的 n! 个不同的 n 位数分为平方和相等、且个数也相等的两组。但你只需要输出其中一组就可以了。每个数字占一行，共输出 n!/2 行。
注意：解可能不唯一，输出任何一组解就可以。
样例输入
3
5 2 1
样例输出
125
512
251
参考答案
#include<bits/stdc++.h>
using namespace std;
vector<int> v;
long long int n,a[10],mid=0;
bool flag(int s,int x){ //判断数字s里面有没有x
while(s){
if(s%10==x) return true;
s/=10;
}
return false;
}
// 找所有数字全排列
void dfs1(int cnt,int s){ //找到第i个数字，
if(cnt==n){ //找完了
v.push_back(s);
} else {
for(int i=0;i<n;i++){
//先判断有没有已经使用过a[i]
if(!flag(s,a[i])){ //没使用过
dfs1(cnt+1,s*10+a[i]);
}
}
}
}
int ans[100];
bool f=false; //标志变量，找到了没
//暴力搜索，找到
void dfs2(int i,int cnt,int sum){
if(f) return;
if(cnt==v.size()/2){ //找完了
if(sum==mid){
f=true;
}
}else { //继续找
for(;i<v.size()&&!f;i++){
ans[cnt]=v[i];
dfs2(i+1,cnt+1,sum+v[i]*v[i]);
}
}
}
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
dfs1(0,0); //找出所有
sort(v.begin(),v.end()); //排序 需要按字典序输出
for(int i=0;i<v.size();i++) //求总平方和
mid+=v[i]*v[i];
mid/=2;//一半
dfs2(0,0,0); //找一半
for(int i=0;i<v.size()/2;i++)//输出
cout<<ans[i]<<' ';
}
上一题
下一题