阿里笔试题解（2020.4.17场）算法,笔试yashem66-

题目一

题干

给定n，构造长度为n的排列，使得满足
$i<j<k$

i<j<k的
$a_i,a_j,a_k$

ai​,aj​,ak​，不出现
$a_k+a_i=a_j*2$

ak​+ai​=aj​∗2的情况。

题解

暴力解法得到
$n=3$

n=3到
$n=8$

n=8部分的答案，观察可知，奇数部分和偶数部之间不会互相干扰（因为当
$a_i$

ai​和
$a_k$

ak​分别为奇数和偶数时，奇数加偶数等于奇数，一定不会有满足
$a_i+a_k=a_j*2$

ai​+ak​=aj​∗2的
$a_j$

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; }  

题目二

题干

给一个带权环路，随机删一条边，使从a到b的最短路径长度变化的可能性有多大（分数表示）。

题解

放代码看看就行了，应该不需要题解吧。需要讲解一下的评论吧。

满分代码