Oql's Blog

题目链接

loj

题面

bzoj5404

题意

$m$ 张凳子排成一列，从 $1$ 开始编号。

$n$ 个人，第 $i$ 个人能坐在不比 $l_i$ 大的凳子上，或者不比 $r_i$ 小的凳子上。

问最少有多少个人没地方坐。

$n,m\leq 2\times 10^5,l_i<r_i$

题意

$n$ 组人，第 $i$ 组 $a_i$ 个人，需要安排在一个$m$ 个座位的，编号为 $0,1,\cdots,m-1$ 的圆桌上，每个位置只能最多做一个人。

其中第 $i$ 组的人能坐在 ${ l_i,(l_i+1)%m,(l_i+2)% m,\cdots,r_i}$的位置上。

问是否存在一种合法的安排。

$n\leq 10^5,m\leq 10^9$

题意

有 $n$ 个班，每个班 $a_i$ 名学生，共做了 $b_i$ 杯奶茶。每个学生最多喝一杯奶茶，但不能喝本班的。问最多有多少个学生能喝到奶茶。

$n\leq 10^6,0\leq a_i,b_i\leq 10^9$

图论中一个比较有趣的定理。

题意

一个随机的排列 $p$，一开始所有位置都不能用。每次随机加一个位置使其变得可用，然后求当前最长上升子序列的长度。

$n\leq 50000,T\leq 3$

时限 $14s$

2019 Multi-University Training Contest 5

Good Numbers

题意

定义一个正整数 $n$ 是好数当且仅当 $n$ 在8进制表示下所有的数码出现的次数为**3的倍数(出现0次亦可)**。

有多少个 $k$ 位的8进制数（不含前导0），满足这个数是好的，且是 $p$ 的倍数。对 $10^9+9$ 取模。

例如：当 $k=3,p=2$ 时，好数有 $222(8),444(8),666(8)$ 三个。

$1\le k \le 10^{18},p<8$

2019 Multi-University Training Contest 2