题目一讲解视频:

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)。

反之就是往左移动。（视频里面会有详细的讲解）

然后是与运算和或运算。

网址：Binary Fundamentals

如果有很多位的话，就是按照每一位进行分别进行位运算。

比如 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 1111n >>= 7;//2.if (n > 0) {//1000 0000num |= 0x80;}std::cout << to16(num) << " ";}
}