Educational Codeforces Round 171 (Rated for Div. 2) 题解(A-C)

2hard4me! / 2025-02-18 / 原文

Educational Codeforces Round 171 (Rated for Div. 2) 题解(A-C)

这场ABC全都犯病了（悲伤）
D E 还没有补，到时候补上。

点 $A$ , $B$ , $C$ , $D$ 的坐标都是整数；
$0 \le A_x, B_x, C_x, D_x \le X$ 和 $0 \le A_y, B_y, C_y, D_y \le Y$ ；
线段 $AB$ 的长度至少为 $K$ ；
线段 $CD$ 的长度至少为 $K$ ；
线段 $AB$ 和 $CD$ 垂直：如果画包含 $AB$ 和 $CD$ 的线段，它们将成直角相交。

请注意，线段不一定要相交。只要线段引出的直线是垂直的，线段就是垂直的。

输入

第一行包含一个整数 $t$ ( $1 \le t \le 5000$ ) - 测试用例数。接下来是 $t$ 个案例。

每个测试用例的第一行也是唯一一行包含三个整数 $X$ 、 $Y$ 和 $K$ （ $1 \le X, Y \le 1000$ ; $1 \le K \le 1414$ ）。

输入的附加限制： $X$ 、 $Y$ 和 $K$ 的值要确保答案存在。

思路

由输入的限制条件可知，保证解存在，并且$K$ 的最大值为 $1414$, $(1000+1000)^{0.5}$也是1414,我们想让AB和CD垂直，并且两个长度都要大于等于$K$，那么我们可以让AB和CD分别为正方形的两个对角线，这样就可以保证两个线段垂直，并且长度都大于等于$K$。

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void sol()
{
    int x, y, k;
    cin >> x >> y >> k;
    int n = min(x, y);
    cout << 0 << ' ' << 0 << ' ' << n << ' ' << n << endl;
    cout << n << ' ' << 0 << ' ' << 0 << ' ' << n << endl;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t--)
        sol();
}

B. Black Cells

大意

给你一条长条，从左到右从 $0$ 到 $10^{18}$ 分成若干个单元格。最初，所有单元格都是白色的。你可以执行以下操作：选择两个白色单元格 $a_i$ 和 $a_j$ ，即 $i ≠ j$ , $|a_i - a_j| ≦ k$ ，并将它们涂成黑色。这里给出了一个列表 $a$ 。该列表中的所有单元格都必须涂黑。此外，不在列表中的单元格也可以涂成黑色。你的任务是确定可以涂黑的 $k$ 的最小值。

输入

Input

输入

第一行包含一个整数 $t$ ( $1 \le t \le 500$ ) - 测试用例数。

每个测试用例的第一行包含一个整数 $n$ ( $1 \le n \le 2000$ )。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ( $0<a_i<10^{18} ; a_i<a_{i+1}$)
输入的附加限制：所有测试用例中 $n$ 的总和不超过 $2000$ 。

思路

显然，如果要两个点被涂黑，那么$|a_i - a_j| ≦ k$ ，很大的$k$总是可以的，所以我们可以二分答案，然后判断此时的$k$是否可以涂黑。
因为$n≤2000$,所以
$check函数$就只要暴力枚举所有的点对，然后判断是否满足条件，满足就记录下来，最后判断是否涂黑了至少$n-1$个点。

代码


#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
ll n;
vector<ll> a;
bool ck(ull mid)
{

    ll cnt = 0;
    int i = 1, j = 1;
    bool vis[10000] = {0};

    for (ll i = 1; i < n; i++)
    {
        for (ll j = i + 1; j <= n; j++)
        {
            if (vis[i] || vis[j])
                continue;
            if (abs(a[j] - a[i]) <= mid)
            {
                vis[j] = 1;
                vis[i] = 1;
                cnt += 2;
            }
        }
    }
    cnt = n - cnt;
    if (cnt <= 1)
        return 1;
    return 0;
}
void sol()
{

    cin >> n;

    a.resize(n + 1);


    for (ll i = 1; i <= n; i++)
        cin >> a[i];

//二分答案
    ull l = 0, r = 1e17;
    while (l + 1 < r)
    {
        ll mid = l + (r - l) / 2;
        if (ck(mid))
            r = mid;
        else
            l = mid;
    }
    cout << r << endl;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while (t--)
        sol();
}

