2024六月APCS題解

1. 特技表演

大意：求出給定長度為

$N$的序列

$⟨A_i⟩$的最長嚴格下降子區間的長度。
解法：可以把這個序列切成很多嚴格下降子區間——當

$A_{i+1}\ge A_i$時，

$A_{i+1}$會是一個新的嚴格下降子區間的開頭，然後要求的是以

$A_i$為結尾的嚴格下降子區間的長度最長是多少。

時間複雜度：

$O(N)$。
空間複雜度：

$O(1)$。

code:

#include <bits/stdc++.h>
#define ALL(x) begin(x), end(x)
using namespace std;
using i64 = long long;

template <class T>
using vec = vector<T>;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n; cin >> n;
    int pre = numeric_limits<int>::max() / 2;
    int ans = 0;
    for (int x, cnt = 0; n--; ) {
        cin >> x;
        if (x >= pre) cnt = 0;
        ans = max(ans, ++cnt);
        pre = x;
    }
    cout << ans << '\n';
}

2. 電子畫布

大意：有

$N$次操作，要把和

$(r,c)$的曼哈頓距離

$\le t$的格子的值都加上

$x$，問最後每個格子的值是多少。
解法：每次操作都去看所有格子有沒有滿足上面講的條件，如果有的話才把值加上

$x$。

時間複雜度：

$O(HWN)$。
空間複雜度：

$O(HW)$。

code:

#include <bits/stdc++.h>
#define ALL(x) begin(x), end(x)
using namespace std;
using i64 = long long;

template <class T>
using vec = vector<T>;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int h, w, q; cin >> h >> w >> q;
    vec<int> val(h * w, 0);
    for (int r, c, t, x; q--; ) {
        cin >> r >> c >> t >> x;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (abs(r - i) + abs(c - j) <= t) val[i * w + j] += x;
            }
        }
    }
    for (int i = 0; i < h * w; i++) cout << val[i] << " \n"[(i + 1) % w == 0];
}

3. 缺字問題

大意：給定一個大小為

$K$個字母的集合和字串

$S$，求出在使用該集合所組出長度為

$L$的字串中，不為字串

$S$的子字串的最小字典序字串為何。
解法：先預處理每個字母在字母集中比多少人大，記為

$\text{id}(c)$，之後定義

$f(l,r)=\sum _{i=l}^{r-1}\text{id}(s_i)\times K^{r-1-i}$，於是就可以使用

$f(l,r)$的值來比較字典序，

$f$越小字典序越小。最後要求的就是

$\text{mex}(f(0,L),f(1,L+1),\dots ,f(|S|-L,|S|))$表示的字串。
另一個解法是：先把

$S_{0\sim L},S_{1\sim L+1},\dots ,S_{(|S|-L)\sim |S|}$這些字串丟進一個set裡面，再用dfs的方式枚舉所有

$K^L$個字串（其實因為

$\text{mex}$的性質，最多跑

$|S|-L+2$個字串就一定會找到），依照字典序枚舉，第一個不在那個set裡面的字串就是答案了。

第一種解法的時間複雜度：

$O(|S|)$、空間複雜度：

$O(|S|)$。
第二種解法的時間複雜度：

$O(L|S|\log |S|)$、空間複雜度：

$O(L|S|)$。

code(第一種解法):

#include <bits/stdc++.h>
#define ALL(x) begin(x), end(x)
using namespace std;
using i64 = long long;

template <class T>
using vec = vector<T>;

constexpr int maxN = 300000;

bitset<maxN> vis;

int pre[26];

char mp[10];

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int S_len = 0;
    auto id = [](char c) -> int { return pre[c - 'a'] - 1; };
    {
        string s; cin >> s;
        S_len = s.length();
        for (auto c : s) ++pre[c - 'a'];
        for (int i = 1; i < 26; i++) pre[i] += pre[i - 1];
        for (auto c : s) mp[id(c)] = c;
    }
    int len; cin >> len;
    string s; cin >> s;
    int N = (int)s.length();
    int hash_val = 0, mul = 1;
    for (int i = 0; i < len; i++) {
        hash_val = hash_val * S_len + id(s[i]);
        if (i) mul *= S_len;
    }
    if (hash_val < N) vis[hash_val] = true;
    for (int i = len; i < N; i++) {
        hash_val -= id(s[i - len]) * mul;
        hash_val = hash_val * S_len + id(s[i]);
        if (hash_val < N) vis[hash_val] = true;
    }
    string ans;
    int x = [&]() -> int {
        for (int i = 0; i < N; i++) if (!vis[i]) return i;
        return N;
    }();
    for (int t = len; t--; ) {
        ans.push_back(mp[(x % S_len)]);
        x /= S_len;
    }
    reverse(ALL(ans));
    cout << ans << '\n';
}

4. 最佳選擇

大意：給一個長度為

$N$的正整數序列

$⟨A_i⟩$，你可以做0次以上的操作——拿走這個序列的第一個或最後一個數字，做完操作之後，拿走的所有數字裡面，偶數和奇數要一樣多，且他們的和不超過

$K$，問最大的和可以是多少？
解法：可以拿的其實是一個前綴和一個不和那個前綴重疊的後綴，所以對每個前綴和

${\text{pre}}_i$，前綴奇數偶數數量差

${\text{diff}}_i$，用

${\text{diff}}_i$分類來存

$({\text{pre}}_i,i)$的pair，之後枚舉後綴查詢和他配的最好的前綴是多少，注意前綴會因為他的位置而過期。
時間複雜度：

$O(N)$。
空間複雜度：

$O(N)$。

code:

#include <bits/stdc++.h>
#define ALL(x) begin(x), end(x)
using namespace std;
using i64 = long long;

template <class T>
using vec = vector<T>;

constexpr int maxDIFF = 2000;

vec<pair<int, int>> pref[maxDIFF * 2 + 1];

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    auto add = [](int diff, int pre, int i) -> void {
        pref[diff + maxDIFF].emplace_back(pre, i);
    };
    auto is_empty = [](int diff) -> bool {
        return pref[diff + maxDIFF].empty();
    };
    auto top = [](int diff) {
        return pref[diff + maxDIFF].back();
    };
    auto pop = [](int diff) -> void {
        pref[diff + maxDIFF].pop_back();
    };
    int n, k; cin >> n >> k;
    vec<int> v(n);
    for (int i = 0, diff = 0, pre = 0; i < n; i++) {
        cin >> v[i];
        diff += ((v[i] & 1) ? 1 : -1);
        pre += v[i];
        add(diff, pre, i);
    }
    int ans = ((is_empty(0) || top(0).first > k) ? 0 : top(0).first);
    for (int i = n - 1, diff = 0, suf = 0; i >= 0; i--) {
        diff += ((v[i] & 1) ? 1 : -1);
        suf += v[i];
        if (suf > k) break;
        if (diff < -maxDIFF || diff > maxDIFF) continue;
        while (!is_empty(-diff) && (top(-diff).second >= i || top(-diff).first + suf > k)) pop(-diff);
        if (diff == 0) ans = max(ans, suf);
        if (!is_empty(-diff)) ans = max(ans, suf + top(-diff).first);
    }
    cout << ans << '\n';
}