比赛回顾

本来想着中秋节上次大分，竟然倒霉的把 Vscode 写炸了，开局重启了半小时电脑。这场比赛人均三道题，A 题想复杂了写了个 dfs 死循环把电脑整死机了，眼看着预测要掉 100 分不得不用 devcpp 含泪打下去，又太慌张 WA 了太多次罚起飞最终排名一落千丈。C 题还卡了下关流，用惯了 vscode 用户代码块都忘了写关流了。

赛后个人总结：

  • vscode 崩溃就删掉所有源文件，重启不管用
  • 宁可多检查一会也不要急着交，一次罚时真的很亏

A.Regular Bracket Sequences—签到

题意：给定数字 n，请输出 n 中左右匹配的长度为 2n 的括号字符串

思路：找出前 n 中即可，其实直接有规律的左右字符串交叉就可以

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int cnt;
int n;
 
void dfs(int l, int r, string s) {
    if (cnt == n) return;
    if (l == r && r == n) {
        cout << s << endl;
        ++cnt;
        return;
    }
    if (l < n) dfs(l + 1, r, s + "(");
    if (r < n) dfs(l, r + 1, s + ")");
}
 
void test_case() {
    cnt = 0;
    cin >> n;
    dfs(0, 0, "");
}

B.Combinatorics Homework—思维

题意：一个信由 a 个 A，b 个 B，c 个 C 字符组成，称一个匹配对为第 i 个位置和第 i+1 位置字符相同，请判断是否能满足信只有 m 个匹配对

思路 ：x 个字符最多可以形成 x-1 个匹配对，所有就看下所有的字符能组成最多的匹配对数量是否大于等于 m，同时还要注意组成最小的匹配对数量是否小于等于 m

1
2
3
4
5
6
7
8
9
10
11
void solve() {
    int a, b, c, m;
    cin >> a >> b >> c >> m;
    int tmp1 = a - 1 + b - 1 + c - 1;
    int tmp2 = max(a, max(b, c));
    tmp2 = tmp2 - (a + b + c - tmp2) - 1;
    if (tmp1 >= m && tmp2 <= m)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}

C.Slay the Dragon—贪心+二分

题意：有 n 位勇士每个勇士战斗力为 ai， 有 m 条龙它们血量是 xi 和攻击力 yi，对于每条龙的攻击我们需要派出一位勇士去攻击龙（战斗力大于等于 xi），剩下勇士去防守龙（战斗力之和大于等于 yi），每次与龙战斗的时候你可以用 1 体力暂时给一位勇士增幅 1 战斗力，请判断战斗每条龙的时候你最少需要用的体力

思路：很容易贪心的想到将勇士们按照战斗力升序排序，先二分找到战斗力大于等于龙的血量用来供给的勇士

  • 如果该勇士恰好战斗力等于 x，那么就是最优解只需要看防御的勇士们是否需要增幅战斗力
  • 否则我应该看看是用该勇士还是用前面的那个勇士（前提是前面还有勇士），两种情况取最小值即是最优解
    • 用该勇士，那么看看防御的勇士们是否需要增幅战斗力
    • 否则需要给前面的勇士增幅，再看看防御的勇士们是否需要增幅战斗力
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
ll a[maxn], sum[maxn];
 
void test_case() {
    ll n;
    cin >> n;
    for (ll i = 1; i <= n; ++i)
        cin >> a[i];
    sort(a + 1, a + 1 + n);
    for (ll i = 1; i <= n; ++i)
        sum[i] = sum[i - 1] + a[i];
    ll m;
    cin >> m;
    while (m--) {
        ll x, y;
        cin >> x >> y;
        ll ans = 0;
        ll pos = lower_bound(a + 1, a + n + 1, x) - a;
        if (pos > n) {
            ans += x - a[n];
            if (sum[n - 1] < y) ans += y - sum[n - 1];
            cout << ans << endl;
            continue;
        } else {
            ll tmp = sum[n] - a[pos];
            if (tmp < y) ans += y - tmp;
            if (a[pos] == x) {
                cout << ans << endl;
                continue;
            }
            if (pos > 1) {
                ll tot = 0;
                tot += x - a[pos - 1];
                tmp = sum[n] - a[pos - 1];
                if (tmp < y) tot += y - tmp;
                ans = min(ans, tot);
            }
            cout << ans << endl;
        }
    }
}

D.The Strongest Build—BFS+思维

题意：有 n 个技能槽，每个技能槽有 ci 个技能项目可以选择，保证每个技能槽的 ci 个技能权值满足 a1 < a2 < … < aci。每个技能槽只能选择一个技能，游戏规定 m 中技能槽搭配是不允许的，请你找出满足游戏规定的权值最大的技能槽搭配。题目保证总存在这样的答案。

思路：关键是如何记录每个技能槽搭配，这里用 map 容器嵌套 vector 容器就可以了（有人用 hash 好像更快）。初始搭配就每个技能槽都选择最后一个技能（这样权值最大）并放入优先队列（按照技能权值大的优先），然后就不断 BFS 从队列中取出来一个技能槽并判断是否满足游戏规定，不满足就依次将每个技能槽的技能项目想下选择一个并重新将该技能槽搭配放入队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
const int maxn = 11;
 
int n, m;
vector<int> a[maxn];
map<vector<int>, bool> mp, was;	//一个记录被ban的搭配，一个记录BFS过程中出现过的搭配
 
struct cmp {  //结构体重载优先队列
    int getsum(const vector<int> &v){
        int s = 0;
        for (int i = 0; i < n; ++i) s += a[i][v[i]];
        return s;
    }
    bool operator()(vector<int> &x, vector<int> &y) {   //大顶堆
        int sumx = getsum(x), sumy = getsum(y);
        return sumx < sumy;
    }
};
 
priority_queue<vector<int>, vector<vector<int> >, cmp> que;  //优先队列保证取出的永远是当前最优的
 
void test_case() {
    cin >> n;
    vector<int> vec;
    for (int i = 0; i < n; ++i) {
        int c;
        cin >> c;
        a[i].resize(c);
        for (int &x : a[i]) cin >> x;
        vec.push_back(c - 1);  //起初每个槽都选择最大的项目
    }
    que.push(vec);
    cin >> m;
    while (m--) {
        vector<int> t(n);
        for (int &x : t) cin >> x, --x;
        mp[t] = 1;
    }
 
    while (1) {  //恒定有答案所以一直循环BFS
        auto v = que.top();
        que.pop();
 
        if (mp[v]) {  //当前最优解被ban
            for (int i = 0; i < n; ++i) {
                if (!v[i]) continue;
                --v[i];
                if (!was[v]) was[v] = 1, que.push(v);  //标记当前选择过选择过然后入队
                ++v[i];
            }
        } else {
            for (int x : v) cout << x + 1 << ' ';
            cout << endl;
            break;
        }
    }
}