醉心代码无法自拔

程序员的自我修养(?)

0%

2024ACM集训队第一次入队赛 验题人题解

发表于 更新于 分类于
本文字数： 5.1k 阅读时长 ≈ 9 分钟

点我补题

观前提醒

我的代码有一个最基本的多测架构，具体架构可以参照板子博客记录的 Template.cpp 章节。对于多测场景，在 main函数里负责读入数据组数，并且在 solve函数里负责每一个单测的解题，这是一种比较好的习惯。在下面的题解代码中，我只会给出每一个单测的 solve 函数。不再赘述。

A.网络竞赛平台与小鹿与正在检验你是否是真人请稍后

思路

可以开一个桶记录从 0 到 9 每一位在输入数字中出现了多少次。题目要求没有前导 0，则首位肯定要从 1~9 中最小的一个数字出。然后就是从 0 到 9 依次输出即可。

针对于我的验题代码：我采用了字符串读入并遍历字符串来快速检索每一位的值（而不是每次%10 记录完后/10），并且采用了 map 代替堆来进行遍历。

代码（验题程序）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void solve()
{
    string str;
    cin >> str;
    map<int, int> mp;
    int mn = 10;
    for (auto ch : str)
    {
        mp[ch - '0']++;
        if (ch != '0')
            mn = min(mn, ch - '0');
    }
    string ans;
    ans.push_back(mn + '0');
    mp[mn]--;
    for (auto &[k, v] : mp)
        while (v)
            v--, ans.push_back(k + '0');
    cout << ans << endl;
}

代码（新手友好版本）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void solve()
{
    int num;
    cin >> num;
    int cnt[10] = {0};
    int mn = 10;
    while (num)
    {
        cnt[num % 10]++;
        if (num % 10 != 0)
            mn = min(mn, num % 10);
        num /= 10;
    }
    cout << mn;
    cnt[mn]--;
    for (int i = 0; i <= 9; i++)
    {
        while (cnt[i] > 0)
            cnt[i]--, cout << i;
    }
    cout << endl;
}

B.ICPC 与小鹿的差旅费用规划

思路

签到。输入 $a,b$ ，输出 $2a+b$。

但是，很多人做题的时候，一个是不明白多测的具体含义（这个我给出的样例也有锅，我谢罪），上来直接开写。

另外一些人则是做题不看数据范围，或者是不知道给出数据范围是干什么用的，这就不好。

在 C++中，int 变量在记录的时候，其上限能记录到 32 位二进制均为 1 的数字，也就是十进制的大约$2\cdot10^9$。而题目中给出的数据范围在 $2\cdot10^{15}$，明显超出此范围。

所以，要用 long long。

十年算竞一场空，不开 long long见祖宗。

代码

1
2
3
4
5
6
7
using i64 = long long;
void solve()
{
    i64 a, b;
    cin >> a >> b;
    cout << a * 2 + b << endl;
}

C.CCPC 与饭后消食的小鹿

思路

本题为 Atcoder Beginner Contest 240 C 题原题，并且数据点也是直接采用的 Atcoder 公开的数据点。

思路

小鹿每次跳跃都会从上一次发展而来，所以我们可以维护两个数组，一个用来记录“上一次跳跃”所到达的点，一个根据“上一次跳跃”到达的点计算本次跳跃到达的新点，然后每次计算完成后，用本次跳跃到达的点的数据覆盖上一次跳跃到达的点。数据范围足够小，不会超时。

思考题：这道题正解是动态规划，怎么样优化才能将暴力代码优化成动态规划的样子？动态规划是什么？

代码

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
void solve()
{
    int last[10200];
    int cur[10200];
    int n, x;
    cin >> n >> x;
    last[0] = 1;
    while (n--)
    {
        int a, b;
        cin >> a >> b;
        for (int i = 0; i <= x; i++)
        {
            if (last[i])
            {
                cur[i + a] = 1;
                cur[i + b] = 1;
            }
        }
        for (int i = 0; i <= x; i++)
        {
            last[i] = cur[i];
            cur[i] = 0;
        }
    }
    if (last[x])
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}

D.百度之星与小鹿的铁牌

思路

这个需要在纸上自行模拟一下路线，也就是为什么ACM竞赛会提供草稿纸。有些数学题不动笔墨是想不到做题思路的。

模拟路线个数以后可以很轻易的发现，从 $1$ 到 $n$ 的路径个数符合斐波那契数列规律，问题转化为求前30项斐波那契数列。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
int fib[40];
void init() // 需要先在 main 函数里执行一次 init
{
    fib[1] = 1, fib[2] = 1;
    for (int i = 3; i < 40; i++)
        fib[i] = fib[i - 1] + fib[i - 2];
}
void solve()
{
    int n;
    cin >> n;
    cout << fib[n] << endl;
}

