\(x+y+z\) 表示赛时预计 \(x\) 分，实际 \(y\) 分，赛后补了 \(z\) 分。
4.5 小时 5 道题。
有一道炼石的题，那场我们打过，当时那题场切了。但是现在不会做了【】
有一道 CF 某 div.2 F 的弱化。没做出来【】
T1. 降温
赛时想出了做法，拍了一点小数据。但是最后被浮点数的精度和 __int128 挂了。
\(60+100\)。
题意
有 \(n\) 个装置，每个装置有初始温度 \(t_i\)。
给定正整数 \(A, B\)，一次降温操作可以将一个装置温度降低 \(A\)，剩下 \((n - 1)\) 个装置温度降低 \(B\)。
求至少需要多少次降温操作才能让所有温度严格小于 \(0\)。
My Solution
我们称将一个数减少 \(A\) 为特殊操作，减少 \(B\) 为特殊操作。显然特殊操作的最小次数即答案。
不妨令对 \(i\) 进行了 \(x_i\) 次特殊操作。我们二分它们的和 \(\sum x_i = X\)，即答案。
对于 \(i\) 而言，它的特殊操作次数为 \(x_i\)，普通操作次数为 \(X - x_i\)。那么它被减少的量为 \(x_i \cdot A + (X - x_i) \cdot B\)。只有这个值 \(> t_i\) 才能满足要求。
那么 check 要做的就是判断是否存在一个这样的 \(x\) 数组，使得每项均为非负整数，且所有数的和为 \(X\)，且：
\[x_i \cdot A + (X - x_i) \cdot B > t_i \]做一些简单的推导：
\[x_i \cdot (A - B) > t_i - X \cdot B \]不等式上做除法不太好做。考虑分类讨论：
若 \(A = B\)，那么在最开始特判即可。答案为 \(\max\{ \lfloor \frac{t_i}A \rfloor +1\}\)。
若 \(A > B\)，那么直接除：
\[x_i > \dfrac{t_i - X \cdot B}{A - B} \]右边是个常数。我们可以求出在这样的情况下 \(x_i\) 的最小值。若每个 \(x_i\) 的最小值之和 \(\le X\) 则 check 合法。
若 \(A < B\)，除过去要变号：
\[x_i < \dfrac{t_i - X \cdot B}{A - B} \]同理我们可以求出每个 \(x_i\) 的最大值。若每个 \(x_i\) 的最大值之和 \(\ge X\) 则 check 合法。
std Solution
一次降温操作是选择一个减 \(A\)，剩下全减 \(B\)。那么我们可以将所有数先全减 \(B\)，在选择某个数加上 \(A - B\)。
仍然二分答案 \(X\)。令 \(a_i = t_i - B \cdot X\)。此时我们需要判断，能否执行 \(X\) 次操作，每次操作会选择一个数加上 \(A - B\)，使得最终整个序列均为负。
\(A = B\) 太水了。我们考虑：
- \(A > B\)：这样的操作是劣的。因此我们每次找当前的最大值执行这样的操作。
- \(A < B\)：这样的操作是优的。因此我们每次找当前的最小值执行这样的操作。
真的操作复杂度不对。
- \(A > B\)：维护 \(b_i = \left\{ \begin{matrix} 0 &,a_i \ge 0 \\ \left\lfloor \dfrac{-a_i}{A-B} \right\rfloor + 1&,a_i < 0 \end{matrix}\right.\)。问题等价于 \(\sum b_i \le X\)。
- \(A < B\)：同理。不写了。
代码没写。
T2. 数学题
\(70+40+100\)。
以为会 70。但是 \((10^4)^2 \times 10 \times 10\) 你觉得能不能过？
题意
求 \(L, R\) 内有多少数的数码种类为 \(A\)。\(L, R\) 位数都为 \(n \le 2 \times 10^5\)。
做法
差分转化。考虑 \(1 \sim x\) 的答案。
数位 DP 套路地枚举 \(y \in [1, x]\) 的第一个与 \(x\) 不同的位置 \(i\)，并枚举这一位填什么。这样我们就得到了 \(y\) 的前 \(i\) 位，且 \(i + 1 \sim n\) 位都可以 \(0 \sim 9\) 任意填。
我们可以求出前 \(i\) 位的种类数 \(B\)。如果 \(B > A\) 那么不可能。否则如果想让 \(y\) 的数码种类为 \(A\)，那么 \(y\) 的 \(i + 1 \sim n\) 位中，一定存在恰好 \((A - B)\) 个与前 \(i\) 位不同的数。这个的方案是 \(\dbinom {10-B}{A-B}\)。
接下来的问题是，在 \((n - i)\) 位中，每个数都有 \(A\) 种填法，但是有 \(B\) 个数至少出现一次。求方案数。
我们容斥枚举，有多少个必选的数没出现。式子：
\[\sum_{c=0}^B (-1)^c\dbinom Bc (A-c)^{n-i} \]复杂度 \(10^2n\)。
标签：10,le,8.7,cdot,模拟,操作,我们,sim From： https://www.cnblogs.com/2huk/p/18348003