2020 牛客寒假算法基础集训营题选(一)解题思路

赛时 AC 率参考

个人赛,有效参赛人数约 2800 人,参赛同学多为大一大二 ACMer。

本题集偏简单。

题号 AC 提交
A 1160 4505
B 2708 5017
C 1908 6674
D 1325 4901
E 331 1247

A. Honoka 和格点三角形

若存在平行于 x 轴或 y 轴的边且长度为 2 ,一共有 2(n-1)(m-2)m+2(m-1)(n-2)n 种情况。

若存在平行于 x 轴或 y 轴的边且长度为 1 ,除去已经计算过的情况(即还存在平行于 x 轴或 y 轴且长度为 2 的边),一共有 2(m-1)(m-2)(n-2)+2(n-1)(n-2)(m-2) 种情况。

相加后化简,得到 2(m+n-2)(2mn-3m-3n+4) ,利用 ab \ \% \ c = ((a \ \% \ c)(b \ \% \ c)) \ \% \ c 计算结果。

Code
ll ans = ((2 * (m + n - 2)) % MOD) * ((2 * m * n - 3 * m - 3 * n + 4) % MOD) % MOD;

B. Kotori 和 Bangdream

水题。

Code
double ans = (a * x + b * (100 - x)) * n / 100;

C. Rin 和快速迭代

直接模拟就行。求因子个数时注意处理完全平方数。

Code
ll sol(ll x)
{
    ll cnt = 0;
    ll i;
    for (i = 1; i * i <= x; i++)
    {
        if (x % i == 0) cnt++;
    }
    cnt = cnt << 1;
    i--;
    if (i * i == x) cnt--;
    return cnt;
}

D. Eli 和字符串

前缀和加尺取法。前缀和用于求某个连续子串各个字母出现的次数。尺取法即连续子串两个指针,右指针不断右移,当发现满足条件的连续子串则左指针开始右移,当右指针移动到尽头则停止。

Code
#include <bits/stdc++.h>
using namespace std;
int cnt[26][200010];
int main()
{
    int n, k;
    string a;
    cin >> n >> k >> a;
    for (int i = 0; i < a.size(); i++)
    {
        for (int j = 0; j < 26; j++)
        {
            cnt[j][i + 1] = cnt[j][i];
        }
        cnt[a[i] - 'a'][i + 1]++;
    }
    int p1 = 0, p2 = 1, ans = n + 1;
    while (1)
    {
        int flag = 0;
        for (int i = 0; i < 26; i++)
        {
            if (cnt[i][p2] - cnt[i][p1] >= k)
            {
                ans = min(ans, p2 - p1);
                flag = 1;
            }
        }
        if (flag == 1) p1++;
        else p2++;
        if (p2 == n + 1) break;
    }
    if (ans == n + 1) cout << "-1" << '\n';
    else cout << ans << '\n';
    return 0;
}

E. Nico 和 Niconiconi

简单 DP。考虑将 dp_i 作为前 i+1 个字符得到分数的最大值,那么 dp_i 可由 dp_{i-1},dp_{i-3},dp_{i-5},dp_{i-9} 转移而来,取最大者即可。要注意避免越界。

Code
for (int i = 0; i < n; i++)
{
    if (i > 0) dp[i] = dp[i - 1];
    if (i >= 3 && s.substr(i - 3, 4) == "nico") dp[i] = max(dp[i], dp[i - 3] + a);
    if (i >= 5 && s.substr(i - 5, 6) == "niconi") dp[i] = max(dp[i], dp[i - 5] + b);
    if (i >= 9 && s.substr(i - 9, 10) == "niconiconi") dp[i] = max(dp[i], dp[i - 9] + c);
}
cout << dp[n - 1] << '\n';
粤 ICP 备 2020080455 号