LGR-213 洛谷入门赛 #31 题解（To be updated）

A 数字谜

前置芝士：表达式，位值原理，顺序结构，加减运算，（分支结构）

明显，个位以后的数都是没有必要的，因为我们只需要知道个位数字是几就可以得出答案。

知道

a

的个位数只需要将

a

对

10

取模即可，将这个数设为

p

。

我们并不知道

b

和

p

的大小关系。可以分类讨论：

0 & b = p \\ b - p & b > p \\ b + 10 - p & b < p \end{cases}$$ 其中 $ans$ 表示本题答案。这就是一个减法退位的原则。实际上，如果你了解取模运算，这个过程就可以直接写为 `(b - p + 10) % 10`。为什么呢？$b \geq p$ 时，其实答案就是 $b - p$，为了 $b < p$ 的情况，我们还需要加上 $10$ 以免 $b < p$，最后对 $10$ 取模也只是这个数的个位数字而已。 ```cpp #include <iostream> using namespace std; int main() { int a, b; cin >> a >> b; int p = a % 10; int ans = (b - p + 10) % 10; cout << ans << endl; return 0; } ``` ### B 会场座位 前置芝士：数组，遍历，等差数列，循环结构，间隔问题 可以明显看出来以 $1$ 和 $0$ 为分界线，左边的是一个首项为 $99$，公差为 $-2$，末项为 $1$ 的递减等差数列，而右边的是一个首项为 $0$，公差为 $2$，末项为 $98$ 的递增等差数列。 把座位号存储在数组 $a$ 中即可。当然，不能傻傻地打表，因为有规律，用 for 循环。 可我们都不知道这两个数列的项数，很简单，等差数列项数公式就是首项减末项的差除以公差再加一的和。简而言之，就是 $\frac{a - b}{x} + 1$，其中 $a,b,x$ 分别代表首项、末项和公差。 算出来两个等差数列的项数都是 $50$。 用两个 for 循环存储即可。当然，也有用一个 for 循环就可以存储的方法，将在代码中给出。 然后找到两个座位号的下表 $pos_a,pos_b$，相减即可。 错！两个座位号的位置可能是 $pos_a < pos_b$ 或 $pos_a > pos_b$，要用绝对值。还有，因为我们要知道的是两个座位的间隔而不是距离，所以我们还要减 $1$。 实际上，可以用 STL 中的 find 函数来找这个位置的下标。~~但对于入门赛来说，这不值得。~~ ```cpp #include <iostream> #include <vector> #include <algorithm> using namespace std; vector<int> n(100); int main() { for (int i = 0; i < 50; ++i) { n[i] = 99 - 2 * i; n[50 + i] = 2 * i; } int a, b; cin >> a >> b; int pos_a = find(n.begin(), n.end(), a) - n.begin(); // 这里的 find 函数涉及到了数组的迭代器的偏移量，将在后面的二分也会学习到同样的做法。 int pos_b = find(n.begin(), n.end(), b) - n.begin(); int gap = abs(pos_a - pos_b) - 1; cout << gap << endl; return 0; } ``` 其中 abs 函数是求绝对值，在 algorithm 头文件可以找到。 find 函数等价于： ```cpp for (int i = 1; i <= 100; i++) { if (a == n[i]) pos_a = i; if (b == n[i]) pos_b = i; } ``` ### C Pollard-Rho 前置芝士：表达式，循环结构 只需要在每一次开锁后改密码即可。 但是！但是！但是！ 第一次开门的密码是原始密码，开门以后才改密码，第二次开门的密码是修改一次的密码。 简而言之，第 $n$ 次开门的密码是修改 $(n-1)$ 次的密码（$n > 0$，$n-1=0$ 时表示原始密码）。 for 循环，注意循环结束的条件是 $i \le k-1$，也就是 $i < k$。 ```cpp #include <iostream> using namespace std; int main() { int x1, C, k; cin >> x1 >> C >> k; int x = x1; for (int i = 1; i < k; ++i) x = (x * x + C) % 10000; cout << x << endl; return 0; } ``` ### D 检票 前置芝士：分支结构，数组 ~~这 $1000$ 分拿至少 $900$ 不就是有手……~~ 开一个数组存储原来的队列，遍历寻找小于等于 $15$ 分钟的人，注意不能排序，从下标 $0$ 到 $n-1$，找到一个小于等于 $15$ 分钟的人就把他往第二个数组里推，注意要累加下标；大于 $15$ 分钟就把他往第三个数组里推，注意也要累加下标。最后先输出第二个数组再输出第三个数组即可。 ```cpp #include <iostream> #include <vector> using namespace std; vector<int> t; vector<int> u, nu; int main() { int n; cin >> n; for (int i = 0; i < n; ++i) cin >> t[i]; for (int i = 0; i < n; ++i) { if (t[i] <= 15) u.push_back(t[i]); else nu.push_back(t[i]); } for (int i = 0; i < u.size(); ++i) cout << u[i] << " "; for (int i = 0; i < nu.size(); ++i) cout << nu[i] << " "; return 0; } ``` ### E 右箭头 前置芝士：数学归纳，循环结构，轴对称，数组 倒数第二个 A 的。 可能我的做法并不是最优解，但可以参考。 注意到 $n,k$ 均为奇数，所以我们可以把右箭头分成以下三个部分：（以样例 $1$ 为例） ``` ......#... ......##.. #########. Part 1 ########## Part 2 #########. ......##.. ......#... Part 3 ``` 当然，样例 $2$ 和 $3$ 这些特殊情况也可以这么分。 Part 2 就是长为 $m$ 的井号长条，Part 3 就是 Part 1 的对称版，所以我们只需要知道 Part 1 怎么搞即可。 首先，Part 1 可以继续细分为： ``` ......#... ......##.. Part 1.1 #########. Part 1.2 ``` 而 Part 1.1 也可以继续细分为： ``` ...... #... ...... ##.. Part 1.1.1 Part 1.1.2 ``` Part 1.1.1 只需要把整个 Part 1 数组全部设为 `.` 即可。 Part 1.1.2 明显就是一个直角三角形。但是我们不知道的东西太多了。 首先，Part 1.1.2 在 Part 1 数组的位置在哪里？ 这就和箭头的直角三角形的斜边的高有关系了。 样例 $3$ 就是样例 $1$ 的箭头的直角三角形。可以看见，

LGR-213 洛谷入门赛 #31 题解（To be updated）

文章操作

A 数字谜

相关推荐

评论

LGR-213 洛谷入门赛 #31 题解（To be updated）