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

如遇到 [Math Processing Error] 报错,请刷新页面再试。

赛时 AC 率参考

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

本题集相比上一题集而言略有难度。

题号 AC 提交
A 1770 4469
B 745 5723
C 689 2282
D 647 2168
E 202 847
F N/A N/A
G N/A N/A
H 5 61

A. 欧几里得

递归次数为 0 次的时候肯定这两个是 10 。递归次数为 1 次的时候则是 21 。假设 a>b ,其实就是已知 ba \bmod b ,然后要让 a 最小,那么就让 \left \lfloor \frac{a}{b} \right \rfloor 最小。那就让它等于 1 ,可以很快发现是斐波那契数列。

Code
a[0] = 1;
a[1] = 2;
for (int i = 2; i < n + 2; i++)
{
    a[i] = a[i - 1] + a[i - 2];
}
if (n == 0) cout << "1" << endl;
else cout << a[n + 1] << endl;

B. 子段乘积

会乘法逆元的话可以直接尺取。

简单来说,如果有一个素数 p ,根据费马小定理则有 a^{p-1}\equiv1(\bmod p) ,那么 {a}\cdot a^{p-2}\equiv1(\bmod p)a^{p-2} 就叫 a \bmod p 意义下的逆元。

Code 1
ll ans = 0, sum = 1, c = 0;
for (i = 1; i <= n; i++)
{
    if (i > k && a[i - k] != 0) sum = sum * qpow(a[i - k], mod - 2) % mod;
    if (a[i] == 0) c = 0;
    else c++, sum = sum * a[i] % mod;
    if (c >= k) ans = max(ans, sum);
}
cout << ans << '\n';

当然,你也可以像本二货一样,赛时直接敲一棵线段树,建完树直接查询(是太闲了吗)。

Code 2
#include <bits/stdc++.h>

using namespace std;

const int maxn = 200010;
const int mod = 998244353;

int a[maxn + 2];

struct tree
{
    int l, r;
    long long pre, add;
} t[4 * maxn + 2];

void build(int p, int l, int r)
{
    t[p].l = l;
    t[p].r = r;
    if (l == r)
    {
        t[p].pre = a[l];
        return;
    }
    int mid = (l + r) / 2;
    build(p * 2, l, mid);
    build(p * 2 + 1, mid + 1, r);
    t[p].pre = (t[p * 2].pre * t[p * 2 + 1].pre) % mod;
}

long long ask(int p, int x, int y)
{
    if (x <= t[p].l && y >= t[p].r)
        return t[p].pre;
    int mid = (t[p].l + t[p].r) / 2;
    long long ans = 1;
    if (x <= mid)
        ans = ans * ask(p * 2, x, y) % mod;
    if (y > mid)
        ans = ans * ask(p * 2 + 1, x, y) % mod;
    return ans;
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    build(1, 1, n);
    long long ans = -1;
    for (int i = 1; i + m - 1 <= n; i++)
    {
        int x, y;
        ans = max(ans, ask(1, i, i + m - 1));
    }
    printf("%lld\n", ans);
    return 0;
}

C. 子段异或

首先前缀异或,注意到如果 a\ XOR\ b=c ,那么 c\ XOR\ a=b ,那么数组里任意两个数异或就是某一个区间的异或值,反正我们也不用关心这个区间从哪开始从哪结束,又因为 a\ XOR\ a=0 ,我们给数组排下序,看看相邻两个数字是否相等就可以了。

Code
for (int i = 1; i < n; i++)
{
    a[i] ^= a[i - 1];
}
sort(a, a + n);
ll ans = 0, cnt = 1;
for (int i = 0; i < n; i++)
{
    if (a[i] == 0) ans++;
    if (i != 0 && a[i] == a[i - 1]) cnt++;
    if (i != 0 && (a[i] != a[i - 1] || i == n - 1))
    {
        ans += cnt * (cnt - 1) / 2;
        cnt = 1;
    }
}
cout << ans << '\n';

D. 最小表达式

