郑州轻工业大学-23级新生C语言周赛(2)题目解析

比赛信息

比赛名称:23级新生C语言周赛(2)

比赛命题:马恩植(空梦)

比赛平台:郑州轻工业大学在线评测系统(http://acm.zzuli.edu.cn/

参赛对象:郑州轻工业大学2023级新生(包含部分校外新生)

比赛时间:2023.11.05 14:00:00 ~ 17:00:00

比赛类型:周赛

官方解析2023级新生周赛第二周题解

直播回放

题目难度

正确率分布情况:

图片[1],郑州轻工业大学-23级新生C语言周赛(2)题目解析,编程网络技术爱好者中心-神域博客网

题目详解

解析:该题目是本应为简单的题目,可是因为许多同学的粗心还有对C的输入输出函数了解不够,导致该题目wa了无数次,正确率也大大降低。

出题人(kmjj)的博客对此有详细解释:如何理解c/c++中的输入/输出函数?—— 山岳库博

首先,该题目需要先用输入函数接收用户输入的字符串,这里要注意:

  1. scanf 函数是不接收空格字符的。
  2. gets 函数支持接收空格。

所以在第5个命令处,许多同学就是在这里wa了,题目要求输入的命令是“ask question”,这里字符串里出现了空格,所以用 scanf 函数的大佬们大多数都入了坑。

代码:

(1). scanf 函数:

#include <stdio.h>
#include <string.h>
int main() {
    //定义变量来存储输入的字符串
    char command[20];
    //输入字符串
    scanf("%s", command);
    //下面对字符串进行识别并输出对应答案
    if (strcmp(command, "base") == 0) {
        printf("严禁发布色情内容,严禁涉政");
    } else if (strcmp(command, "ms") == 0) {
        printf("萌新不推荐使用 vs");
    } else if (strcmp(command, "water") == 0) {
        printf("本群可以灌水但不要一直灌水");
    } else if (strcmp(command, "train") == 0) {
        printf("多读书多动手,编程能力是练出来的不是想出来的");
    } else if (strcmp(command, "ask") == 0) {
        printf("掌握提问艺术,从你我他做起");
    } else if (strcmp(command, "oj") == 0) {
        printf("oj 平台如果自己原来有一个账号的话用学校注册的账户继续往后写就行了,不需要把写过的题再交一遍。");
    } else if (strcmp(command, "standard") == 0) {
        printf("编写代码务必注意代码规范");
    }
    return 0;
}

(2). gets 函数:

#include <stdio.h>
#include <string.h>

int main() {
    char input[20];
    gets(input);
    if (strcmp(input, "base") == 0)
        printf("严禁发布色情内容,严禁涉政");
    else if (strcmp(input, "attention ms") == 0)
        printf("萌新不推荐使用 vs");
    else if (strcmp(input, "water") == 0)
        printf("本群可以灌水但不要一直灌水");
    else if (strcmp(input, "train") == 0)
        printf("多读书多动手,编程能力是练出来的不是想出来的");
    else if (strcmp(input, "ask question") == 0)
        printf("掌握提问艺术,从你我他做起")
    else if (strcmp(input, "oj") == 0)
        printf("oj 平台如果自己原来有一个账号的话用学校注册的账户继续往后写就行了,不需要把写过的题再交一遍。");
    else
        printf("编写代码务必注意代码规范");
    return 0;
}

解析:本题目就是一个简单的公式代入题目,只需要将相应的参数依次输入到公式中,运算即可得出结果。但是这种计算题目,很多人很容易把变量的取值范围以及变量的类型忽略掉,最后导致题目wa了。

本题就很容易犯这样的错误,题目中给的公式里M和N题目描述是实数,所以,我们应该将它们定义为双精度浮点数( double ),对于变量P,它代表最后输出的小数保留几位,所以它一定是正整数,定义为 int

本题目的第二个坑就是关于 printf 函数的用法:本题目要求输入P代表保留P位小数,很多大佬在这里迷糊了,甚至有大佬绕远路,用字符串转换整数类型再填进去!更离谱的还有一个一个判断的!虽然有的也过了,但是这毕竟不是正确的方法。我们应该利用 printf 函数的特性,熟悉它的全部用法。

出题人(kmjj)的博客对此有详细解释:如何理解c/c++中的输入/输出函数?—— 山岳库博

例如:

int p=2;
double res=5.2348;
printf("%.*lf",p,res);

在上面的代码中,printf里的格式化文本中出现了一个*”,此处它的作用就是代替它在后面的参数里所对应的变量的值,那么此处printf的作用就相当于保留两位小数:

double res=5.2348;
printf("%.2lf",res);

那么我们就可以利用此特性来解决这一道题目了。代码如下:

#include <stdio.h>
#include <math.h>
int main() {
    double M, N, e, RT;
    int P;
    e = 2.718281828459045;
    // 依次输入 M、N 和 P
    scanf("%lf %lf %d", &M, &N, &P);
    // 计算红灯时长 RT
    RT = M * pow(e, (-0.114514 * N));
    // 输出结果
    printf("%.*lf\n", P, RT);
    return 0;
}

解析:本题目属于数字求和题目,但是比原始的求和要多了一步,那就是剔除数据中的小数。注意题目中的一句话:“带小数点的数字都算小数。”,这里就是一个很大的坑!许多大佬因为忽略了整数部分不为0而小数部分为0的小数了,所以导致此题目频繁出错。所以这里的过滤条件不只是单纯利用数值判断,而需要通过字符串判断是否存在小数点。

代码如下:

(1).法一:

#include <stdio.h>
#include <string.h>
int main() {
    double num;
    int sum = 0;
    char input[100];
    while (1) {
        scanf("%s", input);
        if (strcmp(input, "0") == 0) {
            break; // 如果输入为0,则结束循环
        }
        //遍历字符串,检查是否存在小数点
        int len = strlen(input);
        int dotIndex = -1;
        for (int i = 0; i < len; i++) {
            if (input[i] == '.') {
                dotIndex = i;
                break;
            }
        }
        //检查到存在小数点,那么此数为小数,跳过该数字
        if (dotIndex != -1) {
            continue;
        }
        //将字符串转换为实数,并将其加到总和中
        sscanf(input, "%lf", &num);
        sum += (int)num;
    }
    // 输出整数的总和
    printf("%d\n", sum);
    return 0;
}

(2).法二:

#include <stdio.h>
#include <stdbool.h>

int main() {
    int n;
    int sum = 0;
    char p;
    while (true) {
        //输入整数部分
        scanf("%d", &n);
        //接收字符部分用来判断是否存在小数点
        int c = scanf("%c", &p);
        if (c != EOF && p == '.') {
            scanf("%*d");   // 使用 %*d 跳过小数的整数部分
            continue;  // 跳过此数值,继续接收下一个数值
        } else if (n == 0) break;
        sum += n;
    }
    printf("%d", sum);
    return 0;
}

解析:本题目考察对数据统计方法的使用以及逻辑运用。通读题目之后,观察数据特点,我们会发现,只有一个ID是用于统计的关键数据,时间戳以及Name都不太重要,只需要统计不同ID的个数即可得到结果。

代码如下:

(1).C语言

#include <stdio.h>
#include <string.h>
int main() {
    //定义ID数组
    int record[1001];
    //初始化ID数组
    memset(record, 0, sizeof(record));
    int id;
    int result = 0;
    //接收数据,此处又出现了*的用法,~的作用相当于取反
    while (~scanf("%*s %d %*s", &id)) {
        /*
        此处的思路比较新奇,灵活运用了自增运算的特性以及题目变量的取值范围
        ++var的运算顺序是先递增变量var再返回var的数值,
        那么此处数组record初始值都为1,那么第一次递增之后就是1,
        接下来如果出现了重复的id,那么就会在原来递增过的基础上继续递增,
        此时,就不符合if判断中的条件了,那么也就不会计数。
        此处id的取值范围是[100000000,100001000],拿着输入的id-100000000,就可以得出此id相应的位置。
        差值的取值范围是[0,1000]
        */
        if (++record[id - 100000000] == 1) ++result;
    }
    printf("%d", result);
    return 0;
}

(2).C++(stl的运用)

#include <iostream>
#include <string>
#include <map>

int main() {
    std::map<long long, std::string> users = {{0, "name"}}; //定义发言人map数组
    int count = 0; //计数结果
    long long id; //储存输入的id
    std::string timestamp; //时间戳
    std::string name; //名字

    //输入时间戳 id 名字
    while(std::cin >> timestamp >> id >> name)
    {
        //从map数组中查找此id是否已经存在
        auto it = users.find(id);
        //如果不存在,那就证明是新的发言人
        if(it == users.end())
        {
            //我们需要将其计数
            count++;
            //并将其记录到数组中
            users[id] = name;
        }
    }
    std::cout << count;
    return 0;
}

解析:此题目接近于阅读理解题目了,但是其中的逻辑关系是比较多的。我们需要注意到这句话:

第一张卡牌上是所有二进制最低为 `1` 的数字,第二张是二进制第二位为 `1` 的数字,第三张卡牌上是所有二进制第三位为 `1` 的数字。观众选择了第 `i` 张卡牌时说明二进制第 `i` 位为 `1`

那么第i张牌上每个数字的二进制第i位都是1,则必存在一个二进制数的前i位都是1,那么该数字也就对应着每张牌上的最大的数字。

再通过观察例子中三张牌的数字特点我们发现,它们都有数字7,而数字7的二进制为 0111 ,也就是说数字7的二进制数值中有3位都是1,此处正好对应了卡牌总数量3,那么问题就迎刃而解了。我们只需要通过位运算来求解N位都是1的二进制数字即可。

代码如下:

代码中,UINT_MAX 表示无符号整数的最大值 0xffffffff ,其二进制为 1111 1111 1111 1111 1111 1111 1111 1111 一共8组4个1组成的32位二进制数,UINT_MAX >> (32 – input) 表示将 UINT_MAX 右移 (32 – input) 位,也就是将最右边的 (32 – input) 个1去掉,剩下的就是 input 个1,也就是 N 个1,再将其以无符号整数输出即可得到我们所需要的最大整数。

#include <stdio.h>
#include <limits.h>
int main() {
    int input;
    //输入卡牌总数量N
    scanf("%d", &input);
    //将 UINT_MAX 右移(32 - input)位
    unsigned result = UINT_MAX >> (32 - input);
    for (int i = 0; i != input; ++i) {
        printf("%u\n", result);
    }
    return 0;
}

解析:这道题目充斥着对于二进制位运算的考察,如果没有比较坚实的二进制位运算基础,那么做起来是比较困难的,也可以做,但是在流程上会多出来很多代码。

首先我们从E题中可以看到:“第一张卡牌上是所有二进制最低为 `1` 的数字,第二张是二进制第二位为 `1` 的数字,第三张卡牌上是所有二进制第三位为 `1` 的数字。观众选择了第 `i` 张卡牌时说明二进制第 `i` 位为 `1`

在此题目中,要求我们求指定卡牌上的所有数字,那么我们首先要缕一缕这个流程:

  1. 首先找出来这些卡牌上的最大数字
  2. 根据E题中的规律,确定每张卡牌上的最小数字
  3. 在最小数字与最大数字之间遍历,查找符合第i位为1的数字并依次输出

捋清楚思路之后,我们即可开始实现相应的代码:

代码如下:

1) 其中,语句 int max_next_val = (1 << count_sum) | 1; 这个表达式的意义是将1左移 count_sum 位,然后与1进行按位或,得到一个 count_sum+1 位二进制数,其中最高位最低位都是1,其余位都是0。其过程如下:

  • 1的二进制为 0001 ,例如我们的卡牌总数量是3,那么通过左移运算 1 << 3 可以实现 0001 -> 1000 的变换。而7的二进制为 0111 ,将其加1即可得到 10001000 的十进制是8,8就是7的下一个数,7又是卡牌总数为3时的最大数,再将 1000 与1进行按位或,即可得到 1001 ,其十进制为9,就此我们即可得到比卡牌最大值多2的数值

