25暑假day4测试题解

T1¶

定义三个变量 $a,b,c$。注意到 $a,b,c<2^{31}$，即可以使用 int 存储。但是接下来我们需要计算三个数字的和，这个和会超过 int 能存储的范围，所以选择使用 long long 来定义 $a,b,c$。

使用逻辑运算符 && 完成对四个条件的判断即可。

T2¶

在读入表达式后，只需按照题目给定的条件运算即可。

char x, z;
long long y, w;
cin >> x >> y >> z >> w;

表达式的合法性
- x 与 z 均为小写字母，if (x >= 'a' && x <= 'z' && z >= 'a' && z <= 'z')
- 也可以使用 islower(x) 和 islower(z) 这两个函数判断。
- x 与 z 相同，即 if (x == z)
- y 与 w 均为整数，这一点由输入保证。
如果表达式合法：
- 输出 abs(y - w) + 1 即可。

T3¶

本题在实质上需要求解一个骰子塔露在空气中面数之和。

把骰子塔露在空气中分为两个部分考虑，最上面的一面，和所有骰子的侧面。

一个骰子，向上的面与侧面点数之和关系如下：

向上的面	侧面点数之和
$1$	$18$
$2$	$18$
$3$	$14$
$4$	$14$
$5$	$10$
$6$	$10$

计算完侧面点数之和，加上顶面的数字，就可以得到最终的答案。

T4¶

有三种方法完成本题：

使用循环

由于每名小朋友都说实话，每个小团体的首领 $i$，将指认自己，即首领满足 $S_i=i$。只需要循环判断有多少个数满足前面的条件即可。

使用数组

使用一个值域数组 bool vis[1000005] 给每个人的首领打标记，最后统计数组中有多少个元素被标记过即可。

使用 sort 函数再结合排序作业题中去重一题的代码即可完成。

T5¶

这是一个区间枚举型问题。

由于区间长度固定为 $k$，因此枚举左端点 $i$ 即可。

左端点 $i$：$[1,n-k+1]$。
右端点 $j=i+k-1$。

接下来可以使用等差数列求和公式直接计算出 $[i,j]$ 的数字之和。

求完以后判断和是不是完全平方数即可。

基本都是今天上课的内容。

T6¶

注意到 $k\leq 3$。即最多只会有三个避难所。

因此本题可以分类讨论完成。

if (k == 1)
{
    // 1 个避难所代码怎么写
}
else if (k == 2)
{
    // 2 个避难所代码怎么写
}
else
{
    // 3 个避难所代码怎么写
}

接下来我们一一分析即可：

一个避难所

首先枚举避难所的编号：for (int i = 1; i <= n; i++)。
- 枚举其余所有村庄 $j$，for (int j = 1; j <= n; j++)。
- 计算 $i,j$ 间距离的最大值记作 $mx$。
- 对所有的 $mx$ 求一个最小的。即最小的最大距离

其中 $dis(i,j)$ 为自定义函数用于计算 $i,j$ 的曼哈顿距离。

int dis(int i, int j)
{
    return abs(x[i] - x[j]) + abs(y[i] - y[j]);
}
if (k == 1)
{
    int mn = 1e9;
    for (int i = 1; i <= n; i++)
    {
        int mx = 0;
        for (int j = 1; j <= n; j++) 
            mx = max(mx, dis(i, j));
        mn = min(mn, mx);
    }
    cout << mn << "\n";
}

两个避难所

思路同上，首先用两个循环枚举两个避难所。

然后枚举所有村庄，在最大的距离中找到最小值。

三个避难所

思路同上。