B. Different Distances 题解题意要求构造一个长度为4 * n的数组使得每个整数1, 2, ..., n都恰好出现4次对于每个数x设它四次出现的位置为p[x,1] p[x,2] p[x,3] p[x,4]则下面三个相邻距离必须两两不同p[x,2] - p[x,1] p[x,3] - p[x,2] p[x,4] - p[x,3]题目保证一定存在答案输出任意一种即可。构造思路关键是找到可以独立使用的小模板。两个数的模板对于两个数a, b可以输出a b a a b b a b检查a的位置是1, 3, 4, 7距离为2, 1, 3b的位置是2, 5, 6, 8距离为3, 1, 2。两者的三个距离都两两不同。三个数的模板对于三个数a, b, c可以输出a a b a b c a c b b c c检查a的位置是1, 2, 4, 7距离为1, 2, 3b的位置是3, 5, 9, 10距离为2, 4, 1c的位置是6, 8, 11, 12距离为2, 3, 1。三个数都满足要求。如何覆盖任意 n因为n 2如果n是偶数把所有数两两一组每组使用两个数模板如果n是奇数先取前三个数使用三个数模板剩下的数一定是偶数再两两一组使用两个数模板。每个模板内部的数字只在该模板中出现。把多个模板直接拼接起来时同一个数字的四个位置整体只会加上同一个偏移量所以相邻距离不变仍然合法。算法步骤读入n。如果n是奇数先输出1, 2, 3的三数模板。从下一个未使用的数字开始每两个数字输出一次二数模板。输出得到的长度为4 * n的数组。正确性证明引理 1二数模板a b a a b b a b对数字a和b都合法。证明a的四次出现位置为1, 3, 4, 7三个相邻距离为2, 1, 3两两不同。b的四次出现位置为2, 5, 6, 8三个相邻距离为3, 1, 2两两不同。因此二数模板合法。引理 2三数模板a a b a b c a c b b c c对数字a, b, c都合法。证明a的四次出现位置为1, 2, 4, 7距离为1, 2, 3。b的四次出现位置为3, 5, 9, 10距离为2, 4, 1。c的四次出现位置为6, 8, 11, 12距离为2, 3, 1。每个数字的三个距离都两两不同因此三数模板合法。引理 3合法模板拼接后模板中每个数字仍然合法。证明拼接会让某个模板中所有位置同时加上同一个偏移量。对于任意数字x它的四个位置都在同一个模板内因此三个相邻距离不会改变。所以拼接不会破坏合法性。定理算法输出的数组满足题目要求。证明算法把1..n划分成若干个大小为2或3的组。根据引理 1 和引理 2每个组内构造出的模板都是合法的根据引理 3所有模板拼接后仍然合法。每个数字恰好属于一个组并在对应模板中出现4次因此最终数组中每个1..n都恰好出现4次。所以算法正确。复杂度分析每个测试用例只输出4 * n个数。时间复杂度O(n) 空间复杂度O(n)如果边生成边输出也可以做到额外空间O(1)。参考代码#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cinT;while(T--){intn;cinn;vectorintans;intcur1;if(n%21){inta1,b2,c3;ans.insert(ans.end(),{a,a,b,a,b,c,a,c,b,b,c,c});cur4;}while(curn){intacur;intbcur1;ans.insert(ans.end(),{a,b,a,a,b,b,a,b});cur2;}for(inti0;i(int)ans.size();i){if(i)cout ;coutans[i];}cout\n;}return0;}