提示信息

NOIP 常用模板的整理与总结

呓语 已关注

参加NOIP竞赛时,熟练掌握一些常用的编程模板可以提高解题效率,下面是一些常见的NOIP编程模板整理与总结:

基础I/O处理

  1. #include <iostream>
  2. using namespace std;
  3. int main() {
  4. ios::sync_with_stdio(false);
  5. cin.tie(0);
  6. int n;
  7. cin >> n;
  8. for (int i = 0; i < n; i++) {
  9. int num;
  10. cin >> num;
  11. cout << num << endl;
  12. }
  13. return 0;
  14. }

数学相关

最小公倍数与最大公约数

  1. #include <iostream>
  2. using namespace std;
  3. // 计算最大公约数
  4. int gcd(int a, int b) {
  5. return b == 0 ? a : gcd(b, a % b);
  6. }
  7. // 计算最小公倍数
  8. int lcm(int a, int b) {
  9. return a / gcd(a, b) * b;
  10. }
  11. int main() {
  12. int a, b;
  13. cin >> a >> b;
  14. cout << "GCD: " << gcd(a, b) << endl;
  15. cout << "LCM: " << lcm(a, b) << endl;
  16. return 0;
  17. }

排序算法

快速排序

  1. #include <iostream>
  2. using namespace std;
  3. void quickSort(int arr[], int left, int right) {
  4. int i = left, j = right;
  5. int pivot = arr[(left + right) / 2];
  6. while (i <= j) {
  7. while (arr[i] < pivot) i++;
  8. while (arr[j] > pivot) j--;
  9. if (i <= j) {
  10. swap(arr[i], arr[j]);
  11. i++;
  12. j--;
  13. }
  14. }
  15. if (left < j) quickSort(arr, left, j);
  16. if (i < right) quickSort(arr, i, right);
  17. }
  18. int main() {
  19. int arr[] = {3, 6, 8, 10, 1, 2, 1};
  20. int n = sizeof(arr)/sizeof(arr[0]);
  21. quickSort(arr, 0, n-1);
  22. for (int i = 0; i < n; i++) {
  23. cout << arr[i] << " ";
  24. }
  25. return 0;
  26. }

图论相关

深度优先搜索(DFS)

  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. vector<bool> visited;
  5. vector<vector<int>> adj;
  6. void dfs(int v) {
  7. visited[v] = true;
  8. cout << v << " ";
  9. for (int u : adj[v]) {
  10. if (!visited[u]) {
  11. dfs(u);
  12. }
  13. }
  14. }
  15. int main() {
  16. int n, m; // n 是顶点数, m 是边数
  17. cin >> n >> m;
  18. adj.resize(n);
  19. visited.resize(n, false);
  20. for (int i = 0; i < m; i++) {
  21. int u, v;
  22. cin >> u >> v;
  23. adj[u].push_back(v);
  24. adj[v].push_back(u); // 无向图
  25. }
  26. dfs(0); // 从顶点0开始DFS
  27. return 0;
  28. }

动态规划

0-1背包问题

  1. #include <iostream>
  2. #include <vector>
  3. using namespace std;
  4. int knapsack(int W, vector<int>& wt, vector<int>& val, int n) {
  5. vector<int> dp(W+1, 0);
  6. for (int i = 0; i < n; i++) {
  7. for (int w = W; w >= wt[i]; w--) {
  8. dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
  9. }
  10. }
  11. return dp[W];
  12. }
  13. int main() {
  14. int W = 50; // 背包容量
  15. vector<int> wt = {10, 20, 30};
  16. vector<int> val = {60, 100, 120};
  17. int n = wt.size();
  18. cout << "Maximum value in Knapsack = " << knapsack(W, wt, val, n) << endl;
  19. return 0;
  20. }

这些模板涵盖了NOIP竞赛中常见的一些问题和算法,熟悉并灵活应用这些模板可以帮助你更好地准备竞赛。在使用这些模板时,注意根据实际题目需求进行调整和优化。

    遇到难题? "AI大模型GPT4.0、GPT" 是你的私人解答专家! 点击按钮去提问......
呓语 关注 已关注

最近一次登录:2024-11-20 06:16:25   

暂时还没有签名,请关注我或评论我的文章
×
免费图表工具,画流程图、架构图