C2020 2021.1.24模拟赛

信息学——模拟赛

---

T1 Unlock

考场题面有锅，然而最后出题人也没补好，所以这题就咕咕了吧。

T2 Shelf

$1^o$ 分析

考虑DP。

设：$f[i]$表示前 $i$ 本书的最小值。

枚举点 $j$，表示 $j$ 到 $i$ 为最后一层。

则有方程：

$f[i] = \min{(f[j - 1] + max[i][j]) \,|\, sum[i][j]<=l}$

一个技巧：$j$ 从 $i$ 开始倒着枚举，好处是我们可以一遍扫一遍存下 $max[i][j]$ 和 $sum[i][j]$ 非常方便

(当然用ST表和前缀和维护也可以)

//The code is from dawn_sdy
#include<bits/stdc++.h>
#define INF INT_MAX
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
const int maxn = 2005;
int n, l;
struct node {
    int h, w;
}book[maxn];
int f[maxn], maxx, sum;
int main(){
//  freopen("bookshelf.in", "r", stdin);
//  freopen("bookshelf.out", "w", stdout);
    n = read(), l = read();
    for(register int i = 1; i <= n; ++i) book[i].h = read(), book[i].w = read();
    for(register int i = 1; i <= n; ++i) {
        f[i] = INF, maxx = sum = 0;
        for(register int j = i; j >= 1; --j) {
            maxx = max(maxx, book[j].h), sum += book[j].w;
            if(sum > l) break;
            f[i] = min(f[i], f[j - 1] + maxx);
        }
    }
    printf("%d", f[n]);
    return 0;
}

T3 running

$1^o$ 分析

先吐槽一句：题面依旧有问题，最后是理解std改的题面。。。

不过此题思路极其巧妙，值得一做。

首先考虑一定只存在速度快的奶牛追上速度慢的奶牛，那么如果按照速度排序，奶牛 $i$ 的贡献只与$[1,i]$有关

考虑奶牛 $i$ 追上奶牛 $j$ 的贡献：

首先算出时间

$$t = \frac{l \times c}{v[n]}$$
表示出 $i$ 和 $j$ 的路程差：
$$S_i - S_j= \frac{l \times c}{v[n]} \times v[i] - \frac{l \times c}{v[n]} \times v[j]$$
算出贡献：
$$Val_{i,j} = \lfloor \frac{\frac{l \times c}{v[n]} \times v[i] - \frac{l \times c}{v[n]} \times v[j]}{l} \rfloor$$
化简一下：
$$Val_{i,j} = \lfloor\frac{c \times v[i]}{v[n]} - \frac{c \times v[j]}{v[n]} \rfloor$$
则 $i$ 的答案为：
$$Ans_i = \sum_{j = 1}^{i - 1}{\lfloor\frac{c \times v[i]}{v[n]} - \frac{c \times v[j]}{v[n]} \rfloor}$$
在考虑这个式子怎么优化前，我们先来考虑一个事情：

$\lfloor a - b\rfloor$ 与 $\lfloor a\rfloor - \lfloor b \rfloor$ 之间的关系。

设：$a = p + k_1$，$b = q + k_2$ 其中 $p, q$ 为整数部分，$k_1,k_2$ 为小数部分。

则$\lfloor a - b\rfloor = \lfloor p - q + k_1 - k_2\rfloor$ ， $\lfloor a\rfloor - \lfloor b \rfloor = p + q$

我们考虑$k_1 - k_2$的影响

$$\begin{cases} \lfloor a - b\rfloor = \lfloor a\rfloor - \lfloor b \rfloor ,\quad &k_1 \geq k_2\\ \lfloor a - b\rfloor = \lfloor a\rfloor - \lfloor b \rfloor - 1, \quad &k_1 < k_2 \end{cases}$$
​ 那么我们可以考虑只考虑$k_1 \geq k_2$的情况，最后算一遍$k_1 < k_2$的情况有多少种，减去即可。

那么就可以将上式展开：

$$Ans_i = (i - 1) \times \lfloor\frac{c \times v[i]}{v[n]}\rfloor - (i - 1) \times \sum_{j = 1}^{i - 1}{(\lfloor\frac{c \times v[j]}{v[n]} \rfloor)} - k$$
其中第一项是常量，复杂度$O(1)$，第二项求和可以用前缀和处理，复杂度$O(n)$，那么我们要计算的就是$k$的个数。

考虑到小数部分不好处理，我们将小数转换成余数，记余数为 $q_i$。

则可以发现 $k$ 就是 满足 $j < i$ 且 $q_j > q_i$ 的个数，即可以看成 $q$ 数组逆序对的对数，而逆序对采用树状数组维护即可，复杂度$O(n\log n)$。

//The code is from dawn_sdy
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read() {
    int x = 0;
    char c = getchar();
    bool f = 0;
    while(!isdigit(c)) f |= (c == '-'), c = getchar();
    while(isdigit(c)) x = (x * 10) + (c ^ 48), c = getchar();
    return f ? -x : x; 
}
const int maxn = 1e5 + 5, maxl = 1e6;
int n, le, c, ans, sum, maxx;
struct node {
    int x, y, v;
}point[maxn];
inline bool operator <(node a, node b) {
    return a.x != b.x ? a.x < b.x : a.y < b.y;
}
namespace Binary_Index_Tree {
    int Tree[maxl << 1 + 5];
    inline int lowbit(int x) { return x & (-x); }
    inline void Update(int x, int num) { 
        while(x <= maxl) { Tree[x] += num, x += lowbit(x); } 
    }
        inline int Query(int x) {
        int res = 0;
        while(x) { res += Tree[x], x -= lowbit(x); }
        return res;
    }
}
using namespace Binary_Index_Tree;
signed main() {
    n = read(), le = read(), c = read();
    for(register int i = 1; i <= n; ++i) point[i].v = read(), maxx = max(maxx, point[i].v);
    for(register int i = 1; i <= n; ++i) point[i].x = point[i].v * le / maxx, point[i].y = (point[i].v * le) % maxx;
    sort(point + 1, point + n + 1);
    for(register int i = 1; i <= n; ++i) {
        ans += point[i].x * (i - 1) - sum - (Query(maxl) - Query(point[i].y)), sum += point[i].x;
        if(point[i].y) Update(point[i].y, 1);
    }
    printf("%lld", ans);
    return 0;
}

$2^o$ 反思与总结

一道非常好的题，需要记住的是 $\lfloor a - b\rfloor$ 的转化方式，以及将小数部分对应余数，进而转化为逆序对的思想。