2025暑假提高级冲刺集训班-8 题解

__xxy_free_ioi__ · 2025-07-23 15:53:57 · 个人记录

坠机了。

T1 [ARC134A] Bridge and Sheets

模拟题，不讲，但注意不要用 ceil 函数，会有精度问题。

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define PII pair<int, int>
#define VI vector<int>
#define sz(a) a.size()
#define all(a) a.begin(), a.end()
#define up(i, s, t) for (int i = s; i <= t; i++)
#define dw(i, s, t) for (int i = s; i >= t; i--)

const int N = 1e5 + 5;

int n, res, L, W, a[N];

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> L >> W;
    up(i, 1, n) cin >> a[i];
    a[0] = -W, a[++n] = L;
    up(i, 1, n) {
        int t = max(0ll, a[i] - a[i - 1] - W);
        res += (t + W - 1) / W;
    } 
    cout << res << '\n';

    return 0;
}

T2 [ABC153E] Crested Ibis vs Monster

完全背包板子，不讲。

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define PII pair<int, int>
#define VI vector<int>
#define sz(a) a.size()
#define all(a) a.begin(), a.end()
#define up(i, s, t) for (int i = s; i <= t; i++)
#define dw(i, s, t) for (int i = s; i >= t; i--)

const int M = 2e4 + 2, N = 1e3 + 2;

int m, n, a[N], b[N], f[M];

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int mxa = 0;
    cin >> m >> n;
    up(i, 1, n) cin >> a[i] >> b[i], mxa = max(mxa, a[i]);
    fill(f + 1, f + m + mxa + 1, 2e9);
    up(i, 1, n) up(j, a[i], m + mxa)
        f[j] = min(f[j], f[j - a[i]] + b[i]);
    int res = 1e15;
    up(i, m, m + mxa) res = min(res, f[i]);
    cout << res << '\n';

    return 0;
}

T3 [tessoku_book_ec B56] Palindrome Queries

两种解法。

解法一：

跑一遍马拉车，看看相同对称中心的最大回文半径是否大于等与询问字符串的半径即可判断。

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define PII pair<int, int>
#define VI vector<int>
#define sz(a) a.size()
#define all(a) a.begin(), a.end()
#define up(i, s, t) for (int i = s; i <= t; i++)
#define dw(i, s, t) for (int i = s; i >= t; i--)

const int N = 2e5 + 10;

int n, q, rad[N];
char s[N];

void read() {
    char c;
    s[0] = '#';
    while (cin >> c && c >= 'a' && c <= 'z') s[++n] = 'A', s[++n] = c;
    cin.unget();
    s[++n] = 'A';
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int mid = 0, r = 0, l;
    cin >> n >> q;
    n = 0, read();
//  up(i, 1, n) cout << s[i];
//  cout << '\n';
    up(i, 1, n) {
        int j = 2 * mid - i;
        if (r < i) rad[i] = 1;
        else rad[i] = min(rad[j], r - i + 1);
        while (s[i - rad[i]] == s[i + rad[i]]) rad[i]++;
        if (i + rad[i] - 1 > r) {
            r = i + rad[i] - 1; 
            mid = i;            
        }
    }
    while (q-- && cin >> l >> r) {
        l = l * 2, r = r * 2;
//      cout << s[l] << ' ' << s[(l + r) / 2] << ' ' << s[r] << '\n';
        int len = r - l + 1;
        if (rad[(l + r) / 2] >= (len + 1) / 2) cout << "Yes\n";
        else cout << "No\n";
    }

    return 0;
}

解法二：

跑两遍哈希，判断从前面跑是否等于从后面跑的即可判断是否是回文串。

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define VI vector<int>
#define sz(a) (int)a.size()
#define all(a) begin(a), end(a)
#define up(i, s, t) for (int i = s; i <= t; i++)
#define dw(i, s, t) for (int i = s; i >= t; i--)

const int N = 2e5 + 4, x = 123, MOD = 998244353;

int XP[N];

struct Hash {
    VI H;
    Hash(const string& ss) : H(ss.size() + 1) {
        int n = ss.size();
        dw(i, n - 1, 0) H[i] = (ss[i] - 'a' + 1 + H[i + 1] * x % MOD) % MOD;
    }
    int hash(size_t i, size_t j) { 
        return (H[i] - H[j + 1] * XP[j - i + 1] % MOD + MOD) % MOD;
    }
};

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int n, Q, l, r;
    string s, t;
    XP[0] = 1;
    up(i, 1, N - 1) XP[i] = XP[i - 1] * x % MOD;
    cin >> n >> Q >> s, t = s, reverse(all(t));
    Hash h1(s), h2(t);
    while (Q-- && cin >> l >> r)
        puts(h1.hash(l - 1, r - 1) == h2.hash(n - r, n - l) ? "Yes" : "No");
    return 0;
}

T4 [ABC271C] Manga

直接模拟。若有书本 i，那么消耗为 1，否则为 2，啥时候大于 n 了，就记录答案，跳出循环即可。

#include <bits/stdc++.h>

using namespace std;

const int N = 3e5 + 10;

int n, x, cost, ans;
set<int> s;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> x;
        s.insert(x);
    }
    for (int i = 1; ; i++) {
        if (s.count(i)) cost += 1;
        else cost += 2;
        if (cost > n) break;
        ans = i;
    }
    cout << ans;

    return 0;
}

T5 [tessoku_book_fo C17] Strange Data Structure?

把它剖成两个序列，前面一半，后面一半，插入中间就可以直接插到前面的末尾，然后维护一下即可。

#include <bits/stdc++.h>

using namespace std;

#define int long long

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int Q, n = 0;
    string x, op;
    list<string> q0, q1;
    for (cin >> Q; Q-- && cin >> op;) {
        if (op == "A" && cin >> x) n++, q1.push_back(x);
        else if (op == "B" && cin >> x) n++, q0.push_back(x);
        else if (op == "C") q0.pop_front(), n--;
        else cout << q0.front() << '\n';
        if (q1.size() > n / 2) q0.push_back(q1.front()), q1.pop_front();
        if (q0.size() > (n + 1) / 2) q1.push_front(q0.back()), q0.pop_back();
    }

    return 0;
}

T6 [USACO20FEB] Timeline G

直接跑拓扑排序再计算即可。

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define PII pair<int, int>
#define VI vector<int>
#define sz(a) a.size()
#define all(a) a.begin(), a.end()
#define up(i, s, t) for (int i = s; i <= t; i++)
#define dw(i, s, t) for (int i = s; i >= t; i--)

const int N = 1e5 + 2;

int n, m, c, s[N], in[N];
vector<PII> g[N];

void topsort() {
    queue<int> q;
    up(i, 1, n) if (!in[i]) q.push(i);
    while (q.size()) {
        int u = q.front(); q.pop();
        for (auto [v, w] : g[u]) {
            in[v]--;
            s[v] = max(s[v], s[u] + w); // 取最值
            if (!in[v]) q.push(v);
        }
    }
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin >> n >> m >> c;
    up(i, 1, n) cin >> s[i];
    up(i, 1, c) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({v, w});
        in[v]++;
    }
    topsort();
    up(i, 1, n) cout << s[i] << '\n';

    return 0;
}