比賽連結

A

題解

知識點：貪心。

對於一個軌道，要麼一次性清理，要麼一個一個清理。顯然，如果行星個數大於直接清理的花費，那麼選擇直接清理，否則一個一個清理。即 \(\sum \min (c,cnt[i])\)，其中 \(cnt[i]\) 表示軌道 \(i\) 的行星個數。

時間複雜度 \(O(n)\)

空間複雜度 \(O(1)\)

程式碼

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int cnt[107];

bool solve() {
    int n, c;
    cin >> n >> c;
    memset(cnt, 0, sizeof(cnt));
    for (int i = 1;i <= n;i++) {
        int x;
        cin >> x;
        cnt[x]++;
    }
    int ans = 0;
    for (int i = 1;i <= 100;i++) ans += min(c, cnt[i]);
    cout << ans << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

B

題解

方法一

知識點：三分。

按位元置從小到大排列，顯然約會花費是一個關於 \(x_0\) 的單谷函數，因此可以三分位置。

由於位置最大有 \(10^8\) ，但點的個數只有 \(10^5\) ，考慮先用 map 儲存有序對 \((x,t)\) ，其中 \(t\) 是位置 \(x\) 的人最大打扮時間，因為比這個時間少的一定不影響結果。遍歷結束以後把 map 內容移到 vector 中用 pair 儲存用以三分，check 函數則只要遍歷一遍 vector 即可。

時間複雜度 \(O(n \log \max(eps))\)

空間複雜度 \(O(n)\)

方法二

知識點：貪心。

把 \(t\) 等效進位置，如果 \(x_i\) 在 \(x_0\) 左側，則等效位置是 \(xi - t\) ;如果 \(x_i\) 在 \(x_0\) 右側，則等效位置是 \(x_i + t\) 。

所有點的左側等效位置最左的位置，就是等效區間左端點；所有點的右側等效位置最右的位置就是等效區間的右端點。

如果等效區間的左右端點來自於不同兩點的等效點，那麼等效區間的中點一定在這兩點之間，否則原來的點必有一個能覆蓋另一個點，等效區間的左右端點就屬於同一個點的等效點。

時間複雜度 \(O(n)\)

空間複雜度 \(O(n)\)

程式碼

方法一

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int x[100007];
map<int, int> mp;
vector<pair<int, int>> v;

double check(double mid) {
    double mx = 0;
    for (auto [i, j] : v) {
        mx = max(mx, abs(i - mid) + j);
    }
    return mx;
}

bool solve() {
    mp.clear();
    v.clear();
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) {
        cin >> x[i];
        mp[x[i]] = 0;
    }
    for (int i = 1;i <= n;i++) {
        int T;
        cin >> T;
        mp[x[i]] = max(mp[x[i]], T);
    }
    for (auto [i, j] : mp) {
        v.push_back({ i,j });
    }

    double l = 0, r = v.back().first;
    while (abs(r - l) >= 1e-7) {
        double mid1 = l + (r - l) / 3;
        double mid2 = r - (r - l) / 3;
        if (check(mid1) <= check(mid2)) r = mid2;
        else l = mid1;
    }
    cout << fixed << setprecision(10) << l << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

方法二

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int x[100007], T[100007];

bool solve() {
    int n;
    cin >> n;
    int l = 1e9, r = 0;
    for (int i = 1;i <= n;i++) cin >> x[i];
    for (int i = 1;i <= n;i++) cin >> T[i];
    for (int i = 1;i <= n;i++) {
        l = min(x[i] - T[i], l);///最左側等效點
        r = max(x[i] + T[i], r);///最右側等效點
    }
    cout << fixed << setprecision(8) << (l + r) / 2.0 << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

C

題解

知識點：貪心。

因為要字典序最小，那麼一個數位他後面沒有更小的數位則可以保留，其他都應該刪除，所以從右往左找一個合法的保留序列，其他的數位加一，並且都是位置隨意的，於是可以插入到保留下來的序列，並使插入後的序列是從小到大字典序最小的排列。因此直接把保留序列外的數位加一以後，對整個序列排序即可。

也可以直接桶排序。

時間複雜度 \(O(n \log n)\)

空間複雜度 \(O(n)\)

程式碼

#include <bits/stdc++.h>
#define ll long long

using namespace std;


bool solve() {
    string s;
    cin >> s;
    int mi = 10;
    for (int i = s.size() - 1;i >= 0;i--) {
        if (s[i] - '0' <= mi) mi = s[i] - '0';
        else s[i] = min(s[i] + 1, '9' + 0);
    }
    sort(s.begin(), s.end());
    cout << s << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}

D

題解

知識點：構造。

注意到操作不會改變無序對 \((a_i, b_{ n - i + 1 })\) 數量以及種類。

引理：\(a = b\) ，當且僅當無序對是迴文的。

充分性：

當 \(a = b\) 時，如果 \(i\) 處存在一組無序對 \((x, y)\) ，則必然會在 \(n-i+1\) 產生相同一組無序對 \((y, x)\) ，除非當 \(n\) 為奇數時，可以在中間產生一個元素相同的無序對 \((x,x)\) ，因此 \(a = b\) 時，無序對必然成迴文狀。

必要性：

當無序對是迴文的，則第 \(i\) 組無序對 \((x,y)\) 可以對應第 \(n-i+1\) 組無序對 \((y,x)\) ，即 \(a_i = b_i\) ,所以 \(a = b\) 。

充要條件：YES 當且僅當無序對 \((a_i, b_{ n - i + 1 })\) 中元素不同的無序對有偶數個，元素相同的無序對僅在 \(n\) 為奇數時至多 \(1\) 種有奇數個。

充分性：

根據引理，顯然滿足右邊條件。

必要性：

顯然沒有任何限制時，給出的無序對條件能排列成迴文的，現在嘗試證明其必然可構造無序對迴文。

注意到操作 \(k = i\) 可以使得 \(a[1 \cdots k]\) 和 \(b[k\cdots n]\) 交換位置，即 \((a[k], b[n - k + 1])\) 這一組無序對被置換到了 \(1\) 號位置，同時 \((a[1],b[n])\) 這一組無序對被置換到了 \(i\) 號位置，但這不會改變 \(a[k+1 \cdots n]\) 和 \(b[1\cdots k-1]\) 的順序，即第 \(k+1\) 到 \(n\) 組無序對及其實際元素順序沒有改變。因此，如果我們想要將無序對通過操作變成一個我們想要的順序，可以從右往左構造。

假設 \(i+1\) 到 \(n\) 的無序對都安排好了，現在 \(i\) 號位置想要 \(j (j\leq i)\) 號位置的無序對時，可以先 \(k=j\) ，將 \(j\) 號替換到 \(1\) 號，然後 \(k=i\) ，將 \(1\) 號替換 \(i\) 號，過程中 \(i+1 \cdots n\) 的無序對不會改變，包括實際元素順序。

上述操作最後結果是無序對 \(j\) 替換到 \(i\) ，且 \(j\) 號無序對元素的實際順序不會改變。但如果我們希望實際元素的順序也發生改變，我們可以加一個步驟 \(k = 1\) 在中間，即通過 \(k = j, k = 1, k = i\) 替換 \(i\) 號後的 \(j\) 號元素實際順序與原來是相反的，這也是為什麼我們只需要知道無序對順序即可，因為元素實際順序是可以隨時改變的。

通過上述操作我們可以實現無序對的任意排列，以及無序對實際元素的順序。因此無序對滿足迴文條件時，必然可以構造出無序對迴文。於是根據引理，得到 \(a = b\) 。

時間複雜度 \(O(n)\)

空間複雜度 \(O(n)\)

程式碼

#include <bits/stdc++.h>
#define ll long long

using namespace std;

string a, b;
int cnt[26][26];

bool solve() {
    memset(cnt, 0, sizeof(cnt));
    int n;
    cin >> n;
    string a, b;
    cin >> a >> b;
    for (int i = 0;i < n;i++) {
        int x = a[i] - 'a', y = b[n - 1 - i] - 'a';
        if (x > y) swap(x, y);
        cnt[x][y]++;
    }

    bool ok = true;
    int esum = 0;
    for (int i = 0;i < 26;i++) {
        for (int j = i;j < 26;j++) {
            if (i == j) esum += cnt[i][j] & 1;
            else ok &= !(cnt[i][j] & 1);
        }
    }

    if (ok && esum <= (n & 1)) cout << "YES" << '\n';
    else cout << "NO" << '\n';
    return true;
}

int main() {
    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        if (!solve()) cout << -1 << '\n';
    }
    return 0;
}