LYOI 2020 萌新赛 Day1 题解

之前压根没想到我 2018 年出的题在退役的两年后会梅开二度，题解写的比较仓促，望大家见谅。

这次的题目当初命制时就是为刚刚学习完 C++ 语言和基本的递推算法的萌新准备的，因此比较简单。听说你们很强，应该有不少人 AK 吧哈哈哈哈哈哈（

部分分给的很足，我觉得应该人均 100 分以上不成问题。

至于 133 是谁，这个你们可以猜一猜。提示一下，和我认识 18 年（

话不多说，开始操作。

133’s Triangle

传送门: 133’s Triangle – 题目 – L🐟OI Online Judge

这道题相信很多刷题比较早的同学可能已经做过类似的了，其实确实就是板子题，妥妥的数塔 Plus。

10 分做法

输出大样例即可。

40 分做法

100 分做法不开 long long 即可（

100 分做法

可以发现，这是一个数塔，而你需要做的就是找到一条权重最大的路径，并且输出它。
为了简化问题，我们可以从下向上搜索，从而找到一条最大的路径。
我们将数塔读入到 triangle 数组内，同时设置一个 ans 数组，将它的每一项初始化为 triangle 数组的内容。
我们从第 $n – 1$ 层开始，由于数塔只能向下或向右走，因此我们比对下方还是右侧较大即可。并将是否右移记录于 move 数组中。
最后 ans[1][1] 即为答案。
输出路径时，只需每次加上 move 数组对应的内容即可知道每一层的下标。因为不需要右移的层 move 为 0，否则为 1，因此直接加上它的值即可。