贪心。加号的数字知道后就知道要有多少个数相加。然后我们将大的数字放在个位十位这种低位数,将小的数字放在高位数。然后是大数加法。

Code
#include <bits/stdc++.h>
using namespace std;

int cnt[20];
int sum[500050];

string s;
int main()
{
    cin >> s;
    int ccnt = 1;
    int n = s.size();
    for (int i = 0; i < n; i++)
    {
        if (isdigit(s[i])) cnt[s[i] - '0']++;
        else ccnt++;
    }
    int p = 0, cp = 0;
    for (int i = 10; i >= 1; i--)
    {
        while (cnt[i])
        {
            sum[cp] += i;
            cnt[i]--;
            p = (p + 1) % ccnt;
            if (p == 0) cp++;
        }
    }
    for (int i = 0; i < 500010; i++)
    {
        sum[i + 1] += sum[i] / 10;
        sum[i] %= 10;
    }
    int opt = 0;
    for (int i = 500010; i >= 0; i--)
    {
        if (opt || sum[i])
        {
            cout << sum[i];
            opt = 1;
        }
    }
    cout << '\n';
    return 0;
}

E. 音乐鉴赏

设第 i 个学生期末随机分数为 y_i ,占比为 x ;如果这个学生平时分为 a_i ,那么如果这个学生最后优秀,其最终的分数必定有:

score_i=y_i \cdot x+(1−x) \cdot a_i \geq 90

整理得:

y_i \geq \frac{90−(1−x) \cdot a_i}{x}

考虑到 y_i 是介于 [0,90] 的任意实数,要求这个学生优秀的概率 p_i ,实则是求满足条件的 y 所占区间长度的比例,所以有:

\begin{align*} p_i&=\frac{90-\frac{90−(1−x) \cdot a_i}{x}}{90} \\ &=\frac{90x-90+(1-x) \cdot a_i}{90x} \\ &=\frac{(90-a_i)(x-1)}{90x} \end{align*}

由于优秀率恰好为 10\ \% ,则优秀人数的数学期望:

E(x)=\sum_{i=1}^{n}p_i = \frac{n}{10}

下面解此方程:

\begin{align*} \sum_{i=1}^{n}\frac{(90-a_i)(x-1)}{90x} &= \frac{n}{10} \\ (x-1) \cdot \sum_{i=1}^{n}(90-a_i) &= 9n \cdot x \\ x&=\frac{\sum_{i=1}^{n}(90-a_i)}{\sum_{i=1}^{n}(90-a_i)-9n} \\ x&=\frac{90n-\sum_{i=1}^{n}a_i}{81n-\sum_{i=1}^{n}a_i} \end{align*}

输出答案时注意需要输出百分数。

Code
double sum = 0;
for (int i = 1; i <= n; i++)
{
    sum += a[i];
}
double ans = (sum - 90 * n) / (sum - 81 * n);
ans *= 100;

本题也可以使用二分求解。

F, G, H. 二维跑步

每题分别代表一个子任务,按易到难排序。
虽然是防 AK,但也别被下面一堆公式吓晕,慢慢推其实还是能推下去的。

题意

一个点在平面直角坐标系中移动,初始位置 (0,0) ,移动了 n 次。从 x=i 的点到 x=i+1 的点有三种方法,到 x=i 的点有一种方法,到 x=i-1 的点有两种方法。已知 nm ,然后问你有多少种方式使得点的 x 坐标最后落在 [-m,m]

F(做法一)

直接 DFS 暴力枚举所有情况逐一判断。

G(做法二)

考虑动态规划,不妨使用 dp_{i,j} 表示走了 i 步后位置在 x=j 的方法数。 显然第 i 步的方法数可以从第 i-1 步转移而来

dp_{i,j} = 3 \cdot dp_{i-1,j-1} + dp_{i-1,j} + 2 \cdot dp_{i - 1,j + 1}

统计答案时,只需要对所有满足题意的位置进行求和即可

\sum_{i=-m}^{m}dp_{n,i}

代码实现时需要注意当前位置可能是负数.

G(做法三)

