首页 › 题库 › 信息学奥赛 › 信息学奥赛-提高级

信息学奥赛-提高级 题库

共 842 道题 ,第 29 / 43 页 · 按题型筛选,点「查看答案」核对解析
561 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习
include <algorithm>
include <cstdio>
include <cstring>
include <vector>
define ll long long
int n, m;
std::vector<int> k, p;
inline int mpow(int x, int k) {
    int ans = 1;
    for (; k; k = k >> 1, x = x * x) {
        if (k & 1) {
            ans = ans * x;
        }
    }
    return ans;
}
std::vector<int> ans1, ans2;
int cnt1, cnt2;
inline void dfs(std::vector<int> &ans, int &cnt, int l, int r, int v) {
    if (l > r) {
        ++cnt;
        ans.push_back(v);
        return;
    }
    for (int i = 1; i <= m; ++i) {
        dfs(ans, cnt, l + 1, r, v + k[l] * mpow(i, p[l]));
    }
    return;
}
std::vector<int> cntans1;
int main() {
    scanf("%d%d", &n, &m);
    k.resize(n + 1);
    p.resize(n + 1);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d", &k[i], &p[i]);
    }
    dfs(ans1, cnt1, 1, n >> 1, 0);
    dfs(ans2, cnt2, (n >> 1) + 1, n, 0);
    std::sort(ans1.begin(), ans1.end());
    int newcnt1 = 1;
    cntans1.push_back(1);
    for (int i = 1; i < cnt1; ++i) {
        if (ans1[i] == ans1[newcnt1 1]) {
            ++cntans1[newcnt1 1];
        } else {
            ans1[newcnt1++] = ans1[i];
            cntans1.push_back(1);
        }
    }
    cnt1 = newcnt1;
    std::sort(ans2.begin(), ans2.end());
    int las = 0;
    ll ans = 0;
    for (int i = cnt2 1; i >= 0; --i) {
        while (las < cnt1 && ans1[las] + ans2[i] < 0) {
            ++las;
        }
        if (las < cnt1 && ans1[las] + ans2[i] == 0) {
            ans += cntans1[las];
        }
    }
    printf("%lld\n", ans);
    return 0;
}
答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
562 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 4.2 最短路径

特殊最短路

题目背景

给定一个含N个点、M条边的带权无向图,边权非负。起点为S,终点为T。对于一条S到T的路径,可以在整条路径中,至多选择一条边作为“免费边”:当第一次经过这条被选中的边时,费用视为0;如果之后再次经过该边,则仍按其原始权重视计费。点和边均允许重复经过。求从S到T的最小总费用。

以下代码求解了上述问题。试补全程序。

include <algorithm>
include <iostream>
include <queue>
include <vector>
using namespace std;
const long long INF = 1e18;
struct Edge {
    int to;
    int weight;
};
struct State {
    long long dist;
    int u;
    int used_freebie; // 0 for not used, 1 for used
    bool operator>(const State &other) const {
        return dist > other.dist;
    }
};
int main() {
    int n, m, s, t;
    cin >> n >> m >> s >> t;
    vector<vector<Edge>> adj(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    vector<vector<long long>> d(n + 1, vector<long long>(2, INF));
    priority_queue<State, vector<State>, greater<State>> pq;
    d[s][0] = 0;
    pq.push(    ①   ); // ①处待完善(注:原文①处对应初始化相关)
    while (!pq.empty()) {
        State current = pq.top();
        pq.pop();
        long long dist = current.dist;
        int u = current.u;
        int used = current.used_freebie;
        if (dist >    ②     ) { // ②处待完善
            continue;
        }
        for (const auto &edge : adj[u]) {
            int v = edge.to;
            int w = edge.weight;
            // 情况1:不使用免费边
            if (d[v][used] >    ③    + w) { // ③处待完善
                d[v][used] = d[u][used] + w;
                pq.push({d[v][used], v, used});
            }
            // 情况2:使用免费边(仅当未使用过)
            if (used == 0 && d[v][1] >    ④     + 0) { // ④处待完善
                d[v][1] = d[u][0] + 0;
                pq.push({d[v][1], v, 1});
            }
        }
    }
    cout <<     ⑤    << endl; // ⑤处待完善
    return 0;
}
答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
563 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.2 图

生产线测试

题目背景

工厂打算通过客户反馈来间接测试生产线,从而找到存在缺陷的生产线。工厂有n条生产线(编号0~n-1),已知其中恰有一条生产线存在缺陷。每一轮测试为,从若干生产线的产品取样混合成一个批次发给客户。若该批次中包含缺陷生产线的产品,客户将要求退货(结果记为1),否则正常收货(记为0)。受售后压力限制,在所有发货批次中,最多只能有k次退货(即结果为1的次数≤k)。工厂的目标是,设计最少的间接测试轮数w(发货总批次),保证根据客户收货或退货的反馈结果,唯一确定存在缺陷的生产线。

以下程序实现了工厂的目标,包含两部分:

i) 确定w的最小值,并设计最优测试方案;

ii) 根据测试结果推断存在缺陷的生产线。

该程序确定w最小值的方法为:由于不同的生产线故障时,测试应当返回不同的结果,因此w轮测试的可能结果数不应少于生产线数量。

`test_subset()` 函数为抽象测试接口,输入所有批次的方案并返回一个二进制编码;该编码表示为每批次的检测结果(即最低位是第1批次、最高位是第w批次);其实现在此处未给出。

`test_subset()` 函数为抽象测试接口,输入所有批次的方案并返回一个二进制编码;该编码表示为每批次的检测结果(即最低位是第1批次、最高位是第w批次);其实现在此处未给出。

试补全程序。

include <algorithm>
include <cstddef>
include <iostream>
include <vector>
using namespace std;
long long comb(int w, int i) { // 计算组合数C(w,i)
    if (i < 0 || i > w) {
        return 0;
    }
    long long res = 1;
    for (int t = 1; t <= i; ++t) {
        res = res * (w t + 1) / t;
    }
    return res;
}
long long count_patterns(int w, int k) { // 计算长度为w、1的个数≤k的码字总数
    long long total = 0;
    for (int t = 0; t <= min(w, k); ++t) {
        total += comb(w, t);
    }
    return total;
}
int test_subset(const vector<vector<int>> &plan); // 抽象测试接口
int solve(int n, int k) {
    // 第1步:求最小w
    int w = 1;
    while (      ①      ) { // ①处待完善
        ++w;
    }
    cout << w << endl;
    // 第2步:生成n个长度为w、含1的数量不超过k的二进制串,保存在code里面
    vector<vector<int>> code(n, vector<int>(w, 0));
    int idx = 0;
    for (int ones = 0; ones <= k && idx < n; ++ones) {
        vector<int> bits(w, 0);
        fill(bits.begin(), bits.begin() + ones, 1);
        do {
            for (int b = 0; b < w; ++b) {
                code[idx][b] = bits[b];
            }
            ++idx;
            if (idx >= n) {
                break;
            }
        } while (    ②      ); // ②处待完善
    }
    // 第3步:生成测试方案plan
    vector<vector<int>> plan(w);
    for (int i = 0; i < w; ++i) {
        for (int j = 0; j < n; ++j) {
            if (         ③       ) { // ③处待完善
                plan[i].push_back(j); // 将第j条生产线产品混合到第i轮测试
            }
        }
    }
    // 第4步:调用测试接口
    int signature = test_subset(plan);
    // 第5步:结果解码,将signature转为二进制串sig_bits
    vector<int> sig_bits(w, 0);
    for (int i = 0; i < w; ++i) {
        if (       ④       ) { // ④处待完善
            sig_bits[i] = 1;
        }
    }
    // 第6步:匹配sig_bits与code,找到缺陷生产线
    for (int j = 0; j < n; ++j) {
        if (        ⑤        ) { // ⑤处待完善
            return j;
        }
    }
    return -1;
}
int main() {
    int n, k;
    cin >> n >> k;
    int ans = solve(n, k);
    cout << ans << endl;
    return 0;
}
答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
564 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