#include <cstdio>
const int MAXN = 2500 + 1;
int n;
long long triangle[MAXN][MAXN], ans[MAXN][MAXN];
bool move[MAXN][MAXN];
int main(int argc, char const *argv[]) {
    freopen("triangle.in", "r", stdin);
    freopen("triangle.out", "w", stdout);
    scanf(
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            scanf(
        }
    }
    for (int i = n - 1; i > 0; i--) {
        for (int j = 1; j <= i; j++) {
            if (ans[i + 1][j] < ans[i + 1][j + 1])
                ans[i][j] += ans[i + 1][j + 1], move[i][j] = 1;
            else
                ans[i][j] += ans[i + 1][j], move[i][j] = 0;
        }
    }
    printf(
    for (int i = 1, j = 1; i <= n; i++) {
        printf(
        j += move[i][j];
    }
    return 0;
}

（其实 133 真的有货架，只不过不是三角形的

133’s Rabbits

传送门: 133’s Rabbits – 题目 – L🐟OI Online Judge

这道题算是一道假防 AK 题，细心的同学可能会发现这是一道斐波那契数列升级版。

10 分做法

直接计算裸的斐波那契数列即可。

30 分做法

开 int 即可。

100 分做法

在这里，我们加入了兔子去世的机制。可以发现，如果你只先计算完兔子数，再用 12 个月之前的数量相减，一定会出错。因为兔子的灵魂不能生出来小兔子（

我们可以发现，对于第 1 个月出生的兔子，在第 13 个月死亡；第 3 个月出生的兔子，在第 15 个月死亡……因此，我们可以记录每个月新增了多少兔子，然后在 12 个月后的新增兔子数目中直接减去它们。

为了降低难度，这里直接给出了询问月数的上限，因此进行预处理即可。

这道题中有一个对 $2^{64}$ 取模的要求。大家可能发现无论如何似乎都不能实现对 $2^{64}$ 取模。但是，如果大家对计算机中数的表示有扎实的基础的话，应当可以想到这个解决方法。

我们知道，long long 的长度是 64 位，由于有一位符号位的存在，因此可以表示的是 $[-2^{63}, 2^{63}-1]$。但是在 unsigned long long 中，由于它是无符号的，也就没有符号位，它的表示范围是 $[0, 2^{64}-1]$。我们知道，我们使用 int 时，如果发生溢出，往往是一个负数。这是因为计算机中使用补码存储数字，负数的最高位符号位为 1，本来为 0 的符号位在超出最大值后会被进位为 1。但是对于无符号数，它是不存在符号位的，当最高位进位时，进位的那一位将被丢弃。

我们知道 $2^{64}-1$ 的二进制表示为 $(1111 1111 1111 1111 1111 1111 1111 1111)_{B}$，这时候，如果我们给它加上一个 1，会发生什么呢？

大家可以尝试一下，你会惊奇地发现答案是 0，这是因为按位进后，最高位的进位被丢弃，于是 64 个数位均为 0。

等等？这是不是好像就是取模呢？

如果我们算出来的数字应当是 $K = 2^{64} + 3$，我们来看看发生了什么。
这个数字还可以写成 $K = (2^{64} – 1) + 1 + 3$，当我们在 unsigned long long 下把 $(2^{64} – 1) + 1$ 时，答案显然是 0。那么我们再加上 3，答案不就是 3 了吗？

因此，利用计算机中无符号数表示的性质，我们就可以直接自然地通过溢出实现 $2^{64}$ 的取模了。

AC 代码:

#include <cstdio>
const int MAXM = 2 * 1e7 + 10;
int m, q;
unsigned long long rabbits[MAXM], birth[MAXM];
int main(int argc, char const *argv[]) {
    freopen("rabbits.in", "r", stdin);
    freopen("rabbits.out", "w", stdout);
    scanf(
    rabbits[1] = 1, rabbits[2] = 1;
    birth[1] = 1, birth[2] = 0;
    for (int i = 3; i <= m; i++) {
        birth[i] = rabbits[i - 2];
        if (i > 12) birth[i] -= birth[i - 12];
        rabbits[i] = rabbits[i - 1] + birth[i];
    }
    while (q--) {
        static int k;
        scanf(
        printf(
    }
    return 0;
}

（其实 133 真的养过兔子

133’s Number

传送门: 133’s Number – 题目 – L🐟OI Online Judge

这其实算是一个福利题，就是进制转换。

10 分做法

因为是待转换的数字是 0，因此无论如何最终答案均为 0。输出 0 即可。

另外 20 分做法

因为输入进制为 10，输出进制也为 10。因此原样输入原样输出即可。

50 分做法

直接进行进制转换。
我们知道，日常生活中使用 10 进制，即“逢十进一”。人们基于十进制，创造了 0-9 的阿拉伯数字。
随着计算机的发展，人们发现十六进制在计算机领域中有很好的用法，因为它可以方便地和二进制换算。但是十六进制的话，阿拉伯数字就不够了。聪明的人们使用字母 ABCDEF 分别代表 10-15 的数字。于是，利用这种方法，我们可以轻而易举地表示 2-36 进制的数字了。

那么我们如何将十进制数转换为任意进制数呢？

大家应该都做过“水仙花”数这一类题目，这类题目的特点就是你需要提取出每一位数字。那么这是如何做到的呢？
我们在处理这些题目时，通常是通过对 10 取模提取出每一位数字。大家有没有想过这是为什么呢？
因为我们十进制的每一个数字，都可以表示成关于 10 的幂次的一个多项式。例如 $133 = 1 \times 10^2 + 3 \times 10^1 + 3 \times 10^0$。
基于此，我们可以推广出任意 $k$ 进制数 N 的表示:

$$N = a_{n} \times k^{n} + a_{n-1} \times k^{n-1} + \cdots + a_1 \times k^{1} + a_0 \times k^{0} $$

所以，如果我们需要得出一个任意 k 进制数的每一位，只需要连续除 k 取余数即可。

100 分做法

在 OI 生活中，“强制在线”的概念即是避免选手通过输入上下文取巧而提出的。其基本要求是选手需要完成上一组输入才能得到真实的下一组输入。

本题是否强制在线没有太大的影响，设置强制在线的目的是让大家建立起强制在线的概念。

对于这道题，需要强制在线的测试点，你只需要把上一个输入的答案，按位提取出来，将这一位的数字在十进制下代表的数相加，再与本组的输入异或即可。

AC 代码:

#include <cstdio>
const char* base = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
bool online = 0;
int t, num, jz, lastans, cnt;
char buf[100000 + 2];
int main(int argc, char const *argv[]) {
    freopen("number.in", "r", stdin);
    freopen("number.out", "w", stdout);
    scanf(
    while (t--) {
        cnt = 0;
        scanf(

        if (online) num = num ^ lastans;
        if (num == 0) putchar('0');
        while (num) {
            buf[cnt++] = base[num
        }
        lastans = 0;
        while (cnt--) {
            putchar(buf[cnt]);
            lastans += (buf[cnt] - '0' < 10 ? buf[cnt] - '0' : buf[cnt] - 'A' + 10);
        } putchar('\n');
    }
    return 0;
}

（其实 133 真的没有给我发过数字

---

这套比赛题是 2018 年我还没有退役的时候出的，但是因为各种原因被鸽了，于是拿到 2020 年给你们这样的萌新使用。
基本上没有考察算法和数据结构，仅仅考察了一些计算机科学的基础。希望大家能在这套题中有所收获。