本文为2023年9月GESP C++四级的上机题目的详细题解！觉得写的不错或者有帮助可以点个赞啦。
目录
题目一讲解视频:
2023年9月GESP C++四级上机题一
题目二讲解视频:
2023年9月GESP C++四级上机题二
题目一:进制转换
B3869 [GESP202309 四级] 进制转换 - 洛谷
解题思路:
我们首先要理解进制的本质。
一个K进制数字，可以理解成逢K进一，也就是每满K的时候往前进一位。
拿最熟悉的十进制数字举例子，个位每满10，十位数字就加一。
所以13可以表示为1 * 10 + 3， 34可以表示成3 * 10 + 4。
十位的数字要满10的时候，就进一位， 百位数字加1，也就是百位数字x就相当于已经有x * 10 * 10了。
那么比如说，十进制的345也就可以表示成3 * 10 * 10 + 4 * 10 + 5。
这个同样应用于任意进制的数字，所以对于一个K进制数字num
求它实际有多大，我们可以用它的第一位乘K的0次，第二位乘K的一次，第三位乘K的二次....最后加上总和，就是这个数字的大小。
这里就可以写一个模拟的思路。
代码(C++):
#include <bits/stdc++.h>
//https://blog.csdn.net/2401_83669813 csdn: @立志成为算法讲师
//0-9, 直接转换成数字
//A-F, 跟'A'的差 + 10
int to10(char c) {
if (c <= '9') {
return c - '0';
}
return c - 'A' + 10;
}
void solve() {
int k;
std::string numK;
std::cin >> k >> numK;
long long ans = 0;
int p = 0;
for (int i = numK.size() - 1; i >= 0; i--) {
int num = to10(numK[i]);
ans += (long long)num * std::pow(k, p);
p++;
}
std::cout << ans << "\n";
}
int main() {
/*
我们先要理解进制的本质
一个K进制的数字,表示的是逢K进一
十进制：
0..9 10..19..
八进制:
0..7 10..17
十进制23 = 2 * 10 + 3
八进制23 = 2 * 8 + 3
十进制的123 = 1 * 10 * 10 + 2 * 10 + 3
八进制的123 = 1 * (8 ^ 2) + 2 * (8 ^ 1) + 3 * (8 ^ 0)
*/
int N;
std::cin >> N;
while (N--) {
solve();
}
}题目二:变长编码
B3870 [GESP202309 四级] 变长编码 - 洛谷
解题思路:
首先来理解左移和右移操作。
对于一个数字n，n >> x，表示的是在n的二进制上整体向左移动，小于0的部分剔除掉。
比如101011 >> 3 => 101 (011)，011小于0，直接剔除掉即可。那么最终结果是101。
在十进制上，n >> x可以看作n / (2 ^ x)。
反之就是往左移动。（视频里面会有详细的讲解）
然后是与运算和或运算。
如果有很多位的话，就是按照每一位进行分别进行位运算。
比如 3 & 6可以看成是：
0 1 1
1 1 0
变成 0 1 0
这个题目对一个数字二进制下，分成每组7位，那么我们可以与运算获取这个数字的后7位，然后通过右移运算，让这个数字的二进制每次减少7位。
对最高位进行操作的话，可以用或运算
具体可以看代码和视频解析！
代码(C++):
#include <bits/stdc++.h>
//https://blog.csdn.net/2401_83669813 csdn: @立志成为算法讲师
char toChar(int num) {
if (num < 10) {
return num + '0';
}
return num - 10 + 'A';
}
std::string to16(int num) {
std::string res(2, '0');
res[0] = toChar(num >> 4);
res[1] = toChar(num & 15);
return res;
}
int main() {
/*
左移,右移运算
n >> x
与运算和或运算&,|
1.不断将数字右移7位,通过与运算获取最后的7位数字
2.对于在最高位添加1,可以通过或运算操作
*/
long long n;
std::cin >> n;
if (n == 0) {
std::cout << "00";
return 0;
}
//1.
while (n > 0) {
int num = n & 0x7F;//0111 1111
n >>= 7;
//2.
if (n > 0) {
//1000 0000
num |= 0x80;
}
std::cout << to16(num) << " ";
}
}