假期计划(holiday)


答案与解析
参考答案
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <cctype>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int INF = 0x3f3f3f3f;

inline int read() {
    char ch = getchar();
    int x = 0, f = 1;
    while (!isdigit(ch)) {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }
    return x * f;
}

inline void write(int x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) {
        write(x / 10);
    }
    putchar(x % 10 + '0');
}

const int cp = 998244353;

inline int ksm(int a, int b) {
    int ret = 1;
    for (; b; b >>= 1, a = 1ll * a * a % cp) {
        if (b & 1) {
            ret = 1ll * ret * a % cp;
        }
    }
    return ret;
}

inline int inv(int x) {
    return ksm(x, cp - 2);
}

inline int rev(int p, int q) {
    return 1LL * p * inv(q) % cp;
}

const int N = 2505;
int n, m, K, pos[N][3], f[N][N];
ull a[N], ans;
vector<int> G[N];
queue<int> Q;

void bfs(int S) {
    f[S][S] = 1;
    Q.push(S);
    while (!Q.empty()) {
        int x = Q.front();
        Q.pop();
        for (auto v : G[x]) {
            if (f[S][v] < 0) {
                f[S][v] = f[S][x] + 1;
                Q.push(v);
            }
        }
    }
}

void check(int A, int B, int C, int D) {
    if (!A || !B || !C || !D) return;
    if (A == B || A == C || A == D || B == C || B == D || C == D) return;
    if (f[1][A] > K || f[A][B] > K || f[B][C] > K || f[C][D] > K || f[D][1] > K) return;
    ans = max(ans, a[A] + a[B] + a[C] + a[D]);
}

signed main() {
    memset(f, -1, sizeof(f));
    n = read(), m = read(), K = read() + 2;
    for (int i = 2; i <= n; ++i) {
        cin >> a[i];
    }
    for (int i = 1, x, y; i <= m; ++i) {
        x = read(), y = read();
        G[x].push_back(y);
        G[y].push_back(x);
    }
    bfs(1);
    for (int i = 2; i <= n; ++i) {
        bfs(i);
        for (int j = 2; j <= n; ++j) {
            if (f[i][j] != -1 && f[1][j] != -1 && f[i][j] <= K && f[1][j] <= K && i != j) {
                int x = j;
                if (a[x] > a[pos[i][0]]) swap(x, pos[i][0]);
                if (a[x] > a[pos[i][1]]) swap(x, pos[i][1]);
                if (a[x] > a[pos[i][2]]) swap(x, pos[i][2]);
            }
        }
    }
    for (int B = 2; B <= n; ++B) {
        for (int C = 2; C <= n; ++C) {
            if (B != C && f[B][C] <= K && f[B][C] != -1) {
                for (int i = 0; i < 3; ++i) {
                    for (int j = 0; j < 3; ++j) {
                        check(pos[B][i], B, C, pos[C][j]);
                    }
                }
            }
        }
    }
    cout << ans;
    return 0;
}


题目详情
565 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

策略游戏(game )


答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;

#define MAXN 100001
#define int long long

int n, m, q, l_1, r_1, l_2, r_2;
int ans, ans1, ans2, ans3, ans4, ans5, ans6;

struct Block {
    #define MAXM 331  // 块的个数
    int n, len, tot;
    int a[MAXN], bl[MAXN];
    int L[MAXM], R[MAXM];  // 每个块的左端点和右端点
    int maxn[MAXM], minn[MAXM];  // 每个块的最大值和最小值

    Block(int x) {  // 构造函数
        n = x;
    }

    void init() {  // 初始化
        len = sqrt(n);  // 块长
        tot = (n - 1) / len + 1;  // 块的数量
        R[0] = 0;
        for (int i(1); i <= tot; ++i) {  // 求 L,R
            L[i] = R[i - 1] + 1;
            R[i] = i * len;
        }
        R[tot] = n;  // 注意最后一个块的右端点

        for (int i(1); i <= tot; ++i) {
            maxn[i] = LLONG_MIN;
            minn[i] = LLONG_MAX;
            for (int j(L[i]); j <= R[i]; ++j) {
                bl[j] = i;  // j 在第 i 个块
                maxn[i] = max(maxn[i], a[j]);
                minn[i] = min(minn[i], a[j]);
            }
        }
    }

    int gmin(int l, int r) {
        int p(bl[l]), q(bl[r]), res(LLONG_MAX);
        if (p == q) {  // 当 l,r 处于同一个块时,暴力枚举
            for (int i(l); i <= r; ++i) {
                res = min(res, a[i]);
            }
            return res;
        }

        for (int i(l); i <= R[p]; ++i) {
            res = min(res, a[i]);  // 枚举第一个块
        }
        for (int i(p + 1); i < q; ++i) {
            res = min(res, minn[i]);  // 枚举中间的块
        }
        for (int i(L[q]); i <= r; ++i) {
            res = min(res, a[i]);  // 枚举最后一个块
        }
        return res;
    }

    int gmax(int l, int r) {  // 同gmin,求最大值
        int p(bl[l]), q(bl[r]), res(LLONG_MIN);
        if (p == q) {
            for (int i(l); i <= r; ++i) {
                res = max(res, a[i]);
            }
            return res;
        }

        for (int i(l); i <= R[p]; ++i) {
            res = max(res, a[i]);
        }
        for (int i(p + 1); i < q; ++i) {
            res = max(res, maxn[i]);
        }
        for (int i(L[q]); i <= r; ++i) {
            res = max(res, a[i]);
        }
        return res;
    }
};

int f(int x) {  // 模拟 B 的决策
    if (x >= 0) {
        return ans6;
    }
    return ans5;
}

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

    cin >> n >> m >> q;
    Block a(n), b(m), a2(n), a3(n);  // a2 为负数处理、a3 为非负数处理

    for (int i(1); i <= n; ++i) {
        cin >> a.a[i];
        a2.a[i] = a3.a[i] = a.a[i];
        if (a.a[i] < 0) {
            a3.a[i] = LLONG_MAX;  // 非负数集合中排除负数
        } else {
            a2.a[i] = LLONG_MIN;  // 负数集合中排除非负数
        }
    }

    for (int i(1); i <= m; ++i) {
        cin >> b.a[i];
    }

    a.init();    // 初始化块结构(不能在构造函数中初始化)
    b.init();
    a2.init();
    a3.init();

    while (q--) {
        cin >> l_1 >> r_1 >> l_2 >> r_2;

        // 获取区间最值
        ans1 = a.gmax(l_1, r_1);
        ans2 = a.gmin(l_1, r_1);
        ans3 = a2.gmax(l_1, r_1);
        ans4 = a3.gmin(l_1, r_1);
        ans5 = b.gmax(l_2, r_2);
        ans6 = b.gmin(l_2, r_2);

        // 计算可能的最大值
        ans = max(ans1 * f(ans1), ans2 * f(ans2));  // A取最大值和最小值的情况
        if (ans3 != LLONG_MIN) {
            ans = max(ans, ans3 * f(ans3));  // A取负数最大值
        }
        if (ans4 != LLONG_MAX) {
            ans = max(ans, ans4 * f(ans4));  // A取非负数最小值
        }

        cout << ans << '\n';
    }

    return 0;
}


题目详情
566 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

星战(galaxy)


答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;

const int N = 5e5 + 5;
int n, m, q, a[N];
long long to[N], sum[N], tot, ans;

