比賽連結

A

題意

給一個字串每個物品對應的燈的照明方向，L/R 能照亮它左側/右側的所有物品（不包括自己對應的物品），現在能交換相鄰兩個燈一次（不改變照明方向），問能否找亮所有物品。

題解

知識點：貪心。

顯然，如果存在 LR 或 RL 就可以照亮全部，否則全是 L 或 R 就不可行。

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

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

程式碼

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

using namespace std;

bool solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    s = "?" + s;
    for (int i = 1;i < n;i++) {
        if (s[i] != s[i + 1]) {
            if (s[i] == 'L') cout << i << '\n';
            else cout << 0 << '\n';
            return true;
        }
    }
    return false;
}

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

題意

構造一組數，使得任意相鄰兩項之和等於全部和。

題解

知識點：構造。

\(n\) 為偶數時，構造 \(1,-1,1,-1,\cdots\) 即可。

\(n\) 為奇數時，顯然奇數項和偶數項要各自相等，隨後由 \(a_1+\cdots+a_n = a_{n-1}+a_{n}\) 可以得到 \((n-1)a_1+(n-3)a_2 = 0\) ，取 \(a_1 = n-3,a_2 = 1-n\) 即可，只有 \(n=3\) 時無解（因為 \(a_1 = 0\)）。

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

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

程式碼

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

using namespace std;

bool solve() {
    int n;
    cin >> n;
    if (n & 1) {
        if (n == 3) return false;
        cout << "YES" << '\n';
        for (int i = 1;i <= n;i++) {
            if (i & 1) cout << n - 3 << ' ';
            else cout << 1 - n << ' ';
        }
        cout << '\n';
    }
    else {
        cout << "YES" << '\n';
        for (int i = 1;i <= n;i++) {
            if (i & 1) cout << 1 << ' ';
            else cout << -1 << ' ';
        }
        cout << '\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 << "NO" << '\n';
    }
    return 0;
}

C

題意

給一組數，可以修改元素變成其相反數。問最少修改幾次，可以使得第 \(m\) 個字首和 \(a_1+\cdots+a_m\) 是所有字首和裡最小的。

題解

知識點：字首和，數學，貪心。

定義 \(a[l,r] = a_l+\cdots+a_r\) 。

當 \(k\in [1,m-1]\) 時

當 \(k\in [m+1,n]\) 時

所以只要保證任意 \(i\in[2,m]\) ，滿足 \(a[i,m]\leq 0\) ；任意 \(i\in[m+1,n]\) ，滿足 \(a[m+1,i] \geq 0\) 即可。

每次操作時，貪心地取最優的即可。

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

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

程式碼

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

using namespace std;

int a[200007];
bool solve() {
    int n, m;
    cin >> n >> m;
    for (int i = 1;i <= n;i++) cin >> a[i];
    int cnt = 0;
    multiset<int> ms;
    ll sum = 0;
    for (int i = m;i >= 2;i--) {
        sum += a[i];
        ms.insert(a[i]);
        if (sum > 0) {
            sum -= 2 * (*prev(ms.end()));
            ms.erase(prev(ms.end()));
            cnt++;
        }
    }
    ms.clear();
    sum = 0;
    for (int i = m + 1;i <= n;i++) {
        sum += a[i];
        ms.insert(a[i]);
        if (sum < 0) {
            sum -= 2 * (*ms.begin());
            ms.erase(ms.begin());
            cnt++;
        }
    }
    cout << cnt << '\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_i\) 。

理髮師有刀片 \(x_i\) ，每個刀片只能用一次，每次可以修減一段連續區間的頭髮，滿足 \(a'_i = \min(a_i,x),i\in[L,R]\)。

問理髮師能不能通過這些刀片將 \(a\) 修剪至 \(b\) 。

題解

知識點：單調棧。

顯然 \(a_i<b_i\) 無解。

利用最大值單調棧維護刀片的值。以下按順序滿足：

1. \(b_i\) 大於棧頂刀片，則棧頂刀片因為太小不能再用了，刀片需要出棧直至 \(b_i\) 小於等於棧頂刀片或棧空。
2. \(b_i = a_i\) ，說明 \(b_i\) 不需要修剪，什麼都不用幹。
3. \(b_i \neq a_i\) ，說明 \(b_i\) 需要修剪，此時如果 \(b_i\) 小於棧頂刀片或棧空，則需要使用新的刀片，滿足 \(x = b[i]\) ，如果不存在這個刀片則無解。

全部滿足後，即 YES 。

程式碼

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

using namespace std;

int a[200007];
int b[200007];
bool solve() {
    int n;
    cin >> n;
    for (int i = 1;i <= n;i++) cin >> a[i];
    for (int i = 1;i <= n;i++) cin >> b[i];
    int m;
    cin >> m;
    map<int, int> mp;
    for (int i = 1;i <= m;i++) {
        int x;
        cin >> x;
        mp[x]++;
    }
    stack<int> st;
    for (int i = 1;i <= n;i++) {
        if (a[i] < b[i]) return false;
        while (!st.empty() && b[i] > st.top()) st.pop();
        if (a[i] != b[i]) {
            if (st.empty() || b[i] < st.top()) {
                if (mp[b[i]]) {
                    mp[b[i]]--;
                    st.push(b[i]);
                }
                else return false;
            }
        }
    }
    cout << "YES" << '\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 << "NO" << '\n';
    }
    return 0;
}