Exam Conclusion

Before：This is my conclusion of the Exams.I will upd it any time to improve myself.

Score & Rank

Exam 1 : 130/300 4/39
Exam 2 : 30/300 26/39
Exam 3 ：100/300 17/39

You will see that I didn’t do a good job in Exam 2.I believe that at least I should get 130/300 with a rank of 9/39 in Exam 2,but something terrible happens.
I will explain it later.

Complication of Exam 1

Problem 1 is a model exercise of the Chunking Idea.

Problem 2 is quite easy.

Problem 3 talks about a new way of Matrix Compression called CSR.It’s also quite easy if you understand the meaning of the method.

Complication of Exam 2

Problem 1 ：D*mn!I really hate it!Quite easy one——Postorder Traversal of Binary Tree.
但是问题出在这里，在模拟栈的时候，我选择构建一个Node类型的数组，理论上在栈的模拟递归中我们一般对指针进行操作，而不信邪的JaneZ坚定地认为直接放Node也没啥问题。
But:我们知道树的析构是很讲究的，先析构左树，再析构右树，最后删自己，但是如果一旦将Node作为数组对象时，在函数生命周期结束时，我需要按照数组的下标顺序一个一个析构对应的Node，这就会使得原本的析构顺序完全乱了套，出现了大规模的Invalid Read（这很坏了）。但数组里如果存的时Node指针,就不会出现这个问题，你是没办法delete 一个没有动态分配的指针的，对吧。所以以RE收场了一道签到题，非常不甘心🥱

Problem 2 ：很难的算法题，主要是从平均值联想不到二分答案，想到了在使用单调队列就比较自然了。

Problem 3 ：更像是一道阅读材料的题目，回忆了shared_ptr 和weak_ptr:

• shared_ptr 允许多个所有者共享实际对象，通过引用计数管理内存

• weak_ptr 不增加强引用计数，用于解决循环引用问题

Complication of Exam 3

Problem 1 ：超级恶心的二维树状数组区间查询区间修改板子题（是的又是板子题）没啥好说的，写了个暴力拿了50分

Problem 2 ：ST表+位运算，真的小丑，ST表倒是写出来了但是卡在了不知道一个异或的性质，导致预处理炸到了O($N^2$)
在这里回忆一下位运算：

• & 与 只有两个对应位都为1时才为1

• | 或 只要两个对应位中有一个1时就为1

• ^ 异或 只有两个对应位不同时才为1
  异或有个性质，2次异或同一个数结果不变，也就是说：a^bb = a
  即：若a ^ b = x，那么有x^b = a（破防了就是这个不知道不然早AC了，还是基础太不扎实了）

Problem 3 ：下午+晚上做了详细的分析，详见Rust RefCell机制