1945(div3)

Dec 16, 2024 11:44 AM

Dec 17, 2024 4:34 AM

A. Setting up Camp

组委会计划在游览结束后带领奥林匹克运动会的参赛选手进行徒步旅行。目前，正在计算需要搭乘的帐篷数量。据了解，每个帐篷最多可容纳 $3$ 人。

在参赛选手中，有 $a$ 名内向型选手， $b$ 名外向型选手和 $c$ 名综合型选手：

每个内向的人都想独自住在帐篷里。因此，内向者的帐篷里必须只有一个人--只有内向者自己。
每个外向者都希望与另外两个人住在一个帐篷里。因此，一个外向者的帐篷里必须正好有三个人。
每个人都可以选择任何一种方式（独居、与他人同住或与他人同住）。

组委会非常尊重每位参赛者的意愿，因此他们希望满足所有参赛者的愿望。

请告诉我们至少需要多少顶帐篷，以便所有参加者都能根据自己的喜好找到住处。如果无法满足所有参与者的愿望，则输出 $- 1$ 。

void solve() {
    int a, b, c;cin >> a >> b >> c;
    int x = b % 3;
    if (x && x + c < 3) {
        cout << "-1\n";return;
    }
    cout << a + (b + c) / 3 + ((b + c) % 3 ? 1 : 0) << '\n';
}

B. Fireworks

徒步旅行的其中一天恰逢节假日，因此决定晚上在营地安排一场节日焰火表演。为此，徒步旅行的组织者购买了两个烟花发射装置和大量的发射炮弹。

两个装置同时开启。第一个装置每隔 $a$ 分钟（即发射后 $a, 2 \cdot a, 3 \cdot a, \dots$ 分钟）发射一次烟花。第二个装置每 $b$ 分钟（即发射后 $b, 2 \cdot b, 3 \cdot b, \dots$ 分钟）发射一次烟花。

每个烟花在发射后的 $m + 1$ 分钟内都可以在天空中看到，也就是说，如果一个烟花是在装置开启后的 $x$ 分钟后发射的，那么从 $x$ 到 $x + m$ （包括首尾两分钟）的每一分钟都可以看到该烟花。如果一个烟花在另一个烟花 $m$ 分钟后发射，则两个烟花都将在一分钟内可见。

天空中最多可以同时看到多少枚烟花？

#define int long long
void solve() {
    int a, b, m;cin >> a >> b >> m;
    cout << m / a + m / b + 2 << '\n';
}

C. Left and Right Houses

莱托沃村有 $n$ 栋房子。村民们决定修建一条大路，将村子分为左右两边。每个居民都想住在街道的右侧或左侧，这可以用序列 $a_{1}, a_{2}, \dots, a_{n}$ 来描述，其中 $a_{j} = 0$ 如果 $j$ /th 房子的居民想住在街道的左侧；否则， $a_{j} = 1$ 。

道路将从两栋房子之间穿过。它左边的房子将被宣布为左侧，右边的房子将被宣布为右侧。更正式地说，让道路从房屋 $i$ 和 $i + 1$ 之间通过。那么位于 $1$ 和 $i$ 之间的房屋将位于街道的左侧，位于 $i + 1$ 和 $n$ 之间的房屋将位于街道的右侧。道路也可以***经过第一栋房屋之前和最后一栋房屋之后；在这种情况下，整个村庄分别被宣布为右侧或左侧。

为了使设计公平，我们决定在铺设道路时，至少要让村子两边各一半的居民对选择感到满意。也就是说，在一侧的 $x$ 个居民中，至少有 $⌈ \frac{x}{2} ⌉$ 个居民愿意住在这一侧，其中 $⌈ x ⌉$ 表示四舍五入的实数 $x$ 。

在路的左边，会有 $i$ 座房子，在相应的 $a_{j}$ 中，至少要有 $⌈ \frac{i}{2} ⌉$ 个零。路的右边有 $n - i$ 座房子，在相应的 $a_{j}$ 中至少要有 $⌈ \frac{n - i}{2} ⌉$ 个一。

