首页 › 题库 › 信息学奥赛 › 综合练习

信息学奥赛-提高级 题库

共 511 道题 ,第 21 / 26 页 · 按题型筛选,点「查看答案」核对解析
401 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习
include <algorithm>
include <cstdio>
include <cstring>
bool flag[27];
int n;
int p[27];
int ans = 0;
void dfs(int k) {
    if (k == n + 1) {
        ++ans;
        return;
    }
    for (int i = 1; i <= n; ++i) {
        if (flag[i]) continue;
        if (k > 1 && i == p[k 1] + 1) continue;
        p[k] = i;
        flag[i] = true;
        dfs(k + 1);
        flag[i] = false;
    }
    return;
}
int main() {
    scanf("%d", &n);
    dfs(1);
    printf("%d\n", ans);
    return 0;
}
答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
402 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习
include <algorithm>
include <cstdio>
include <cstring>
define ll long long
int cnt_broken = 0;
int cnt_check = 0;
int n, k;
inline bool check(int h) {
    printf("now check:%d\n", h);
    ++cnt_check;
    if (cnt_broken == 2) {
        printf("You have no egg!\n");
        return false;
    }
    if (h >= k) {
        ++cnt_broken;
        return true;
    } else {
        return false;
    }
}
inline bool assert_ans(int h) {
    if (h == k) {
        printf("You are Right using %d checks\n", cnt_check);
        return true;
    } else {
        printf("Wrong answer!\n");
        return false;
    }
}
inline void guess1(int n) {
    for (int i = 1; i <= n; ++i) {
        if (check(i)) {
            assert_ans(i);
            return;
        }
    }
}
inline void guess2(int n) {
    int w = 1;
    while (w * (w + 1) / 2 < n) {
        ++w;
    }
    int ti = w;
    int nh = 0;
    while (true) {
        nh += ti;
        if (nh > n) {
            nh = n;
        }
        if (check(nh)) {
            for (int j = nh ti + 1; j < nh; ++j) {
                if (check(j)) {
                    assert_ans(j);
                    return;
                }
            }
            assert_ans(nh);
            return;
        }
        --ti;
        if (ti == 0) {
            assert_ans(n);
            return;
        }
    }
}
int main() {
    scanf("%d%d", &n, &k);
    int t;
    scanf("%d", &t);
    if (t == 1) {
        guess1(n);
    } else {
        guess2(n);
    }
    return 0;
}
答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
403 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习
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;
}
答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情
404 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

假期计划(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;
}


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

策略游戏(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;
}


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

星战(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;
}


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

数据传输(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;
}


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

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 的情况。

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

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 路径查找,确保每次将数字移动到最小可能的节点,从而得到字典序最小的结果。

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

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、结果计算:总合法方案数为总方案数减去所有非法方案数的和,确保结果为非负数后输出。

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

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

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,计算当前段和并检查非递减条件,更新最小平方和及最后一段的和。

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

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;
}


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

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;
}

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

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;
}


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

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;
}


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

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;
}
题目详情
417 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

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;
}
题目详情
418 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

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;
}
题目详情
419 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

T4、擂台游戏(arena)

