YACS2023年8月乙组

V_Melville精進録 / 2023-09-05 / 原文

T1：序列最大公约数

$\mathcal{O}(\sqrt{s})$ 枚举 $\gcd$ 即可

代码实现

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n, s;
    cin >> n >> s;
    
    int ans = 0;
    for (int i = 1; i*i <= s; ++i) {
        if (s%i != 0) continue;
        if (i >= n) ans = max(ans, s/i);
        if (s/i >= n) ans = max(ans, i);
    }
    
    cout << ans << '\n';
    
    return 0;
}

双倍经验：CF803C

T2：最长回文

经典区间 $\operatorname{dp}$ 题

记 dp[i][j] 表示对于字符串 $s$ 的子串 s[i:j] 删除若干字符使得 s[i:j] 变成回文串最少需要删除的字符数

代码实现

#include <bits/stdc++.h>

using namespace std;

int main() {
    string s;
    cin >> s;
    int n = s.size();
    
    vector dp(n, vector<int>(n));
    for (int span = 2; span <= n; ++span) {
        for (int i = 0; i <= n-span; ++i) {
            int j = i+span-1;
            dp[i][j] = min(dp[i+1][j], dp[i][j-1]) + 1;
            if (s[i] == s[j]) {
                dp[i][j] = min(dp[i][j], dp[i+1][j-1]);
            }
        }
    }
    
    cout << dp[0][n-1] << '\n';
    
    return 0;
}

T3：香槟塔

注意到，当香槟杯已经满了的话，对我们来说就没用了，我们可以用 std::set 来维护还没有装满的香槟杯，如果装满了就从 std::set 中移除即可

对于操作 1，我们可以利用 std::set 二分找到 $\geqslant x$ 的最小的位置，然后直接跳到这个位置来模拟即可，而不需要再从 $x$ 开始

代码实现

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<int> w(n);
    rep(i, n) cin >> w[i];
    
    set<int> s;
    rep(i, n) s.insert(i);
    
    int q;
    cin >> q;
    
    vector<int> ans(n);
    rep(qi, q) {
        char type; int x;
        cin >> type >> x;
        --x;
        if (type == 'A') {
            int y;
            cin >> y;
            
            auto it = s.lower_bound(x);
            while (it != s.end() and y) {
                int i = *it;
                int d = min(y, w[i]-ans[i]);
                y -= d;
                ans[i] += d;
                if (ans[i] == w[i]) s.erase(it++);
            }
        }
        else {
            cout << ans[x] << '\n';
        }
    }
    
    return 0;
}

双倍经验：CF371D

T4：极值的和

我们可以固定每个数 $a_i$，并以 $a_i$ 作为最大值，求以 $a_i$ 为最大值的区间个数，那么我们只需找到距离 $i$ 左边最近的大于它的位置以及右边最近的大于它的位置即可，不妨记做 $l_i$ 和 $r_i$
然后，根据乘法原理，以 $a_i$ 为最大值的区间个数就是 $(i-l_i) \times (r_i-i)$

对于 $l_i$ 和 $r_i$ 可以用单调栈来求

于是 $\sum\limits_{1 \leqslant i \leqslant j \leqslant n} \max(a_i, a_{i+1}, \cdots, a_j) = \sum\limits_{i=1}^n (i-l_i) \times (r_i-i) \times a_i$

代码实现

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

int main() {
    int n;
    cin >> n;
    
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    
    vector<int> l(n), r(n, n);
    stack<int> s;
    rep(i, n) {
        while (s.size() and a[s.top()] <= a[i]) {
            r[s.top()] = i;
            s.pop();
        }
        l[i] = !s.size() ? -1 : s.top();
        s.push(i);
    }
    
    ll ans = 0;
    rep(i, n) {
        ans += ll(i-l[i])*(r[i]-i)*a[i];
    }
    
    cout << ans << '\n';
    
    return 0;
}

双倍经验：P6503