考虑到 n 步下来本质还是左移、右移、不动三种方式的组合,只需设出三种方式分别的步数,用组合数公式即可。这里不妨设 x 坐标不变的次数为 i ,其中 ax 坐标增加了,那么就会有 n-i-a 次坐标减少。我们可以知道最后的坐标位置为 x_{final}=a-(n-i-a)=2a-n+i 。为了让这个坐标处于 [-m,m] 这个区间,我们要有:

\left\{\begin{matrix} -m \leq 2a-n+i \leq m \\ 0 \leq a \leq n-i \end{matrix}\right.

由于 a 还是一个整数,算出来的结果还需要上下取整:

max(\left \lceil \frac{-m+n-i}{2} \right \rceil,0)\leq a \leq min(\left \lfloor \frac{m+n-i}{2} \right \rfloor,n-i)

结合高中数学内容,我们知道 i 次坐标不变, a 次坐标增加的方案数一共是 C _{n}^{i}(C _{n-i}^{a} \cdot 3^{a} \cdot 2^{n-i-a}) ,我们进行求和操作,得出的结果是:

ans = \sum _{i=0}^{n} \textrm{C} _{n}^{i}(\sum_{a=max(\left \lceil \frac{-m+n-i}{2} \right \rceil,0)}^{min(\left \lfloor \frac{m+n-i}{2} \right \rfloor,n-i)} \textrm{C}_{n-i}^{a} \cdot 3^{a} \cdot 2^{n-i-a})

H(做法四)

在做法四的基础上,我们尝试将上面的式子拆为多部分。令:

\left\{\begin{matrix}\begin{align*}f(p,q)&=C_p^q \cdot3^q \cdot 2^{p-q} \\ L(i)&=max(\left \lceil \frac{-m+n-i}{2} \right \rceil,0) \\ R(i)&=min(\left \lfloor \frac{m+n-i}{2} \right \rfloor,n-i) \\ G(i)&=\sum_{a=L(i)}^{R(i)}f(n-i,a) \\ ans &= \sum_{i=0}^{n}C_{n}^{i} G(i) \end{align*} \end{matrix}\right.

在这些式子中,我们发现要缩短 ans 的计算时间,就必须缩短 G(i) 的计算时间。考虑到计算 G(i)L(i)R(i) 都是一次性计算完成,但是 f(p,q) 这样的式子我们要算上很多遍,我们我们就尝试优化 f(p,q) 的计算。

考虑到我们除了要计算 f(n-i,a) ,还要计算 f(n-i-1,a)f(n-i+1,a) 等等,因为恰好有 C_p^q=C_{p-1}^{q}+C_{p-1}^{q-1} 这个公式,也就有了前项推后项的思路。我们尝试将 23 的指数和组合数匹配一下,得出 f(p,q)=2f(p-1,q)+3f(p-1,q-1) 这样的式子。

接下来就不用再管 f(p,q) 等于什么了,回到 G(i) 这个层面。我们用上面的结论尝试展开上面的式子:

\begin{align*} G(i) &= \sum_{a=L(i)}^{R(i)}f(n-i,a) \\ &= \sum_{a=L(i)}^{R(i)}(3f(n-(i+1),a-1)+2f(n-(i+1),a)) \\ &= 3f(n-(i+1),L(i)-1)+2f(n-(i+1),L(i))+3f(n-(i+1),L(i))+ \cdots +2f(n-(i+1),R(i)-1))+3f(n-(i+1),R(i)-1)+2f(n-(i+1),R(i)) \\ &= 5 \sum_{a=L(i)}^{R(i)-1}f(n-(i+1),a)+3f(n-(i+1),L(i)-1)+2f(n-(i+1),R(i)) \end{align*}

你会发现有一项是 \sum_{a=L(i)}^{R(i)-1}f(n-(i+1),a) ,和 G(i+1) 的形式很像,但是后者是 \sum_{a=L(i+1)}^{R(i+1)}f(n-(i+1),a) ,还是有点区别。怎么办呢?就人为创造一个 \sum_{a=L(i+1)}^{R(i+1)}f(n-(i+1),a) 呗。还是上面那个式子,我们把所有的 L(i) 换成 L(i+1) ,把 R(i)-1 换成 R(i+1) ,但这算出来就和 G(i) 差了几个的 f(n-i,a) 怎么办呢。先标记为 \Delta 到后面再算呗。

\begin{align*} G(i)&=\sum_{a=L(i+1)}^{R(i+1)+1}f(n-i,a)+\Delta \\ &=\sum_{a=L(i+1)}^{R(i+1)+1}(3f(n-(i+1),a-1)+2f(n-(i+1),a))+\Delta \\ &=3f(n-(i+1),L(i+1)-1)+2f(n-(i+1),L(i+1))+3f(n-(i+1),L(i+1))+ \cdots +2f(n-(i+1),R(i+1)))+3f(n-(i+1),R(i+1))+2f(n-(i+1),R(i+1)+1)+\Delta \\ &=5 \sum_{a=L(i+1)}^{R(i+1)}f(n-(i+1),a)+3f(n-(i+1),L(i+1)-1)+2f(n-(i+1),R(i+1)+1)+\Delta \\ &=5G(i+1)+3f(n-(i+1),L(i+1)-1)+2f(n-(i+1),R(i+1)+1)+\Delta \end{align*}
Code
#include <bits/stdc++.h>
using namespace std;

