CF55D

传送门

简要题意

定义一个正整数为美丽的当且仅当这个数能被所有非零位上的数整除。
给定$l$,$r$,求$l$到$r$中有多少数是美丽的。
多组数据,$l,r\le 9\times 10^{18}$

约瑟夫问题的一些解法

约瑟夫问题:

有n个人,编号为$1..n$,从第1个人开始报数,报到m的人离开,求最后的幸存者。

算法1(Simple算法):

用队列模拟,可以算出每一次出队的人。

时间复杂度$O(nm)$

当n很小而m很大时,可以通过取膜将$O(nm)$优化为$O(n^2)$

ARC082C ConvexScore

简要题意

给定n个点,定义一个凸多边形包含点数s为:这个凸多边形覆盖的点数-这个凸多边形的角数(每一个角$<180°$)

设总点集为A。
这个凸多边形的分值为为:$2^s$

求由这n个点构成的所有凸多边形的分值和$mod 998244353$

ARC082D Sandglass

题意:有一个沙漏由A,B两个杯子组成。一共有X克沙子。
每秒会有一克沙子从上杯子流到下杯子,直到流完为止。

一共会有k次翻转杯子,第i次翻转杯子会在第 $r_i$ 秒。

有q组询问,每组形如 $t,a$ ,表示一开始A杯子在上,里面有a克沙子(B杯子里有 $X-a$ 克沙子),求第t秒的时候A杯子里有多少沙子。
$q,k\le 10^5$

|

博客使用Disqus作为评论系统