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 取模也只是这个数的个位数字而已。

#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 函数来找这个位置的下标。但对于入门赛来说，这不值得。

#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 函数等价于：

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。

#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 分钟就把他往第三个数组里推，注意也要累加下标。最后先输出第二个数组再输出第三个数组即可。

#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 的箭头的直角三角形。可以看见，