9.

​ 当N为偶数时，先取前两个数字，比较之后，大的为max,小的为min。

​ 后面的数字两两一组，组内比较之后，大的和max比较，小的和min比较。

​ 当N为奇数时，max和min都取第一个数字，后面的数字两两一组，组内比较之后，

​ 大的和max比较，小的和min比较。

​

偶数需要比较的次数为：1+（N-2) / 2 * 3 = 3 / 2 * N - 2

奇数需要比较的次数为（N-1）/ 2 * 3.

​

​ 验证后 可得答案是A

11.

​ n个节点的边数范围：（n-1）– (n*(n-1)/2)

​ 所以边数可为：3 4 5 6 其中3 4有异构，所以有6种结构。

12.
$$ n个元素构成元素的子集数为:2^n $$

这个可以这样理解：构造集合时，对于每个元素，都可以选或者不选， 分步完成。

10个元素选7个和选3个方案数是一样的。 10 * 9 * 8 / 3！=120.

答案为：120 / 1024= 15 / 128

13.
$$ 10000 = 2^4*5^4 $$

    和10000公约数为2的数字个数：10000 / 2 = 5000

    和10000公约数为5的数字个数：10000 / 5 = 2000

    和10000公约数为10的数字个数：10000 / 10 = 1000

    其中第三个集合为前两个集合的交集，所以和10000互质的数字个数为：

    10000 - （5000+2000-1000）= 4000



14. 代入即可



16. ​   由题意得，丙去一定丁没去，接下来再做假设即可。

​   假设下雨的话，乙去或者不去都会有矛盾。

​   所以可得没下雨，在假设没下雨乙去，也有矛盾，所以没下雨且乙没去。

​   若此时假设甲不去，也有矛盾，所以甲去了。

17. ​     先算1-2000范围内的 ：

​               只有一位有8的：9 * 9 *  2 * 3

​               有两位有8的：9 * 2 * 3

​               有三位有8的： 2

​               2000-2018范围含8的：2

计算得：544


19.  题意为统计 %15==1的完全平方数   逐一验证即可

20. 递推即可。  
$$
f(i,j) = f(i-1,j) - f(i,j-1) + f(i-1,j-1)
$$
可以把 f(i,j) 理解成第 i 行 第 j 列的值。

第 i 行 第 j 列的值和左上角，左，上的值有关。

根据关系式推导就可以得到结果。

推导过程如下：

0 1 2 3 4 5 6
1 0 3 2 5 4 7
2 -1 4 1 6 3 8
0 1 2 3 4 5 6
1 0 3 2 5 4 7
2 -1 4 1 6 3 8



可以将推导过程转换成如下代码：

```c++
//2018 初赛 20
#include<iostream>
using namespace std;
int f[10][10]; 
int main()
{
    for(int i=0;i<=5;i++)
    {
        for(int j=0;j<=6;j++)
        {
            if(i==0)f[i][j]=j;
            else if(j==0)f[i][j]=i%3;
            else
                f[i][j]=f[i-1][j]-f[i][j-1]+f[i-1][j-1];
            cout<<f[i][j]<<" ";
        }
        cout<<endl;
    }
    return 0;
}
```



21. 代入即可

22. 第一空：和判断质数的思路类似，所有约数在除数为1-sqrt(n）的时会在除数和商的位置都出现。

第二空：除数和商都是约数，都要进数组，但是要避免重复。

第三空：规定：任何数和0的最大公约数都是本身。

第四空：欧几里得求最大公约数法：

```c++
int gcd(int a, int b) {
    if (b == 0)  return a;
    else  return gcd(a, a %b);
}
```

相关知识：

最小公倍数的求解：当得到 a 和 b 的最大公约数 z 后，可以得到 a 和 b 的最小公倍数是 (ab / z)，由于 ab 在实际计算中有可能溢出，因此更恰当的写法是 **(a / z \* b)** 。

第五空：类似照相问题，每个人都和身后的人照照片。

            每个数字都和后面数字求最大公约数。求出来的结果，加到结果变量上。

23.

1.a[x]=i    记录元素的位置

2. i+1  右指针当然指右边
3. R[a[i]]   删除操作 和下面的操作对称
4. a[i]  删除操作 和上面的操作对称
5. R[i]  输出结果