int main() {
    mt19937 rnd(time(0));
    scanf("%d%d", &n, &m);
    
    for (int i = 1; i <= n; ++i) {
        ans += (a[i] = rnd());
    }
    
    for (int i = 1, u, v; i <= m; ++i) {
        scanf("%d%d", &u, &v);
        to[v] += a[u];
        sum[v] = to[v];
        tot += a[u];
    }
    
    scanf("%d", &q);
    for (int i = 1, t, u, v; i <= q; ++i) {
        scanf("%d%d", &t, &u);
        
        if (t == 1) {
            scanf("%d", &v);
            to[v] -= a[u];
            tot -= a[u];
        }
        if (t == 2) {
            tot -= to[u];
            to[u] = 0;
        }
        if (t == 3) {
            scanf("%d", &v);
            to[v] += a[u];
            tot += a[u];
        }
        if (t == 4) {
            tot += sum[u] - to[u];
            to[u] = sum[u];
        }
        
        puts(tot == ans ? "YES" : "NO");
    }
    
    return 0;
}


题目详情
567 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

数据传输(transmit)


答案与解析
参考答案
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const ll N = 200500, B = 20, K = 3;
ll n, q, T;
ll v[N], mn[N];
vector<ll> e[N];
ll f[B][N], dep[N];
ll dis[B][N][K][K];

void gi(ll &x, ll y) {
    x = min(x, y);
}

void dfs(ll k, ll fa) {
    dep[k] = dep[fa] + 1;
    f[0][k] = fa;
    
    for (ll i = 1; i < B; i++) {
        f[i][k] = f[i - 1][f[i - 1][k]];
    }
    
    auto D = dis[0][k];
    if (T == 1) {
        D[0][0] = v[fa];
    }
    if (T == 2) {
        D[0][0] = D[1][0] = v[fa];
        D[0][1] = 0;
    }
    if (T == 3) {
        D[0][0] = D[1][0] = D[2][0] = v[fa];
        D[0][1] = D[1][2] = 0;
        D[2][2] = mn[k];
    }
    
    for (ll i = 1; i < B; i++) {
        for (ll x = 0; x < 3; x++) {
            for (ll y = 0; y < 3; y++) {
                for (ll z = 0; z < 3; z++) {
                    gi(dis[i][k][x][z], dis[i - 1][k][x][y] + dis[i - 1][f[i - 1][k]][y][z]);
                }
            }
        }
    }
    
    for (auto to : e[k]) {
        if (to != fa) {
            dfs(to, k);
        }
    }
}

ll lca(ll x, ll y) {
    if (dep[x] < dep[y]) {
        swap(x, y);
    }
    
    for (ll i = B - 1; i >= 0; i--) {
        if (dep[f[i][x]] >= dep[y]) {
            x = f[i][x];
        }
    }
    
    if (x == y) {
        return x;
    }
    
    for (ll i = B - 1; i >= 0; i--) {
        if (f[i][x] != f[i][y]) {
            x = f[i][x];
            y = f[i][y];
        }
    }
    
    return f[0][x];
}

vector<ll> calc(ll k, ll l) {
    vector<ll> res(3, v[k]);
    
    for (ll i = B - 1; i >= 0; i--) {
        if (dep[f[i][k]] < dep[l]) {
            continue;
        }
        
        vector<ll> nw = res;
        fill(res.begin(), res.end(), 1e18);
        
        for (ll x = 0; x < 3; x++) {
            for (ll y = 0; y < 3; y++) {
                gi(res[y], nw[x] + dis[i][k][x][y]);
            }
        }
        
        k = f[i][k];
    }
    
    return res;
}

ll calcdis(ll x, ll y) {
    ll l = lca(x, y);
    auto F = calc(x, l), G = calc(y, l);
    ll res = 1e18;
    
    gi(res, F[0] + G[0] - v[l]);
    
    for (ll i = 0; i < T; i++) {
        for (ll j = 0; j < T; j++) {
            gi(res, F[i] + G[j] + (mn[l] * (i + j > T)));
        }
    }
    
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin >> n >> q >> T;
    
    for (ll i = 1; i <= n; i++) {
        cin >> v[i];
        mn[i] = v[i];
    }
    
    for (ll i = 1; i < n; i++) {
        ll x, y;
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
        mn[x] = min(mn[x], v[y]);
        mn[y] = min(mn[y], v[x]);
    }
    
    memset(dis, 1, sizeof(dis));
    dfs(1, 0);
    
    while (q--) {
        ll s, t;
        cin >> s >> t;
        cout << calcdis(s, t) << '\n';
    }
    
    return 0;
}


题目详情
568 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

day1-1 格雷码


答案与解析
参考答案
#include <iostream>
#include <string>
using namespace std;

int main() {
    int n;
    unsigned long long k;
    cin >> n >> k;
    
    unsigned long long gray = k ^ (k >> 1);
    string result(n, '0'); // 初始化为n个'0'的字符串
    
    for (int i = 0; i < n; ++i) {
        // 检查第(n-1 - i)位是否为1,若为1则将对应位置设为'1'
        if (gray & (1ULL << (n - 1 - i))) {
            result[i] = '1';
        }
    }
    
    cout << result << endl;
    return 0;
}


方法思路

1、格雷码性质:第 k 个格雷码的二进制值可以通过 k ^ (k >> 1) 计算得到,其中^表示异或运算,>>表示右移运算。

2、转换为二进制字符串:将计算得到的格雷码值转换为 n 位的二进制字符串,不足 n 位时在前面补零。

代码解释

1、输入处理:读取输入的 n(格雷码的位数)和 k(编号)。

2、计算格雷码值:利用性质 gray = k ^ (k >> 1) 计算第 k 个格雷码的数值。

3、生成二进制字符串:初始化一个长度为 n 的字符串,所有字符初始为 '0'。通过位运算逐位检查格雷码值的每一位,若某一位为 1,则将字符串对应位置的字符设为 '1'。

4、输出结果:输出生成的 n 位二进制字符串。

这种方法的时间复杂度为 O (n),空间复杂度为 O (n),能够高效处理 n 最大为 64 的情况。

题目详情
569 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

day1-2 括号树


答案与解析
参考答案
#include <iostream>
#include <vector>
#include <string>
using namespace std;

int n;
string brackets;
vector<vector<int>> children;
long long ans = 0;

void dfs(int u, vector<int>& stack, vector<int>& dp, long long& cnt) {
    char c = brackets[u - 1];
    int prev_stack_size = stack.size();
    int prev_dp_size = dp.size();
    long long prev_cnt = cnt;
    int prev_left = -1; // 记录弹出的左括号位置,用于回溯

    if (c == '(') {
        stack.push_back(u);
        dp.push_back(0);
    } else {
        if (!stack.empty()) {
            prev_left = stack.back();
            stack.pop_back();
            int current_dp = (prev_left > 1 ? dp[prev_left - 2] : 0) + 1;
            dp.push_back(current_dp);
            cnt += current_dp;
        } else {
            dp.push_back(0);
        }
    }

    ans ^= (long long)u * cnt;

    for (int v : children[u]) {
        dfs(v, stack, dp, cnt);
    }

    // 回溯操作,恢复进入当前节点前的状态
    dp.pop_back();
    if (c == '(') {
        stack.pop_back();
    } else {
        if (prev_left != -1) {
            stack.push_back(prev_left);
        }
    }
    cnt = prev_cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    cin >> brackets;
    children.resize(n + 1); // 节点编号从1到n
    for (int i = 2; i <= n; ++i) {
        int f;
        cin >> f;
        children[f].push_back(i);
    }

    vector<int> stack;
    vector<int> dp;
    long long cnt = 0;

    dfs(1, stack, dp, cnt);

    cout << ans << endl;

    return 0;
}


方法思路

1、合法括号子串判断:使用栈来匹配括号,维护一个动态规划数组dp,其中dp[i]表示以第i个字符结尾的合法括号子串数量。

2、树的遍历:通过 DFS 遍历树的每个节点,处理每个节点的括号时,维护栈和dp数组,并在回溯时恢复状态,以避免重复计算。

