寫在開頭

有不足的地方各位佬多多指教呀！

持續更新（bushi）

Update-20251104

更改了數學公式渲染方式。

A

題面

給定李華的初始rating \(R\) ，div.2的計分上限 \(X\)，李華每次rating的變化最大值 \(D\)，以及cf比賽的次數 \(n\)，問李華最多可以正式參加多少場cf。

\( 0 \le R \le 10^9 \\ 1 \le X \le 10^9 \\ 1 \le D,n \le 1000 \\ \sum{n} \le 3 \times 10^4 \)

解析

由于div.1沒有計分下限，所以讓李華的rating盡可能低即可。

時間復雜度為 \(O(n)\)。

代碼

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int rat, x, d, n;
        cin >> rat >> x >> d >> n;
        string s;
        cin >> s;
        int num = 0;
        for(int i = 0; i < n; i++)
            if(s[i] == '1'){
                num++;
                if(rat >= x)
                    rat -= d;
            }else{
                if(rat < x)
                    num++;
            }
        cout << num << '\n';
    }
    return 0;
}

B

題面

給定一個 \(n \times n\) 的表格，每個格子被染上黑白兩色中的一個，你可以選擇任意多個白色格子并將其染黑，問是否存在一種染色使得所有的黑格是聯通的（對角相連不算聯通），并且在任一行或一列存在連續3個黑格。

\( 1 \le n \le 100 \\ \sum{n} \le 2000 \)

解析

用 \(0\) 表示白格，用 \(1\) 表示黑格（這里與原題符號不一樣），那么關鍵發現是所有的滿足條件的方案一定是如下形狀的：

只有四個黑格構成一個正方形。

\( 0000\\ 0110\\ 0110\\ 0000\\ \)

一條蛇形

\( 110000000\\ 011000000\\ 001100000\\ 000110000\\ 000011000\\ 000001100\\ 000000110\\ 000000011\\ 000000001\\ \)

還是蛇形，方向變了

\( 000000110\\ 000001100\\ 000011000\\ 000110000\\ 001100000\\ 011000000\\ 110000000\\ 000000000\\ 000000000\\ \)

因此我們只需要判斷這些情況即可。

第一種情況可以直接判斷是否只有四個黑格并且他們構成正方形，如果初始情況不是4個黑格而是一個子圖，那么可以并入情況二和三。

第二種情況可以判斷所有的黑格是否全部落在相鄰的兩個對角線上，如果用 \(a_{ij}\) 表示格子，那么這等價于 \(abs(i - j)\) 的值是否是相鄰的兩個整數。

情況三和二類似，只是判斷的時候將 \(i - j\) 改為 \(i + j\) 即可。

我判斷情況二和三的方案是用了兩個 \(set\)，將每個黑格的 \(i - j\) 和 \(i + j\) 插入集合即可。

時間復雜度 \(O(n^2 \log{n})\)。

代碼

#include <bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        set <int> s1, s2;
        vector <pair <int, int>> pos;
        vector <vector <char>> a(n, vector <char> (n));
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++){
                cin >> a[i][j];                
                if(a[i][j] == '#')
                    s1.insert(i + j), 
                    s2.insert(i - j),
                    pos.push_back({i, j});
            }
        bool tag = 0;
        if(s1.size() == 2){
            vector <int> v(s1.begin(), s1.end());
            if(abs(v[0] - v[1]) == 1)
                tag = 1;
        }
        if(s2.size() == 2){
            vector <int> v(s2.begin(), s2.end());
            if(abs(v[0] - v[1]) == 1)
                tag = 1;
        }
        if(s1.size() < 2 || s2.size() < 2)
            tag = 1;
        if(pos.size() == 4){
            sort(pos.begin(), pos.end());
            int x = pos[0].first, y = pos[0].second;
            if(pos[1] == make_pair(x, y + 1) && pos[2] == make_pair(x + 1, y) && pos[3] == make_pair(x + 1, y + 1))
                tag = 1;
        }
        cout << (tag ? "Yes\n" : "No\n");
    }
    return 0;
}

C

題面