E.蓝桥杯与鹿与小面包

思路

智慧题。题目要求删除若干组数以后恰好留下一个最大的数，我们逆过来考虑，有哪些数被删除以后可以留下。

当一个数左侧有 $n\cdot k$个数的时候，其右侧也一定有 $m \cdot k$ 个数 $(n,m > 0)$，因为题目保证经过删除数字操作以后恰好只剩下一个数。

所以只需要计算满足条件的数字的最大值即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
void solve()
{
    int n, k;
    cin >> n >> k;
    int num, ans = 0;
    for (int i = 1; i <= n; i++)
    {
        cin >> num;
        if ((i - 1) % k == 0)
            ans = max(ans, num);
    }
    cout << ans;
}

F.睿抗与小鹿的贪心消消乐

思路

模拟。按部就班的写，注意判断特殊情况（比如三个格子相邻且都是万能颜色 .）即可。

考验代码底力的题目。

代码

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
using Point = pair<int, int>;
#define x first
#define y second
void solve()
{
    int n;
    cin >> n;
    vector<string> grid(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> grid[i], grid[i] = '$' + grid[i];
    int q;
    cin >> q;
    while (q--)
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            vector<Point> vec(3);
            vector<int> xs, ys;
            for (int i = 0; i < 3; i++)
            {
                cin >> vec[i].x >> vec[i].y;
                xs.push_back(vec[i].x), ys.push_back(vec[i].y);
            }
            sort(xs.begin(), xs.end());
            sort(ys.begin(), ys.end());
            set<char> st;
            if (xs[0] == xs[1] && xs[1] == xs[2] && ys[1] - ys[0] == 1 && ys[2] - ys[1] == 1)
            {
                for (auto &pt : vec)
                    if (grid[pt.x][pt.y] != '.')
                        st.insert(grid[pt.x][pt.y]);
                cout << (st.size() <= 1 ? "YES" : "NO") << endl;
            }
            else if (ys[0] == ys[1] && ys[1] == ys[2] && xs[1] - xs[0] == 1 && xs[2] - xs[1] == 1)
            {
                for (auto &pt : vec)
                    if (grid[pt.x][pt.y] != '.')
                        st.insert(grid[pt.x][pt.y]);
                cout << (st.size() <= 1 ? "YES" : "NO") << endl;
            }
            else
                cout << "NO" << endl;
        }
        else if (op == 2)
        {
            Point pt;
            char val;
            cin >> pt.x >> pt.y >> val;
            grid[pt.x][pt.y] = val;
        }
    }
}

G.天梯赛与小鹿与字符串维护

思路

另一道模拟题。也是按部就班的模拟就好了，需要一定字符串知识。

如果看不懂题解代码，请先学习完C++的string字符串部分再来补题。

代码

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
void solve()
{
    int n;
    cin >> n;
    string str;
    cin >> str;
    vector<int> val(26);
    for (int i = 0; i < 26; i++)
        cin >> val[i];
    int q;
    cin >> q;
    while (q--)
    {
        int op;
        cin >> op;
        if (op == 1)
        {
            string s;
            cin >> s;
            str += s;
        }
        else if (op == 2)
        {
            int ans = 0;
            for (auto ch : str)
                ans += val[ch - 'a'];
            cout << ans << endl;
        }
        else if (op == 3)
        {
            int l, r;
            cin >> l >> r;
            assert(r <= str.size());
            str = str.substr(0, l - 1) + str.substr(r);
        }
    }
}

Fun Facts

1.本套题目的主人公是教练鹿老师的儿子，他现在也是一名信息竞赛选手。当然，我们事先在出题的时候没有告诉鹿老师，所以他在看到题面的时候乐了好一阵。

2.所有的比赛背景介绍由我撰写。包括梗图也是我找的，看着感觉是不是还不错。

3.一开始想要拿一道大模拟做最难的题，并且一开始想要放在 A 题的位置。但是我们担心大家都不会写，最后取消了，放了个比较简单的题在 A 的位置上。

4.A 题想要教会大家两件事：题目难度与顺序无关，题目背景与题目无关。

5.消消乐题目经过了一次数据削弱，但是削弱后的随机数据卡掉了我的验题程序。（削弱后随机数据随机出了 ... 数据，这组数据成功卡掉了半数验题人的答案）

6.榜单的颜色不仅是想要对应彩虹色，比如青绿色和青蓝色对应言和和洛天依的弹幕应援色。所有的颜色都有对应的 VOCALOID 应援色，当然是我自己搞的。看看有没有有心人能收集全。（？

7.想要看大家比赛结果的我过于热切，于是物理补考只写了 30 分钟就匆匆交卷跑路了（？？）

8.感谢所有集训队成员为新生赛做出的努力！