提示：这篇文章也在作者的博客上发布，协议为 CC BY-NC-ND 4.0。
在十分紧张的情况下幸运完成了P2，于是结合考试中做的一些笔记与大家略微分享我的思路
由于大家编写MIPS代码时主要以翻译为主，且选择工具链不一（指各种语言），所以本文将只展示思路，以伪代码形式呈现，并将我遇到的MIPS难点单独列出
和《算法设计与分析》考试是笔试一个道理www
T1：P2_L2_merorder_2023
Main Idea
由于两个序列均为已经排好序的不下降数组，所以在编写程序时只需要遍历两个数组一遍，将较小者逐一合入新数组即可
Pseudo Code
输入：两个长度分别为m，n的不下降数组a[] b[]
输出：一个长度为(m+n)的数组ans[]，为所求合并后的数组 \[ \begin{aligned} &i\leftarrow 0;\\ &j\leftarrow 0;\\ &while\ (i<n\ \&\&\ j<m)\ do\\ &\quad while\ (A[i]<=B[j])\ do\\ &\qquad print\ (A[i++]);\\ &\quad end\\ &\quad while\ (A[i]>B[j])\ do\\ &\qquad print\ (B[j++]);\\ &\quad end\\ &end\\ &while\ (i<n)\ do\\ &\quad print(A[i++]);\\ &end\\ &while\ (j<m)\ do\\ &\quad print(B[j++]);\\ &end\\ \end{aligned} \] 复杂度分析：i和j需要遍历完两个数组一遍，所以复杂度为O(n+m)
注意点：
这种写法由于是while套while，会导致lable上增加难度，建议提前在代码中为不同的while注释不同的名字，方便程序写作，如：
1
2
3
4
5
6
7
8
9
10
11while(){
//while1
while()/*do something*/;
//while2
while()/*do something*/;
//while3
}
while()/*do something*/;
//while4
while()/*do something*/;
//while5在实际写作中，因为不考虑效率要求，也可以将内层循环中的while改为if，设置标签时会更简单一些
本题数据范围较小，所以也可以使用类似计数排序的方法，期望复杂度和遍历两个数组一致
说出来给大家乐呵一下，在下
.space忘乘4了，de了好一会儿🙏
T2：P2_L1_asteroids_2023
题目编号 1122-1162
本题的代码已经给出来啦~而且方法很巧妙，对着翻译就好！
甚至可以不看题面
没有想到可以补充的地方，过~
T3：LeetCode: 390. 消除游戏
为大家找到了代码的提交入口（误）
除用标程的递归外（标程的参数可以减少至一个），本题也可以使用位运算完成
Main Idea
将这n个数标记为0…n-1
若当前为奇数轮，则删除操作为从0开始，隔一个删除一个，可以等效为“删除所有二进制末尾为0的数字“，答案当前位的二进制赋1
若当前为偶数轮，则删除操作为从最后一个数开始，隔一个删除一个，可以等效为”删除所有二进制下末尾数与最大数末位数相同的数字“，答案当前位的二进制赋最大数末位数的反
换种说法，就是： \[ (ans)_2[i]=\left\{ \begin{aligned} &1&i\equiv 0(mod\ 2)\\ &(n)_2[i]&i\equiv 1(mod\ 2)\\ \end{aligned} \right. \] 注意，在上式中：
i代表的是二进制第i位，奇数轮的i为偶数，偶数轮的i为奇数
编号从0开始，所以 \[ (n)_2[i]==\sim (n-1)_2[i] \]
我们的编号是从0开始的，最后别忘了将答案加一
Pseudo Code1
\[ \begin{aligned} &ans\leftarrow 0;\\ &for\ i\ from\ 0\ to\ \log(n)-1\ do\\ &\quad if\ (i\&1)\ then\\ &\qquad ans\leftarrow ans\ |\ (2^i\ \&\ n);\\ &\quad else\\ &\qquad ans\leftarrow ans\ |\ 2^i;\\ &\quad endif\\ &end\\ &ans\leftarrow ans+1;\\ &print(ans); \end{aligned} \]
复杂度分析：i从0循环到logn-1，整体复杂度为O(log)
Pseudo Code2
或者我们换一种实现方法，将for循环拆开 \[ \begin{aligned} &mod\leftarrow 2^{[\log(n)]};\\ &ans\leftarrow (n\ |\ 1431655765);\\ &ans\leftarrow ans\mod mod;\\ &ans\leftarrow ans+1;\\ &print(ans);\\ \end{aligned} \] 其中：
mod为n二进制下最高位1对应的数
\[ 1431655765=2^0+2^2+......2^{2k} \]
复杂度分析：O(1)
(家人们谁懂啊 把nlog的朴素方法优化到O(1)，真的是一件很酷的事~)