Codeforces 1288A~E 题解
Codeforces 1288A Deadline 题解
题意
给定两个整数$n,d$ ($1\le n,d\le 10^9$),问当$x$为非负整数时,$x+\left\lceil\frac{d}{x+1}\right\rceil$有没有可能小于等于$n$。
题解
因为$x$为整数且$x,\left\lceil\frac{d}{x+1}\right\rceil$都是非负的,所以$x+\left\lceil\frac{d}{x+1}\right\rceil=\left\lceil x+\frac{d}{x+1}\right\rceil$。
定义函数$f(x)=x+\frac{d}{x+1}$,当$x=\sqrt{d}-1$时$f(x)$有最小值$2\sqrt{d}-1$。
看当$x=\left\lfloor\sqrt{d}-1\right\rfloor$和$\left\lceil\sqrt{d}-1\right\rceil$时,$\left\lceil f(x)\right\rceil$是否小于等于$n$即可。
程序
1 | // #pragma GCC optimize(2) |
Codeforces 1288B Yet Another Meme Problem 题解
题意
定义函数$conc(a,b)$($a,b$不能含有前导零)为$a$和$b$“拼”起来,如$conc(12,23)=1223,conc(100,11)=10011$。
给定两个整数$A,B$ ($1\le A,B\le10^9$),求数对$(a,b)$的个数,满足:$1\le a\le A,1\le b\le B$且$a\cdot b+a+b=conc(a,b)$。
题解
定义$|a|$为整数$a$的长度。
若$a\cdot b+a+b=conc(a,b)$
$a\cdot b+a+b=a\cdot10^{|b|}+b$
$a\cdot b+a=a\cdot10^{|b|}$
$a\cdot(b+1)=a\cdot10^{|b|}$
$b+1=10^{|b|}$。
所以$b$的样子应该是$99\dots99$,所以答案即为$a\times(|b+1|-1)$。
程序
1 | // #pragma GCC optimize(2) |
Codeforces 1288C Two Arrays 题解
题意
给定两个整数$n,m(1\le n\le10^3,1\le m\le 10)$,求数组对$(a,b)$的个数模$10^9+7$ 满足:
- 两个数组的长度都是$m$。
- 每个数组中的每个数都在$[1,n]$中。
- $a_i\le b_i (1\le i\le m)$。
- 数组$a$为非下降序列。
- 数组$b$为非上升序列。
题解
把数组$a$和$b$按一下顺序连接起来:
$a_1,a_2,\dots,a_m,b_m,b_{m-1},\dots,b_1$。
这个数组是一个长度为$2m$的非下降序列,且每个数都在$[1,n]$中。
满足条件的数组的个数即 从$n$个不同元素中可重复地选$2m$个元素,不计顺序。
所以答案为$H_{n}^{2m}=\binom{n+2m-1}{2m}$。
程序
1 | // #pragma GCC optimize(2) |
Codeforces 1288D Minimax Problem 题解
题意
给定$n$ ($1\le n\le3\cdot10^5$)个数组$a_1,a_2,\dots,a_n$,每个数组都有$m$ ($1\le m\le8$)个整数,记第$x$个数组的第$y$个数为$a_{x,y}$。
现在需要选择两个数组$a_i,a_j$ ($1\le i,j\le n$,允许$i=j$),然后就可以得到一个新的长度为$m$数组$b$,满足$b_k=\max(a_{i,k},b_{j,k}),k=1,2,\dots,m$。
求如何选择$i,j$,使得$\min\limits_{k=1}^m b_k$最大。
题解
二分答案,记之为$x$。
把数组$a_i$变成$m$位二进制数$c_i$,
若$a_i,a_j$能满足条件即$\min\limits_{k=1}^m b_k\ge x$,当且仅当$c_i|c_j=2^m-1$。
显然,枚举$i,j$是不行的。因为$m$最大只有$8$,可以把$c_i$作为键值存入大小为$256$的数组中,对应的值为$i$ (即$\mathbb{vis}[c_i]=i$),然后枚举$c_i,c_j$即可。
程序
1 | // #pragma GCC optimize(2) |
Codeforces 1288E Messenger Simulator 题解
题意
给定整数$n$和$m$次操作($1\le n,m\le 3\cdot10^5$)。有一个长度为$n$的排列$p$,初始值为$p=[1,2,\dots,n]$,每次操作给定一个整数$a$ ($1\le a\le n$),设$p_i=a$,则把$p_1,p_2,\dots,p_i$循环右移一次。
求$1,2,\dots,n$,在整个操作过程中,下标的最小值和最大值。
题解
首先,最小值很容易确定:如果一个数从来没有被操作过,答案就是它的初始位置,因为它不可能往前移了;否则就是$1$。
再来考虑最大值。如果循环右移$p_1,p_2,\dots,p_i$一次,那么就变成$p_i,p_1,\dots,p_{i-1}$,就是把$p_i$放到最前面。
可以想到相当于一个大小为$m+n$的数组$q$,初始排列放在$q_{m+1},q_{m+2},\dots,q_{m+n}$,预留下前$m$个位置。第$i$次操作$q_j$时,令$q_{m-i}=q_j,q_j=0$,就完成了操作。
再考虑下标,这个数组中,下标就是这个数前面有多少数。自然地想到用树状数组维护。
树状数组中,每个值都是$0$或$1$,再用另一个数组维护每个数的位置即可。
程序
1 | // #pragma GCC optimize(2) |