Nowcoder Contest 3002 Solution (Chinese)

2020 牛客寒假算法基础集训营 1(字符串、贪心、矩阵快速幂、概率论、计算几何、并查集、数论)

A. Honoka 和格点三角形

大意

给出 \(m \times n\) 格点矩阵,问在矩阵里面能找出多少个面积为 \(1\),且至少有一条边平行于 \(x\) 轴或 \(y\) 轴的三角形。答案对 \(1000000007\) 取模。

思路

若存在平行于 \(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\ mod\ c = ((a\ mod\ c)(b\ mod\ c))\ mod\ c\) 计算结果。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long n, m, tempa, tempb;
    cin >> n >> m;
    tempa = 2 * (m + n - 2);
    tempb = (2 * m * n - 3 * m - 3 * n + 4);
    cout << (tempa % 1000000007) * (tempb % 1000000007) % 1000000007 << endl;
    return 0;
}

B. Kotori 和 Bangdream

大意及思路

签到题。求数学期望,也就是可能结果的概率乘以其结果的总和。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    double n, x, a, b;
    cin >> n >> x >> a >> b;
    double ans = (a * x + b * (100 - x)) * n / 100;
    printf("%.2lf\n", ans);
    return 0;
}

C. Umi 和弓道

大意

一个人在 \((x_0,y_0)\),给出 \(n\) 个靶子,在 \(x\) 轴或 \(y\) 轴放置挡板,令放置挡板后可以射中的靶子数量不多于 \(k\) 个。

思路

只要靶子和 \((x_0,y_0)\) 不在一个象限就有可能被挡掉。要想挡掉一个靶子,只需求出靶子和 \((x_0,y_0)\) 所在直线与坐标轴的交点,并保证挡板覆盖了这个点。我们只需要恰好覆盖 \(n-k\) 个这样的点就行了。

#include <bits/stdc++.h>
using namespace std;
const double inf = 1e18;
vector<double> v1, v2;
int main()
{
    v1.clear();
    v2.clear();
    double x0, y0;
    int n, k, i;
    cin >> x0 >> y0 >> n >> k;
    k = n - k;
    for (i = 0; i < n; i++)
    {
        double x, y;
        cin >> x >> y;
        if (x * x0 < 0)
        {
            v2.push_back(y0 - x0 * (y - y0) / (x - x0));
        }
        if (y * y0 < 0)
        {
            v1.push_back(x0 - y0 * (x - x0) / (y - y0));
        }
    }
    double mi = inf;
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    if (v1.size() >= k)
    {
        double head = 0, tail = k - 1;
        while (tail < v1.size())
        {
            mi = mi > (v1[tail] - v1[head]) ? (v1[tail] - v1[head]) : mi;
            tail++, head++;
        }
    }
    if (v2.size() >= k)
    {
        double head = 0, tail = k - 1;
        while (tail < v2.size())
        {
            mi = mi > (v2[tail] - v2[head]) ? (v2[tail] - v2[head]) : mi;
            tail++, head++;
        }
    }
    if (mi == 1e18)
        cout << -1;
    else
        printf("%.7lf", mi);
    return 0;
}

D. Hanayo 和米饭

大意

给出 \(n-1\) 个数,求一个数使得所有的 \(n\) 个数经过排序后可形成公差为 \(1\) 的等差数列。保证答案存在且唯一。

思路

签到题。将 \(n-1\) 个数排序,看相邻两数的差是否为 \(2\)。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int a[n - 1];
    for (int i = 0; i < n - 1; i++)
    {
        cin >> a[i];
    }
    sort(a, a + n - 1);
    for (int i = 0; i < n - 2; i++)
    {
        if (a[i + 1] - a[i] != 1)
        {
            cout << a[i] + 1 << endl;
            break;
        }
    }
    return 0;
}

E. Rin 和快速迭代

大意

令 \(f(x)\) 为 \(x\) 因子个数,将 \(f\) 迭代下去,问迭代多少次能得到 \(2\)。

思路

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

#include <bits/stdc++.h>
using namespace std;
long long sol(long long x)
{
    long long temp = 0;
    long long i;
    for (i = 1; i * i <= x; i++)
    {
        if (x % i == 0)
            temp++;
    }
    temp = temp << 1;
    i--;
    if (i * i == x)
        temp--;
    return temp;
}
int main()
{
    long long n;
    cin >> n;
    int ans = 0;
    while (1)
    {
        n = sol(n);
        ans++;
        if (n == 2)
        {
            cout << ans << endl;
            return 0;
        }
    }
    return 0;
}

F. ##TODO##

G. Eli 和字符串

大意

给出一个字符串,求连续子串的最小长度,要求这个连续子串要包含至少 \(k\) 个相同的某个字母。

思路

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

#include <bits/stdc++.h>
using namespace std;
int cnt[26][200010];
int main()
{
    int n, k;
    string a;
    cin >> n >> k >> a;
    int l = a.size();
    for (int i = 0; i < l; 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" << endl;
    else
        cout << ans << endl;
    return 0;
}

H. Nozomi 和字符串

大意

一个 \(01\) 串,允许你改变其中的 \(k\) 个数字,然后找出一个尽可能长的连续子串,这个子串上的所有字符都相同。求这个子串的长度。

思路

依然是尺取法。分成将 \(0\) 变成 \(1\) 和将 \(1\) 变成 \(0\) 两种情况。对于前者,还是两个指针,右指针不断右移,当遇到 \(0\) 就用掉一次操作直到次数用尽。接下来右指针继续右移直到再次需要操作的时候,这时左指针右移直到已用操作数恰好减一为止,这时右指针继续右移。后者同理。

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    int n, k, ans = 0;
    cin >> n >> k >> s;
    int pl = 0, pr = 0, change = 0;
    // 0 => 1
    for (int i = 0; i < n; i++)
    {
        if (s[i] == '0')
        {
            if (change < k)
            {
                change++;
            }
            else
            {
                while (pl <= pr && s[pl] != '0')
                    pl++;
                pl++;
            }
        }
        pr++;
        ans = max(ans, pr - pl);
    }
    pl = 0, pr = 0, change = 0;
    for (int i = 0; i < n; i++)
    {
        if (s[i] == '1')
        {
            if (change < k)
            {
                change++;
            }
            else
            {
                while (pl <= pr && s[pl] != '1')
                    pl++;
                pl++;
            }
        }
        pr++;
        // cout << pl << " " << pr << endl;
        ans = max(ans, pr - pl);
        // cout << ans << endl;
    }
    cout << ans << endl;
    return 0;
}

I. Nico 和 Niconiconi

大意

给出一个字符串,其中 nico 计 \(a\) 分,niconi 计 \(b\) 分,niconiconi 计 \(c\) 分,每个字符都只能参与一次计分,问最大分数。

思路

简单 DP。\(dp[i]\) 可由 \(dp[i-1]\)、\(dp[i-3]\)、\(dp[i-5]\) 和 \(dp[i-9]\) 转移而来,转移后取最大者即可。要注意避免越界。

#include <bits/stdc++.h>
using namespace std;
long long dp[300010];
int main()
{
    string s;
    long long n, a, b, c;
    cin >> n >> a >> b >> c >> s;
    for (long long 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] << endl;
    return 0;
}

J. ## TODO##

Leave a Reply

Your email address will not be published. Required fields are marked *