3、状态回溯:进入子节点前记录当前栈、dp数组和合法子串总数的状态,处理完子节点后恢复这些状态,确保每个节点的处理独立。

代码解释

1、输入处理:读取节点数n、括号字符串和父节点信息,构建子节点列表。

2、DFS 遍历:从根节点(节点 1)开始遍历,处理每个节点的括号:

3、左括号:压入栈,dp数组添加 0(以左括号结尾无合法子串)。

4、右括号:若栈非空,弹出栈顶左括号,计算以当前右括号结尾的合法子串数,更新dp和合法子串总数cnt。

5、状态回溯:处理完子节点后,恢复栈、dp数组和cnt到进入当前节点前的状态,确保后续节点处理正确。

6、异或和计算:每个节点处理时,计算i * k_i并累加到异或和ans中。

这种方法确保了每个节点的处理时间为 O (1)(均摊),整体时间复杂度为 O (n),空间复杂度为 O (n),适用于大规模数据。

题目详情
570 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

day1-3 传统型


答案与解析
参考答案
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int MAXN = 2010;

vector<int> adj[MAXN];
int pos[MAXN];      // 数字i的初始节点
int ans[MAXN];      // 数字i的最终节点
int parent[MAXN];   // BFS中记录父节点

// 查找从u到v的路径(节点序列,不包含u,包含v)
vector<int> findPath(int u, int v, int n) {
    fill(parent, parent + n + 1, -1);
    queue<int> q;
    q.push(u);
    parent[u] = 0;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        if (cur == v) break;
        for (int neighbor : adj[cur]) {
            if (parent[neighbor] == -1) {
                parent[neighbor] = cur;
                q.push(neighbor);
            }
        }
    }
    vector<int> path;
    int cur = v;
    while (parent[cur] != 0) {
        path.push_back(cur);
        cur = parent[cur];
    }
    reverse(path.begin(), path.end());
    return path;
}

// 查找u所在连通块中的最小节点
int findMinNode(int u, int n) {
    vector<bool> visited(n + 1, false);
    queue<int> q;
    q.push(u);
    visited[u] = true;
    int minNode = u;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        if (cur < minNode) minNode = cur;
        for (int neighbor : adj[cur]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
    return minNode;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i) {
            cin >> pos[i];
            ans[i] = pos[i];
            adj[i].clear();
        }
        for (int i = 0; i < n - 1; ++i) {
            int x, y;
            cin >> x >> y;
            adj[x].push_back(y);
            adj[y].push_back(x);
        }
        for (int i = 1; i <= n; ++i) {
            int u = ans[i];
            int minNode = findMinNode(u, n);
            if (u == minNode) continue;
            vector<int> path = findPath(u, minNode, n);
            ans[i] = minNode;
            // 移除路径上的边(简化处理,实际需更精确标记)
            int prev = u;
            for (int v : path) {
                auto& vec = adj[prev];
                vec.erase(find(vec.begin(), vec.end(), v));
                auto& vec2 = adj[v];
                vec2.erase(find(vec2.begin(), vec2.end(), prev));
                prev = v;
            }
        }
        for (int i = 1; i <= n; ++i) {
            cout << ans[i] << (i == n ? "\n" : " ");
        }
    }
    return 0;
}


方法思路

1、树的表示:使用邻接表表示树的结构。

2、贪心策略:对于每个数字从 1 到 n,找到其当前所在节点所在连通块中编号最小的节点,然后通过路径查找将该数字移动到该最小节点。

3、路径查找:使用广度优先搜索(BFS)查找当前节点到最小节点的路径,并标记路径上的边为已处理,确保后续处理不重复使用这些边。

代码解释

1、输入处理:读取多组测试数据,构建树的邻接表,并记录每个数字的初始节点。

2、查找最小节点:对于每个数字,使用 BFS 查找其所在连通块中编号最小的节点。

3、路径查找:使用 BFS 查找当前节点到最小节点的路径。

4、更新节点与边:将数字移动到最小节点,并移除路径上的边,确保后续处理不重复使用这些边。

5、输出结果:输出每个数字最终所在的节点编号,形成字典序最小的排列。

该方法通过贪心策略和 BFS 路径查找,确保每次将数字移动到最小可能的节点,从而得到字典序最小的结果。

题目详情
571 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

day2-1 Emiya家今天的饭


答案与解析
参考答案
#include <iostream>
#include <vector>
using namespace std;

const int MOD = 998244353;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> a[i][j];
        }
    }

    // 计算总方案数:所有选至少一道且烹饪方法不同的方案数
    long long total = 1;
    for (int i = 0; i < n; ++i) {
        int sum = 0;
        for (int j = 0; j < m; ++j) {
            sum = (sum + a[i][j]) % MOD;
        }
        total = total * (sum + 1) % MOD; // 每道可选择任意食材或不选
    }
    total = (total - 1 + MOD) % MOD; // 减去都不选的情况

    long long invalid = 0;
    // 对每种食材j,计算非法方案数(该食材使用次数超过一半)
    for (int j = 0; j < m; ++j) {
        // dp[i][d + n]表示前i道烹饪方法,j的数量比其他食材多d的方案数
        vector<vector<int>> dp(n + 1, vector<int>(2 * n + 2, 0));
        dp[0][n] = 1; // 初始状态:0道,差值为0

        for (int i = 1; i <= n; ++i) {
            int sum_a = 0;
            for (int k = 0; k < m; ++k) {
                sum_a = (sum_a + a[i - 1][k]) % MOD;
            }
            int aj = a[i - 1][j];
            int others = (sum_a - aj + MOD) % MOD;

            // 遍历前i-1道的所有可能差值
            for (int d = -(i - 1); d <= i - 1; ++d) {
                int pos = d + n;
                if (dp[i - 1][pos] == 0) continue;

                // 不选当前烹饪方法
                dp[i][pos] = (dp[i][pos] + dp[i - 1][pos]) % MOD;
                // 选当前烹饪方法的j食材
                dp[i][pos + 1] = (dp[i][pos + 1] + (long long)dp[i - 1][pos] * aj) % MOD;
                // 选当前烹饪方法的非j食材
                dp[i][pos - 1] = (dp[i][pos - 1] + (long long)dp[i - 1][pos] * others) % MOD;
            }
        }

        // 统计差值大于0的情况(j的数量超过一半)
        for (int pos = n + 1; pos <= 2 * n; ++pos) {
            invalid = (invalid + dp[n][pos]) % MOD;
        }
    }

    long long ans = (total - invalid + MOD) % MOD;
    cout << ans << endl;

    return 0;
}


方法思路

1、总方案数计算:首先计算所有满足 “烹饪方法互不相同” 的方案数(至少选一道菜)。对于每道烹饪方法,可以选择其中一种食材或不选,因此总方案数为所有烹饪方法可选情况的乘积减 1(减去都不选的情况)。

2、非法方案数计算:对于每种食材,计算存在该食材使用次数超过一半的非法方案数。使用动态规划来跟踪每道烹饪方法选择后,该食材数量与其他食材数量的差值,从而判断是否超过一半。

3、结果计算:总合法方案数等于总方案数减去所有非法方案数的和,结果对 998244353 取模。

代码解释

1、输入处理:读取烹饪方法数n和食材数m,以及每道烹饪方法使用各食材的菜数。

2、总方案数计算:通过遍历每道烹饪方法,计算其可选情况的乘积,再减 1 得到至少选一道的总方案数。

3、非法方案数计算:对每种食材,使用动态规划跟踪其数量与其他食材数量的差值,统计差值大于 0 的情况(即该食材使用次数超过一半)。

4、结果计算:总合法方案数为总方案数减去所有非法方案数的和,确保结果为非负数后输出。

该方法通过动态规划高效处理了每种食材的非法情况,确保了时间复杂度和空间复杂度在合理范围内。

