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

待填坑。

 

说点什么

avatar
50
  Subscribe  
提醒