确定道路应该铺设在哪座房子 $i$ 之后，以满足所述条件，并尽可能靠近村庄中央。从形式上看，在所有合适的位置 $i$ 中，尽量减少 $| \frac{n}{2} - i |$ 。

如果有多个合适位置 $i$ 的最小值 $| \frac{n}{2} - i |$ ，则输出较小的一个。

主要是对于找到最合适的答案的问题，当 n 为偶数时没有问题，当 n 为奇数时就会有两个可能答案取最小值

void solve() {
    int n;cin >> n;string a;cin >> a;a = ' ' + a;
    vector<int> pre(n + 1), suf(n + 2);
    for (int i = 1;i <= n;i++) {
        pre[i] = pre[i - 1] + (a[i] == '0');
    }
    for (int i = n;i >= 1;i--) {
        suf[i] = suf[i + 1] + (a[i] == '1');
    }
    vector<int> ans;
    for (int i = 0;i <= n;i++) {
        int x = pre[i], y = suf[i + 1];
        if (x >= (i + 1) / 2 && y >= (n - i + 1) / 2) {
            ans.push_back(i);
        }
    }
    int op1 = (n + 1) / 2, op2 = n / 2, res = 1e9, tar = 1e9;
    for (int i = ans.size() - 1;i >= 0;i--) {
        if (abs(op1 - ans[i]) < res || abs(op2 - ans[i]) < res) {
            res = min(abs(op1 - ans[i]), abs(op2 - ans[i]));
            tar = ans[i];
        }
        if (abs(op1 - ans[i]) == res || abs(op2 - ans[i]) == res) {
            res = min(abs(op1 - ans[i]), abs(op2 - ans[i]));
            tar = min(tar, ans[i]);
        }
    }
    cout << tar << '\n';
}

D. Seraphim the Owl

大家排成 $n$ 号队，从 $i = 1$ 号开始，向猫头鹰谢拉菲姆请教生命的意义。不巧的是，基里尔正忙着为这个问题编写传说，所以他来得晚了一些，站在了 $n$ 号人之后的队尾。基里尔对这种情况完全不满意，于是他决定贿赂一些排在他前面的人。

对于队列中的 $i$ \th 人，基里尔知道两个值： $a_{i}$ 和 $b_{i}$ ： $a_{i}$ 和 $b_{i}$ 。如果此刻基里尔站在位置 $i$ 上，那么他可以选择任意一个位置 $j$ ，比如 $j < i$ ，然后与位置 $j$ 上的人交换位置。在这种情况下，基里尔必须支付他 $a_{j}$ 个硬币。而对于每个 $k$ 这样的 $j < k < i$ ，基里尔将不得不支付 $b_{k}$ 个硬币给位置 $k$ 的人。基里尔可以任意多次执行此操作。

基里尔很节俭，所以他想花尽可能少的硬币，但是他又不想等太久，所以基里尔认为他应该排在第一个 $m$ 人的队伍中。

请帮助基里尔确定，为了不等太久，他最少需要花费多少金币。

可以注意到确定的答案序列一定有一个特点，最后一个值一定是在 $a_{i}$ 上的某个位置，在这之后的每个位置都是取的 $min (a_{i}, b_{i})$ 。就可以拿 $a_{i}$ 做为媒介，当当前位置达到要求时，就将之前累计的 $min (a_{i}, b_{i})$ 之和累加再加上最后必须加上的 $a_{i}$

void solve() {
    int n, m;cin >> n >> m;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];
    for (int i = 1;i <= n;i++)cin >> b[i];
    ll ans = 1e18, now = 0;
    for (int i = n;i >= 1;i--) {
        if (i <= m)ans = min(ans, now + a[i]);
        now += min(a[i], b[i]);
    }
    cout << ans << '\n';
}

E. Binary Search

给你一个大小为 $n$ 的排列数 $p$ 和一个需要求出的数字 $x$ 。

