当前位置：首页 > news >正文

【CODEMATE】进制转换（transform）粤港澳青少年信息学创新大赛 C/C++/Python 解题思路

news 来源：原创 2025/6/23 3:21:19

问题描述
做题思路，解决过程
- 思路：
- 踩过的坑：
- 核心代码
- - C 语言 / C++ 切片：
  - C 语言 / C++ 判断 ‘A’ 数量：
  - Python 切片：
  - Python 判断 ‘A’ 数量：
完整代码
- C 语言完整代码
- C++ 完整代码
- Python 完整代码
评测结果
- C语言
- C++
- Python
后记

问题描述

知识点：字符串位运算难度值：3 尝试：15 AC：5 上传者：_Separation

题目背景：

码上学习工作室 CSP - J 月赛 A 题

十六进制是一种基数为 ‘16’ 的计数系统，使用数字 ‘0’ 到 ‘9’ 和字母 ‘A’ 到 ‘F’ 来表示数值。在这种系统中，逢 ‘16’ 进 ‘1’，‘A ~ F’ 代表 ‘10 ~ 15’ 。

问题描述:

给定一个正整数 n 和一个有 4n 位的二进制数（不保证没有前导零）

请你求出，该二进制数转化为十六进制表示后共有多少个 ‘A’ 。

输入输出格式:

Input

输入两行。

第一行输入一个正整数 n 。

第二行输入一个只由 ‘01’ 构成的 4n 位二进制数，不保证没有前导零。

Output

输出一行。

行输出一个整数，表示输入的二进制数用十六进制表示时 ‘A’ 的个数。

输入输出样例:

输入数据 1

3
101010111100

输出数据 1

【样例 ‘1’ 解释】：该二进制数用十六进制表示为 ‘ABC’ ，其中有一个 ‘A’ 。

输入数据 2

10
1111111111111110000000000000001110001101

输出数据 2

数据范围与提示：

对于前 20% 的数据，保证 n = 1

对于前 40% 的数据，保证 n ≤ 10

对于前 60% 的数据，保证 n ≤ 10³

对于 100% 的数据，保证 1 ≤ n ≤ 10⁶

做题思路，解决过程

通过读题可以得知：

题目至少需要 3 个变量，分别是：输入变量正整数 n 、长度为 4n 的字符串 str（只有01构成的的二进制字符串）、输出变量 num （str 转换成十六进制表示时 ‘A’ 的个数）。

思路：

第一步：先将二进制串 str 按间距为 4 切片（4 位二进制可以表示 1 位十六进制），如将输入数据 1 ：101010111100，切成 1010 、 1011 、 1100。第二步：由题目得知需要求 ‘A’ 的个数，由于所求 ‘A’ 是个固定值（‘A’ 二进制为 1010 、十进制为 10 、十六进制为 ‘A’），所以直接判断 str 切片里是否有 ‘A’ 的二进制值即可。

踩过的坑：

一开始看到题目我想着先将二进制串 str 转换为十六进制串，再判断十六进制串里有多少个 ‘A’，如果用这种方法又涉及到不同进制间转换，python 里倒是有方法可以实现，但是放到 C/C++ 里就需要自己写方法函数，走弯路了。

后来反思为什么会出现这种思路，由于常规思考都是线性的，所以理所当然会按照解决问题的过程一步一步去构思代码（面向过程），在比赛面对算法题时，时间是有限的，输入输出也是有限的，我们只需要将输入输出对应起来即可，所以思考时需要更抽象、抓住问题本质（抽象、黑盒测试、面向对象）。

还有一点就是题目里说的：“第二行输入一个只由 ‘01’ 构成的 4n 位二进制数，不保证没有前导零。”，还好题目说的是“不保证没有前导零”，意思是会有前导零，使二进制串的长度为 4n。如果题目改成“没有前导零”，那就麻烦一点，需要先判断补多少个前导零，再切片。虽然题目有说输入字符串长度为 4n，但是咱们做题得会举一反三，多点想法是有利于自己的，注意做题思路别被想法带偏了。

核心代码

1. 将字符串按间距 4 切片

2. 对 ‘A’ 数量的判断：

C 语言 / C++ 切片：

利用循环，按 4 为增量做循环，直到遍历数组即可。

int n;	//定义变量 nscanf("%d", &n);	//获取 n 的值
//也可以写成：
//cin >> n;	// C++ 的输入函数char str[n*4];	//定义二进制数组 strscanf("%s", str);	//获取二进制数组值
//cin >> str;//切片
for(int i=0, j=0; i<n*4; i+=4, j++ )
{printf("第 %d 次切片：", j);	//cout << "第 " << j << " 次切片";printf("%c", str[i]);printf("%c", str[i+1]);printf("%c", str[i+2]);printf("%c\n", str[i+3]);
}