const int mod = 998244353;
const int N = 3000010;
int n, m, f2[N], f3[N], q[N], p[N], G[N];

//////// 快速幂 ////////
int qpow(int a, int b)
{
    int ans = 1;
    a %= mod;
    for (; b; b >>= 1)
    {
        if (b & 1)
            ans = 1ll * ans * a % mod;
        a = 1ll * a * a % mod;
    }
    return ans;
}

//////// 组合数 ////////
int c(int a, int b) { return 1ll * q[a] * p[b] % mod * p[a - b] % mod; }

//////// 算 f(a,b) ////////
int f(int a, int b) { return 1ll * c(a, b) * f3[b] % mod * f2[a - b] % mod; }

int main()
{
    cin >> n >> m;
    f2[0] = f3[0] = q[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        // 算 i!,2 的 i 次方,3 的 i 次方,对 mod 取模
        q[i] = 1ll * q[i - 1] * i % mod;
        f2[i] = 1ll * f2[i - 1] * 2 % mod;
        f3[i] = 1ll * f3[i - 1] * 3 % mod;
    }

    // 乘法逆元
    p[n] = qpow(q[n], mod - 2);
    for (int i = n - 1; i >= 0; i--)
        p[i] = 1ll * p[i + 1] * (i + 1) % mod;

    //////// 算 G(i) ////////
    int l = 0, r = 1;
    G[n] = 1;
    for (int i = n - 1; i >= 0; i--, r++)
    {

        // 算 5 * G(i + 1) + 3 * f(...) + 5 * f(...)
        G[i] = (5ll * G[i + 1] % mod + 3ll * f(n - i - 1, l - 1) % mod + 2ll * f(n - i - 1, r) % mod) % mod;
        int ql = max((n - i - m + 1) / 2, 0), qr = min((n - i + m) / 2, n - i);
        // 此时 l = L(i + 1), r = R(i + 1) + 1
        // 此时 ql = L(i), qr = R(i)

        // 算 delta
        while (l < ql)
            G[i] = (1ll * G[i] - f(n - i, l) + mod) % mod, l++;
        while (l > ql)
            l--, G[i] = (1ll * G[i] + f(n - i, l)) % mod;
        while (r > qr)
            G[i] = (1ll * G[i] - f(n - i, r) + mod) % mod, r--;
        while (r < qr)
            r++, G[i] = (1ll * G[i] + f(n - i, r)) % mod;
        // 此时 l = L(i), r = R(i)
        // 此时 i--, r++
    }

    //////// 算答案 ////////
    int ans = 0;
    for (int i = n; i >= 0; i--)
        ans = (ans + 1ll * G[i] * c(n, i) % mod) % mod;
    cout << ans << endl;
    return 0;
}
粤 ICP 备 2020080455 号