题解 | #河南理工大学算法(ACM)协会第一次招新#

B 梅开二度

大致题意：向数组 中添加一个数，使得集合 构成一个排列。

想法：

将集合 分成集合 和集合 。一开始 。

集合 构成一个排列 等价于 。

由于向数组 中添加一个数，最多使集合增加两个数，所以如果一开始的集合 元素的数量小于 ，则输出 。

若 ，说明只差一个数 ，向数组 的最后添加 ，就可以补全 ，构成排列，所以输出 。

若 ，此时 ，若可以将 中的唯一一个元素拆成集合 中未出现的两个元素，则输出 ，否则输出 。

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

int n, m, a[200010];

void solve() {
    int res = 0, x = 0;
    map<int, int> mp;
    cin >> n;
    for (int i = 1; i <= n - 1; i++) cin >> a[i];
    for (int i = 1; i <= n - 1; i++) mp[a[i] - a[i - 1]]++;

    for (int i = 1; i <= n; i++) {
        if (mp.find(i) == mp.end()) x += i;
        else res++;
    }

    if (n - res == 1) cout << "YES\n";
    else if (n - res == 2) {
        if (mp[x] == 1 + (x <= n)) cout << "YES\n";
        else cout << "NO\n";
    }
    else cout << "NO\n";
}

signed main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

I 最大值

max_element() 可以找数组或 vector 的最大值。

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

const int N = 2000010;
long long n, m, a[N];

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cout << (*max_element(a + 1, a + n + 1) % 998244353) << "\n";
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T = 1;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

M 小a爱闯关

测评数据

由于可以重复闯关，所以优先选择血量损失最小的关卡闯。若血量损失最小的关卡无法闯，则优先选择血量损失次小的。

对数组 进行排序的同时，保留 的下标 。

从小到大遍历数组 ，当 r >= idx 时，选择这个关卡闯关。

时间复杂度：因为 ，所以每次闯关 必定减小，闯关时间复杂度 ，排序时间复杂度 ，总时间复杂度 。

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

int n, r, ans;
pair<int, int> a[100010];

int main() {
    cin >> n >> r;
    for (int i = 1; i <= n; i++) cin >> a[i].first, a[i].second = i;
    sort(a + 1, a + 1 + n);
    for (int i = 1; i <= n; i++) {
        while (r >= a[i].second) r -= a[i].first, ans++;
    }
    cout << ans;
    return 0;
}