简答题
偏难
#7563
势均力敌 用 n (> 2) 个不同的个位数字组成一个 n 位数,显然有 n! 个不同的结果。可以证明,这 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
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <bits/stdc++.h>
using namespace std;
int a[10005];
vector<int> v;
long long num = 0, n;
long long cnt, flag;
bool st[10005], stt[10005];
long long pa[10005];
void dfs(int x)
{
if (x == n) v.push_back(num);
for (int i = 0; i < n; i++)
{
if (!st[a[i]])
{
int fa = num;
st[a[i]] = true;
num = num * 10 + a[i];
dfs(x + 1);
num = fa;
st[a[i]] = false;
}
}
}
void dfs1(int x, int p)
{
if (flag == 1) return;
if (x == (int)v.size() / 2)
{
num = 0;
for (int i = 0; i < x; i++) num += pa[i] * pa[i];
if (num * 2 == cnt)
{
for (int i = 0; i < x; i++) cout << pa[i] << '\n';
flag = 1;
return;
}
}
for (int i = p; i < (int)v.size(); i++)
{
if (!stt[i])
{
stt[i] = true;
pa[x] = v[i];
dfs1(x + 1, i + 1);
stt[i] = false;
pa[x] = 0;
}
}
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
dfs(0);
for (auto t : v) cnt += t * t;
dfs1(0, 0);
}</pre>
这道题暂未补解析。