你忘了二进制搜索必须对数组进行排序。

为了得到正确的答案，你可以在运行算法之前执行以下操作不超过 $2$ 次：选择索引 $i$ ， $j$ （ $1 \leq i, j \leq n$ ）并交换位置 $i$ 和 $j$ 上的元素。

执行二进制搜索声明两个变量 $l = 1$ 和 $r = n + 1$ 。然后执行下面的循环：

如果 $r - l = 1$ ，结束循环
$m = ⌊ \frac{r + l}{2} ⌋$
如果 $p_{m} \leq x$ ，赋值 $l = m$ ，否则 $r = m$ 。

我们的目标是在算法之前重新排列排列组合中的数字，以便在算法执行之后， $p_{l}$ 等于 $x$ 。可以证明 $2$ 操作总是足够的。

Solution

问题在于如何在操作数不超过两个的情况下，使得二分结果恰好为 $x$ 。

这样可以将数组排序，这样一定能达到目标，但是很容易超过 2 的答案。

vector<pair<int, int>> op;
for (int i = 1;i <= n;i++) {
	if (a[i] != i) {
		op.push_back({i,mp[i]});
		mp[a[i]] = mp[i];
		swap(a[i], a[mp[i]]);
		mp[i] = i;
	}
}
cout << op.size() << '\n';
for (auto [x, y] : op)cout << x << " " << y << '\n';

实际上，被骗了，实际上，很简单，只需要一次一定能解决问题。

只需要在二分最终结果 $l$ 和当前 $x$ 的位置 $p o s$ 交换即可。

void solve() {
    int n, x;cin >> n >> x;vector<int> a(n + 1);
    int p = 0;
    for (int i = 1;i <= n;i++) {
        cin >> a[i];
        if (a[i] == x)p = i;
    }
    int l = 1, r = n + 1;
    while (r - l > 1) {
        int m = r + l >> 1;
        if (a[m] <= x)l = m;
        else r = m;
    }
    cout << "1\n";
    cout << p << " " << l << '\n';
}

F. Kirill and Mushrooms

橡树下生长着 $n$ 种蘑菇，每种蘑菇都有魔力 $v_{i}$ 。基里尔非常想用这些蘑菇制作一种魔力最大的灵药。

灵药的强度等于其中蘑菇的数量与这些蘑菇中最小魔力的乘积。为了配制灵药，基里尔将依次采摘生长在橡树下的蘑菇。基里尔可以按照任何顺序采集蘑菇。

然而，事情并非如此简单。智慧橡树告诉基里尔从 $1$ 到 $n$ 的数字 $p$ 的排列组合。如果基里尔只采摘 $k$ 个蘑菇，那么所有指数为 $p_{1}, p_{2}, \dots, p_{k - 1}$ 的蘑菇的魔力就会变成 $0$ 。基里尔不会使用魔力为零的蘑菇来配制灵药。

你的任务就是帮助基里尔采集蘑菇，使他能够酿造出最大魔力的灵药。不过，基里尔有点害怕在橡树附近逗留太久，所以在所有合适的采集蘑菇的选项中，他要求您找到蘑菇数量最少的那个。

Solution

堆
(待更 $\dots$ )
Codeforces Round 935 (Div. 3)（A,B,C,D,E,F）-CSDN博客

void solve() {
    int n;cin >> n;
    vector<int> t(n + 1), a(n + 1);
    for (int i = 1;i <= n;i++)cin >> t[i];
    for (int i = 1, id;i <= n;i++) {
        cin >> id;
        a[i] = t[id];
    }
    priority_queue <int, vector<int>, greater<int>> h;
    ll ans = 0, tot;
    for (int i = n;i >= 1;i--) {
        h.push(a[i]);
        if (n - i + 1 < i)continue;
        while (h.size() > i)h.pop();
        if (ans <= 1ll * i * h.top()) {
            ans = 1ll * i * h.top();
            tot = h.size();
        }
    }
    cout << ans << ' ' << tot << '\n';
}