2) 紧接着语句 int min_val = 1 << (id1); 这个表达式的意义是将1左移 id1 位,得到一个二进制数,其中第 id 位是1,其余位都是0。由E题我们知道,每张卡牌的最小值的二进制格式为0b***,其中第 id 位的数为1。执行这个表达式的过程如下:

  • 1的二进制为 0001 ,例如我们需要的卡牌 id 是2,那么通过左移运算 1 << (id1) 可以实现 0001 -> 0010 的变换。此时我们就得到了第 id 位为1,其余位置都为0的数,这也对应了E题中每张卡牌上的最小值的规律,由此我们即可得到第id张卡牌上的最小值

3) 最后语句 i & min_val ,这个表达式的意义是判断 imin_val 的二进制表示中,第 id 位是否都是1,如果是,就返回1,如果不是,就返回0。这就实现了在最小数字与最大数字之间遍历,查找符合第 id 位为1的数字。由此,如果第 id 位数字都为1,说明该数字满足条件,输出即可

#include <stdio.h>
int main () {
    //卡牌的总数量
    int count_sum=0;
    //需要查询的卡牌数量
    int count_need=0;
    //查询的卡牌位置
    int id=0;

    //输入卡牌的总数量以及需要查询的卡牌数量
    scanf("%d %d", &count_sum, &count_need);
    //根据卡牌总数量计算出比卡牌最大值多2的数值
    int max_next_val = (1 << count_sum) | 1;
    //循环 需要查询的卡牌数量 次
    while (count_need--) {
        //输入需要查询的卡牌位置id
        scanf("%d", &id);
        //计算出第id张卡牌上的最小值
        int min_val = 1 << (id - 1);
        //从1开始遍历到卡牌最大值
        for (int i = 1; i != max_next_val; ++i) {
            //如果第id位数字都为1,说明该数字满足条件,输出即可
            if ((i & min_val) != 0)
                printf("%d ", i);
        }
        printf("\n");
    }
    return 0;
}

