CF Edu171 ABC

這場ABC全都犯病了（悲傷）
D E 還沒有補，到時候補上。

目錄

• Educational Codeforces Round 171 (Rated for Div. 2) 題解(A-C)
• 目錄
  • A. Perpendicular Segments
  • B. Black Cells
  • C. Action Figures
  • D. Sums of Segments
  • E. Best Subsequence

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

大意
在莫諾卡普家附近有一家出售動作人偶的商店。一套新的公仔即將推出；這套公仔包含 \(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;
}

D. Sums of Segments

E. Best Subsequence