C语言 / C++ 切片运行结果

C切片运行结果

C 语言 / C++ 判断 ‘A’ 数量：

稍加修改切片循环的代码，将打印切片的代码换成判断代码即可。

判断 ‘A’ 的方法有很多种，作者提供两种思路：

1.按 4 位二进制分成一组，判断是否为 ‘1010’。

2.将四位二进制分成一组，判断其十进制值是否为 10。

//在切片循环代码的基础上修改
// 方法 1
int num_A=0;
for(int i=0; i<n*4; i+=4)
{if(str[i]!='1')continue;	//如果不符合 'A' 的二进制，则直接寻址下 4 位，节省时间else if(str[i+1]!='0')continue;else if(str[i+2]!='1')continue;else if(str[i+3]!='0')continue;elsenum_A++;/**也可以将循环内代码写成：if(s[i]=='1' && s[i+1]=='0' && s[i+2]=='1' && s[i+3]=='0')num_A++;*/
}printf("%d", num_A);// 方法 2
/**
int num_A=0;// 将字符 ‘1’ 或 ‘0’ 转换成整数 1 或 0
for(i=0;i<n*4;i++)
{str[i]-='0';
}// 4 位二进制为一组，转换成十进制数
for(i=0; i<n*4-3; i+=4)
{	num=bin[i]*8 + bin[i+1]*4 + bin[i+2]*2 + bin[i+3];if(num==10){num_A+=1;}
}printf("%d", num_A);
*/

C 语言 / C++ 判断 ‘A’ 数量运行结果

C判断运行结果

Python 切片：

Python 的切片语句是：序列[start:stop:step]，序列可以是字符串、列表、元组等； start:stop 表示切片起点和终点； step 表示步长，由于切片都是在元素的左边切一刀，这就导致切片 1 序列[0:4] 实际值是 序列[0:3] ，轮到下一个切片 2 序列[4:8] ，切片 1 的结束下标 3 与切片 2 的起点下标的差值就是 step 。

n=int(input())
str=input()# 利用循环语句切片
for i in range(0, len(str), 4): print(str[i:i+4])

Python 切片运行结果
python切片

Python 判断 ‘A’ 数量：

判断代码也是在切片的基础上稍加修改，加入变量 num_A 记录 ‘A’ 的个数。由于 Python 里没有自增自减的运算，所以用 += 代替 ++。

n=int(input())
str=input()
num_A=0;# 利用循环语句切片
for i in range(0, len(str), 4): if(str[i:i+4]=="1010")num_A+=1;print(num_A)

Python 判断 ‘A’ 数量运行结果：

完整代码

C 语言完整代码

#include <stdio.h>int main()
{int n, num_A=0;	//定义变量 n 、变量 num_Ascanf("%d", &n);	//获取 n 的值char str[n*4];	//定义二进制数组 strscanf("%s", str);	//获取二进制数组值//判断 ‘A’ 数量for(int i=0; i<n*4; i+=4){if(str[i]!='1')continue;	//如果不符合 'A' 的二进制，则直接寻址下 4 位，节省时间else if(str[i+1]!='0')continue;else if(str[i+2]!='1')continue;else if(str[i+3]!='0')continue;elsenum_A++;}printf("%d", num_A);
}

C++ 完整代码

#include <iostream>using namespace std;int main()
{int n, num_A=0;	//定义变量 n 、变量 num_Acin >> n;	//获取 n 的值char str[n*4];	//定义二进制数组 strcin >> str;	//获取二进制数组值//判断 ‘A’ 数量for(int i=0; i<n*4; i+=4){if(str[i]!='1')continue;	//如果不符合 'A' 的二进制，则直接寻址下 4 位，节省时间else if(str[i+1]!='0')continue;else if(str[i+2]!='1')continue;else if(str[i+3]!='0')continue;elsenum_A++;}cout << num_A;
}

Python 完整代码

n=int(input())
str=input()
num_A=0# 利用循环语句切片
for i in range(0, len(str), 4): # 从这里可以看出 n 的数值不影响 str 的输入if(str[i:i+4]=="1010"):num_A+=1# 输出 "A" 的个数
print(num_A)

评测结果

C语言

C评测

C++

C++评测

Python

Python评测

后记

通过评测结果可以看出 Python 的代码虽然短，但在耗时、内存占用上远远比不上 C/C++，这也是为什么尽管各大语言兴起，也无法撼动 C/C++ 基石，经典经久不衰是有其道理的。

这篇文章花了很长时间打磨，从读题、解题再到优化，回顾这一过程也可以说是自己进步的过程，不积硅步无以至千里，不积小流无以成江海，冲！

目录