你要購買 \(n\) 個物品，每個物品價值 \(a_i\)，給定 \(x\) 為忠誠度，每個物品價值不超過 \(x\)，定義忠誠度等級為 \(\lfloor \frac{s}{x} \rfloor\)，其中 \(s\) 為當前已經購買的物品的價值綜合，如果購買某個物品時忠誠度等級升級了，那么當前購買物品的價值就是升級獲得的積分，求可獲得的最多的積分以及對應的一個方案。

\( 1 \le n \le 10^5 \\ 1 \le x \le 10^9 \\ 1 \le a_i \le x \\ \sum n \le 10^5 \)

解析

最終購買的物品總價值是固定的，因此升級次數 \(k\) 是固定的，最貪心的是這 \(k\) 次升級時購買的物品是價值最多的 \(k\) 個物品。這可以由以下構造完成：

定義 \(sum\) 為當前購買的物品的價值和對 \(x\) 取模后的結果（即 \(sum = s \mod{x}\)），每次選擇要買的物品時使用如下策略：如果還未被購買的物品中價值最大的（記其價值為 \(a_{max}\)）滿足 \(sum + a_{max} \ge x\)，那么就購買它，否則購買價值最小的，每次買完后更新 \(sum\)。不難發現如果價值最大的都無法升級時價值小的也無法升級，所以取出的都是價值最大的。

時間復雜度 \(O(n \log{n})\)，瓶頸在排序。

代碼

#include <bits/stdc++.h>
using namespace std;
#define ll long long

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int n, x;
        cin >> n >> x;
        ll sum = 0ll;
        vector <int> a(n + 1, 0);
        for(int i = 1; i <= n; i++){
            cin >> a[i];
            sum += a[i];
        }
        sort(a.begin() + 1, a.end());
        int k = sum / x;
        ll ans = 0ll;
        for(int i = n; i > n - k; i--)
            ans += a[i];
        cout << ans << '\n';
        int l = 1, r = n, num = 0;
        while(l <= r){
            if(num + a[r] >= x){
                num = (num + a[r]) % x;
                cout << a[r] << ' ';
                r--;
            }else{
                num += a[l];
                cout << a[l] << ' ';
                l++;
            }
        }
        cout << '\n';
    }
    return 0;
}

D

題面

給定一個長為n的數組b，問最少移除多少個元素，才能使得不存在 \(i\)，\(j\)，使得 \(1 \le i \lt j \le n\) 且 \(b_j - b_i = 1\)（不妨把滿足這種條件的 \(i\)，\(j\) 對成為壞的）。

\( 1 \le n \le 3 \times 10^5 \\ 1 \le b_i \le n \\ \sum{n} \le 3 \times 10^5 \)

解析一

考慮問題的反面，最多可以取多少個元素，我們來進行 \(dp\)。

考慮一個 \(pair\) 數組 \(a\)，\(a_i = \{ b_i, i \}\)，將這個數組排序，第一關鍵字按增序排列，第二關鍵字按降序排列，記 \(dp_i\) 表示排列后前 \(i\) 個數最多可以取多少個，那么有狀態轉移方程如下：

最后 \(n - \max{dp}\) 就是答案。

那為什么是這樣？考慮這樣一組樣例：
n = 3, a[n] = {2, 1, 3}。
如果我們直接用 \(dp_i = 1 + \max_{j \lt i, a_j.first + 1 \ne a_i.first} {dp_j}\) 來轉移會有一個問題，在更新 \(3\) 的 \(dp\) 值時因為有 \(1\) 的影響會直接更新為 \(3\)，但是 \((2, 3)\) 也是不被允許的，更新錯誤的原因在于 \(2\) 和 \(3\) 沒有緊挨著。所以我們可以按 \(a.first\) 的值的順序來更新，這個時候對于位于 \(i\) 后面的 \(j\) 但是滿足 \(b_j + 1 = b_i\) 這樣的數可以用其 \(dp\) 值直接更新 \(dp_i\)，于是得到了上面的轉移方程。至于為什么第二關鍵字是倒序，這時因為對于 \(a.first\) 相等的數來說，它的原本的位置越靠前，越容易繼承到第一關鍵字比它小但是第二關鍵字比它大的數的 \(dp\) 值。

