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) |