醉心代码无法自拔

程序员的自我修养(?)

0%

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

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

点我补题 （需要更换）

A.九九八十一难

思路

01背包。尝试将每一种物品放入背包中，检查容积是否刚好为 $sum / 2$ 即可。

Fun Fact：验题人一开始用错解卡过了样例，然后出题人进行了紧急（并不）加强。

代码（验题程序）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void solve()
{
    int n;
    cin >> n;
    vector<int> vec(n);
    for (auto &v : vec)
        cin >> v;
    int tgt = accumulate(all(vec), 0);
    if (tgt & 1)
    {
        cout << "No" << endl;
        return;
    }
    tgt /= 2;
    constexpr int MAX = 100 * 200 + 10;
    vector<int> dp(MAX, 0);
    dp[0] = 1;
    for (auto &v : vec)
        for (int i = MAX - 1; i >= 0; i--)
            if (dp[i])
                dp[i + v]++;
    cout << (dp[tgt] ? "Yes" : "No") << endl;
}

B.眼看喜

思路

似乎是纯模拟题。本题所采用的技巧((l)++,(r+1)–)可以在多种类型的题目（比如CF2014D 或者各种括号序列题）见到。比较重要。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void solve()
{
    int x, m;
    cin >> x >> m;
    vector<int> vec(x + 10, 0);
    while (m--)
    {
        int l, r;
        cin >> l >> r;
        vec[l] += 1, vec[r + 1] -= 1;
    }
    int ans = (vec[0] == 0);
    for (int i = 1; i <= x; i++)
    {
        vec[i] += vec[i - 1], ans += !vec[i];
    }
    cout << ans << endl;
}

C.耳听怒

出题人说自己有严格的数学证明。怎么证的问他去。

反正手玩一下可以发现在 $n \times n $ 的大前提下，后手似乎必胜。那就猜后手必胜交一发吧。

嘿，后手确实必胜。

代码（Python）

1
print("Tianmingren")

D.鼻嗅爱

思路

实际技巧和B题相同。

对于每个位置，记录其最远能走到的位置的方法就是将其最远位置+1的格子的格子减去1，然后一轮遍历下来看看第 $n$ 个格子有没有办法可以到达即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void solve() {
    int n;
    cin >> n;
    vector<int> c(n + 2);
    for (int i = 1; i <= n; i ++ ){
        int x;
        cin >> x;
        c[i] += c[i - 1];
        if (c[i] || i == 1){
            c[i] += 1;
            c[min(n, i + x) + 1] -= 1;
        }
    }
    cout << (c[n] ? "Yes" : "No")<<endl;
}

E.舌尝思

思路

Python秒了

C++有两种方案，一种是题目提示里给出的求数位和相加模9是否为0并且奇数和与偶数和只差模11是否为0。

另一种是模拟竖式除法直接一步一步取模。

按需取用。

代码（思路2）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int divMod(string str, int num)
{
    int s = 0;
    for (auto &ch : str)
        s = (s * 10 + ch - '0') % num;
    return s;
}

void solve()
{
    int n;
    cin >> n;
    int ans = 0;
    while (n--)
    {
        string str;
        cin >> str;
        ans += (divMod(str, 99) == 0);
    }
    cout << ans << endl;
}

代码（Python）

1
2
3
4
5
6
import sys
sys.set_int_max_str_digits(10000)
ans = 0
for _ in range(int(input())):
    ans += (int(input()) % 99 == 0)
print(ans)

F.身本忧

思路

很签的模拟吧，基本上样例过了就不会出错的那种。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void solve()
{
    int n, m;
    cin >> n >> m;
    vector<string> vec(n);
    for (auto &s : vec)
        cin >> s;
    for (int i = 0; i < n; i++)
    {
        cout << string(m * 2 + 1, '#') << endl;
        for (int j = 0; j < m; j++)
        {
            cout << '#' << (char)(vec[i][j] ^ 32);
        }
        cout << '#' << endl;
    }
    cout << string(m * 2 + 1, '#') << endl;
}

G.意欲现

思路

防AK。做法很像是贪心，但是这同时是一个dp优化技巧，叫做slope trick，可以用priority_queue将 $O(N^2)$ 的 dp 优化到 log 复杂度。

验题人乱搞搞过去的，然后被其他验题人指出来这个技巧后经验++了

这个题裸题在CF上2300

[Codeforces] Tutorial-Slope Trick

[博客园] 学习笔记 - Slope Trick

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void solve()
{
    priority_queue<i64> que;
    int n, x;
    i64 ans = 0;
    cin >> n;
    while (n--)
    {
        cin >> x;
        que.push(x);
        if (x < que.top())
            ans += que.top() - x, que.pop(), que.push(x);
    }
    cout << ans << endl;
}

H.六根归一

思路

根据 $x $ 和 $y$ 计算一下天数（注意余数加一），然后取模加一即可。

代码

1
2
3
4
5
6
7
8
void solve()
{
    int x, y, a;
    cin >> x >> y >> a;
    int d = x / y + (x % y != 0);
    cout << (a - 1 + d) % 7 + 1 << endl;
}

Fun Facts

1.本套新生赛出题人AK了黑神话悟空。

2.黑神话悟空的题面吸引来很多外校群友来验题。在此表达我对福建师范大学ACM队学长对我校新生赛一段时间以来的大力支持。他们的新生赛也好玩，有兴趣可以去打。

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