AtCoder ABC 273 复盘

A A Recursive Function

模拟，递归、递推、累乘都可以。我用的累乘。

AC Code

B Broken Rounding

也是模拟，每次将 \(X\leftarrow X\div 10^{i-1}\) 后判断 \(X\bmod 10\) 是否 \(\geq 5\)，若是，\(X\leftarrow X+10\)；若不是，不进行操作。最后再将 \(X\div 10\) 输出。

AC Code

C (K+1)-th Largest Number

典型的二分。每一次二分出最小的大于等于 \(a_i\) 的数的下标 \(L\)，然后用一个数组记录答案。

AC Code

D LRUD Instructions

大型模拟。需要用 map 存储障碍物，然后每次移动时 \(O(\log N)\) 的查询路径上距离起点最近的障碍物，并移动至障碍物前；如无障碍物，直接按输入移动。总体时间复杂度 \(O((N+Q)\log N)\)。

AC Code

E Notebook

很显然，如果直接存储直接恢复会爆炸（\(\color{#052242}\texttt{TLE}\) 和 \(\color{#052242}\texttt{MLE}\)）。于是我们想到一件事，能否在一个一维数组上完成所有的操作？答案是肯定的，我们可以采用类似 list+stack 的方法完成。

1. 插入，插入时即向类链表 lst 的尾部插入 \(x\)，向类栈 stk 压入 \(x\)。

2. 删除，删除即删除链表尾部。

3. 保存，将 map \(save_x\leftarrow\) 栈顶指针（下标）。因为以后的操作均在下标为 \(x\) 的元素之后（即在栈顶之上）操作，所以可以通过将栈顶指针指回 \(save_x\) 实现恢复。

4. 恢复，将栈顶指针指向 \(save_x\)。

每次输出栈顶即可。

AC Code