解析:仔细观察二进制表达式,实际上有一个非常简单的二进制规律:

第三张卡牌上的数字(列举4个):

第1个:4 (DEC) -> 0100 (BIN)

第2个:5 (DEC) -> 0101 (BIN)

第3个:6 (DEC) -> 0110 (BIN)

第4个:7 (DEC) -> 0111 (BIN)

通过观察我们会发现,相邻的两个数只有一位不一样,而且这一不同的一位互相为反,例如:第3个与第4个数,它们的二进制数只有第1位不一样,前者为0,后者为1,以此类推前面的数也是如此,那么此时,这里就涉及到了二进制里的著名规律:格雷码(gray code)

相邻格雷码之间的联系是它们的二进制表示只有一位不同。下面是求格雷码的函数示例:

#include <stdio.h>
#include <limits.h>

typedef unsigned long long LLU;
LLU gray_code(int k, LLU i) {
    LLU j = i - 1;
    LLU left = j >> (k - 1);
    LLU right = j & (ULLONG_MAX >> (64 - k + 1));
    LLU result = (left << k) | (((LLU) 1) << (k - 1)) | right;
    return result;
}

其中, k 代表格雷码的起始位数, i 是要转换为格雷码的原始数。

那么我们代入本题目,就可以这样理解:

  • 我们输入 k 就可以规定格雷码的位数一定是 k 位,且第 k 位的数固定是1,比如我们输入的 k3 ,那么他的起始二进制数值就是0100。
  • 接着,我们输入 i 就代表着在起始值作为第一个数的基础上的,与它相邻的第 i 1 个数,比如输入的 i2,那么格雷码输出的就是与 0100 相邻的第一个数,对应到题目中也就是第三张卡牌的第二个数字。
  • 由此,我们可知:通过格雷码的计算,我们就可以得到与题目相邻二进制数值之间规律相同的数字了。

