前言

由于疫情，本来在 2020 后半年会举行的区域赛，想着 2021 年已经大四下学期了，内心处于退役养老阶段，突然在几个月前被通知说被派去了昆明和银川，也只能带着生锈的大脑继续上了。今年的昆明站是线上赛，在牛客网上举行，因为线上赛没有了之前在南昌和香港站的现场氛围，所以感觉比较微妙，而且各种步骤都变得繁琐了起来，原本不需要队员注意的事项也需要队员来做，所以总体来说我还是更喜欢线下赛。

比赛日程

• 4月2日

• 4月3日

比赛规则

因为是第一次打线上赛，所以还是想记录一下这有点繁琐的比赛规则（以下仅为一部分）

1. 竞赛试题数：13 题（英文）
2. 每个参赛队伍仅允许使用唯一主参赛计算机进行题目查看、程序编写调试、代码提交等操作（即不能双开看题）
3. 一支队伍能且仅能独立使用唯一打印设备（要打印啥信息自己备打印机）
4. 在比赛期间不得关闭浏览器或关闭牛客笔试平台页面
5. 比赛期间参赛选手如果需要上洗手间，必须请示本地监考志愿者，由本地监考志愿者通过腾讯会议联系线上监考人员，获准后才可以离开
6. 每个队伍都要配备三个监控机位（电脑），机位电脑均接入腾讯会议，并且要录屏，最后打题的电脑录屏要上交

4.2热身赛

A.Meditation

题目大意：
给你 n 个数字，从里面挑出 k 个，要求他们的和是最大的

• 1 ≤ k ≤ n ≤ 100000
• 对于每个数字，0 ≤ g ≤ 10000

样例

输入
5 3
10
22
7
3
10

输出
42

思路
完全的签到题，排序相加就完事了

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;

int n,k,a[maxn];
ll sum = 0;

int main()
{
    scanf("%d%d", &n, &k);
    for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    sort(a+1, a+1+n);
    for(int i = n; k; --i) {
        sum += a[i];
        k--;
    }
    printf("%d\n", sum);
    return 0;
} 

B.Rounds

题目大意
有 n 个人，从 1 到 n 编号，每个人有一个整数信用值，现在要玩 k 轮游戏，第 i 轮游戏会从除了第 i 个人之外的其他人身上每人扣 s 信用值，并且都加到第 i 个人身上，每轮游戏后，都能找到一个人有最低信用值 c，问进行 k 轮游戏后，可能会出现的最低信用值 c 的最大值是多少

• 1 ≤ n ≤ 100000
• 1 ≤ k ≤ n
• 1 ≤ s ≤ 100000000
• 对于每个最低信用值 c ，1 ≤ c ≤100000000，而且 s×(n-1) ≤ c，即保证每轮游戏不会减成负数

样例

输入
3 10
24
42
38

输出
28

说明
After round 1 the amounts of credits held are 44, 32, 28 and the minimum is 28.
After round 2 the amounts of credits held are 34, 52, 18 and the minimum is 18.
After round 3 the amounts of credits held are 24, 42, 38 and the minimum is 24.
The best possible outcome is therefore 28.

思路
根据 n 的数据范围来看，显然 $O(n^2)$ 暴力模拟不可取，因为题目每一步都涉及到区间加减以及区间查询最值两个操作，所以可联想到用线段树维护整个数组，用 $O(nlogn)$ 的复杂度解决问题。题目并没给出具体操作次数 k ，但告诉我们 k 一定不会大于 n ，所以就当他操作了 n 轮即可。

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 10;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int n, k;
ll a[maxn];
struct node {
    ll mi;
    ll v;
    ll lazy; 
}tree[maxn << 2];

void build(int p, int l, int r) {
    if (l == r) {
        tree[p].v = a[l];
        tree[p].mi = a[l];
        tree[p].lazy = 0;
    } else {
        int mid = (l + r) >> 1;
        build(p << 1, l, mid);
        build(p << 1 | 1, mid + 1, r);
        tree[p].mi = min(tree[p<<1].mi, tree[p<<1|1].mi);
        tree[p].lazy = 0;
        tree[p].v = tree[p<<1].v + tree[p<<1|1].v;
    }
}

void pushdown(int p, int l, int r) {
    if (tree[p].lazy) {
        tree[p<<1].lazy += tree[p].lazy;
        tree[p<<1|1].lazy += tree[p].lazy;
        tree[p<<1].v += tree[p].lazy * (((l + r) >> 1) - l + 1);
        tree[p<<1|1].v += tree[p].lazy * (r - ((l + r) >> 1));
        tree[p<<1].mi += tree[p].lazy;
        tree[p<<1|1].mi += tree[p].lazy;
        tree[p].lazy = 0;
    }
}

void add(int p, int l, int r, int x, int y, ll v) {
    if (x <= l && r <= y) {
        tree[p].lazy += v;
        tree[p].v += v * (r - l + 1);
        tree[p].mi += v;
        return;
    } else {
        int mid = (l + r) >> 1;
        pushdown(p, l, r);
        if (x <= mid) add(p << 1, l, mid, x, y, v);
        if (y > mid) add(p << 1 | 1, mid + 1, r, x, y, v);
        tree[p].v = tree[p<<1].v += tree[p<<1|1].v;
        tree[p].mi = min(tree[p<<1].mi, tree[p<<1|1].mi);
    }
}

ll query(int p, int l, int r, int x, int y) {
    if (x <= l && r <= y) {
        return tree[p].mi;
    } else {
        int mid = (l + r) >> 1;
        ll ans = INF;
        pushdown(p, l, r);
        if (x <= mid) ans = min(ans, query(p<<1, l, mid, x, y));
        if (y > mid) ans = min(ans, query(p<<1|1, mid + 1, r, x, y));
        return ans;
    }
}

int main() {
    // freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1, 1, n);
    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        add(1, 1, n, 1, n, -k);
        add(1, 1, n, i, i, 1ll * k * n);
        ans = max(ans, query(1, 1, n, 1, n));
        // cout << "------->" << query(1, 1, n, 1, n) << '\n';
    }
    cout << ans << '\n';
    return 0;
}

C.Statues

题目大意
有 n 个展示灯，按 1-n 编号，有 k 个雕像，每盏灯下只能放一个雕像，每个雕像有一个重量 s 。已知每个雕像摆在对应的第 p 号展示灯下，但此时雕像重量并一定不是按升序排列，每次把雕像从 i 号灯移动到 j 号灯需要耗费 s×|i-j| 的时间，问最少需要耗费多少时间，能让雕像重量按升序排列。

样例

思路
DP思路

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;
typedef long long ll;
const int maxn = 5e3 + 10;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int n, k;
ll dp[maxn][maxn];
P pos[maxn];

int main() {
    // freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(0);
    cin >> n >> k;
    for (int i = 1; i <= k; i++) {
        int a, s;
        cin >> a >> s;
        pos[i] = P(s, a);
    }
    sort(pos + 1, pos + 1 + k);
    for (int i = 0; i < maxn; i++)
        for (int j = 0; j < maxn; j++)
            dp[i][j] = INF;
    dp[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            dp[i][j] = min(dp[i][j], dp[i - 1][j]);
            if (j) dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1ll * pos[j].first * (ll)abs(pos[j].second - i));
        }
    }
    cout << dp[n][k] << '\n';
    return 0;
}

版权属于：PCsky

本文链接：http://hyouka.club/index.php/archives/165/

转载时须注明出处及本声明