蓝桥杯作为国内知名的编程竞赛，吸引了无数编程爱好者的参与。在备考过程中，掌握常用的算法和数据结构是至关重要的。本文将为大家整理并解析算法竞赛中常用的代码片段，涵盖分输入输出、排序、查找以及图论模板，并附上注释版的C++、Java和Python代码，帮助大家更好地备考。
一、分输入输出
在算法竞赛中，输入输出的效率直接影响程序的运行时间。以下是几种常见的输入输出方式：
C++
#include <iostream>
using namespace std;
int main() {
ios::sync_with_stdio(false); // 关闭同步，提高输入输出效率
cin.tie(0);
int n;
cin >> n; // 输入一个整数
cout<< n << endl; // 输出一个整数
return 0;
}
Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 输入一个整数
System.out.println(n); // 输出一个整数
scanner.close();
}
}
Python
import sys
input = sys.stdin.read
data = input().split()
n = int(data[0]) # 输入一个整数
print(n) # 输出一个整数
二、排序
排序是算法竞赛中最基础的操作之一。常用的排序算法包括快速排序、归并排序和堆排序等。
C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
vector<int> arr = {3, 1, 4, 1, 5, 9};
sort(arr.begin(), arr.end()); // 使用STL的sort函数进行排序
for (int num : arr) {
cout << num << " ";
}
return 0;
}
Java
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] arr = {3, 1, 4, 1, 5, 9};
Arrays.sort(arr); // 使用Arrays.sort进行排序
for (int num : arr) {
System.out.print(num + " ");
}
}
}
Python
arr = [3, 1, 4, 1, 5, 9]
arr.sort() # 使用列表的sort方法进行排序
for num in arr:
print(num, end=" ")
三、查找
查找算法在处理大数据时尤为重要。常用的查找算法包括二分查找和哈希表查找。
C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int binarySearch(vector<int>& arr, int target) {
int left = 0, right = arr.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1; // 未找到
}
int main() {
vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int target = 5;
int index = binarySearch(arr, target);
if (index != -1) cout << "Found at index " << index << endl;
else cout << "Not found" << endl;
return 0;
}
Java
import java.util.Arrays;
public class Main {
public static int binarySearch(int[] arr, int target) {
int left = 0, right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) left = mid + 1;
else right = mid - 1;
}
return -1; // 未找到
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int target = 5;
int index = binarySearch(arr, target);
if (index != -1) System.out.println("Found at index " + index);
else System.out.println("Not found");
}
}
Python
def binary_search(arr, target):
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1 # 未找到
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 5
index = binary_search(arr, target)
if index != -1:
print(f"Found at index {index}")
else:
print("Not found")
四、图论模板
图论在算法竞赛中占有重要地位，常用的图论算法包括深度优先搜索（DFS）、广度优先搜索（BFS）和最短路径算法（如Dijkstra和Floyd）。
C++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void bfs(vector<vector<int>>& graph, int start) {
vector<bool> visited(graph.size(), false);
queue<int> q;
q.push(start);
visited[start] = true;
while (!q.empty()) {
int node = q.front();
q.pop();
cout << node << " ";
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
q.push(neighbor);
visited[neighbor] = true;
}
}
}
}
int main() {
vector<vector<int>> graph = {{1, 2}, {0, 2}, {0, 1, 3}, {2}};
bfs(graph, 0);
return 0;
}
Java
import java.util.*;
public class Main {
public static void bfs(List<List<Integer>> graph, int start) {
boolean[] visited = new boolean[graph.size()];
Queue<Integer> queue = new LinkedList<>();
queue.add(start);
visited[start] = true;
while (!queue.isEmpty()) {
int node = queue.poll();
System.out.print(node + " ");
for (int neighbor : graph.get(node)) {
if (!visited[neighbor]) {
queue.add(neighbor);
visited[neighbor] = true;
}
}
}
}
public static void main(String[] args) {
List<List<Integer>> graph = new ArrayList<>();
graph.add(Arrays.asList(1, 2));
graph.add(Arrays.asList(0, 2));
graph.add(Arrays.asList(0, 1, 3));
graph.add(Arrays.asList(2));
bfs(graph, 0);
}
}
Python
from collections import deque
def bfs(graph, start):
visited = [False] * len(graph)
queue = deque([start])
visited[start] = True
while queue:
node = queue.popleft()
print(node, end=" ")
for neighbor in graph[node]:
if not visited[neighbor]:
queue.append(neighbor)
visited[neighbor] = True
graph = [[1, 2], [0, 2], [0, 1, 3], [2]]
bfs(graph, 0)
总结
通过整理和解析常用的算法竞赛代码片段，我们可以更好地理解和掌握这些基础操作。在备考蓝桥杯时，熟练运用这些代码片段将大大提高解题效率。希望本文能为大家的备考之路提供一些帮助，祝大家在蓝桥杯中取得优异成绩！
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
