题解 |预热赛

出题、验题人预估难度分级：

简单：，其中

中等：，其中

较难：，其中

接下来按照预估的难度顺序进行讲解

这道题直接用输出一行文字即可，代码如下：

#include <stdio.h>

int main () {
    printf("和我签订契约，成为ACMer吧");
    return 0;
}

(PS：喜欢我写的小故事么(●´∀｀●))

按照要求输出数字三角形，观察样例我们可以发现，

第一行输出一个数字，第二行输出两个数字……一直到第行输出个数字。

我们可以用两层循环来控制，当第一层循环进行到到的时候，第二层循环限制它循环次即可。

至于每次输出的数字，我们一开始让他输出，然后每次就可以了，代码如下：

#include <stdio.h>

int main() {
    int n;
    scanf("%d", &n);

    int now = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            printf("%-10d", now);
            now++;
        }
        printf("\n");
    }
    
    return 0;
}

这道题题目中说，只要任意两个坐标的值相等，就可以跃迁，没有任何其他限制。

那我们只需要判断一下起点和终点的值是否相等就可以了。

如果相等，直接从起点跳到终点就可以了；否则，无论如何也无法到达。

还有一点，就是我们需要注意且的情况，此时起点即是终点。代码如下：

#include <stdio.h>

int main () {
    int n, m, x, bg, ed;
    scanf("%d%d", &n, &m);

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            scanf("%d", &x);

            if (i == 1 && j == 1) {
                bg = x;
            } 
            if (i == n && j == m) {
                ed = x;
            }
        }
    }

    if (bg == ed) {
        printf("YES");
    } else {
        printf("NO");
    }
    
    return 0;
}

这道题目给了一个进制数，要求转化为进制数。

其实原理很简单，我们想一下，进制的意思，就是“逢进”；大家也肯定听说过二进制，只有和构成，是“逢进”。

那么进制的意思其实就是“逢进”。我们先定义变量，每次输入一个新的数字的时候，就让变量执行“”的操作就可以了，也就是ans = ans × k + x。

这个就是简单的进制转换的做法，但如果是进制以上的进制，就需要引入其他字符了，这个后续会进行学习。

注意这里，我们输入的数字是挨着的，所以语句里要限制输入数字的位数，写成“%1d”的形式。代码如下：

#include <stdio.h>

int main () {
    int n, k, x;
    scanf("%d%d", &n, &k);

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%1d", &x);
        ans = ans * k + x;
    }
    printf("%d", ans);

    return 0;
}   

这道题没啥思路，因为都写在题面上了，你只能按照这种方法去计算（

不过这个理念还是有点重要的，它涉及到了前缀最小值的知识，而如果你想接触算法竞赛，前缀的概念将是你不得不品的一环（确信）

每输入一个新的数字，我们就把他和当前的最小值进行比较，如果小于最小值，就更新最小值为刚才输入的值，然后答案加上当前的最小值，最后输出答案即可，代码如下：

#include <stdio.h>

int main () {
    int n, x;
    scanf("%d", &n);

    int ans = 0;
    int min = 1000000007;
    
    for (int i = 1; i <= n; i++) {
        scanf("%d", &x);
        if (x < min) {
            min = x;
        }
        ans += min;
    }

    printf("%d\n", ans);

    return 0;
}

算法竞赛中非常经典的**最近公共祖先（LCA）**问题，属于图论的范畴。

但这道题目用的是其最简单的模型，如题目中所述，每个数字的祖先，都是它除以2向下取整得到的数字； 那么，对于给定的两个整数和，我们可以对其进行一个模拟：如果，就让除以2；如果，就让除以2。

重复这个操作直到和相等，那么此时的或就是他们的最近公共祖先。代码如下：

#include <stdio.h>

int main () {
    int a, b;
    scanf("%d%d", &a, &b);

    while (a != b) {
        if (a > b) a /= 2;
        else b /= 2;
    }

    printf("%d", a);

    return 0;
}

在这道题中，小增同学每次可以跳级台阶，也可以跳级台阶，要我们计算方案数。那么我们可以对比较小的情况进行枚举：

，此时只能从第级台阶向上跳步，方案数为；

，此时可以从第级台阶向上跳步，或者是从第级台阶向上跳步，方案数为的方案数 加上 的方案数；

，此时可以从第级台阶向上跳步，或者是从第级台阶向上跳步，方案数为的方案数 加上 的方案数；

，此时可以从第级台阶向上跳步，或者是从第级台阶向上跳步，方案数为的方案数 加上 的方案数；

……

以此类推，我们可以得到一个递推公式：，正好是斐波那契数列的表达式！

因此，第级台阶的方案数就是斐波那契数列中第项的值；但是我们没学数组，所以需要使用三个变量来进行计算，方法如下：

#include <stdio.h>
const int mod = 998244353;

int main () {
    int n;
    scanf("%d", &n);

    if (n == 2) {
        printf("1");
        return 0;
    }

    long long a1 = 1, a2 = 1, a3;
    for (int i = 3; i <= n; i++) {
        a3 = (a1 + a2) % mod;
        a1 = a2;
        a2 = a3;
    }
    printf("%lld", a3);

    return 0;
}

两个人轮流玩游戏，每回合从自己方选取一个数，从另一方选取一个数，然后，如果有一张牌点数则遗弃，问最后谁能赢。

我们注意到，如果减完之后，就丢掉了，也就是说，对于和，如果，那么变成；如果，变成。

我们可以将其化为：，同理，即。

因此，我们的问题就转化为了，求和，并比较他们的大小，谁大谁赢，相等则平局。代码如下：

#include <stdio.h>

int main () {   
    int n, x;
    scanf("%d", &n);

    int sum1 = 0, sum2 = 0;

    for (int i = 1; i <= n; i++) {
        scanf("%d", &x);
        sum1 += x;
    }
    for (int i = 1; i <= n; i++) {
        scanf("%d", &x);
        sum2 += x;
    }

    if (sum1 > sum2) {
        printf("CCY");
    } else if (sum1 == sum2) {
        printf("DEADLOCK");
    } else {
        printf("SSZ");
    }
    
    return 0;
}

我们观察前几项的情况：

如果我们将其的幂次进行编码，可以表示成这样：

，其中，最右边是低位，最左边是高位。

比如第一项，最右边的代表次方有，而次和次方都没有，对应；

再看第六项，它表示次和次方都有，而次方没有，对应。

这些数的排列，正好是到的二进制表示。

所以哪些幂次要加，哪些幂次不加，取决于在二进制表示下，哪些位置为，哪些位置为。代码如下：

#include <stdio.h>

int main () {
    int k, n;
    scanf("%d%d", &k, &n);
    
    long long ans = 0;
    long long now = 1;
    
    while (n) {
        if (n % 2 == 1) ans += now;
        now = now * k;
        n = n / 2;
    }
    
    printf("%lld", ans);
    
    return 0;
}

如果有不够详细的地方，欢迎在群里提问~

制作：24计科师范 董天逸