题目详情
572 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

day2-2 划分


答案与解析
参考答案
#include <cstdio>
#include <vector>
#include <climits>
using namespace std;

typedef long long ll;
const int MAXN = 1e5 + 10;  // 调整为更常见的测试规模,可根据需要扩大
const ll INF = LLONG_MAX / 2;

ll a[MAXN];
ll sum[MAXN];
ll dp[MAXN];  // dp[i]表示前i个元素的最小平方和
ll last[MAXN]; // last[i]表示前i个元素最后一段的和

int main() {
    int n, type;
    scanf("%d%d", &n, &type);

    // 读取或生成数组a
    if (type == 0) {
        for (int i = 0; i < n; ++i) {
            scanf("%lld", &a[i]);
        }
    } else {
        ll x, y, z, b1, b2;
        int m;
        scanf("%lld%lld%lld%lld%lld%d", &x, &y, &z, &b1, &b2, &m);
        vector<ll> b(n + 2);  // 1-based索引
        b[1] = b1;
        if (n >= 2) b[2] = b2;
        for (int i = 3; i <= n; ++i) {
            b[i] = (x * b[i - 1] + y * b[i - 2] + z) % (1LL << 30);
        }
        int prev_p = 0;
        for (int j = 0; j < m; ++j) {
            int p, l, r;
            scanf("%d%d%d", &p, &l, &r);
            ll len = r - l + 1;
            for (int i = prev_p + 1; i <= p && i <= n; ++i) {
                a[i - 1] = (b[i] % len) + l;
            }
            prev_p = p;
        }
    }

    // 计算前缀和
    sum[0] = 0;
    for (int i = 1; i <= n; ++i) {
        sum[i] = sum[i - 1] + a[i - 1];
    }

    // 初始化DP
    dp[0] = 0;
    last[0] = 0;  // 前0个元素没有段,用0作为初始值

    for (int i = 1; i <= n; ++i) {
        dp[i] = INF;
        // 寻找最佳的j,j < i
        for (int j = 0; j < i; ++j) {
            ll current_sum = sum[i] - sum[j];
            // 关键条件:当前段的和 >= 前一段的和
            if (current_sum >= last[j]) {
                ll candidate = dp[j] + current_sum * current_sum;
                if (candidate < dp[i]) {
                    dp[i] = candidate;
                    last[i] = current_sum;
                }
            }
        }
    }

    printf("%lld\n", dp[n]);
    return 0;
}


方法思路

1、动态规划状态定义:dp[i] 表示前 i 个元素的最小平方和,last[i] 表示前 i 个元素划分的最后一段的和。

2、状态转移:对于每个 i,寻找所有 j < i 使得 sum[i] - sum[j] >= last[j](保证当前段和 >= 前一段和),则 dp[i] = min(dp[j] + (sum[i]-sum[j])²),同时更新 last[i] = sum[i]-sum[j]。

3、优化策略:利用前缀和的单调性,维护有效候选 j 的集合,避免不必要的计算。

代码解释

1、明确判断条件 current_sum >= last[j],确保当前段的和大于等于前一段的和,严格满足非递减要求。

2、动态规划初始化:dp[0] = 0 表示空序列的平方和为 0,last[0] = 0 作为初始参考值。

3、状态转移:对每个位置 i,遍历所有可能的前一段结束位置 j,计算当前段和并检查非递减条件,更新最小平方和及最后一段的和。

题目详情
573 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 1.1 树与二叉树

day2-3 树的重心


答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 3e5 + 10;

vector<int> adj[MAXN];

// 计算以u为根,排除exclude节点的子树大小
int compute_size(int u, int parent, int exclude) {
    int s = 1;
    for (int v : adj[u]) {
        if (v != parent && v != exclude) {
            s += compute_size(v, u, exclude);
        }
    }
    return s;
}

// 查找以root为根,排除exclude节点的子树的所有重心
vector<int> find_centroids(int root, int exclude, int total_size) {
    vector<int> centroids;
    function<void(int, int, int&)> dfs = [&](int u, int p, int& current_size) {
        current_size = 1;
        int max_sub = 0;
        for (int v : adj[u]) {
            if (v != p && v != exclude) {
                int child_size = 0;
                dfs(v, u, child_size);
                current_size += child_size;
                max_sub = max(max_sub, child_size);
            }
        }
        max_sub = max(max_sub, total_size-current_size);
        if (max_sub <= total_size / 2) {
            centroids.push_back(u);
        }
    };
    int dummy = 0;
    dfs(root, exclude, dummy);
    return centroids;
}

ll solve() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) adj[i].clear();
    vector<pair<int, int>> edges;
    for (int i = 0; i < n-1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        edges.emplace_back(u, v);
    }
    ll ans = 0;
    for (auto& e : edges) {
        int u = e.first, v = e.second;
        // 计算分割后两个子树的大小
        int s = compute_size(u, -1, v);
        int t = n-s;
        // 查找两个子树的重心
        vector<int> c1 = find_centroids(u, v, s);
        vector<int> c2 = find_centroids(v, u, t);
        // 累加重心编号
        for (int x : c1) ans += x;
        for (int x : c2) ans += x;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        cout << solve() << '\n';
    }
    return 0;
}


方法思路

1、子树大小计算:对于每条边,删除后会得到两个子树,需要分别计算这两个子树的大小。

2、重心查找:对于每个子树,遍历其所有节点,判断每个节点是否为该子树的重心。判断条件是:删除该节点后,其所有子树的大小(包括父方向的子树)均不超过子树总大小的一半。

3、遍历所有边:对每条边,分别处理分割后的两个子树,找到各自的重心并求和,最终累加所有边的结果。

代码解释

1、compute_size函数:计算以u为根,排除exclude节点的子树大小。通过递归遍历子树,累加所有子节点的大小(排除父节点和exclude节点)。

2、find_centroids函数:查找以root为根,排除exclude节点的子树的所有重心。使用深度优先搜索(DFS)遍历子树,计算每个节点的最大子树大小(包括父方向的子树大小),判断是否为重心。

3、solve函数:处理每组测试用例,读取树的结构,遍历每条边,计算分割后两个子树的大小,查找各自的重心并累加结果。

该方法通过递归和深度优先搜索高效处理每个子树的重心查找,确保了时间复杂度在合理范围内,能够处理题目给定的数据规模。

题目详情
574 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

1、廊桥分配


答案与解析
参考答案
//参考代码1
#include <bits/stdc++.h>
using namespace std;

const int Maxn = 1e5 + 5;

struct e {
    int st, ed;
} a[Maxn];

bool cmp(e x, e y) {
    return x.st < y.st;
}

priority_queue<int> hp_id;
priority_queue<pair<int, int>> hp_ed;

int n, m1, m2, ca[Maxn], cb[Maxn];

