NOIP 常用模板的整理与总结
参加NOIP竞赛时,熟练掌握一些常用的编程模板可以提高解题效率,下面是一些常见的NOIP编程模板整理与总结:
基础I/O处理
#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int num;
cin >> num;
cout << num << endl;
}
return 0;
}
数学相关
最小公倍数与最大公约数
#include <iostream>
using namespace std;
// 计算最大公约数
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
// 计算最小公倍数
int lcm(int a, int b) {
return a / gcd(a, b) * b;
}
int main() {
int a, b;
cin >> a >> b;
cout << "GCD: " << gcd(a, b) << endl;
cout << "LCM: " << lcm(a, b) << endl;
return 0;
}
排序算法
快速排序
#include <iostream>
using namespace std;
void quickSort(int arr[], int left, int right) {
int i = left, j = right;
int pivot = arr[(left + right) / 2];
while (i <= j) {
while (arr[i] < pivot) i++;
while (arr[j] > pivot) j--;
if (i <= j) {
swap(arr[i], arr[j]);
i++;
j--;
}
}
if (left < j) quickSort(arr, left, j);
if (i < right) quickSort(arr, i, right);
}
int main() {
int arr[] = {3, 6, 8, 10, 1, 2, 1};
int n = sizeof(arr)/sizeof(arr[0]);
quickSort(arr, 0, n-1);
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
return 0;
}
图论相关
深度优先搜索(DFS)
#include <iostream>
#include <vector>
using namespace std;
vector<bool> visited;
vector<vector<int>> adj;
void dfs(int v) {
visited[v] = true;
cout << v << " ";
for (int u : adj[v]) {
if (!visited[u]) {
dfs(u);
}
}
}
int main() {
int n, m; // n 是顶点数, m 是边数
cin >> n >> m;
adj.resize(n);
visited.resize(n, false);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u); // 无向图
}
dfs(0); // 从顶点0开始DFS
return 0;
}
动态规划
0-1背包问题
#include <iostream>
#include <vector>
using namespace std;
int knapsack(int W, vector<int>& wt, vector<int>& val, int n) {
vector<int> dp(W+1, 0);
for (int i = 0; i < n; i++) {
for (int w = W; w >= wt[i]; w--) {
dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
}
}
return dp[W];
}
int main() {
int W = 50; // 背包容量
vector<int> wt = {10, 20, 30};
vector<int> val = {60, 100, 120};
int n = wt.size();
cout << "Maximum value in Knapsack = " << knapsack(W, wt, val, n) << endl;
return 0;
}
这些模板涵盖了NOIP竞赛中常见的一些问题和算法,熟悉并灵活应用这些模板可以帮助你更好地准备竞赛。在使用这些模板时,注意根据实际题目需求进行调整和优化。