AtCoder Beginner Contest 230

solved: 5/8

A

  如果x>=42那就++, 然后输出补全为三位数有前导0的x

B

  模拟

C

  模拟

D

  先按右端点升序排序, 再按左端点升序

  可以发现每一拳都打在右端点是最优的, 证明的话可以发现, 假设我有某一拳打中间, 前面已经全部被摧毁了, 覆盖到后面的区域肯定不如右端点广

  然后贪心地打拳就可以了

E

  整除分块, 对于$\lfloor \frac{n}{i} \rfloor$, 可以发现他的值是一段一段连续的, 下降的

  这个值也是可以算的, 假设当前枚举到i, 那么和i的值相同的区间就是覆盖的区间就是$[i, \frac{n}{\lfloor \frac{n}{i}\rfloor}]$

  当前的值是$\lfloor \frac{n}{i} \rfloor$, 设为x, 那么满足$\lfloor \frac{n}{R} \rfloor=x$的最大的R就是$\lfloor \frac{n}{x} \rfloor$

  这个R的值是可以证明的

  $$

    Rx<=n, R>=\frac{n}{x}

  $$

上一篇:整除分块学习笔记


下一篇:Catalan (卡特兰数)