int main() {
    scanf("%d%d%d", &n, &m1, &m2);
    
    for (int i = 1; i <= m1; ++i) {
        scanf("%d%d", &a[i].st, &a[i].ed);
    }
    
    sort(a + 1, a + m1 + 1, cmp);
    
    for (int i = 1; i <= n; ++i) {
        hp_id.push(-i);
    }
    
    for (int i = 1; i <= m1; ++i) {
        if (!hp_ed.empty()) {
            while (-hp_ed.top().first < a[i].st) {
                hp_id.push(-hp_ed.top().second);
                hp_ed.pop();
                if (hp_ed.empty()) {
                    break;
                }
            }
        }
        
        if (!hp_id.empty()) {
            int x = -hp_id.top();
            hp_id.pop();
            ca[x]++;
            hp_ed.push(make_pair(-a[i].ed, x));
        }
    }
    
    for (int i = 1; i <= n; ++i) {
        ca[i] += ca[i - 1];
    }
    
    while (!hp_ed.empty()) {
        hp_ed.pop();
    }
    while (!hp_id.empty()) {
        hp_id.pop();
    }
    
    for (int i = 1; i <= m2; ++i) {
        scanf("%d%d", &a[i].st, &a[i].ed);
    }
    
    sort(a + 1, a + m2 + 1, cmp);
    
    for (int i = 1; i <= n; ++i) {
        hp_id.push(-i);
    }
    
    for (int i = 1; i <= m2; ++i) {
        if (!hp_ed.empty()) {
            while (-hp_ed.top().first < a[i].st) {
                hp_id.push(-hp_ed.top().second);
                hp_ed.pop();
                if (hp_ed.empty()) {
                    break;
                }
            }
        }
        
        if (!hp_id.empty()) {
            int x = -hp_id.top();
            hp_id.pop();
            cb[x]++;
            hp_ed.push(make_pair(-a[i].ed, x));
        }
    }
    
    for (int i = 1; i <= n; ++i) {
        cb[i] += cb[i - 1];
    }
    
    int mx_ans = 0;
    for (int i = 0; i <= n; ++i) {
        mx_ans = max(mx_ans, ca[i] + cb[n - i]);
    }
    
    printf("%d", mx_ans);
    
    return 0;
}
//参考代码2
#include <bits/stdc++.h>
using namespace std;

