企业官网建设流程全解析

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, 3；
• b的位置是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, 3；
• b的位置是3, 5, 9, 10，距离为2, 4, 1；
• c的位置是6, 8, 11, 12，距离为2, 3, 1。

三个数都满足要求。

如何覆盖任意 n

因为n >= 2：

• 如果n是偶数，把所有数两两一组，每组使用两个数模板；
• 如果n是奇数，先取前三个数使用三个数模板，剩下的数一定是偶数，再两两一组使用两个数模板。

每个模板内部的数字只在该模板中出现。把多个模板直接拼接起来时，同一个数字的四个位置整体只会加上同一个偏移量，所以相邻距离不变，仍然合法。

算法步骤

1. 读入n。
2. 如果n是奇数，先输出1, 2, 3的三数模板。
3. 从下一个未使用的数字开始，每两个数字输出一次二数模板。
4. 输出得到的长度为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)。

参考代码

#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cin>>T;while(T--){intn;cin>>n;vector<int>ans;intcur=1;if(n%2==1){inta=1,b=2,c=3;ans.insert(ans.end(),{a,a,b,a,b,c,a,c,b,b,c,c});cur=4;}while(cur<=n){inta=cur;intb=cur+1;ans.insert(ans.end(),{a,b,a,a,b,b,a,b});cur+=2;}for(inti=0;i<(int)ans.size();i++){if(i)cout<<' ';cout<<ans[i];}cout<<'\n';}return0;}