25暑假day1测试题解
T1¶
考查取余知识点。
首先要了解几个概念。
- 向下取整：$\lfloor x \rfloor$，返回 $\leq x$ 的最大整数。
- 例如：$\lfloor 1.5 \rfloor = 1$，$\lfloor -1.5 \rfloor = -2$
- 向上取整：$\lceil x \rceil$，返回 $\geq x$ 的最小整数。
- 例如：$\lceil 1.5 \rceil = 2$，$\lceil -1.5 \rceil = -1$
- 向 $0$ 取整：直接抹去小数部分。
而 C++ 中的 / 在整型之间计算时是向 $0$ 取整。
这就造就了 C++ 中 % 运算符和数学上的取余会有区别。
数学上取余叫做模运算，符号表示为 mod，在大多数编程语言中均用 % 表示。
题目一般讲的模运算或取余某个数字都是按照数学上的模运算定义的。定义 $a \bmod b$ 的结果为
换算成 C++ 的代码为：a % b = a - b * (a / b)。
而 C++ 中 / 是向 $0$ 取整，数学上是向下取整，因此在负数计算时可能会有区别。
因此 C++ 中当计算 a % b 时，若结果为负数，则需要 修正
修正办法
当结果为负数，再加一次余数 $b$ 即可，注意确保余数 $b$ 为正整数。（当然大多数题目基本都是对正整数取余）
- 具体可以参考 模运算讲解。
int x;
cin >> x;
int ans = x % 2023;
if (ans < 0)
ans += 2023;
cout << ans;
T2¶
知识点：数学题
当 $a$ 是 $b$ 的倍数，且 $b$ 也是 $c$ 的倍数时。就可以铺满整个矩形。
一共需要 $\dfrac{a}{c}\times \dfrac{b}{c}$ 个地毯。
注意数据范围中：$a,b,c$ 的范围都是 $\leq 10^{18}$ 的，如果你这样写就会出错。
long long a, b, c;
cin >> a >> b >> c;
if (a % c == 0 && b % c == 0)
{
cout << a * b / c / c;
}
else
{
cout << -1;
}
原因在于先计算 $a\times b$ 最坏情况为 $10^{18}\times 10^{18}=10^{36}$ 从而导致结果超出 long long 上限后出错。
有的同学在条件判断中写：
if ((a * b) % (c * c) == 0)错误原因同上。
而题目有一句话是：保证答案不超过 $10^{18}$ 因此这个题必须 (a / c) * (b / c)。
T3¶
知识点：简单循环加条件判断语句。
这个题不需要数组，一边输入一边判断条件是否成立即可。
定义 $sum$ 求满足条件的个数，初始化 $sum=0$。
- 循环 $n$ 次。
- 每次输入两个整数 $x,y$。
- 当满足 $k\times x+b=y$ 时，令 $sum\leftarrow sum+1$。
注意数据范围：$k\times x+b$ 会超出 int，因此建议将相关变量设定为 long long。
T4¶
知识点：数位拆分。
判断是否存在 $62$ 可以数位拆分一边拆一边判断，具体实现如下：
定义 long long x 代表输入的数字。
- 对 $x$ 执行数位拆分。
while (x != 0) - 当
x % 100 == 62说明存在 $62$ 此时可以直接输出YES，并提前终止程序。 - 若整个数位拆分结束后都不存在 $62$ 后才可以输出
NO。
x % 10获取个位，x % 100获取后两位，x % 1000获取后三位。
x / 10删去个位，x / 100删去后两位，x / 1000删去后三位。以此类推。
bool ok = 0; // 假设不存在 62
while (x)
{
if (x % 100 == 62)
{
ok = 1;
}
x /= 10;
}
// 根据 ok 的值决定输出内容即可
T5¶
知识点：循环嵌套。
小技巧：计算次方可以使用 pow 这个函数。
- 参数列表：
pow(a, b)传入两个参数，用于计算 $a^b$。 - 返回值类型：
double类型。因此结果的有效数字超过 $6$ 位以后会转变为科学计数法。- 因此需要使用类型转换后输出。
- 例如
cout << pow(2, 30)无法显示 $2^{30}$ 真实面目。需要改为int ans = pow(2, 30)以后输出ans。当然前提是计算结果在int范围内。
在本题最多计算 $9^9$ 不会超过 int 上限。
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= i; j++)
{
int ans = pow(i, j);
cout << i << " ^ " << j << " = " << ans << " ";
}
cout << "\n";
}
T6¶
知识点：二维数组。
准备工作
定义 m, n, sx, sy 这四个 int 变量存储第一行输入。
由于接下来要输入 $n$ 行，每行 $2m$ 个数字。其中两两一组，分别对应位置 $(i,j)$ 要去的下一个位置的行和列。
因此可以这样处理这个输入。
初始化 int x[1005][1005], y[1005][1005] 存储所有位置的指引。
// 注意先输入 m 后输入 n
cin >> m >> n >> sx >> sy;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> x[i][j]; // 存储 i, j 要去的下一个位置的行
cin >> y[i][j]; // 存储 i, j 要去的下一个位置的列
}
}
具体实现
接下来是一个循环的过程，循环条件自然为 while (sx != 0 && sy != 0)
每次要做：
- 首先直接输出当前位置 $(s_x,s_y)$。
- 然后找到下一个位置。
- 令 $s_x\leftarrow x[sx][sy]$。
- 令 $s_y\leftarrow y[sx][sy]$。
- 注意具体实现时，先把过去的位置缓存到其他变量后再更新。
- 否则当 $s_x$ 更新后，用更新后的 $s_x$ 更新 $s_y$ 就会出错。