第二题比较简单数据也水，题解就先不放了，说一下第一题吧。
题干：
构造一个长度为n的排列，使得对于任意的1<=i<j<k<=n，不存在ai+ak=2*aj。
---
题解：
先暴力做一下，0分，不过用暴力的程序找到了一些性质：若“1 5 3 2 6 4”该排列满足题目中要求的性质，则序列"1 9 5 3 11 7"（第1 5 3 2 6 4个奇数）和序列"2 10 6 4 12 8"（第1 5 3 2 6 4个偶数）均满足题目要求中的性质。
稍加思索可以发现，排列中的奇数部分和偶数部分不会互相影响（因为当ai和ak的奇偶性不相同时，ai+ak一定是奇数，一定没有满足条件的aj）。所以构造时可以奇数部分和偶数部分分开构造，然后再拼接在一起。比如上面提到的例子中的序列"1 9 5 3 11 7"和"2 10 6 4 12 8"拼在一起形成的新排列"1 9 5 3 11 7 2 10 6 4 12 8"就是n=12时的答案。
一步一步往下拆分，就是分治的思路。
不懂的地方可以看看代码，再不懂的话可以把代码拷到本地然后把生成的过程输出一下。
#include <cstdio>
using namespace std;
const int maxn=int(1e6)+11;
int n;
int a[maxn];
void solve(int l,int r,int mark) {
if(l==r) {
if(mark) a[l]=1;
else a[l]=2;
return;
}
int mid=(l+r)>>1;
solve(l,mid,1), solve(mid+1,r,0);
for(int i=l;i<=r;++i)
a[i]=a[i]*2-mark;
return;
}
int main() {
scanf("%d",&n);
solve(1,n,0);
int i;
for(i=1;i<=n;++i) printf("%d ",a[i]/2);
putchar('\n');
return 0;
}
全部评论
(4) 回帖