AC手记

记录从暴力到最优的每一步

0%

2025 CCPC郑州邀请赛VP实况及题解

发表于 更新于 分类于 1.2k 1 分钟

2025 CCPC郑州邀请赛VP实况及题解

比赛实况

郑州邀请赛的前期题难度不算高，在赛时我成功地做出了D、H、J、M题，但是剩下通过率较高的F和G却没有写出来，最后就是一个$4$题$85$罚时的结果。接下来我来讲解一下各题的思路。

题解

D.2025

简单数学题，只需要判断给定数字$n$以及它的数位和是否为完全平方数即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void moth()
{
    ll n;
    cin >> n;
    ll t = sqrtl(n);
    if (t * t == n)
    {
        ll res = 0;
        while (n)
        {
            res += n % 10;
            n /= 10;
        }
        ll s = sqrtl(res);
        if (s * s == res)
            cout << "Yes\n";
        else
            cout << "No\n";
        return;
    }
    cout << "No\n";
}

H.树论函数

题目大意：定义$f(n)=n(n+1)$，如果存在$f(n)=f(a) \cdot f(b)$，则从点$n$出发分别向$a$和$b$连边，并且给定$s,l,r$，求从点$s$出发能够到达$[l,r]$范围内点的个数。
已知$f(n)=n(n+1)$，$f(n+1)=(n+1)(n+2)$，所以$f(n)f(n+1)=(n^2+2n)(n^2+2n+1)$，那么点$n$和$n+1$一定连通，所以所有的点均连通，答案为$r-l+1$。

1
2
3
4
5
6
void moth()
{
    ll s, l, r;
    cin >> s >> l >> r;
    cout << r - l + 1 << '\n';
}

J.Ring Trick

题目大意：已知每个大写字母有多少个洞，我们需要求出给定字符串在经过移位之后最多会有几个洞。
那么我们可以将字符串的每个字母移位$26$次，因为总共只有$26$个字母，所以$26$次移位之后字符串会变为原来的字符串，不断地取洞数的最大值即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void moth()
{
    int holes_cnt[26] = {1, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0};
    string s;
    cin >> s;
    ll ans = 0;
    for (int i = 0; i <= 30; i++)
    {
        ll sum = 0;
        for (int j = 0; j < s.length(); j++)
        {
            int t = (int)s[j] - 65;
            t = (t + i) % 26;
            sum += holes_cnt[t];
        }
        ans = max(ans, sum);
    }
    cout << ans << '\n';
}