塔尖周赛 - round7

周赛说明

• 难度：基础语法为主。涉及简单算法和数学思维。
• 题量：$5$ 道题目，限时 $120$ 分钟完成。
• 时间：周日晚 7:00 - 9:00
• 赛制：乐多赛制，重复提交会扣除一定的分数。提交后会有反馈，但没有大样例。

赛后讲解

• 讲解时间：2025/2/9 21:00
• 讲解方式：腾讯会议线上讲解
• 讲解链接：https://meeting.tencent.com/dm/zDKA6v9Ciu6t

T1

分析

难度：简单数学题

• 子任务 $1$（$30$ 分）：由于 $x\leq M$，所以直接输出 $h$ 和 $m-x$ 就好。
• 子任务 $2$（$30$ 分）：由于是刚好减去一个小时，所以直接输出 $h-1$ 和 $m$ 就好。
• 子任务 $3$（$40$ 分）：有多种做法。
  • 可以将输入的时间先统一转为分钟，即 $h\times 60+m$，然后减去 $x$ 以后将得到的分钟转回小时和分钟即可。例如：int s = h * 60 + m - x。
  • 小时就是 s / 60，分钟就是 s % 60。

满分参考代码

int h, m;
cin >> h >> m;
int s = h * 60 + m - x;
cout << s / 60 << " " << s % 60;

T2

分析

难度：简单的条件判断与求和

• 子任务 $1$（$30$ 分）：因为只有一道题，所以直接输出 $a_1,b_1$ 中的较大值就好。
• 子任务 $2$（$30$ 分）：因为保证了 $a_i\leq b_i$ 所以直接输出所有 $b_i$ 之和就好，简单的循环输入与求和。
• 子任务 $3$（$40$ 分）：在子任务 $2$ 的基础上，加上判断 $a_i,b_i$ 哪个高算哪个就好。注意 $n$ 最多为 $100$，而每个数字最多为 $10^9$，而 int 可以存储的最大值大约为 $2\times 10^9$，最后的答案可以达到 $100\times 10^9$ 是超过了 int 的，需要使用 long long。

满分参考代码

int n;
cin >> n;
long long sum = 0;
for (int i = 1; i <= n; i++)
{
    int a, b;
    cin >> a >> b;
    if (a > b)
    {
        sum += a;
    }
    else
    {
        sum += b;
    }
}
cout << sum;

T3

分析

难度：简单的字符串枚举，主要给大家提醒了一下转义符的使用。

• 子任务 $1$（$30$ 分）：因为保证了不包含 \ 所以只有一个单词，只需要输出 $1$ 即可。
• 子任务 $2$（$30$ 分）：因为保证了编码长度为 $5$，所以答案就是 (s.size() + 1) / 6。
• 子任务 $3$（$40$ 分）：单词数就是 \ 数量加一。记住反斜杠本身也是个特殊字符，需要用转义模式 \\ 表示即可。

满分参考代码

string s;
int ans = 0;
cin >> s;
for (int i = 0; i < s.size(); i++)
    if (s[i] == '\\')
        ans++;
cout << ans + 1 << "\n";

T4

分析

难度：数组综合应用。

• 子任务 $1$（$30$ 分）：因为 $x=1$，所以在完成了基础的暴力枚举标记所有有数的位置后，就是一个弱化版的 最长平台 问题，有几段树答案就是几。统计多少个位置有树且前一个位置没树即可（第一个位置特殊判断）。
• 子任务 $2$（$30$ 分）：每次不再是区间修改而是单点修改了。给没学过循环嵌套的同学送点分，但其实意义不大。
• 子任务 $3$（$40$ 分）：如果是数据范围更大，就需要使用差分的方式处理。但是数据范围这么小，直接暴力标记每个位置有没有树即可。标记完后，问题就变成了判断有几段树的数量达到了 $x$。

满分参考代码

