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

这场ABC全都犯病了（悲伤）

目录

• Educational Codeforces Round 171 (Rated for Div. 2) 题解(A-C)
• 目录
  • A. Perpendicular Segments
  • B. Black Cells
  • C. Action Figures

A. Perpendicular Segments

大意
给你一个坐标平面和三个整数 \(X\) 、 \(Y\) 和 \(K\) 。请找出两条线段 \(AB\) 和 \(CD\) ，使得

1. 点 \(A\) , \(B\) , \(C\) , \(D\) 的坐标都是整数；
2. \(0 \le A_x, B_x, C_x, D_x \le X\) 和 \(0 \le A_y, B_y, C_y, D_y \le Y\) ；
3. 线段 \(AB\) 的长度至少为 \(K\) ；
4. 线段 \(CD\) 的长度至少为 \(K\) ；
5. 线段 \(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