C. Action Figures

大意
在莫诺卡普家附近有一家出售动作人偶的商店。一套新的公仔即将推出；这套公仔包含 $n$ 个公仔， $i$ 个公仔需要花费 $i$ 个金币，在 $i$ 天到 $n$ 天之间可以购买。

在 $n$ 天中的每一天，莫诺卡普都知道他是否可以去商店。

每次莫诺卡普去商店时，他都可以购买商店里出售的任意数量的动作模型（当然，他不能购买尚未出售的动作模型）。如果莫诺卡普在同一天内至少买了两个，他就可以获得相当于他所买的最贵的折扣（换句话说，他可以免费获得他所买的最贵的一个）。

Monocarp 想从这套书中买一个 $1_{th}$ 数字， $2_{th}$ 数字，......， $n_{th}$ 数字。他不能两次购买同一个数字。他最少要花多少钱？

输入

第一行包含一个整数 $t$ ( $1 \le t \le 10^4$ ) - 测试用例数。

每个测试用例由两行组成：

第一行包含一个整数 $n$ （ $1 \le n \le 4 \cdot 10^5$ ）。( $1 \le n \le 4 \cdot 10^5$ )--集合中的数字个数（和天数）；
第二行包含一个字符串 $s$ （ $|s| = n$ ，每个 $s_i$ 要么是 0 要么是 1）。如果 Monocarp 可以在 $i$ -3 天去商店，那么 $s_i$ 为 1；否则， $s_i$ 为 0。

输入的其他限制

在每个测试用例中， $s_n$ 为 1，因此 Monocarp 总是能够在 $n$ /th 天内购买所有数字；
所有测试用例中 $n$ 的总和不超过 $4 \cdot 10^5$ 。

**第一行包含一个整数 $t$ （ $1 \le t \le 10^4$ ）--测试案例数。每个测试用例由两行组成：- 第一行包含一个整数 $n$ ( $1 \le n \le 4 \cdot 10^5$ ) --集合中数字的个数（和天数）； - 第二行包含一个字符串 $s$ ( $|s| = n$ , 每个 $s\_i$ 要么是 0 要么是 1)。如果 Monocarp 可以在 $i$ -th 天去商店，那么 $s\_i$ 为 1；否则， $s\_i$ 为 0：- 在每个测试用例中， $s\_n$ 都是 1，所以 Monocarp 总是能够在第 $n$ 天内买到所有的数字； - 所有测试用例中 $n$ 的总和不超过 $4 \cdot 10^5$ 。

思路
贪，都可以贪！每个商品的价格都是他的下标。
对于每一个0,显然都是要买的。由于第$i$个只能在$i_{th}$到最后一天买，所以我们想要贪心的话，只能从后往前思考。

用一个栈来维护遇到的$1$的下标

先从小到大遍历，如果遇到了$1$，那么就把压入栈里。
这样的话，栈顶的值肯定比栈底的值大。

之后从后往前遍历
如果遇到了$0$，看看栈里有没有$1$

如果有，那么栈顶的1就不用买，直接弹出
如果没有，那么什么都不做（）
然后$ans$加上当前的下标，因为当前的$0$一定要买。

遍历完之后，$0$已经买完了，如果栈里还有$1$，那么我们两两配对，取最小的那个，加到$ans$上。这个实现起来就是把栈里上面 $q.size()/2$ 的元素弹出，然后把剩下的加到$ans$上。

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void sol()
{
    ll n;
    cin >> n;
    string s;
    cin >> s;
    s = ' ' + s;
    ll ans = 0;
    ll need = 0;
    queue<int> q;
    for (int i = n; i >= 1; i--)
    {
        if (s[i] == '1')
            q.push(i);
        else
        {
            if (!q.empty())
                q.pop();
            ans += i;
        }
    }

    int op = q.size() / 2;
    while (op--)
        q.pop();
    
    while (!q.empty())
    {
        ans += q.front();
        q.pop();
    }
    cout << ans << endl;
}
int main()
{
    int t;
    cin >> t;
    while (t--)
        sol();
    return 0;
}