C++ 算法竞赛编程要点总结
C++ 算法竞赛编程要点总结
1 常用算法与数据结构
参考相关算法资料进行系统学习。
2 STL 容器使用技巧
2.1 map 容器
#include <map>
#include <utility>
using namespace std;
typedef pair<int, int> coordinate;
// 初始化方式
map<string, coordinate> records = {{"Alice", make_pair(5, 850)}, {"Bob", make_pair(3, 875)}};
coordinate point;
map<string, coordinate> entries;
point = make_pair(5, 850);
entries.insert(make_pair("Alice", point));
// 迭代器操作
map<string, coordinate>::iterator iter;
string target = "Alice";
if(entries.count(target) > 0) {
iter = entries.find(target);
}
// 访问元素
int value = iter->second.first;
string key = iter->first;
2.2 pair 配对
typedef pair<int, int> coordinate;
coordinate point;
point = make_pair(5, 850);
int x = point.first;
int y = point.second;
2.3 queue 队列
void reset_queue(queue<Node>& q) {
queue<Node> empty_queue;
swap(empty_queue, q);
}
2.4 vector 向量
注意容器使用前需要清空操作（vec.clear(), while(!queue.empty()) queue.pop()）
// vector 的查找依赖 algorithm 库
vector<int>::iterator pos = find(vec.begin(), vec.end(), 8);
if (pos != vec.end()) {
cout << *pos << endl;
} else {
cout << "Not found" << endl;
}
// count 函数类似使用
2.5 string 字符串
// 长度获取
int length = text.length();
int size = text.size();
// 排序
bool compare_strings(string a, string b) {
return a < b;
}
vector<string> result;
sort(result.begin(), result.end(), compare_strings);
// 字符串比较
string sample = "x";
if (sample[0] == 'x') { // 正确
cout << 1;
}
// if (sample == 'x') // 错误用法
// 清空操作
text.clear();
text.erase(pos, len);
3 编程技巧
3.1 浮点数精度处理
设置精度阈值 eps = 1e-9。当 fabs(a-b) < eps 时，视为 a == b。
fabs 和 abs 函数位于 cmath 头文件中。
3.2 结构体构造函数
struct TreeNode {
int value;
int depth;
int count;
TreeNode *left_child, *right_child;
TreeNode(int val) {
value = val;
depth = 1;
count = 1;
left_child = right_child = nullptr;
}
};
struct DataItem {
int number;
string content;
char symbol;
void setup(int a, string b, char c) {
this->number = a;
this->content = b;
this->symbol = c;
}
DataItem() : symbol(), content(), number() {}
DataItem(int a, string b, char c) : symbol(c), content(b), number(a) {}
} items[10];
items[1] = {7, "cpp", 'g'};
items[2].setup(8, "java", 'h');
items[3] = DataItem(9, "python", 'i');
3.3 动态内存分配
char* buffer = new char[size];
int *array = new int[10];
delete []array;
3.4 模运算特性
被除数 ÷ 除数 = 商 … 余数
余数 = 被除数 - 商 × 除数
% 运算符仅适用于整型操作数。
3.5 奇偶性判断
if (number & 1) { // 奇数
// 处理奇数逻辑
}
4 常见错误与注意事项
4.1 除零错误
避免 a/b > 6 的写法，改为 a > 6*b 的形式。
4.2 段错误 (Segmentation Fault)
- 字符串常量修改：char *ptr = "hello"; ptr[0] = 'H'; // 错误
- 缺少地址符：scanf("%d", num); 应为 scanf("%d", &num);
- 空指针解引用：int *p = nullptr; *p = 1;
- 数组越界访问
- 栈溢出
4.3 类型转换问题
注意 int、double、long long 等类型的正确使用及对应的输出格式符。
4.4 变量作用域
避免全局变量命名冲突，注意函数内部变量覆盖问题。
5 实用函数库
5.1 cctype 库
包含 isalpha, isdigit 等字符判断函数。
5.2 数学函数
#include <cmath>
double square_root = sqrt(number);
double power_result = pow(base, exponent);
int integer_abs = abs(integer_value);
double floating_abs = fabs(float_value);
5.3 排序函数
推荐使用 sort 函数：
sort(array, array + length, comparator);
sort(vector.begin(), vector.end());
6 输入输出处理
6.1 scanf/printf 返回值
- 正整数：成功读取的参数个数
- 0：输入格式不匹配
- EOF(-1)：输入流结束
6.2 输入结束判断
// 方法1
while(scanf("%d", &value) == 1)
// 方法2
while(cin >> value)
6.3 处理含空格字符串
使用 getline 函数避免 cin 对空格的截断：
string line;
getline(cin, line);
7 数学基础
7.1 几何公式
- 余弦定理：cos A = (b² + c² - a²) / (2bc)
- 正弦定理：a/sinA = b/sinB = c/sinC = 2R
- 海伦公式：S = √[p(p-a)(p-b)(p-c)]，其中 p = (a+b+c)/2
7.2 行列式计算
二阶、三阶行列式可用对角线法则计算。行列式的几何意义是线性变换的伸缩比例因子。
性能考量
现代计算机大约每秒可执行 10^7-10^8 条简单指令。算法复杂度应控制在合理范围内，通常百万级别较为安全。
