难度和cspj相当 T4 数据已经加强

复制代码的,请自行滚蛋

T1

因为种子选手只能替换一场, 那么只需找到替换获得收益最大的那场比赛即可.

#include <bits/stdc++.h>
using namespace std;

const int N = 500050; // 最大数据量+50
int a[N], b[N]; // a[i]小胡得分, b[i]小X得分

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n; // 比赛场数
    cin >> n;
    long long totle = 0; // 小X参加所有比赛的总分
    int maxd = INT32_MIN; // 最大分差(a[i]-b[i])
    for (int i = 1; i <= n; ++i) {
        cin >> a[i] >> b[i];
        totle += b[i];
        maxd = max(maxd, a[i] - b[i]);
    }
    cout << totle + maxd << endl;
    return 0;
}

T2

对于每一个8位的字符串,我们依次去和文章的每一个连续的8位的字符串比较. 如何比较两个字符串呢?因为字符没有顺序,所以我们可以将两个字符串的字符进行排序,然后比较,只要相等即可. 这样我们就知道了复杂度是 O(n*m),m为文章长度.显然当n和m都很大时,会超时. 我们可以使用unordered_map来优化,将排序后的字符串存入unordered_map,统计数量. 然后遍历每一个8位的字符串,将其排序,然后在unordered_map查看他的个数,加入答案即可. 这样我们就将复杂度优化到了O(n+m),n为文章长度.

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 50;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string s;
    cin >> s;
    
    int n;
    cin >> n;
    
    unordered_map<string, int> cnt;

    for (int i = 0; i + 7 < s.size(); ++i) {
        string sub = s.substr(i, 8);
        sort(sub.begin(), sub.end());
        cnt[sub]++;
    }
    
    int total = 0;
    for (int i = 0; i < n; ++i) {
        string word;
        cin >> word;
        sort(word.begin(), word.end());
        total += cnt[word];
    }
    
    cout << total << endl;
    
    return 0;
}

T3

对于后面的人来说,前面的人越早结束越好,他们的开始时间对后面的人来说没有影响.所以我们只要对每一个会议按照结束时间进行排序, 然后从前往后遍历,我们先找上一个结束时间大的,看看能不能接上,能接上就直接接上,不能接上就看看那么结束时间早的看看能不能接上, 能接上接上,如果两个时间都不能接上,那么只能说这个会议没有缘分了.

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 50;

struct Node {
    int s, e;
    bool operator<(const Node& m) const {
        return e < m.e;
    }
} m[N];

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

    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> m[i].s >> m[i].e;
    }
    sort(m + 1, m + 1 + n);
    int cnt = 0;
    int last1 = 0, last2 = 0;
    for (int i = 1; i <= n; ++i) {
        if (m[i].s >= last1) {
            last1 = m[i].e;
            cnt++;
        }
        else if (m[i].s >= last2) {
            last2 = m[i].e;
            cnt++;
        }
        int a = max(last1, last2);
        int b = min(last1, last2);
        last1 = a;
        last2 = b;
    }

    cout << cnt << endl;

    return 0;
}

T4

显然是动态规划问题,根据题意很容易想到一种状态$dp[i][j]$,表示前i个字符,删除个字符的最多位置匹配. 显然状态方程为:

$$dp[i][j] = \max(dp[i-1][j] + (a[i] == i-j), dp[i-1][j-1]); $$

前i个字符删除j个字符时,$a[i]$ 正好落在了$i-j$这个位置,如果可以匹配,那么就加上$1$. 否则,就删除$a[i]$这个字符,那么就等于$dp[i-1][j-1]$.

#include <bits/stdc++.h>
using namespace std;
const int N = 1050; // 1000 + 50
int n;
int a[N]; // 输入数组
int dp[N][N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= i-1; ++j) {
            dp[i][j] = max(dp[i - 1][j]+(a[i] == i-j), dp[i - 1][j - 1]);
        }
    }

    int ans = 0;
    for (int j = 0; j <= n; ++j) {
        ans = max(ans, dp[n][j]);
    }

    cout << ans << endl;
    return 0;
}

T5

此题换一个说法就是存在多少对$a_i + a_j \leq M$的数对$(i,j)$. 我们可以先将数组进行排序,然后使用双指针,一个指向数组的开头,一个指向数组的结尾. 如果$a[l] + a[r] \leq M$,那么说明$a[l]$和$a[l+1],a[l+2],\dots,a[r]$都可以和$a[r]$组成数对, 那么答案就加上$r-l$,然后$l++$. 如果$a[l] + a[r] > M$,那么说明$a[r]$和$a[l+1],a[l+2],\dots,a[r-1]$都不能和$a[l]$组成数对, 那么答案就加上$0$,然后$r--$.

