1. 题目104:A == B ? 问题解析与实现
1.1 问题理解与边界分析
这道题目要求我们比较两个可能非常长的非负实数是否相等。关键难点在于:
- 数字可能非常大(不超过1000位),无法用常规数值类型存储
- 数字前后可能存在无效的0(前导零和末尾零)
- 需要考虑小数点的存在及其位置
例如:
- "00100" 和 "100" 应该视为相等
- "0100.1234576" 和 "00000000100.123457" 应该视为不等
- "100.0" 和 "100" 应该视为相等
1.2 解决方案设计
核心思路是将两个数字都转换为规范化的形式后再比较:
- 去除前导零(整数部分前面的0)
- 去除小数部分末尾的0
- 如果小数部分全部去除后只剩下小数点,则也去除小数点
具体实现步骤:
cpp复制string normalizeNumber(string s) {
// 1. 去除前导零
int i = 0;
while (i < s.size() - 1 && s[i] == '0') {
i++;
}
s = s.substr(i);
// 2. 处理小数部分
size_t dotPos = s.find('.');
if (dotPos != string::npos) {
// 去除小数部分末尾的0
while (!s.empty() && s.back() == '0') {
s.pop_back();
}
// 如果小数点后没有数字了,去除小数点
if (!s.empty() && s.back() == '.') {
s.pop_back();
}
}
return s;
}
1.3 完整实现与测试
cpp复制#include <iostream>
#include <string>
using namespace std;
string normalizeNumber(string s) {
// 实现同上
}
int main() {
int n;
cin >> n;
string a, b;
while (n--) {
cin >> a >> b;
string normA = normalizeNumber(a);
string normB = normalizeNumber(b);
cout << (normA == normB ? "YES" : "NO") << endl;
}
return 0;
}
测试用例:
code复制输入:
2
100.0 00100
0100.1234576 00000000100.123457
输出:
YES
NO
2. 题目105:母牛制造的回文问题
2.1 问题分析与算法选择
这个问题要求我们在忽略标点符号和空格的情况下,找出文本中最长的回文子串。关键点:
- 只考虑字母(A-Z, a-z),忽略其他字符
- 回文不区分大小写
- 需要输出原始文本中的回文(保留标点符号和空格)
算法选择:
- 中心扩展法:时间复杂度O(n^2),空间复杂度O(1)
- Manacher算法:时间复杂度O(n),但实现较复杂
考虑到题目限制回文长度不超过2000,中心扩展法足够高效。
2.2 实现步骤详解
- 预处理:提取所有字母并记录在原字符串中的位置
- 在纯字母串上寻找最长回文
- 根据位置信息映射回原字符串
cpp复制#include <iostream>
#include <vector>
#include <cctype>
using namespace std;
int main() {
string text;
char c;
while (cin.get(c)) {
text += c;
}
string letters;
vector<int> positions;
// 预处理:提取字母并记录位置
for (int i = 0; i < text.size(); i++) {
if (isalpha(text[i])) {
letters += toupper(text[i]);
positions.push_back(i);
}
}
if (letters.empty()) {
cout << "0" << endl;
return 0;
}
int maxLen = 1;
int start = 0;
// 中心扩展法
for (int center = 0; center < letters.size(); center++) {
// 奇数长度回文
int left = center, right = center;
while (left >= 0 && right < letters.size() && letters[left] == letters[right]) {
int len = right - left + 1;
if (len > maxLen) {
maxLen = len;
start = left;
}
left--;
right++;
}
// 偶数长度回文
left = center;
right = center + 1;
while (left >= 0 && right < letters.size() && letters[left] == letters[right]) {
int len = right - left + 1;
if (len > maxLen) {
maxLen = len;
start = left;
}
left--;
right++;
}
}
// 输出结果
cout << maxLen << endl;
int originalStart = positions[start];
int originalEnd = positions[start + maxLen - 1];
for (int i = originalStart; i <= originalEnd; i++) {
cout << text[i];
}
cout << endl;
return 0;
}
2.3 测试与边界情况
输入:
code复制Confucius say: Madam, I'm Adam.
输出:
code复制11
Madam, I'm Adam
边界情况处理:
- 输入没有字母:输出0
- 多个相同长度的回文:输出最先出现的
- 回文跨越多行:保留原始格式
3. 题目107:16进制加法问题
3.1 问题分析与算法设计
实现两个16进制数相加,需要考虑:
- 16进制数字表示(0-9, a-f)
- 可能的大数相加(超过普通整数范围)
- 进位处理
算法步骤:
- 从最低位开始相加
- 处理进位(16进制进位)
- 将结果转换为字符
3.2 关键函数实现
cpp复制// 字符转16进制数值
int charToHex(char c) {
if (c >= '0' && c <= '9') return c - '0';
if (c >= 'a' && c <= 'f') return c - 'a' + 10;
if (c >= 'A' && c <= 'F') return c - 'A' + 10;
return 0; // 非法字符处理
}
// 16进制数值转字符
char hexToChar(int n) {
if (n >= 0 && n <= 9) return '0' + n;
if (n >= 10 && n <= 15) return 'a' + (n - 10);
return '0'; // 非法值处理
}
string addHex(string a, string b) {
string result;
int i = a.size() - 1;
int j = b.size() - 1;
int carry = 0;
while (i >= 0 || j >= 0 || carry > 0) {
int sum = carry;
if (i >= 0) sum += charToHex(a[i--]);
if (j >= 0) sum += charToHex(b[j--]);
result = hexToChar(sum % 16) + result;
carry = sum / 16;
}
return result;
}
3.3 完整实现与测试
cpp复制#include <iostream>
#include <string>
using namespace std;
// 上述转换函数...
int main() {
int t;
cin >> t;
while (t--) {
string a, b;
cin >> a >> b;
cout << addHex(a, b) << endl;
}
return 0;
}
测试用例:
code复制输入:
2
4b0d 4887
2745 7438
输出:
9394
9b7d
4. 题目109:大实数加法问题
4.1 问题分析与算法设计
实现两个正实数相加,需要考虑:
- 整数部分和小数部分分开处理
- 小数部分对齐(补零)
- 小数部分向整数部分的进位
算法步骤:
- 分离整数和小数部分
- 小数部分相加,处理进位
- 整数部分相加
- 合并结果,去除不必要的零
4.2 关键函数实现
cpp复制// 整数部分相加
string addInteger(string a, string b) {
string result;
int i = a.size() - 1;
int j = b.size() - 1;
int carry = 0;
while (i >= 0 || j >= 0 || carry > 0) {
int sum = carry;
if (i >= 0) sum += a[i--] - '0';
if (j >= 0) sum += b[j--] - '0';
result = char(sum % 10 + '0') + result;
carry = sum / 10;
}
return result;
}
// 小数部分相加,返回结果和进位
string addDecimal(string a, string b, int &carry) {
// 对齐小数部分
int maxLen = max(a.size(), b.size());
a.resize(maxLen, '0');
b.resize(maxLen, '0');
string result = addInteger(a, b);
carry = 0;
if (result.size() > maxLen) {
carry = result[0] - '0';
result = result.substr(1);
}
// 去除末尾的0
while (!result.empty() && result.back() == '0') {
result.pop_back();
}
return result;
}
string addRealNumber(string a, string b) {
// 分离整数和小数部分
size_t dotA = a.find('.');
size_t dotB = b.find('.');
string intA = (dotA == string::npos) ? a : a.substr(0, dotA);
string decA = (dotA == string::npos) ? "" : a.substr(dotA + 1);
string intB = (dotB == string::npos) ? b : b.substr(0, dotB);
string decB = (dotB == string::npos) ? "" : b.substr(dotB + 1);
// 小数部分相加
int carryFromDecimal = 0;
string decimalPart = addDecimal(decA, decB, carryFromDecimal);
// 整数部分相加(包括小数部分的进位)
string integerPart = addInteger(intA, intB);
if (carryFromDecimal > 0) {
integerPart = addInteger(integerPart, to_string(carryFromDecimal));
}
// 组合结果
if (decimalPart.empty()) {
return integerPart;
} else {
return integerPart + "." + decimalPart;
}
}
4.3 完整实现与测试
cpp复制#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
// 上述函数实现...
int main() {
int T;
cin >> T;
while (T--) {
string a, b;
cin >> a >> b;
cout << addRealNumber(a, b) << endl;
}
return 0;
}
测试用例:
code复制输入:
3
1.1 2.9
1.1111111111 2.3444323343
1 1.1
输出:
4
3.4555434454
2.1
5. 题目110:考试排名问题
5.1 问题分析与数据结构设计
这个问题需要处理学生考试成绩排名,关键点:
- 输入格式复杂:可能有括号表示错误次数
- 排名规则:
- 按AC题数降序
- 按总耗时升序
- 按姓名字典序升序
- 输出格式要求严格
数据结构设计:
cpp复制struct Student {
string name;
int solved;
int time;
};
5.2 输入解析与处理
关键是如何解析题目状态:
- 正数:AC耗时
- 负数:未AC
- 带括号:AC耗时(错误次数)
使用stringstream解析带括号的格式:
cpp复制int time, wrong = 0;
if (token.find('(') != string::npos) {
stringstream ss(token);
char ch;
ss >> time >> ch >> wrong >> ch;
} else {
time = stoi(token);
}
5.3 完整实现
cpp复制#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
using namespace std;
struct Student {
string name;
int solved;
int time;
};
bool compareStudents(const Student &a, const Student &b) {
if (a.solved != b.solved) return a.solved > b.solved;
if (a.time != b.time) return a.time < b.time;
return a.name < b.name;
}
int main() {
int n, m;
cin >> n >> m;
vector<Student> students;
string name, token;
while (cin >> name) {
Student s{name, 0, 0};
for (int i = 0; i < n; i++) {
cin >> token;
int time, wrong = 0;
if (token.find('(') != string::npos) {
stringstream ss(token);
char ch;
ss >> time >> ch >> wrong >> ch;
} else {
time = stoi(token);
}
if (time > 0) {
s.solved++;
s.time += time + wrong * m;
}
}
students.push_back(s);
}
sort(students.begin(), students.end(), compareStudents);
for (const auto &s : students) {
printf("%-10s %2d %4d\n", s.name.c_str(), s.solved, s.time);
}
return 0;
}
5.4 测试与输出格式
输入:
code复制8 20
Smith -1 -16 8 0 0 120 39 0
John 116 -2 11 0 0 82 55(1) 0
Josephus 72(3) 126 10 -3 0 47 21(2) -2
Bush 0 -1 -8 0 0 0 0 0
Alice -2 67(2) 13 -1 0 133 79(1) -1
Bob 0 0 57(5) 0 0 168 -7 0
输出:
code复制Josephus 5 376
John 4 284
Alice 4 352
Smith 3 167
Bob 2 325
Bush 0 0
6. 算法竞赛实用技巧总结
6.1 输入输出处理技巧
- 大数处理:使用字符串存储和运算
- 复杂输入解析:善用stringstream处理带格式的输入
- 高效读取:对于大规模数据,考虑使用更快的IO方法
6.2 常见算法应用场景
- 字符串处理:正则表达式、KMP、Trie树
- 数值计算:大数运算、高精度计算
- 排序与搜索:自定义排序规则、二分查找
6.3 调试与测试技巧
- 边界测试:0值、最大值、特殊格式
- 中间输出:关键步骤打印中间结果
- 对拍测试:与已知正确代码对比结果
在实际编程竞赛中,这些问题的解决不仅需要扎实的算法基础,还需要对编程语言的熟练掌握和对问题边界的敏锐洞察。通过系统化的训练和不断的实践,可以显著提高解决此类问题的能力和效率。
