Educational Codeforces Round 80 (CF1288)
A. Deadline
题意
给出正整数 \(n,d\)，求不等式 \(x+\lceil \frac{d}{x+1}\rceil \le n\) 是否有非负整数解。
思路
先不考虑上取整，
\[x+ \frac{d}{x+1} = x+1+\frac{d}{x+1} -1 \ge 2\sqrt d -1 \]当且仅当 \(x+1=\frac{d}{x+1}\) 即 \(x=\sqrt d - 1\) 时取得最小值。
我们只需要判断最小值是否小于 \(n\) 即可。
加上上取整后，最小值一定在 \(x=\lfloor \sqrt d \rfloor - 1\) 或 \(\lceil \sqrt d \rceil - 1\) 时取到。
只用代入并判断是否成立即可。
B. Yet Another Meme Problem
题意
给出正整数 \(A,B\)，求有多少对 \((a,b)(1\le a\le A,1\le b \le B)\)，
满足 \(a \times b + a + b = conc(a,b)\)，\(conc(a,b)\) 表示 \(a,b\) 拼接后形成的数。
思路
\[conc(a,b)=10^{\log_{10}b+1} a+b \]左右同减 \(b\) 得：
\[a \times b+a = 10^{\log_{10}b+1}a \]同除 \(a\) 得：
\[b+1=10^{\log_{10} b+1} \]\(b\) 就等于 \(9,99,999,\dots\)，容易发现 \(n\) 以内这些数的个数为 \(\lfloor\log_{10}(n+1)\rfloor\)。
对于这些 \(b\)，所有 \(a\) 都能与它们配对，所以答案为：
\[\lfloor\log_{10}(B+1)\rfloor \times A \]C. Two Arrays
题意
给出正整数 \(n,m\)，求数列 \((A,B)\) 的个数，满足：
\(|A|=|B|=m\)，\(1 \le A_i \le B_i\le n\)，\(A\) 不减，\(B\) 不增。
答案对 \(10^9+7\) 取模。
思路
定义 \(dp_{i,j,k}\) 表示考虑前 \(i\) 个位置，\(A_i=j,B_i=k\) 的方案数。
答案为 \(\sum_{i=1}^n \sum_{j=i}^{n} dp_{m,i,j}\)。
转移方程：
\[dp_{t,i,j} = \sum_{k=1}^{i} \sum_{l=j}^{n} dp_{t-1,k,l} \]状态数 \(O(mn^2)\) 转移 \(O(n^2)\)，总时间复杂度 \(O(mn^4)\)，考虑优化。
发现转移可以使用二维前缀和优化至 \(O(1)\) （左上角 \((1,j)\)，右下角 \((i,n)\) 的矩形和），总时间复杂度 \(O(mn^2)\)。
D. Minimax Problem
题意
给出正整数 \(n,m\)，和 \(n\) 个长度为 \(m\) 的序列。
可以选择两个序列 \(i,j\) 组合出新的序列 \(b\) 满足 \(b_k=\max(a_{i,k},a_{j,k})\)。
求 \(\min b_i\) 的最大值。
思路
看到最小值最大可以想到二分。
考虑二分答案 \(x\)，根据题意，\(a_{i,k}\) 和 \(a_{j,k}\) 中至少有一个大于等于 \(x\)。
又看到 \(m\le 8\) 可以想到装压，把每个序列压成一个 \(m\) 位二进制数 \(S\)。
第 \(i\) 位代表 \(a_i\) 是否大于等于 \(x\)。
两个序列满足答案即 \(S_i \text{ or } S_j = 2^m-1\)。
显然无法直接枚举两个序列，可以转化为枚举两个状态并判断是否存在。
时间复杂度：\(O(\log W (nm+4^m))\)。
E. Messenger Simulator
题意
给出正整数 \(n,m\) 和长度为 \(m\) 的序列 \(A\)。
有长度为 \(n\) 的序列 \(B\)，初始时 \(B_i=i\)。
对于每个 \(A_i\)，把 \(B\) 中 \(A_i\) 移动到第一位。
求每个数在 \(B\) 中出现过的最大位置和最小位置。
思路
在序列开头插入，会使部分数的位置改变，不便于维护。
由于插入的次数固定为 \(m\)，我们可以先在 \(B\) 序列前预留 \(m\) 个空位出来插入。
把 \(A_1\) 至 \(A_m\) 从 \(m\) 至 \(1\) 倒着插入。
这样确实方便了插入，但查询数的真实位置（去除空位）变得复杂。
数的真实位置为该数在 \(B\) 序列中的位置及前面位置中数的个数，用树状数组维护。
插入数和维护树状数组的同时更新答案。
时间复杂度：\(O(n+m\log(n+m))\)。
标签：CF1288,10,Educational,le,正整数,log,Codeforces,序列,题意 From： https://www.cnblogs.com/maniubi/p/18540750