Codeforces AIM Tech Round 5 (Div. 1 + Div. 2) 解题报告

题目链接：Codeforces AIM Tech Round 5
CF终于上分了QAQ

A – Find Square

模拟。

B – Unnatural Conditions

这是一个构造题，假设$S(a),S(b)$都非常非常大，则可以满足$S(a) \geq n, S(b) \geq n$，那么什么情况下是$S(a+b)$会非常小（小于m）呢？很显然是在有进位的时候——如果所有的位全部进位成0，只留下第一位是1，这种情况一定满足$S(a+m) \leq m$。

C – Rectangles

题目保证了$n$个矩形中有$n-1$个有公共点，也即是说去掉其中一个矩形就可以得到$n-1$个矩形的公共交，在这个公共交里随便找个点输出就是最后的答案。
我们需要确认是去掉那个矩形，假设第$i$个矩形是一个异类，那么它前面所有的矩形一定和后面所有的矩形有公共交，否则前面所有矩形和后面所有矩形求公共交为空集，所以维护前缀交和后缀交即可。

D – Order book

我们先在草稿纸上列一些数据。如果所有ADD对应的p所组成的有序集合是这样的:
$$\{1,2,3,5,6,7,8,9,11\}$$
那么假如2是Best Buy，那么Best Sell 一定是3，并且2前面的一定是buy，3后面的一定是sell。所以我们解题关键就是维护这个分解位置，即Best Sell和Best Buy。然后对于每个ACCEPT，要分类讨论：

• $b_{buy} = p$ 说明这个ACCEPT一定是Buy
• $b_{sell} = p$ 说明这个ACCEPT一定是Sell
• $b_{buy} < p < b_{sell}$ 说明这个ACCEPT可能是Buy可能是Sell
• $b_{buy} > p | p > b_{sell}$ 非法ACCEPT

这样只有第三种情况需要把最后的可能性翻倍。对于每一次操作，删除ACCEPT的p并且将Best Buy和Best Sell设为最接近p的上下两个值。（这里就用到了set迭代器的给力功能）
最终我们可以确定Best Buy和它的左边都是Buy，Best Sell和它的右边都是Sell，那么中间还有未确定的元素，根据记数原理，如果还剩下$m$个数，则需要把可能性乘以$m+1$。

E – Restore Array

硬核构造题，按照官方的题解补了下题，但是有些细节还是不能理解。
找到一个最大的元素作为$b_n$（即$b$数列的最后一个元素，如果不是最后一位则可以通过切割移动来实现），然后$a_i = \sum_{j = i}^{n – 1} b_j +  2\cdot b_n $ 。
我觉得出题人是想试图把 $b_i = a_i \mod a_{i + 1}$ 转化成$b_i = a_i – a_{i + 1} \quad (b_i < a_{i + 1})$，所以当$a_i > b_{max}$ 的时候可以满足这个条件，当然$b_i$不能全为0。我不能理解的有两点，第一是为什么是加上$2 \cdot b_n$，第二点是为什么$a_n = b_n$，这两点之间可能存在联系，也就是更改$a_n$之后$2 \cdot b_n$这一项也会随之更改？
有几个点要注意的是最大值的前一位如果和最大值相等，这个最大值是不能取的，因为此时$a_n – 1 = 3 \cdot b_n, b_{n – 1} \neq a_{n – 1} \mod a_n = 0 $。所以面对这种情况需要单独判断，此时又要分两种情况，一种是全为0，这是可构造的，否则是不可构造的。

F,G,H

待填坑。