Ed Round 80_牛客博客

A.DeadLine (暴力/简单数学,三分查找)

$题意:给出两个正整数n,d.问式子x +\lceil \frac{d}{x + 1}\rceil<=n是否可能成立.在x∈[1,n]的情况下.$

方法一:

$观察等式x +\lceil \frac{d}{x + 1}\rceil,左边匀速递增，右边递减速度先快后慢(求导可知)\\ 那么整条曲线先降后增，我们需要找到最低点.当右边每次下降少于1的那一刻就是最优点\\ \Delta = (d/x) - (d/(x+1)) = d/x*(x+1) = 1时x \approx \sqrt{d}\\ 所以可以暴力枚举到 \sqrt{d}+1,或者直接带x = \sqrt{d}$

方法二:

$x +\lceil \frac{d}{x + 1}\rceil的最小值等效于求min(x+1+\lceil \frac{d}{x + 1}\rceil) - 1.\\ 由均值不等式 a+ b \geq \sqrt{ab} \\ 所以答案就是\sqrt{(x+1)*d} - 1\\ 对于取整的处理，求其+-2就ok$

方法二:三分查找

$\text{[math]}$

emm,比赛的时候弄错了，写了个假算法，用的二分去写的。但是鬼使神差的过了，而且还过了hack，想不通。也真是运气好了.不然这一场就炸了.

B. Yet Another Meme Problem (打表)

$问有多少对(a,b)使得a⋅b+a+b=conc(a,b)成立,a,b取值范围分别为[1,A],[1,B].\\ con(12,23) = 1223$

思路：打表找规律发现只有当b = 9,99,999 这种全9数时上式才成立。

合理性:

$\text{[math]}$

C.Two Arrays (dp/组合数学)

题意: 给你n，m，利用1~n之间的数（可重复）来组成长度为m的数组a,b，要求数组a非递减,数组b非递增，且对应位上的a数组的数 <= b数组中的数，求出a,b数组对数.

方法1：dp变形

$这是我一开始的思路，比较绕\\设dp[i][j]为长度为i位以j结尾的不下降/不上升的序列的方案数\\状态转移为:dp[i][j] = \sum_{k = 1}^jdp[i-1][k],转移方式用前缀和优化.算出dp1,dp2代表a数组和b数组\\根据乘法原理可知两数组拼在一起的方案数为\\ans = \sum_{i=1}^{i = n} \sum_{j=1}^{j = n}dp1[m][i]*dp2[m][j]--(i <= j) \\时间复杂度O(n^2+nm)$

优化:

$发现将数组b逆序接在数组a的后面正好符合:\\ a1 <= a2 <= ... <= am <= bm <= b_{m-1} <= ... <= b1\\ 所以直接dp求到2*m就好.\\ 时间复杂度:O(nm)$

方法二:组合数学

$根据上面的分析我们可以将问题转换为从[1,n]中依次选择2*m个数字，使得其不下降\\设序列为11222...i.设a1为1的个数,a2为2的个数,an为n的个数,那么符合下式:\\a1 + a2 +...+an = 2*m(可重复选择的组合)\\ 答案即为C(2m + n - 1,n-1)$ 5

D.MiniMax Problem(二分答案，枚举子集)

题解:

观察到m很小,那么我们可以将每一行转化成一个二进制数mask[i],若当前的值大于等于目标值，那么就设为1，否则设为0.这样以来，对于一个目标值x来说，我们只要找到任意两行的mask符合mask[i]|mask[j] == (1<<m)-1即可.

直接枚举复杂度太高，将其压缩成一个二级制数映射到数组book里去,两层循环i,j枚举子集, i | j == (1<<m)-1且book[i] == 1 且 book[j] == 1 时，存在两行满足条件.记录下这时的i,j，记为res1,res2

最后O(n)循环遍历mask数组，找res1 res2.

AC代码:https://codeforces.com/contest/1288/submission/68964584

E. Messenger Simulator (树状数组，动态维护)

题意:

一开始有一个初始顺序的排列[1,n]，一共有m次操作，每次将数ai从序列中取出，放到最开头的位置生成一个新的排列。

求问在所有过程中每一个数最小的下标位置和最大的下标位置。

具体题解见:

https://www.jianshu.com/p/7eded28309e5