考慮如何維護這個 \(max\)，不難發現，處理到 \(i\) 的時候所有已經處理過的數都是第一關鍵字不大于 \(a_i.first\) 的數，于是分為三類，第一類是 \(a_j.first + 2 \le a_i.first\)，這一類用樹狀數組維護最值（這里相當于將第二類情況延時處理了一輪），第二類是 \(a_j.first + 1 = a_i.first\)，這一類比較第二關鍵字，第三類是 \(a_j.first = a_i.first\)，這一類直接繼承前一個數的 \(dp + 1\) 值，同時如果在某個 \(j\) 滿足第二類時特別處理一下即可。

時間復雜度 \(O(n \log{n})\)。

代碼

#include <bits/stdc++.h>
using namespace std;
typedef pair <int, int> pii;

template <class T>
struct Fenwick{
    int n;
    vector <T> tr;

    Fenwick(int _n){init(_n);}

    void init(int _n){
        n = _n;
        tr.assign(n + 1, T{});
    }

    int lowbit(int x){return x & -x;}

    void add(int x, T w){
        for(int i = x; i <= n; i += lowbit(i))
            tr[i] = tr[i] + w;
    }

    T query(int x){
        T ans{};
        for(int i = x; i; i -= lowbit(i))
            ans = ans + tr[i];
        return ans;
    }
};

struct i32{
    int x;

    i32 operator+ (const i32 n) const{
        return {max(x, n.x)};
    }
};

void solve(){
    int n;
    cin >> n;
    vector <pii> a(n + 1), d(n + 1, {0, 0});
    vector <int> dp(n + 1, 0);
    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        a[i] = {x, i};
    }
    sort(a.begin() + 1, a.end(), [&](pii x, pii y){
        if(x.first == y.first) return x.second > y.second;
        return x.first < y.first;
    });
    for(int i = 1; i <= n; i++){
        if(!d[a[i].first].first) 
            d[a[i].first].first = i;
        d[a[i].first].second = i;
    }
    Fenwick <i32> t(n);
    auto find = [&](int s, int t, int x){
        int ans = -1;
        while(s <= t){
            int mid = s + ((t - s) >> 1);
            if(a[mid].second > x)
                ans = mid, s = mid + 1;
            else 
                t = mid - 1;
        }
        return ans;
    };
    for(int i = 1; i <= n; i++){
        if(d[i].first){
            int m = t.query(n).x + 1;
            for(int j = d[i].first; j <= d[i].second; j++){
                if(d[i - 1].first){
                    int x = find(d[i - 1].first, d[i - 1].second, a[j].second);
                    if(x != -1)
                        dp[a[j].second] = max(m + j - d[i].first, dp[a[x].second] + 1);
                    else
                        dp[a[j].second] = m + j - d[i].first;
                }else
                    dp[a[j].second] = m + j - d[i].first;
                if(j > d[i].first)
                    dp[a[j].second] = max(dp[a[j - 1].second] + 1, dp[a[j].second]);
            }
        }
        if(d[i - 1].first)
            for(int j = d[i - 1].first; j <= d[i - 1].second; j++)
                t.add(a[j].second, {dp[a[j].second]});
    }
    if(d[n].first)
        for(int j = d[n].first; j <= d[n].second; j++)
            t.add(a[j].second, {dp[a[j].second]});
    cout << n - t.query(n).x << '\n';
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t--) solve();
    return 0;
}

解析二

這個做法來自于 \(peltorator\)（cf名），代碼鏈接：https://codeforces.com/contest/2161/submission/346684700

這是本蒟蒻在比賽的評論區發現的大佬的解答orz，感覺很妙，在這里分享給各位佬。

考慮構造一個圖，將所有的壞的 \(i\)，\(j\) 對之間連一條邊，那么這道題變為找這個圖的最小點覆蓋，注意到這個圖是個二分圖，因為點 \(i\) 僅和值為 \(b_i + 1\) 的點相連，所以由K?nig定理，最小點覆蓋等于最大邊匹配，這個邊匹配可以貪心的取：

先找 \(b_i\) 的值最小的 \(i\)， 如果有一樣小的就取 \(i\) 值最大的，如果它和點 \(j\) 連有邊，那么一定有 \(b_j = b_i + 1\)，我們在所有滿足這個條件的 \(j\) 中選擇 \(j\) 值最大的，然后將 \(i\) 和 \(j\) 一同刪去，重復這個過程。

時間復雜度 \(O(n)\)。