章节概述
字符串是字符序列，在算法竞赛中常见的操作包括遍历、查找、替换、转换等。
C++ string 类提供了丰富的成员函数。
核心原理
1. 字符串的底层表示
- C 风格: char 数组，以 ‘\0’ 结尾
- C++ string: 动态分配，自动管理内存
2. 核心操作复杂度
| 操作 | 复杂度 | 说明 |
|---|---|---|
| s[i] | O(1) | 下标访问 |
| s.size() | O(1) | 返回长度 |
| s.find(c) | O(n) | 查找字符/子串 |
| s.substr(pos, len) | O(len) | 截取子串 |
| s.erase(0, 1) | O(n) | 删除首字符需移动 |
3. 字符处理技巧
- 字符转数字:
c - '0' - 字符下标映射:
c - 'a'→ [0, 25] - 小写转大写:
c - 32或toupper(c) - 数字反转:
while(n) { rev = rev*10 + n%10; n /= 10; }
关键数据结构
- E_容器_Container — string 是特殊的 vector
P5015 [NOIP2018 普及组] 标题统计
题目: 给定一行字符串标题，统计其中英文字符和数字字符的总数。
#include <iostream>
#include <string>
using namespace std;
int main() {
string s;
getline(cin, s);
int cnt = 0;
for (char c : s)
if (c != ' ' && c != '\n')
cnt++;
cout << cnt << endl;
return 0;
}P1765 手机
题目: 手机键盘上字母分布，每个字母在键上的位置决定按键次数。求总按键次数。
#include <iostream>
#include <string>
using namespace std;
int main() {
string k[] = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
string s;
getline(cin, s);
int ans = 0;
for (char c : s) {
if (c == ' ') { ans++; continue; }
for (int i = 0; i < 8; i++) {
int pos = k[i].find(c);
if (pos != string::npos) {
ans += pos + 1;
break;
}
}
}
cout << ans << endl;
return 0;
}P1553 数字反转（升级版）
题目: 给定一个数（可能为整数、小数、分数或百分数），反转其数字部分。
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
string rev(string s) {
reverse(s.begin(), s.end());
while (s.size() > 1 && s[0] == '0') s.erase(0, 1);
return s;
}
int main() {
string s;
cin >> s;
if (s.find('.') != string::npos) {
int pos = s.find('.');
string a = s.substr(0, pos), b = s.substr(pos + 1);
while (b.size() > 1 && b.back() == '0') b.pop_back();
cout << rev(a) << "." << rev(b) << endl;
} else if (s.find('/') != string::npos) {
int pos = s.find('/');
cout << rev(s.substr(0, pos)) << "/" << rev(s.substr(pos + 1)) << endl;
} else if (s.back() == '%') {
s.pop_back();
cout << rev(s) << "%" << endl;
} else {
cout << rev(s) << endl;
}
return 0;
}推荐练习题（洛谷）
相关技巧
多平台练习
| 洛谷 | 本题单 | 竞赛基础 |
| POJ (北大) | PKU JudgeOnline | 经典题目，适合巩固 |
| HDU (杭电) | HDU OJ | 暑期多校训练 |
| Codeforces | Codeforces | 国际竞赛，适合提升 |