#include <bits/stdc++.h>
using namespace std;
int L, M, x;
bool a[5005];
int main()
{
    cin >> L >> M >> x;
    // 一开始认为所有位置都有树
    for (int i = 0; i <= L; i++)
        a[i] = true;
    // 把建地铁的位置的树都拔掉
    for (int i = 1; i <= M; i++)
    {
        int l, r;
        cin >> l >> r;
        for (int j = l; j <= r; j++)
            a[j] = false;
    }
    // 从前往后，找整段的树
    int now = 0; // 当前段的树的棵数
    int ans = 0; // 记录有几段树的长度达到了 x
    for (int i = 0; i <= L; i++)
    {
        if (a[i] == true)
            now++;
        else
        {
            if (now >= x)
                ans++;
            now = 0;
        }
    }
    // 有可能出现一段树，需要特殊处理
    if (now >= x)
        ans++;
    cout << ans << "\n";
    return 0;
}

T5

难度：质数筛法和质因子以及二分。

本题实际是求出有多少个数字有 $4$ 个因子，因为 $1$ 和它本身一定是其中的两个因子。

• 子任务 $1,2$（$30$ 分）：暴力枚举 $1\sim n$ 之间的所有数字，对于每个数字 $i$ 求出它的因子个数，若因子个数等于 $4$。则是符合条件的数字，答案个数加 $1$ 即可。时间复杂度为 $O(n^2)$。
• 子任务 $3$（$30$ 分）：由于 $n$ 一定等于 $3333333$，可以使用暴力代码跑出这个结果，利用条件判断语句直接输出。暴力代码只是运行结果需要等的久一点，并不是说它是错误的。

子任务 $4$（$40$ 分）

考虑从质因子的角度来思考一个数字 $i$ 有 $4$ 个因子是什么情况。

设 $n$ 的质因子分解形式如下：

$$n=p_1^{a_1}\times p_2^{a_2}\times \cdots\times p_k^{a_k} $$

其中 $p_i$ 是质数，$a_i$ 是正整数。

根据约数个数定理可知，一个数字 $n$ 的因子个数就是

$$d=\prod\limits_{i=1}^k (a_i+1)$$

其中 $d$ 代表 $n$ 的约数个数。即现在要研究 $d=4$ 的情况。只有以下两种。

• 该数字分解后只有一个质因子且指数为 $3$，即这个数字可以被分解为 $p_i^3$。例如 $8$ 会有 $4$ 个因子。

• 该数字分解后只有两个质因子且指数均为 $1$，即这个数字可以被分解为 $p_i^1\times p_j^1$。例如 $6$ 会有 $4$ 个因子。

• 对于第一种情况，相当于我们需要知道在 $1\sim n$ 之间有多少个质数满足它的 $3$ 次幂依然小于等于 $n$。

  • 由于 $n\leq 10^7$，且 $216^3>10^7$。因此符合这样条件的质数都是小于 $216$ 的。我们罗列小于等于 $216$ 的所有质数进行检验即可。

• 对于第二种情况，相当于我们需要知道在 $1\sim n$ 之间有多少组质数 $(p_i,p_j)$ 且 $p_i<p_j$，满足它们的乘积依然小于等于 $n$。

  • 枚举两个会超时，不妨考虑只枚举 $p_i$，则此时符合条件的 $p_j$ 必然是连续的一段质数。具备单调性，可以二分找到最后一个小于等于 $\frac{n}{p_i}$ 的位置记作为 $j$。那么符合要求的个数就是 $j-i$ 个，

在整个过程中不可能枚举 $1\sim 10^7$ 以内的所有质数，可以提前使用筛法筛出 $1\sim n$ 的所有质数，然后遍历质数数组进行求解。时间复杂度的上限为筛法。

#include <bits/stdc++.h>
using namespace std;
int n, sum, cnt, prime[10000005];
bool vis[10000005];
void init(int n)
{
    vis[0] = vis[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!vis[i]) // i 是质数
        {
            prime[++cnt] = i;
            // 从 i 的 2 倍开始，每次加 i，下一次就是 i * 3，i * 4 ……
            for (int j = i * 2; j <= n; j += i)
                vis[j] = 1; // i 的倍数都不是质数
        }
    }
}
int main()
{
    cin >> n;
    init(n);
    for (int i = 1; i <= cnt; i++)
    {
        int j = upper_bound(prime + 1, prime + cnt + 1, n / prime[i]) - prime;
        j--; // 减去 1 找到最后一个小于或等于的
        if (j >= i) sum += (j - i);
    }
    for (int i = 1; i <= cnt; i++)
    {
        if (prime[i] * prime[i] * prime[i] <= n)
            sum++;
        else break; // 后续的只会越来越大
    }
    cout << sum;
    return 0;
}