25暑假集训摸底测试

T1¶

知识点：if - else if - else 语句。

注意输出格式，不要加 Win。

T2¶

知识点：数位拆分

通过除以 $10$ 删去末尾若干位，通过取余操作完成对个位的获取。

个位：n % 10
十位：(n / 10) % 10
百位：(n / 100) % 10

int a = n % 10;
int b = (n / 10) % 10;
int c = (n / 100) % 10;
// 接下来分别计算题目的要求即可

T3¶

知识点：条件判断语句和基本思维。

从 $A\to B$ 有两种路线：

$A\to B$ 用时 $x$ 分钟。
$A\to C\to B$ 用时 $y+z$ 分钟。

因此 $A\to B$ 的最短用时为

\[ \min(x,y+z) \]

同理可得 $B\to C$ 和 $A\to C$ 的最短用时。

具体实现可以借助 min 函数完成，或书写 if - else 语句。

T4¶

知识点：简单循环加条件判断加一维数组。

准备工作

定义变量 sum 存储人物的精神力，初始化 long long sum = x0。

根据数据范围显然可以看出需要使用 long long 类型。

定义变量 num 存储挂件的数量，初始化 int num = 0 即可。

定义数组 int a[100005] 存储第 $i$ 个装备所需的精神力最小值。
定义数组 int b[100005] 存储第 $i$ 个装备所需精神力最大值。

具体实现

从前往后遍历 $a$ 数组。for (int i = 1; i <= n; i++)
当满足 sum >= a[i] 时，说明满足第 $i$ 件装备的穿戴要求，此时：
- sum += b[i]，更新精神力。
- num++，更新挂件数量。

T5¶

知识点：数组进阶技巧之标记数组的使用。

准备工作

定义数组 bool vis[1000005] 用来对每个避雷针进行打标记。

初始化 vis[i] 均为 $0$ 表示第 $i$ 个避雷针未被劈中。

定义变量 int sum = 0 统计答案。

具体实现

读入 $m$ 个雷的位置，分别记作 $x$。（雷序列可以不用数组）
- 若 $x-2\geq 1$，则标记 vis[x - 2] = 1。
- 若 $x-1\geq 1$，则标记 vis[x - 1] = 1。
- 标记 vis[x] = 1。
- 若 $x+1\leq n$，则标记 vis[x + 1] = 1。
- 若 $x+2\leq n$，则标记 vis[x + 2] = 1。
最后遍历标记数组，统计出 vis[1] $\sim$ vis[n] 中值 $1$ 的个数，即为答案。

T6¶

知识点：数组的使用。

本题的关键在于实现出 shift 操作。

shift 操作可以理解为：

$p[1]\to p[2]$
$p[2]\to p[3]$
$p[3]\to p[4]$
$\ldots$
$p[n-1]\to p[n]$
$p[n]\to p[1]$

在具体实现中，核心代码是 p[i + 1] = p[i]，其中 $i\in [1,n-1]$。

注意这里实现时，必须倒序更新。

int temp = p[n];
for (int i = n - 1; i >= 1; i--)
    p[i + 1] = p[i];
p[1] = temp;

只有倒序更新才可以正确保证每个位置不被其他位置覆盖。特别的，第一个位置需要先保存原本 $p[n]$ 的值以后，最后更新。

接下来，可以使用一个 while (true) 的无限循环。

在循环内进行 shift 操作。
操作后完以后输出整个排列 $p$。
当满足 $p_n=n$ 时，结束循环。

完整代码如下：

while (true)
{
    int temp = p[n];
    for (int i = n - 1; i >= 1; i--)
        p[i + 1] = p[i];
    p[1] = temp;
    for (int i = 1; i <= n; i++)
        cout << p[i] << " ";
    cout << "\n";
    if (p[n] == n)
        break;
}

T7¶

知识点：字符串

注意到输入的数字长度非常大，显然需要使用字符串存储输入的数字。

由于数字的长度最多为 $10^5$，因此无法计算出所有数位的总乘积。（long long 只能存储最多 $19$ 位数字，它爷爷来了都存不下）

题目只需要判断乘积和 $k$ 比较，注意到 $k\leq 10^9$，因此一边乘一边判断即可。

细节：若字符串 s 存在字符 $0$，虽然可能前面的字符先乘起来会超过 $k$，但最终乘以 $0$ 都会得到 $0$。

int n, k;
cin >> n >> k;
while (n--)
{
    string s;
    cin >> s;
    long long sum = 1;
    bool ok = 0;
    for (char c : s)
    {
        sum = sum * (c - '0');
        if (sum > k)
        {
            ok = 1;
            break;
        }
    }
    if (s.find('0') != s.npos) // 如果有字符 0 必然不超过 k
        ok = 0;
    if (!ok) cout << "kawaii\n";
    else cout << "dame\n";
}

T8¶

知识点：进阶循环嵌套，数组的使用。

准备工作

变量 n, k, t 均为 int 类型。

数组：int x[1005], y[1005] 存储密码机坐标。

数组：bool vis[1005] 判断第 $i$ 个密码机是否属于出生密码机。

距离函数：

由于题目仅仅用来判断距离的远近，因此无需开根号算具体值。就用距离的平方比较，避免误差。根据题目的数据范围，距离的平方不可能超过 int。

int dis(int x1, int y1, int x2, int y2)
{
    return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}

解题思路

首先读入所有的密码机。
读入求生者选择的坐标 xi, yi。
- 遍历所有密码机坐标，判断是否存在一个密码机 $j$ 使得 x[j] == xi && y[j] == yi。
- 若存在，则说明第 $j$ 个密码机属于出生密码机。
- 此时标记 vis[j] = true。
读入所有出生点的坐标 xi, yi。
- 维护一个距离最大值 mx 初始化为 $0$。
- 维护一个距离最大的密码机编号 pos 初始化为 $0$。
- 遍历所有密码机坐标：
  - 若 dis(xi, yi, x[j], y[j]) > mx，则更新 mx 和 pos。
- 求得最大距离和编号以后，若 vis[pos] 为 true，则说明该密码机属于出生密码机。且会被封禁，此时执行 ans++ 即可。

核心代码

int ans = 0;
while (t--)
{
    int xi, yi;
    cin >> xi >> yi;
    int mx = -1e9, pos = 0;
    for (int i = 1; i <= n; i++)
    {
        if (dis(xi, yi, x[i], y[i]) > mx)
        {
            mx = dis(xi, yi, x[i], y[i]);
            pos = i;
        }
    }
    if (vis[pos]) // 第 pos 个出生密码机被封禁
    {
        ans++;
    }
}
cout << ans;