答案与解析
参考答案
//参考代码1
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define RCL(a,b,c,d) memset(a,b,sizeof(c)*(d))
#define FOR(i,a,b) for(int i(a);i<=(int)(b);++i)
#define DOR(i,a,b) for(int i(a);i>=(int)(b);--i)
using namespace std;
constexpr int N((1<<17)+10);
namespace IOstream {
#define getc() getchar()
#define putc(ch) putchar(ch)
#define isdigit(ch) ('0'<=(ch)&&(ch)<='9')
	template<class T>void rd(T &x) {
		static char ch(0);
		for(x=0,ch=getc(); !isdigit(ch); ch=getc());
		for(; isdigit(ch); x=(x<<1)+(x<<3)+(ch^'0'),ch=getc());
	}
	template<class T>void wr(T x,const char End='\n') {
		static int top(0);
		static int st[50];
		do st[++top]=x%10,x/=10;
		while(x);
		while(top)putc(st[top]^'0'),--top;
		putc(End);
	}
} using namespace IOstream;
bool d[N];
char s[N];
int n,m,k,Q;
int a_[N],a[N],c[N],wt[N<<1],wn[N<<1];
ll sum[N];
#define v (u<<1)
void dfs0(int u,int h) {
	if(!h)return wn[u]=a[wt[u]=u-(1<<k)+1],void();
	dfs0(v,h-1),dfs0(v|1,h-1),wt[u]=wt[v|d[u]|(wn[v]<h)],wn[u]=wn[v|(d[u]^(wn[v|d[u]]<h))];
}
void dfs1(int u,int hmx,int h,int L,int R) {
	if(L>R)return;
	if(!h) {
		int x(u-(1<<k)+1);
		if(L<min(R,x))sum[L]+=x,sum[min(R,x)]-=x;
		if(a[x]>=hmx&&max(L,x)<R)sum[max(L,x)]+=x,sum[R]-=x;
		return;
	}
	dfs1(v|d[u],hmx?hmx:h,h-1,L,R),dfs1(v|!d[u],hmx,h-1,L,wn[v|d[u]]>=h?min(wt[v|d[u]],R):R);
}
#undef v
signed main() {
	rd(n),rd(m);
	while((1<<k)<n)++k;
	FOR(i,1,n)rd(a_[i]);
	FOR(i,1,m)rd(c[i]);
	DOR(i,k-1,0) {
		scanf("%s",s);
		DOR(j,(1<<i)-1,0)d[j|1<<i]=s[j]^48;
	}
	rd(Q);
	while(Q--) {
		static int X[4];
		rd(X[0]),rd(X[1]),rd(X[2]),rd(X[3]);
		FOR(i,1,n)a[i]=a_[i]^X[i&3];
		dfs0(1,k),RCL(sum+1,0,ll,n);
		FOR(i,0,k)dfs1(1<<(k-i),0,i,!i?1:(1<<(i-1))+1,(1<<i)+1);
		FOR(i,1,n)sum[i]+=sum[i-1];
		ll ans(0);
		FOR(i,1,m)ans^=i*sum[c[i]];
		wr(ans);
	}
	return 0;
}
//参考代码2
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define ll long long
#define RCL(a,b,c,d) memset(a,b,sizeof(c)*(d))
#define FOR(i,a,b) for(int i(a);i<=(int)(b);++i)
#define DOR(i,a,b) for(int i(a);i>=(int)(b);--i)
using namespace std;
constexpr int N((1<<17)+10);
namespace IOstream {
#define getc() getchar()
#define putc(ch) putchar(ch)
#define isdigit(ch) ('0'<=(ch)&&(ch)<='9')
	template<class T>void rd(T &x) {
		static char ch(0);
		for(x=0,ch=getc(); !isdigit(ch); ch=getc());
		for(; isdigit(ch); x=(x<<1)+(x<<3)+(ch^'0'),ch=getc());
	}
	template<class T>void wr(T x,const char End='\n') {
		static int top(0);
		static int st[50];
		do st[++top]=x%10,x/=10;
		while(x);
		while(top)putc(st[top]^'0'),--top;
		putc(End);
	}
} using namespace IOstream;
bool d[N];
char s[N];
int n,m,k,Q;
int a_[N],a[N],c[N],wt[N<<1],wn[N<<1];
ll sum[N];
#define v (u<<1)
void dfs0(int u,int h) {
	if(!h)return wn[u]=a[wt[u]=u-(1<<k)+1],void();
	dfs0(v,h-1),dfs0(v|1,h-1),wt[u]=wt[v|d[u]|(wn[v]<h)],wn[u]=wn[v|(d[u]^(wn[v|d[u]]<h))];
}
void dfs1(int u,int hmx,int h,int L,int R) {
	if(L>R)return;
	if(!h) {
		int x(u-(1<<k)+1);
		if(L<min(R,x))sum[L]+=x,sum[min(R,x)]-=x;
		if(a[x]>=hmx&&max(L,x)<R)sum[max(L,x)]+=x,sum[R]-=x;
		return;
	}
	dfs1(v|d[u],hmx?hmx:h,h-1,L,R),dfs1(v|!d[u],hmx,h-1,L,wn[v|d[u]]>=h?min(wt[v|d[u]],R):R);
}
#undef v
signed main() {
	rd(n),rd(m);
	while((1<<k)<n)++k;
	FOR(i,1,n)rd(a_[i]);
	FOR(i,1,m)rd(c[i]);
	DOR(i,k-1,0) {
		scanf("%s",s);
		DOR(j,(1<<i)-1,0)d[j|1<<i]=s[j]^48;
	}
	rd(Q);
	while(Q--) {
		static int X[4];
		rd(X[0]),rd(X[1]),rd(X[2]),rd(X[3]);
		FOR(i,1,n)a[i]=a_[i]^X[i&3];
		dfs0(1,k),RCL(sum+1,0,ll,n);
		FOR(i,0,k)dfs1(1<<(k-i),0,i,!i?1:(1<<(i-1))+1,(1<<i)+1);
		FOR(i,1,n)sum[i]+=sum[i-1];
		ll ans(0);
		FOR(i,1,m)ans^=i*sum[c[i]];
		wr(ans);
	}
	return 0;
}
//参考代码3
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ls x<<1
#define rs x<<1|1
#define lson x<<1,l,mid
#define rson x<<1|1,mid+1,r
#define ll long long
using namespace std;
const int N = (1 << 17) + 5;
int mx[20][N << 2], lg[N], aa[N], ok[N], a[N], c[N], n, m, nn = 1;
bool vis[N];
ll ans[N], sum;
struct node {
	ll sum;
	int x;
	bool tp, d;
} t[N << 2];
inline void build(int x, int l, int r) {
	if (l == r) {
		t[x].x = l;
		return ;
	}
	int mid = l + r >> 1, k = lg[r - l + 1], d = t[x].d;
	build(lson);
	build(rson);
	int win = a[t[x << 1 | d].x] >= k;
	t[x].x = t[x << 1 | (d ^ !win)].x;
	if (!d && win)t[x].tp = 1, ok[r]++, ok[mid]--;
	else t[x].tp = 0;
}
inline void build2(int x, int l, int r, int *mx) {
	t[x].sum = (l + r) * (r - l + 1ll) / 2;
	if (l == r)return ;
	int mid = l + r >> 1, k = lg[r - l + 1], d = t[x].d;
	if (~mx[x])mx[ls] = mx[rs] = mx[x];
	else mx[x << 1 | d] = k;
	build2(lson, mx);
	build2(rson, mx);
}
inline void up(int x) {
	sum += !vis[x] * x;
	vis[x] = 1;
}
inline int rd() {
	char c;
	int f = 1;
	while (!isdigit(c = getchar()))if (c == '-')f = -1;
	int x = c - '0';
	while (isdigit(c = getchar()))x = x * 10 + (c ^ 48);
	return x * f;
}
inline char gc() {
	char c;
	while ((c = getchar()) <= ' ');
	return c;
}
int main() {
	// freopen("arena.in","r",stdin);
	// freopen("arena.out","w",stdout);
	n = rd();
	m = rd();
	for (int i = 1; i <= n; i++)aa[i] = rd();
	for (int i = 1; i <= m; i++)c[i] = rd();
	while (nn < n)nn <<= 1;
	for (int i = 2; i <= nn; i++)lg[i] = lg[i >> 1] + 1;
	for (int i = nn / 2; i; i >>= 1)
		for (int j = i; j < i * 2; j++)
			t[j].d = gc() - '0';
	memset(mx, -1, sizeof mx);
	for (int s = 0; (1 << s) <= nn; s++)
		build2(1 << s, 1, nn>>s, mx[s]);
	for (int T = rd(); T--;) {
		int yh[4] = {rd(), rd(), rd(), rd()};
		for (int i = 1; i <= n; i++)a[i] = aa[i] ^ yh[i & 3];
		memset(ok, 0, sizeof ok);
		build(1, 1, nn);
		for (int i = nn, rt = 1, s = 0; i; i--) {
			if ((1 << lg[i]) == i) {
				if (i != nn)rt <<= 1, s++;
				for (int j = 1; j <= i; j++)vis[j] = 0;
				sum = 0;
				up(t[rt].x);
			}
			ans[i] = sum;
			if (ok[i] += ok[i + 1])continue;
			up(i);
			int x = i + nn - 1;
			while (x != rt) {
				int d = x & 1;
				x >>= 1;
				if (!d)
					if (t[x].tp)sum += t[rs].sum;
					else break;
				else if (a[t[ls].x] >= mx[s][ls])up(t[ls].x);
			}
		}
		ll num = 0;
		for (int i = 1; i <= m; i++)num ^= i * ans[c[i]];
		printf("%lld\n", num);
	}
	return 0;
}
题目详情
420 简答题 偏难 信息学奥赛 ·信息学奥赛-提高级 · 综合练习

假设输入的x是不超过65535的自然数,完成下面的判断题和单选题:

答案与解析
正确答案:(缺答案,待补录)
这道题暂未补解析。
题目详情