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("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            scanf("%lld", &triangle[i][j]), ans[i][j] = triangle[i][j];
        }
    }
    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("%lld\n", ans[1][1]);
    for (int i = 1, j = 1; i <= n; i++) {
        printf("%lld ", triangle[i][j]);
        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("%d %d", &m, &q);
    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("%d", &k);
        printf("%llu\n", rabbits[k]);
    }
    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("%d %d", &t, &online);
    while (t--) {
        cnt = 0;
        scanf("%d %d", &num, &jz);

        if (online) num = num ^ lastans;
        if (num == 0) putchar('0');
        while (num) {
            buf[cnt++] = base[num % jz], num /= jz;
        }
        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 年给你们这样的萌新使用。
基本上没有考察算法和数据结构,仅仅考察了一些计算机科学的基础。希望大家能在这套题中有所收获。

发表评论

邮箱地址不会被公开。 必填项已用*标注