代码:

#include <stdio.h>
#include <limits.h>

typedef unsigned long long LLU;
int main() {
    int k;
    LLU i;
    while (~scanf("%*d %d %llu", &k, &i)) {
        if (k == 0 && i == 0) break;
        /*此处是格雷码计算部分起始处*/
        LLU j = i - 1;
        LLU left = j >> (k - 1);
        LLU right = j & (ULLONG_MAX >> (64 - k + 1));
        LLU result = (left << k) | (((LLU) 1) << (k - 1)) | right;
        /*此处是格雷码计算部分结束处*/
        printf("%llu\n", result);
    }
    return 0;
}

当然,本题目还有第二个规律:每张卡牌上数字出现的规律都是连续出现 x 个,然后跳过 x 个,再连续出现 x 个,此处的 x 就是每一张卡牌所对应的二进制位(最小值),以此往复。其过程如下:

第一张卡牌上的数字(列举4个):

第1个:1 (DEC) -> 0001 (BIN)

第2个:3 (DEC) -> 0011 (BIN)

第3个:5 (DEC) -> 0101 (BIN)

第4个:7 (DEC) -> 0111 (BIN)

第一张卡牌的最小值为1,那么我们可以发现:第一个到第二个是,先出现一个数字1,然后跳过一个数字2,再连续出现一个数字3,也即:1 2(跳过) 3 4(跳过) 5 6(跳过) 7

那么按照此规律,我们就可以来依据逻辑编写代码了:

#include <stdio.h>

typedef unsigned long long LLU;

int main () {
    int k;
    LLU i;
    while (~scanf("%*d %d %llu", &k, &i)) {
        if (k == 0 && i == 0) break;
        LLU interval = LLU(1) << (k - 1);
        LLU div = i / interval;
        LLU mod = i % interval;
        LLU result = (div * interval << 1) + (mod == 0 ? 0 : interval + mod) - 1;
        printf("%llu\n", result);
    }
    return 0;
}

解析:本题目考察对 scanf 函数的掌握程度,本题目中的十六进制数与八进制数都可以直接由 scanf 函数接收,不需要自己再去编写进制转换的代码了。同时也要注意此处的数据类型

(1).C语言

#include <stdio.h>

typedef unsigned long long LLU;

int main() {
    LLU var, real;
    scanf("%llx %llo", &var, &real);
    printf("%d", (int) (var - real));
    return 0;
}

(2).Python

hex_year = input().strip()
oct_year = input().strip()

decimal_hex_year = int(hex_year, 16)
decimal_oct_year = int(oct_year, 8)

year_diff = decimal_hex_year - decimal_oct_year

print(year_diff)

以上解析内容中,部分代码来自出题人(kmjj)的官方博客:2023级新生周赛第二周题解
详细解析由本人编写,其中部分拓展代码也由本人编写,如有问题,请及时联系,喵~

------本文已结束,感谢您的阅读------
THE END
喜欢就支持一下吧
点赞14 分享
评论 抢沙发
头像
善语结善缘,恶语伤人心
提交
头像

昵称

取消
昵称常用语 夸夸
夸夸
还有吗!没看够!
表情图片

    暂无评论内容