单选题

3.

这道题有问题
首先16位的位图每个像素占两个字节
所以一共是1600*900*2=2880000B
但是接下来就有问题了：1KB应该是$1024(2^{10})B$1024(210)B还是$1000(10^3)B$1000(103)B呢？
查询*：

千字节（英语：Kilobyte，缩写为KB）是计算机数据存贮器存储单位字节的多倍形式。国际单位制 (SI)以1000 ($10^3$103)来定义前缀千，故1千字节表示1字节的1000倍。千字节单位的符号为kB。但在信息技术领域中，尤其是表示主存储容量时，千字节通常表示1024（$2^{10}$210）个字节。这是由数据流的二进制存储法决定的。这种情况下，在表示1024字节时，千字节的符号常记为大写字母K或KB。

然而百度百科又说道：

千字节(Kilobyte)，写作kB或K，一种资讯计量单位，是计算机数据存贮器存储单位字节的多倍形式。现今通常在标示内存等具有一般容量的储存媒介之储存容量时使用。根据国际单位制标准，1kB =
1000B（字节, Byte）。
在信息技术领域中，尤其是表示主存储容量时，此计量单位容易与单位Kibibyte(KiB)混淆。根据按照IEC命名标准，用于二进制存储单位的标准命名是KiB, MiB等，1kiB = 1024B。这是由数据流的二进制存储法决定的。
Linux和macOS X采用国际单位制标准命名。但是，Windows仍然错误地将KiB标记为KB。由于Windows系统仍然以旧的方式记录数据容量，导致混淆已经普遍化，通常Kilobyte也可指Kibibyte，即1KB = 1024B。

这就产生了歧义
标准答案中，1KB按照1024B算
但是我个人认为应该将KB换成KiB，以消除歧义
然而我好像一向都是使用1024的，为什么做题时想到1000去了我也不知道
对啊我平时不是按照1024算的吗

6.

可以看出这个程序会递归$\log_2(n)$log2​(n)次
然而那个常数2很让我头疼
最后想了想：
每一次递归n都会缩小到原来一半
于是乘回这么多个二就是原来的大小
那不还是$n\log n$nlogn嘛
$\log n*n\log n=n\log^2n$logn∗nlogn=nlog2n

7.

实际上牵扯到一个叫表达式树的东西
题目中的式子转化后如下：

把每一次运算看作一个结点，左右孩子便是两个操作数，返回值是得到的结果
后缀形式就是后序遍历输出这个式子

同时后缀形式还有一个特点：
它是用栈储存操作数的
从前往后扫，遇到数就压入栈，遇到操作就把栈顶俩数取出来进行操作，结果再压入栈

8.

简单图：没有重边
连通图：边数一定是3+
四个点：最多连6条边
分类讨论
3条边：
六条边中选三条连，所以$C_6^3=20$C63​=20
有四种情况要去掉：

所以有16种
4+条边：
无论怎么连都是联通的啦
$C_6^4+C_6^5+C_6^6=15+6+1=22$C64​+C65​+C66​=15+6+1=22
$22+16=38$22+16=38

9.

听说是用什么插板法诶！
然而我不会还想着手动DP结果连转移方程都想不出来
百度知道上有一个很好的解释：

插板法是排列组合里用到的方法，一般用来解决几个相同元素分组的办法
比如说要把7个球分成3组，求一共有多少种方法。想象下把7个球排成一列，7个球就有6个间隔，分成三组就需要在这些间隔中插入两个板。那结果就是6选2的组合了。

既然这里可以不分配名额，就假设每个班本身就有一个名额
意味着把11个名额分成4个组
$C_{11-1}^{4-1}=C_{10}^3=120$C11−14−1​=C103​=120
妈妈我终于会做这题了！

11.

最好情况：其中一个数组的所有值都小于另外一个数组，按顺序进入临时数组
（图中连边代表进行比较）

最坏情况：两边你一个我一个地进入临时数组

边数自己数吧

多选题

18.

此处的稳定是指在排序的过程中相等的两个元素不会改变先后顺序
比如一个按照绝对值排序的程序有可能把$5,-3,2,4,1,3$5,−3,2,4,1,3排成$1,2,3,-3,4,5$1,2,3,−3,4,5，这个程序的排序算法就是不稳定的
顺便把时空复杂度也贴出来吧（摘自*，稍作更改以符合中文语法）：
稳定的排序
冒泡排序（bubble sort）— $O(n^{2})$O(n2)
插入排序（insertion sort）— $O(n^{2})$O(n2)
鸡尾酒排序（cocktail sort）— $O(n^{2})$O(n2)
桶排序（bucket sort）— $O(n)$O(n)；需要 $O(k)$O(k)额外空间
计数排序（counting sort）— $O(n+k)$O(n+k)；需要 $O(n+k)$O(n+k)额外空间
归并排序（merge sort）— $O(n\log n)$O(nlogn)；需要 $O(n)$O(n)额外空间
原地归并排序—如果使用目前最佳的版本：$O(n\log^2 n)$O(nlog2n)
二叉排序树排序（binary tree sort）— $O(n\log n)$O(nlogn)期望时间； $O(n^{2})$O(n2)最坏时间；需要 $O(n)$O(n)额外空间
鸽巢排序（pigeonhole sort）— $O(n+k)$O(n+k)；需要 $O(k)$O(k)额外空间
基数排序（radix sort）— $O(nk)$O(nk)；需要 $O(n)$O(n)额外空间
侏儒排序（gnome sort）— $O(n^{2})$O(n2)
图书馆排序（library sort）— 期望时间$O(n\log n)$O(nlogn)； 最坏时间$O(n^{2})$O(n2)；需要 $(1+\varepsilon )n$(1+ε)n额外空间
块排序（block sort）— $O(n\log n)$O(nlogn)
不稳定的排序
选择排序（selection sort）— $O(n^{2})$O(n2)
希尔排序（shell sort）— 如果使用目前最佳的版本（缩小增量序列为3-光滑数¹） $O(n\log^2 n)$O(nlog2n)
克洛弗排序（Clover sort）— 期望时间$O(n)$O(n)， 最坏情况$O(n^{2})$O(n2)
梳排序— $O(n\log n)$O(nlogn)
堆排序（heap sort）— $O(n\log n)$O(nlogn)
平滑排序（smooth sort）— $O(n\log n)$O(nlogn)
快速排序（quick sort）— 期望时间$O(n\log n)$O(nlogn)， 最坏情况$O(n^{2})$O(n2)；对于大规模随机数组一般视作已知最快的比较型排序
内省排序（introsort）— $O(n\log n)$O(nlogn)
耐心排序（patience sort）— 最坏情况时间$O(n\log n+k)$O(nlogn+k)，需要额外的 $O(n+k)$O(n+k)空间，还需要找到最长的递增子序列（longest increasing subsequence）

21.

贪心吧
每次选能够换取最多0的操作
操作应该符合交换律和结合律

23.

我竟然在初赛用了复赛算法！

首先这就是裸的最小割²
然后最小割=最大流³
手动跑最大流（展现人类智慧的时候到了！）
然后枚举呗

后面的等我做完再说吧

---

1. 若一正整数的素因数均不大于B，此整数即为B-光滑数。 ↩︎

2. 切断几条边，让两个点不连通，被切断边的权值和最小的方案就是最小割 ↩︎

3. 自行百度 ↩︎