首页 › 题库 › C/C++编程考级 › C/C++编程三级 › 简答题
简答题 偏难
#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 &lt;bits/stdc++.h&gt; using namespace std; int a[10005]; vector&lt;int&gt; 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 &lt; 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 &lt; x; i++) num += pa[i] * pa[i];         if (num * 2 == cnt)         {             for (int i = 0; i &lt; x; i++) cout &lt;&lt; pa[i] &lt;&lt; '\n';             flag = 1;             return;         }     }     for (int i = p; i &lt; (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 &gt;&gt; n;     for (int i = 0; i &lt; n; i++) cin &gt;&gt; a[i];     dfs(0);     for (auto t : v) cnt += t * t;     dfs1(0, 0); }</pre>
这道题暂未补解析。