竞赛总览

CSDN 编程竞赛二十四期：比赛详情 (csdn.net)

本次竞赛感觉打模板的题变少了，而且多了很多可以集思广益的题目，参赛体验很好。

竞赛题解

题目1、计数问题

试计算在区间1到n的所有整数中，数字x（0≤x≤9）共出现了多少次？例如，在1到11中，即在 1,2,3,4,5,6,7,8,9,10,11中，数字1出现了4次。

#include <cstdio>

int calc (int x, int y) {
    int result = 0;
    while (x > 0) {
        if (x % 10 == y) result += 1;
        x /= 10;
    }
    return result;
}

int main () {
    int result = 0;
    int n, m;
    scanf ("%d", &n);
    scanf ("%d", &m);
    for (int i = 1; i <= n; i++) {
        result += calc (i, m);
    }
    printf ("%d", result);
    return 0;
}

模拟法，对1到n区间中的每个数进行逐位统计，如果该位是数字x则记录。此题属于初级难度，类似的题目有2021年蓝桥杯省赛的卡片等。 

题目2、小艺的英文名

小艺酱想给自己起一个英文名字。小艺酱想要装的自己学识渊博。所以她想要自己英文名字必须满足：1.只有字母表中前k个小写字母。2.必须是回文串。3.前k个小写字母每个字母至少出现一次。小艺酱已经自己完成了部分，空余的字母部分用’?’代替。请你帮她完成她的英文名字。

此题还有一个要求是输出字典序最小的答案。

这道题目也属于初级难度，但是有几个坑需要注意一下，如果没有找到的话可能无法拿到满分。

1、只有字母表中的前k个小写字母，这里需要检查一下。不过本人没写这个限制条件也通过了这道题目，可能是测试数据里正好没有这一项。

2、必须是回文串，这里需要检查一下。如果左边和右边有一个字符是问号，可以将另一边补全。如果左边和右边的字符不一致，直接输出无解（QAQ）即可。

3、前k个小写字母，每个字母至少出现一次。所以还要再用循环统计一次，看看经上一步补全之后的字符串里面有哪些字母。判断完之后，再根据已有字母，找出前k个小写字母里面没有出现过的字母，存入数组中备用。

4、然后可以开始填充了，根据问号填充小写字母。由于是回文串，只需要填一半即可（0到n/2，或者n/2+1到2n），另一半根据对称位置直接补相同的字母。

这里还有个坑，如果补全是从左向右的，即0到n/2，可能会出现一个问题：顺着补全前k个小写字母，使其都出现过一次，后面剩下的位置根据题目的要求，字典序最小，全部填小写字母a。这样的话字典序其实不是最小的。

所以要从中间往前补全前k个小写字母，而不是从前往后补。

补全前k个小写字母的过程中，可以用一个临时变量t来记录。刚开始t指向未出现字母列表的末尾位置，每补一次之后t减1，如果过程中t变为0，直接补a即可。最后，根据t是否为0判断前k个小写字母是否都出现过，如果符合条件输出答案，否则输出无解。

题目3、蛇形矩阵

给你一个整数n，输出n∗n的蛇形矩阵。

#include <cstdio>
#include <iostream>
#include <string>

int data [1005][1005];

void fill (int& r, int& c, int& x, int i) {
    data [r][c] = ++x;
    r += i % 2 == 0 ? -1 : +1;
    c += i % 2 == 0 ? +1 : -1;
}

int main () {
    int n; scanf ("%d", &n);
    int r = 0, c = 0, x = 0;
    int end = n * 2 + 1;
    for (int i = 0; i < end; i++) {
        if (i < n) {
            r = i % 2 == 0 ? i : 0;
            c = i % 2 == 0 ? 0 : i;
            while ((i % 2 == 0 ? r : c) > -1) {
                fill (r, c, x, i);
            }
        } else {
            r = i % 2 == 0 ? (n - 1) : i - (n - 1);
            c = i % 2 == 0 ? i - (n - 1) : (n - 1);
            while ((i % 2 == 1 ? r : c) < n) {
                fill (r, c, x, i);
            }
        }
    }
    for (int i = 0; i < n; i++) {     if (i > 0) printf ("n");
        for (int j = 0; j < n; j++) { if (j > 0) printf (" ");
            printf ("%d", data [i][j]);
        }
    }
    return 0;
}

很多年前我解决这道题的方法是使用模拟法，顺着n个数字填充二维数组，直到填满为止。这种方法需要维护填充位置信息（行、列），但非常不方便，每次都要推理很久才能解决。

