111
考点一：基础输入输出与模拟（难度：签到题 ★☆☆☆☆）
题目特征：题目描述较长，像是叙述一个过程或规则。不需要复杂算法，严格按照题意一步步实现即可。常见于第1、2题。
核心思想：仔细读题，注意边界条件。多用cout进行调试，输出中间变量。
必背模板：多组输入输出处理（这是ACM考题的标配）。
#include <iostream>
using namespace std;
int main() {
int t; // 测试组数
cin >> t;
while (t--) { // 处理t组数据
int n;
cin >> n;
int arr[1000]; // 假设最多1000个元素
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
// 你的处理代码...
cout << "结果" << endl; // 输出结果
}
return 0;
}考点二：排序与查找（难度：简单 ★★☆☆☆）
题目特征：对一组数据排序后输出、求第K大/小的数、在有序数组中查找某个值的位置。
核心思想：直接用STL sort/lower_bound。
必背模板：
1.冒泡排序
#include <iostream>
using namespace std;
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n-1-i; j++) {
if (arr[j] > arr[j+1]) {
// 交换
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
int main() {
int n;
cin >> n;
int arr[1000];
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
// 排序
bubbleSort(arr, n);
// 输出结果
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << endl;
return 0;
}
2.查找最大/最小值 #include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int arr[1000];
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
// 找最大值
int maxVal = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > maxVal) {
maxVal = arr[i];
}
}
// 找最小值
int minVal = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] < minVal) {
minVal = arr[i];
}
}
cout << "最大值: " << maxVal << endl;
cout << "最小值: " << minVal << endl;
return 0;
}
3.二分查找
#include <iostream>
using namespace std;
int main() {
int n, target;
cin >> n >> target;
int arr[1000];
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
int left = 0, right = n-1;
bool found = false;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == target) {
cout << "找到，位置: " << mid << endl;
found = true;
break;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
if (!found) {
cout << "未找到" << endl;
}
return 0;
}
考点三：贪心算法（难度：中等 ★★★☆☆）
题目特征：问题可以分解成一系列步骤，每一步都采取当前状态下最优选择（局部最优），从而希望导致全局最优。常考：区间调度、简单背包、哈夫曼编码（合并果子）。
核心思想：先排序，再贪心。关键是证明（考试时想不出就直接写，有步骤分）。
必背模板：活动选择（简化版）
#include <iostream>
using namespace std;
int main() {
int n; // 活动数量
cin >> n;
int start[1000], end[1000];
for (int i = 0; i < n; i++) {
cin >> start[i] >> end[i];
}
// 按结束时间排序（用冒泡排序）
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n-1-i; j++) {
if (end[j] > end[j+1]) {
// 交换结束时间
int temp = end[j];
end[j] = end[j+1];
end[j+1] = temp;
// 同时交换开始时间
temp = start[j];
start[j] = start[j+1];
start[j+1] = temp;
}
}
}
// 贪心选择
int count = 1; // 至少能安排一个活动
int lastEnd = end[0];
for (int i = 1; i < n; i++) {
if (start[i] >= lastEnd) {
count++;
lastEnd = end[i];
}
}
cout << count << endl;
return 0;
考点四：动态规划 - 经典线性DP（难度：中上 ★★★★☆）
题目特征：求“最值”、“总数”、“是否可行”。问题可以被分解为重叠的子问题。目录中第9章就是动态规划。
核心思想：定义 dp[i]或 dp[i][j]数组的含义 -> 找出状态转移方程 -> 确定初始值 -> 计算顺序。
必背模板1：斐波那契/爬楼梯（入门理解）
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int dp[1000]; // dp[i]表示第i个斐波那契数
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
cout << dp[n] << endl;
return 0;
}
必背模板2：简单路径
#include <iostream>
using namespace std;
int main() {
int n, m; // n行m列的网格
cin >> n >> m;
int dp[100][100]; // dp[i][j]表示到达(i,j)的路径数
// 初始化第一行和第一列
for (int i = 0; i < n; i++) dp[i][0] = 1;
for (int j = 0; j < m; j++) dp[0][j] = 1;
// 计算其他位置
for (int i = 1; i < n; i++) {
for (int j = 1; j < m; j++) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
cout << dp[n-1][m-1] << endl;
return 0;
}
必背模板3：简单背包问题（贪心版）
#include <iostream>
using namespace std;
int main() {
int n, capacity; // n个物品，背包容量
cin >> n >> capacity;
int weight[1000], value[1000];
for (int i = 0; i < n; i++) {
cin >> weight[i] >> value[i];
}
// 计算性价比（价值/重量）并排序
double ratio[1000];
int index[1000];
for (int i = 0; i < n; i++) {
ratio[i] = (double)value[i] / weight[i];
index[i] = i;
}
// 按性价比排序（降序）
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n-1-i; j++) {
if (ratio[j] < ratio[j+1]) {
// 交换ratio
double tempRatio = ratio[j];
ratio[j] = ratio[j+1];
ratio[j+1] = tempRatio;
// 交换index
int tempIndex = index[j];
index[j] = index[j+1];
index[j+1] = tempIndex;
}
}
}
// 贪心选择
int currentWeight = 0;
double totalValue = 0.0;
for (int i = 0; i < n; i++) {
int idx = index[i];
if (currentWeight + weight[idx] <= capacity) {
currentWeight += weight[idx];
totalValue += value[idx];
}
}
cout << "最大价值: " << totalValue << endl;
return 0;
}}
考点五：并查集（难度：中等 ★★★☆☆）
题目特征：题目中出现“朋友的朋友是朋友”、“连通性”、“分组”、“合并集合”等关键词。目录第10章就是并查集。
核心思想：维护一个father数组，实现find（查找根节点+路径压缩）和merge（合并集合）两个函数。
必背模板：
#include <iostream>
using namespace std;
int father[1000]; // 假设最多1000个元素
// 初始化
void init(int n) {
for (int i = 1; i <= n; i++) {
father[i] = i;
}
}
// 查找（递归版本，带路径压缩）
int find(int x) {
if (father[x] != x) {
father[x] = find(father[x]);
}
return father[x];
}
// 合并
void merge(int a, int b) {
int rootA = find(a);
int rootB = find(b);
if (rootA != rootB) {
father[rootA] = rootB;
}
}
int main() {
int n, m; // n个元素，m个操作
cin >> n >> m;
init(n);
for (int i = 0; i < m; i++) {
int op, a, b;
cin >> op >> a >> b;
if (op == 1) { // 合并操作
merge(a, b);
} else if (op == 2) { // 查询操作
if (find(a) == find(b)) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
}
return 0;
}
补充：
判断素数
#include <iostream>
#include <cmath>
using namespace std;
bool isPrime(int n) {
if (n <= 1) return false;
for (int i = 2; i <= sqrt(n); i++) {
if (n % i == 0) return false;
}
return true;
}
int main() {
int n;
cin >> n;
if (isPrime(n)) {
cout << n << " 是素数" << endl;
} else {
cout << n << " 不是素数" << endl;
}
return 0;
}
求最大公约数（欧几里得算法）
#include <iostream>
using namespace std;
int gcd(int a, int b) {
while (b != 0) {
int temp = a % b;
a = b;
b = temp;
}
return a;
}
int main() {
int a, b;
cin >> a >> b;
cout << gcd(a, b) << endl;
return 0;
}
简单递归：阶乘计算
#include <iostream>
using namespace std;
int factorial(int n) {
if (n <= 1) {
return 1;
}
return n * factorial(n-1);
}
int main() {
int n;
cin >> n;
cout << factorial(n) << endl;
return 0;
}
字符串处理（统计字符）：
#include <iostream>
#include <cstring> // 使用strlen函数
using namespace std;
int main() {
char str[1000];
cin >> str; // 或 cin.getline(str, 1000) 读取整行
int len = strlen(str);
int letter = 0, digit = 0, other = 0;
for (int i = 0; i < len; i++) {
if ((str[i] >= 'a' && str[i] <= 'z') ||
(str[i] >= 'A' && str[i] <= 'Z')) {
letter++;
} else if (str[i] >= '0' && str[i] <= '9') {
digit++;
} else {
other++;
}
}
cout << "字母: " << letter << endl;
cout << "数字: " << digit << endl;
cout << "其他: " << other << endl;
return 0;
}
考场快速索引指南
1、读题后，快速判断类型：
问“怎么安排最多” -> 先想贪心（排序+遍历）。
问“最大价值/最小代价/有多少种方法” -> 先想动态规划（背包、线性DP）。
问“是否连通/是否同一组” -> 直接上并查集模板。
题目描述就是步骤 -> 模拟，小心实现。
需要先排序或找位置 -> 直接用STL sort/lower_bound。
2、写代码的步骤：
1.第一步：写好头文件#include <bits/stdc++.h>和using namespace std;（竞赛万能头，节省时间）。
2.第二步：根据判断的类型，把对应数据结构的定义和核心函数先抄上去（比如dp数组定义，并查集类）。
3.第三步：再根据题目具体要求，修改main函数里的输入输出和逻辑细节。
考试策略
先看输入输出格式：严格按照题目要求的格式
判断问题类型：
排序 → 用冒泡排序
找最大/最小 → 遍历比较
计数/统计 → 遍历累加
路径/组合 → 考虑动态规划
最优选择 → 考虑贪心