#include <bits/stdc++.h>
using namespace std;
const int N = 500050; // 最大数据量+50
int a[N]; // 输入数组
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n, m; // 数组长度和限制
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    sort(a + 1, a + 1 + n);
    int l = 1, r = n;
    long long ans = 0;
    while (l < r) {
        if (a[l] + a[r] <= m) {
            ans += r - l;
            l++;
        }
        else {
            r--;
        }
    }
    cout << ans << endl;
    return 0;
}

T6

直接看代码,贪心

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 50;

struct Node {
    long long x, t;

    bool operator<(const Node& other) const {
        return x < other.x;
    }
};

Node a[N];

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

    long long n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].x >> a[i].t;
    }

    sort(a + 1, a + 1 + n); // 按位置排序

    priority_queue<long long> pq;
    long long sum = 0, ans = 0;

    for (int i = 1; i <= n; i++) {
        if (sum + a[i].x + a[i].t <= m) {
            sum += a[i].t;
            pq.push(a[i].t);
            ans++;
        }
        else if (!pq.empty() && a[i].t < pq.top()) {
            sum = sum - pq.top() + a[i].t;
            pq.pop();
            pq.push(a[i].t);
        }
    }

    cout << ans << endl;
    return 0;
}

T7

bfs 秒解

#include<bits/stdc++.h>
using namespace std;

int n;

struct Node {
    int a, b;
};

Node a[10005];

unordered_map<int, int> stp;
unordered_map<int, vector<int>> mp;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].a >> a[i].b;
        mp[a[i].a].push_back(a[i].b);   // 拿到a就能看b
        // mp[a[i].b].push_back(a[i].a);
    }

    int m, x, y;
    cin >> m >> x >> y;

    queue<int> q;
    q.push(x);    // x拿到
    q.push(y);    // y拿到
    stp[x] = stp[y] = 0;  // x和y的步数都是0
    while (!q.empty()) {
        int t = q.front();
        q.pop();
        if (t == m) {
            cout << stp[t] << endl;
            return 0;
        }
        for (int i = 0; i < mp[t].size(); i++) {
            int v = mp[t][i];
            if (stp.count(v) == 0) {  // 没走过
                stp[v] = stp[t] + 1;
                q.push(v);
            }
        }
    }
    cout << "IMPOSSIBLE" << endl;

    return 0;
}

T8

题目分析

本题要求根据给定条件还原一个整数序列，使得每个位置的数值尽可能大。关键条件有两个：

1. 序列中第 $M$ 个位置的数必须是最大值 $X$。
2. 对于 $C$ 个区间 $[i, j]$，需要满足区间两端 $A_i \leq A_j$，且区间内其他位置的值严格小于 $A_i$。

方法思路

初始值设定：

• 由于每个位置的数最大可能是 $X$，因此先将所有位置的值初始化为 $X$。

约束处理：

• 对于每个区间 $[i, j]$，需要满足 $A_i \leq A_j$，因此若发现 $A_i > A_j$，则将 $A_i$ 调整为 $A_j$。
• 区间内的其他位置 $A_k$ 必须满足 $A_k < A_i$，因此若 $A_k \geq A_i$，则将 $A_k$ 调整为 $A_i - 1$。

迭代调整：

• 使用 BFS 不断处理每个位置的约束条件，直到所有约束都被满足。每次调整后，将受影响的位置加入队列继续处理。

代码实现

#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
int n, m, x, c;
int a[N];  // 存储数列每个位置的值
int vis[N];  // 标记数组，用于 BFS

vector<pair<int, int>> g[N];  // 存储与每个位置相关的区间

int main() {
    cin >> n >> m >> x >> c;
    fill(a + 1, a + n + 1, x); // 初始最大值设为x

    // 读入区间并存储相关信息
    for (int i = 0; i < c; ++i) {
        int l, r;
        cin >> l >> r;
        g[r].push_back({l, r});  // 与r相关的区间
        g[l].push_back({l, r});  // 与l相关的区间
    }

    // 初始化队列，将所有位置加入队列
    queue<int> q;
    for (int i = 1; i <= n; ++i) {
        q.push(i);
        vis[i] = 1;
    }

    // BFS处理约束条件
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        vis[u] = 0;
        
        // 处理与u相关的所有区间
        for (auto [l, r] : g[u]) {
            // 确保A[l] <= A[r]
            if (a[l] > a[r]) {
                a[l] = a[r];
                if (!vis[l]) {
                    q.push(l);
                    vis[l] = 1;
                }
            }

            // 处理区间内其他位置，确保A[k] < A[l]
            for (int i = min(l, r) + 1; i < max(l, r); ++i) {
                if (a[i] > a[l] - 1) {
                    a[i] = a[l] - 1;
                    if (!vis[i]) {
                        q.push(i);
                        vis[i] = 1;
                    }
                }
            }
        }
    }

    // 输出结果
    for (int i = 1; i <= n; ++i) {
        cout << a[i] << endl;
    }

    return 0;
}