后来忘记在哪里看到了一个更好的方法，于是这道题变成了一道模板题。

主要思路：

顺着对角线填充，将蛇形矩阵分为上三角形和下三角形两个部分。

例如，3*3的蛇形矩阵：

1 2 6
3 5 7
4 8 9

可以拆分为两个三角形：

1 2 6    0 0 0
3 5 0    0 0 7
4 0 0    0 8 9

这个例子比较简单，看不出什么名堂，再换个5*5的蛇形矩阵看一下：

01 02 06 07 15
03 05 08 14 16
04 09 13 17 22
10 12 18 21 23
11 19 20 24 25

 注释掉代码中else的部分，只保留if的部分：

01 02 06 07 15
03 05 08 14 00
04 09 13 00 00
10 12 00 00 00
11 00 00 00 00

 这样就可以从结果中看出来填充方法了：

1、填第1条对角线，填1个数，到1。

2、填第2条对角线，填2个数，到3。

3、填第3条对角线，填3个数，到6。

…

N、填第N条对角线，填N个数，到N*(N+1)/2。

下三角形和上三角形的填充思路差不多，只要算好起始填充位置和填充方向就可以无脑填充了。

可以直接在else后面加一行continue代码实现快速注释，在注释掉下三角形填充代码之后，可以在上三角形的if后面加一行代码 if (i % 2 == 1) continue;

这样的话程序只会填充奇数对角线，5*5的蛇形矩阵结果将变为：

01 00 04 00 09
00 03 00 08 00
02 00 07 00 00
00 06 00 00 00
05 00 00 00 00

在这个结果中，可以清晰地看出程序的运行逻辑。

总得来说，这道题目很适合新手学习。此题的思路其实很多，以上只是其中一种比较简单的思路。

题目4、放货物

小明是一名快递员，他现在手上一共有N个快件需要运送。但是货车有限，所以我们希望用最少的货车来进行工作。现在已知，一辆车的限定额度为最多放置K件货物。此外，小明很不喜欢13这个数字，所以他不希望任何一辆货车中的货物数量为13。现在小明想要知道，最少使用多少辆货车能够将这N个快件都放置到货车上。

#include <cstdio>

int solution (int n, int k) {
    if (n < k) return 1 + (n == 13 ? 1 : 0);
    if (k == 13) k = k - 1;
    return (n / k) + (n % k == 0 ? 0 : 1) + (k == 14 && n % k == 13 ? 1 : 0);
}

int main () {
    int n, k;
    while (scanf ("%d %d", &n, &k) != EOF) {
        printf ("%dn", solution (n, k));
    }
    return 0;
}

题目有点长，简单地说就是将n件货物装车，每辆车最多放k件货物，但不能放13件货物，求装车数量。

1、首先考虑最简单的情况，如果n小于k，直接装一辆车就可以了。不过，需要特别注意，如果n是13，不能装一辆车，必须装两辆车才可以。

2、如果k是13，虽然车上可以放13件货物，但是货主要求不能这样，所以一辆车最多只能放12件货物，k实际上是12。

3、其余情况就比较简单了，直接将货物无脑往车上扔就行了。扔满前n-1辆车如果还有剩余，再单独开一辆车即可。

这样的话，答案是(n / k) + (n % k == 0 ? 0 : 1)。

不过，这里其实还有一个大坑。

本人之前见过类似的题，很快就意识到这个坑了，如果是新手做这道题可能会踩雷。

假设货物不能恰好将货车全部装满。那么，n%k这个余数肯定不是0，因此需要单独开一辆车拉走剩余的货物。

但是如果这个余数恰好是13的话，就要开两辆车？是不是有点浪费了？

其实这里有个折中的办法，和两个锅烙三个饼有点相似，算是个小学生奥数题吧，就是将一辆已经装满的货车上的货物扔出来一件，给货物数为13的这辆新车。

比如说车最多装15件货物，这样做的话就可以得到两个装了14件货物的车，就可以发车了。

但是，如果货车最多装14件货物，就不能这样拿了，因为拿走之后满足了新车的要求，老车又不符合条件了。如果遇到这种情况，就必须再开一辆车了。

最终答案为(n / k) + (n % k == 0 ? 0 : 1) + (k == 14 && n % k == 13 ? 1 : 0)。

最后

以上就是愉快果汁为你收集整理的CSDN 编程竞赛二十四期题解竞赛总览竞赛题解的全部内容，希望文章能够帮你解决CSDN 编程竞赛二十四期题解竞赛总览竞赛题解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。