// 计算某类航班(国内或国际)分配bridgeNum个廊桥时,能停靠的最大飞机数
int countPlanes(vector<pair<int, int>>& flights, int bridgeNum) {
    if (bridgeNum == 0) return 0;
    sort(flights.begin(), flights.end()); // 按到达时间升序排序

    // used: 存储(离开时间, 廊桥编号),小根堆(按离开时间排序,便于释放过期廊桥)
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> used;
    // idle: 存储空闲廊桥编号,小根堆(便于分配最小编号的空闲廊桥)
    priority_queue<int, vector<int>, greater<>> idle;
    for (int i = 1; i <= bridgeNum; ++i) {
        idle.push(i);
    }

    int res = 0;
    for (auto& flight : flights) {
        int arrTime = flight.first, depTime = flight.second;
        // 释放所有离开时间 <= 当前航班到达时间的廊桥(将这些廊桥加入空闲队列)
        while (!used.empty() && used.top().first <= arrTime) {
            idle.push(used.top().second);
            used.pop();
        }
        // 若有空闲廊桥,分配给当前航班
        if (!idle.empty()) {
            int bridgeId = idle.top();
            idle.pop();
            used.push({depTime, bridgeId});
            res++;
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m1, m2;
    cin >> n >> m1 >> m2;

    vector<pair<int, int>> domestic, international;
    // 读取国内航班信息
    for (int i = 0; i < m1; ++i) {
        int a, b;
        cin >> a >> b;
        domestic.emplace_back(a, b);
    }
    // 读取国际航班信息
    for (int i = 0; i < m2; ++i) {
        int a, b;
        cin >> a >> b;
        international.emplace_back(a, b);
    }

    // 计算国内分配0~n个廊桥时的最大停靠数
    vector<int> ca(n + 1);
    for (int i = 0; i <= n; ++i) {
        ca[i] = countPlanes(domestic, i);
    }
    // 计算国际分配0~n个廊桥时的最大停靠数
    vector<int> cb(n + 1);
    for (int i = 0; i <= n; ++i) {
        cb[i] = countPlanes(international, i);
    }

    // 枚举所有分配方案,找到最大值
    int maxAns = 0;
    for (int i = 0; i <= n; ++i) {
        maxAns = max(maxAns, ca[i] + cb[n - i]);
    }

    cout << maxAns << endl;
    return 0;
}


题目详情
575 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

2、括号序列


答案与解析
参考答案
//参考代码1
#include <bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 550, mo = 1e9 + 7;
LL dp[N][N][5];
int n, k;
char S[N];

signed main() {
    scanf("%d%d", &n, &k);
    scanf("%s", S + 1);
    
    // 初始化边界
    for (int i = 1; i <= n; ++i) {
        dp[i][i - 1][0] = 1;
    }
    
    // 枚举区间长度
    for (int len = 1; len <= n; ++len) {
        // 枚举左右端点
        for (int i = 1, j = i + len - 1; j <= n; ++i, ++j) {
            // 处理长度不超过k的*或?序列
            if (len <= k && dp[i][j - 1][0] && (S[j] == '*' || S[j] == '?')) {
                dp[i][j][0] = 1;
            }
            
            // 用子区间转移(长度至少为2才有意义)
            if (len >= 2) {
                // 判断左右端点是否为匹配的括号
                if ((S[i] == '(' || S[i] == '?') && (S[j] == ')' || S[j] == '?')) {
                    dp[i][j][1] = (dp[i + 1][j - 1][0] + dp[i + 1][j - 1][2] + 
                                   dp[i + 1][j - 1][3] + dp[i + 1][j - 1][4]) % mo;
                }
                
                // 枚举子区间的断点
                for (int t = i; t <= j - 1; ++t) {
                    dp[i][j][2] = (dp[i][j][2] + dp[i][t][3] * dp[t + 1][j][0]) % mo;
                    dp[i][j][3] = (dp[i][j][3] + (dp[i][t][2] + dp[i][t][3]) * dp[t + 1][j][1]) % mo;
                    dp[i][j][4] = (dp[i][j][4] + dp[i][t][0] * dp[t + 1][j][3]) % mo;
                }
            }
            
            // 合并状态
            dp[i][j][3] = (dp[i][j][3] + dp[i][j][1]) % mo;
        }
    }
    
    printf("%lld", dp[1][n][3]);
    return 0;
}
//参考代码2
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N = 550;
const int MOD = 1e9 + 7;

int n, k;
char s[N];
LL dp[N][N][5]; // dp[i][j][0~4] 分别对应不同状态

int main() {
    scanf("%d%d", &n, &k);
    scanf("%s", s + 1); // 字符串从下标1开始存储

    // 初始化:空区间是合法的*串(用于后续转移)
    for (int i = 1; i <= n; ++i) {
        dp[i][i - 1][0] = 1;
    }

    // 枚举区间长度
    for (int len = 1; len <= n; ++len) {
        // 枚举左端点i,右端点j = i + len - 1
        for (int i = 1, j = i + len - 1; j <= n; ++i, ++j) {
            // 状态0:*串,长度<=k,且j位置可填*或?,且[i,j-1]是*串
            if (len <= k && dp[i][j - 1][0] && (s[j] == '*' || s[j] == '?')) {
                dp[i][j][0] = 1;
            }

            // 长度至少为2时,处理其他状态
            if (len >= 2) {
                // 状态1:(A)形式,判断i和j是否可作为括号
                if ((s[i] == '(' || s[i] == '?') && (s[j] == ')' || s[j] == '?')) {
                    dp[i][j][1] = (dp[i + 1][j - 1][0] + dp[i + 1][j - 1][2] + 
                                   dp[i + 1][j - 1][3] + dp[i + 1][j - 1][4]) % MOD;
                }

                // 枚举断点t,拆分区间为[i,t]和[t+1,j]
                for (int t = i; t < j; ++t) {
                    // 状态2:A*B,A是状态3,B是状态0
                    dp[i][j][2] = (dp[i][j][2] + dp[i][t][3] * dp[t + 1][j][0]) % MOD;

                    // 状态3:A*B,A是状态2或3,B是状态1;或直接由状态1转移(后续会加)
                    dp[i][j][3] = (dp[i][j][3] + (dp[i][t][2] + dp[i][t][3]) * dp[t + 1][j][1]) % MOD;

                    // 状态4:A*B,A是状态0,B是状态3
                    dp[i][j][4] = (dp[i][j][4] + dp[i][t][0] * dp[t + 1][j][3]) % MOD;
                }

                // 状态3还可由自身的状态1转移而来(总合法状态包含(A)形式)
                dp[i][j][3] = (dp[i][j][3] + dp[i][j][1]) % MOD;
            }
        }
    }

    // 最终答案:整个区间[1,n]的合法超级括号序列数量(状态3)
    printf("%lld\n", dp[1][n][3]);
    return 0;
}

题目详情
576 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

3、回文


答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;

int t, n, l, r, l1, r1;
int a[1000010], ton1[1000010], ton[1000010], vis[1000010];
stack<int> q;
vector<int> q1;

int read() {
    int asd = 0, qwe = 1;
    char zxc;
    while (!isdigit(zxc = getchar())) {
        if (zxc == '-') {
            qwe = -1;
        }
    }
    while (isdigit(zxc)) {
        asd = asd * 10 + zxc - '0';
        zxc = getchar();
    }
    return asd * qwe;
}

int dfs(int k) {
    // cout << k << " " << l1 << " " << r1 << " " << l << " " << r << " " << q.size() << endl;
    if (k == n / 2) {
        for (int i = 0; i <= n / 2 - 1; i++) {
            if (q1[i] == 1) {
                cout << "L";
            } else {
                cout << "R";
            }
        }
        while (!q.empty()) {
            int x = q.top();
            q.pop();
            if (a[l] == x) {
                cout << "L";
                l++;
            } else {
                cout << "R";
                r--;
            }
        }
        cout << endl;
        return 1;
    } else {
        // cout << ton[l1 + 1] << l - 1 << ton[l1 + 1] << r + 1 << endl;
        if (vis[a[l1 + 1]] == 0 && (ton[l1 + 1] == l - 1 || ton[l1 + 1] == r + 1)) {
            l1++;
            if (ton[l1] == l - 1) {
                l--;
            } else {
                r++;
            }
            q1.push_back(1);
            q.push(a[l1]);
            vis[a[l1]] = 1;
            return dfs(k + 1);
        } else if (vis[a[r1 - 1]] == 0 && (ton[r1 - 1] == l - 1 || ton[r1 - 1] == r + 1)) {
            r1--;
            if (a[ton[r1]] == a[l - 1]) {
                l--;
            } else {
                r++;
            }
            q1.push_back(2);
            q.push(a[r1]);
            vis[a[r1]] = 1;
            return dfs(k + 1);
        } else {
            return 0;
        }
    }
}

int main() {
    // freopen("palin.in" , "r" , stdin);
    // freopen("palin.out" , "w" , stdout);
    t = read();
    while (t--) {
        n = read() * 2;
        l1 = 0;
        r1 = n + 1;
        
        while (!q.empty()) {
            q.pop();
        }
        q1.clear();
        
        for (int i = 1; i <= n; i++) {
            vis[i] = ton1[i] = ton[i] = 0;
        }
        
        for (int i = 1; i <= n; i++) {
            a[i] = read();
            if (ton1[a[i]]) {
                ton[i] = ton1[a[i]];
                ton[ton1[a[i]]] = i;
            } else {
                ton1[a[i]] = i;
            }
        }
        
        // 第一种尝试:从左侧开始
        vis[a[++l1]] = 1;
        l = r = ton[l1];
        q1.push_back(1);
        q.push(a[l1]);
        
        if (dfs(1) == 0) {
            // 重置状态,尝试从右侧开始
            for (int i = 1; i <= n; i++) {
                vis[i] = 0;
            }
            q1.clear();
            l1 = 0;
            r1 = n + 1;
            
            while (!q.empty()) {
                q.pop();
            }
            
            vis[a[--r1]] = 1;
            l = r = ton[r1];
            q1.push_back(2);
            q.push(a[r1]);
            
            if (dfs(1) == 0) {
                cout << -1 << endl;
            }
        }
    }
    return 0;
}


题目详情
577 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

4、交通规划


答案与解析
参考答案
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;
const int MAXN = 360005;  // 增大数组容量适配题目规模
const ll INF = 1e18;

struct Edge {
    int to, rev;
    ll cap;
    Edge(int t, int r, ll c) : to(t), rev(r), cap(c) {}
};

vector<Edge> g[MAXN];
int level[MAXN], iter[MAXN];
int n, m, T;

// 添加双向边
void add_edge(int from, int to, ll cap) {
    g[from].emplace_back(to, (int)g[to].size(), cap);
    g[to].emplace_back(from, (int)g[from].size() - 1, 0);  // 反向边初始容量为0
}

// BFS构建层次图
void bfs(int s) {
    memset(level, -1, sizeof(level));
    queue<int> q;
    level[s] = 0;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (const Edge& e : g[u]) {
            if (e.cap > 0 && level[e.to] < 0) {
                level[e.to] = level[u] + 1;
                q.push(e.to);
            }
        }
    }
}

// DFS寻找增广路
ll dfs(int u, int t, ll f) {
    if (u == t) return f;
    for (int& i = iter[u]; i < g[u].size(); ++i) {
        Edge& e = g[u][i];
        if (e.cap > 0 && level[u] < level[e.to]) {
            ll d = dfs(e.to, t, min(f, e.cap));
            if (d > 0) {
                e.cap -= d;
                g[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

// 计算最大流(最小割)
ll max_flow(int s, int t) {
    ll flow = 0;
    while (true) {
        bfs(s);
        if (level[t] < 0) return flow;
        memset(iter, 0, sizeof(iter));
        ll f;
        while ((f = dfs(s, t, INF)) > 0) {
            flow += f;
        }
    }
}

// 射线编号转网格坐标(修正版)
pair<int, int> get_coord(int p) {
    p--;  // 转为0基索引
    if (p < m) {                // 上边界:(1, p+1)
        return {0, p};
    }
    p -= m;
    if (p < n-1) {              // 右边界:(p+2, m)
        return {p+1, m-1};
    }
    p -= n-1;
    if (p < m) {                // 下边界:(n, m-p)
        return {n-1, m-1 - p};
    }
    p -= m;                     // 左边界:(n-p, 1)
    return {n-1 - p, 0};
}

int main() {
    // 移除文件操作,适配标准输入输出
    scanf("%d%d%d", &n, &m, &T);
    
    // 存储水平和垂直边的权重
    vector<vector<ll>> horizontal(n-1, vector<ll>(m));
    vector<vector<ll>> vertical(n, vector<ll>(m-1));
    
    // 读取水平边(上下相邻格子)
    for (int i = 0; i < n-1; ++i) {
        for (int j = 0; j < m; ++j) {
            scanf("%lld", &horizontal[i][j]);
        }
    }
    
    // 读取垂直边(左右相邻格子)
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m-1; ++j) {
            scanf("%lld", &vertical[i][j]);
        }
    }
    
    while (T--) {
        int k;
        scanf("%d", &k);
        
        // 清空图结构
        for (int i = 0; i < MAXN; ++i) {
            g[i].clear();
        }
        
        int S = 0;                  // 源点(黑色)
        int T_node = n * m + 1;     // 汇点(白色)
        int node_cnt = n * m;       // 网格节点总数
        
        // 连接水平相邻格子(i,j)和(i+1,j)
        for (int i = 0; i < n-1; ++i) {
            for (int j = 0; j < m; ++j) {
                int u = i * m + j + 1;  // 网格节点编号从1开始
                int v = (i+1) * m + j + 1;
                ll cap = horizontal[i][j];
                add_edge(u, v, cap);
                add_edge(v, u, cap);  // 双向边
            }
        }
        
        // 连接垂直相邻格子(i,j)和(i,j+1)
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m-1; ++j) {
                int u = i * m + j + 1;
                int v = i * m + (j+1) + 1;
                ll cap = vertical[i][j];
                add_edge(u, v, cap);
                add_edge(v, u, cap);  // 双向边
            }
        }
        
        // 处理附加点约束
        for (int i = 0; i < k; ++i) {
            ll x3;
            int p, t;
            scanf("%lld%d%d", &x3, &p, &t);
            
            // 获取射线对应的网格坐标
            auto [r, c] = get_coord(p);
            if (r < 0 || r >= n || c < 0 || c >= m) {
                // 无效坐标处理
                continue;
            }
            
            int node = r * m + c + 1;  // 转换为节点编号
            
            if (t == 1) {  // 必须染黑色(连接到源点)
                add_edge(S, node, INF);    // 保证不会被割开
                add_edge(node, S, x3);     // 附加权重
            } else {        // 必须染白色(连接到汇点)
                add_edge(node, T_node, INF);  // 保证不会被割开
                add_edge(T_node, node, x3);   // 附加权重
            }
        }
        
        // 计算并输出最小割(最大流)
        printf("%lld\n", max_flow(S, T_node));
    }
    
    return 0;
}


题目详情
578 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

T1、决斗(duel)


答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int n, x;
struct bj {
	int num;
	bool flag, gjf;
};
vector<bj> v;
int bs(int k) {
	int r = n - 1, l = 0, res = -1;
	while (l <= r) {
		int mid = l + (r - l) / 2;
		if (v[mid].num > k && v[mid].flag == true && v[mid].gjf == true) {
			res = mid;
			r = mid - 1;
		} else l = mid + 1;
	}
	return res;
}
bool cmp(bj a, bj b) {
	return a.num < b.num;
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x;
		v.push_back({x, true, true});
	}
	sort(v.begin(), v.end(), cmp);
	
	for (int i = 0; i < n - 1; i++) {
		int re = bs(v[i].num);
		if (re == -1) continue;
		else {
			v[i].flag = false;
			v[re].gjf = false;
		}
	}
	int ans = 0;
	for (int i = 0; i < n; i++)
		if (v[i].flag == true) ans++;
	cout << ans;
	return 0;
}
题目详情
579 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

T2、超速检测(detect)


答案与解析
参考答案
#include<bits/stdc++.h>
using namespace std;
bool Mbegin;
void File_Work(){
	freopen("detect.in","r",stdin);
	freopen("detect.out","w",stdout);
}
const int N=1e5+8;
int n,m,L,V,p[N],d[N],v[N],a[N];
struct Interval{
	int l,r;
	void init(){
		l=r=0;
	}
	friend bool operator <(Interval a,Interval b){
		if(a.r!=b.r)
			return a.r<b.r;
		return a.l<b.l;
	}
}itv[N];
bool check(int pos,int i){
	int x=p[pos]-d[i];
	int v2=v[i]*v[i]+2*a[i]*x;
	if(V*V<v2)
		return 1;
	return 0;
}
void MAIN(){
	for(int i=1;i<=n;i++)
		p[i]=0,itv[i].init();
	cin>>n>>m>>L>>V;
	for(int i=1;i<=n;i++)
		cin>>d[i]>>v[i]>>a[i];
	for(int i=1;i<=m;i++)
		cin>>p[i];
	sort(p+1,p+m+1);
	int ans1=0;
	for(int i=1;i<=n;i++){
		if(p[m]<d[i])
			continue;
		int pos=lower_bound(p+1,p+m+1,d[i])-p;
		if(a[i]==0&&v[i]>V)
			itv[++ans1]={pos,m};
		else if(a[i]<0){
			int x=p[pos]-d[i];
			int v2=v[i]*v[i]+2*a[i]*x;
			if(V*V<v2){
				int l=pos,r=m,res=0;
				while(l<=r){
					int mid=(l+r)/2;
					if(check(mid,i)==1){
						res=mid;
						l=mid+1;
					}
					else
						r=mid-1;
				}
				itv[++ans1]={pos,res};
			}
		}
		else if(a[i]>0){
			int x=p[m]-d[i];
			int v2=v[i]*v[i]+2*a[i]*x;
			if(V*V<v2){
				int l=pos,r=m,res=0;
				while(l<=r){
					int mid=(l+r)/2;
					if(check(mid,i)==1){
						res=mid;
						r=mid-1;
					}
					else
						l=mid+1;
				}
				itv[++ans1]={res,m};
			}
		}
	}
	cout<<ans1<<' ';
	sort(itv+1,itv+ans1+1);
	int ans2=0,cur;
	for(int i=1;i<=ans1;i++){
		if(itv[i].l<=cur&&cur<=itv[i].r)
			continue;
		ans2++;
		cur=itv[i].r;
	}
	cout<<m-ans2<<'\n';
}
bool Mend;
int main(){
//	File_Work();
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cerr<<fixed<<setprecision(3)<<(&Mbegin-&Mend)/1048576.0<<" MB\n\n\n";
	int testid=0,testnum=1;
//	cin>>testid;
	cin>>testnum;
	while(testnum--)
		MAIN();
	cerr<<"\n\n\n"<<fixed<<setprecision(0)<<1e3*clock()/CLOCKS_PER_SEC<<" ms";
	return 0;
}
题目详情
580 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

T3、染色(color)


答案与解析
参考答案
//参考代码1
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
 
ll t,anstmp;
ll dp[2000005][2];
ll lst[2000005];
 
struct num{
    ll n,last;
}a[2000005];
 
int main(){
    ll t;
    scanf("%lld",&t);
    while (t--){
        ll n;
        scanf("%lld",&n);
        memset(dp,0,sizeof(dp));
        memset(lst,0,sizeof(lst));
        anstmp=0;
        for (ll i=1;i<=n;i++){
            scanf("%lld",&a[i].n);
            if (lst[a[i].n]) a[i].last=lst[a[i].n];
            else a[i].last=0;
            lst[a[i].n]=i;
            if (a[i-1].n==a[i].n) anstmp=anstmp+a[i].n;
        }
        for (ll i=1;i<=n;i++){
            if (a[i].n==a[i-1].n){
                dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
                dp[i][1]=dp[i-1][1];
                continue;
            }
            else dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
            if (a[i].last) dp[i][1]=max(max(dp[a[i].last][0],dp[a[i].last][1]),max(dp[a[i].last+1][0],dp[a[i].last+1][1]))+a[i].n;
        }
        printf("%lld\n",max(dp[n][0],dp[n][1])+anstmp);
    }
    return 0;
}
//参考代码2
#include<bits/stdc++.h>
using namespace std;
#define int long long
int rd() {
	int x = 0, w = 1;
	char ch = 0;
	while (ch < '0' || ch > '9') {
		if (ch == '-') w = -1;
		ch = getchar();
	}
	while (ch >= '0' && ch <= '9') {
		x = x * 10 + (ch - '0');
		ch = getchar();
	}
	return x * w;
}
void wt(int x) {
	static int sta[35];
	int f = 1;
	if(x < 0) f = -1,x *= f;
	int top = 0;
	do {
		sta[top++] = x % 10, x /= 10;
	} while (x);
	if(f == -1) putchar('-');
	while (top) putchar(sta[--top] + 48);
}

namespace work{
	const int N = 2e5+5,M = 1e6 + 5;
	int n,a[M],s[M],f[M],t[M];
	void solve() {
		memset(s,0,sizeof(s));
		memset(t,0,sizeof(t));
		memset(f,0,sizeof(f));
		n = rd();
		for(int i = 1;i<=n;i++) a[i] = rd();
		for(int i = 2;i<=n;i++) s[i] = s[i - 1] + (a[i] == a[i - 1]) * a[i];
		for(int i = 1;i<=n;i++) {
			f[i] = f[i - 1];
			if(t[a[i]]) f[i] = max(f[i],f[t[a[i]] + 1] + a[i] + s[i] - s[t[a[i]] + 1]);
			t[a[i]] = i;
		}
		wt(f[n]);putchar('\n');
	}
	
}


signed main() {
	int T = rd();
	while(T--) work::solve();
	return 0;
}
题目详情