(148 − 10102) × D16 − 11012 的结果，并选择十进制值。(char)('a' + 13) 与下面哪个值相等？N 次（N >= 2），在压缩字符串中它被表示为“字符 + 数字 N”。例如，编码 A12 代表 12 个连续的字符 A。B 代表 1 个字符 B。| 1 | #include <cctype> |
| 2 | #include <iostream> |
| 3 | #include <string> |
| 4 | using namespace std; |
| 5 | |
| 6 | int main() { |
| 7 | string z; |
| 8 | cin >> z; |
| 9 | string s = ""; |
| 10 | |
| 11 | for (int i = 0; i < z.length(); ) { |
| 12 | char ch = z[i]; |
| 13 | |
| 14 | if (① && isdigit(z[i + 1])) { |
| 15 | i++; |
| 16 | int count = 0; |
| 17 | while (i < z.length() && isdigit(z[i])) { |
| 18 | count = ②; |
| 19 | i++; |
| 20 | } |
| 21 | for (int j = 0; j < ③; ++j) { |
| 22 | s += ch; |
| 23 | } |
| 24 | } else { |
| 25 | s += ④; |
| 26 | ⑤; |
| 27 | } |
| 28 | } |
| 29 | |
| 30 | cout << s << endl; |
| 31 | return 0; |
| 32 | } |
程序实现字符串解码：输入一个由字母和数字组成的编码串，将“字符 + 数字”还原为重复若干次的字符，并输出原字符串。
例如，输入 a12b3，输出 aaaaaaaaaaaabbb。
i 指向当前待处理字符。z[i + 1] 不越界。count = count * 10 + (z[i] - '0') 组成完整次数，支持多位数。ch 追加 count 次，实现解码。i 移到下一个字符。z[i] - '0' 将数字字符转换为对应整数；i++ 负责跳过已经处理的字符或数字，避免重复处理。
N 个人，分为两类：已知精明人严格占据多数，即如果精明人有 k 个，则满足 k > N / 2。你只能通过函数 query(i, j) 让第 i 个人判断第 j 个人：返回 true 表示判断结果为“精明人”；返回 false 表示判断结果为“糊涂人”。你的目标是通过互相判断，找出至少一个百分之百能确定的精明人。同时，你无需关心 query(i, j) 的内部实现。
以下程序利用“精明人占多数”的优势，通过“消除”过程让人们互相判断并进行抵消，经过若干轮抵消后，最终留下的候选者必然属于多数派，即精明人。
例如，假设有三个人 0、1、2。如果 0 说 1 是糊涂人，而 1 也说 0 是糊涂人，则 0 和 1 至少有一个是糊涂人。程序将同时淘汰 0 和 1。由于三人里至少有两个精明人，我们确定 2 是精明人。
| 1 | #include <iostream> |
| 2 | #include <vector> |
| 3 | using namespace std; |
| 4 | |
| 5 | int N; |
| 6 | bool query(int i, int j); |
| 7 | |
| 8 | int main() { |
| 9 | cin >> N; |
| 10 | |
| 11 | int candidate = 0; |
| 12 | int count = ①; |
| 13 | |
| 14 | for (int i = 1; i < N; ++i) { |
| 15 | if (②) { |
| 16 | candidate = i; |
| 17 | count = 1; |
| 18 | } else { |
| 19 | if (③) { |
| 20 | ④; |
| 21 | } else { |
| 22 | count++; |
| 23 | } |
| 24 | } |
| 25 | } |
| 26 | |
| 27 | cout << ⑤ << endl; |
| 28 | return 0; |
| 29 | } |
程序从一组“精明人”和“糊涂人”中找出一个确定的精明人编号。核心方法是多数派消除：不同阵营的两个人可以互相抵消，最终留下的候选人再进行验证。
candidate 和计数 count；初始把 0 号人作为候选人，计数为 1。N - 1 号人员。count--；否则执行 count++，表示候选阵营又得到一票支持。count == 0 表示当前候选已没有未抵消的支持；query(candidate, i) == false && query(i, candidate) == false 表示两人互相认为对方糊涂，可以配对抵消；candidate = i 用于更新候选人。
这种方法只需一次扫描，时间复杂度为 O(N)，额外空间复杂度为 O(1)。