This collection presents fundamental algorithms and their applications to simple problems, primari sourced from the Lanqiao Cup competition. The problems are relatively straightforward, focusing more on algorithm templates and basic approaches. For better algorithm retention, the implementations are concise, frequently utilizing built-in C++ functions. Note that the time complexity may not be optimal in all cases.
Common Functions
C++ Vector Functions: Usage and Examples
C++ Sort Function: Usage, Principles, and Case Studies
C++ String Functions: Basic Operations and Usage
C++ Queue Implemantation and Usage
C++ Pair: Detailed Usage Guide
C++ Map: Common Operations and Examples
C++ Set: Comprehensive Guide
Maze BFS
- Maze Navigation - Lanqiao Cloud Course
#include <iostream>
#include <queue>
#include <vector>
#include <climits>
// Maximum maze dimensions
const int MAX_SIZE = 100;
// Direction vectors for up, down, left, right movements
const int rowMoves[] = {-1, 1, 0, 0};
const int colMoves[] = {0, 0, -1, 1};
// Maze grid and visited tracking
std::vector<std::vector<int>> maze(MAX_SIZE, std::vector<int>(MAX_SIZE));
std::vector<std::vector<bool>> visited(MAX_SIZE, std::vector<bool>(MAX_SIZE, false));
// Structure to represent a position in the maze
struct Position {
int row, col;
int steps;
int cost;
Position(int r, int c, int s, int t) : row(r), col(c), steps(s), cost(t) {}
};
// Function to find shortest path using BFS
int findPath(int startRow, int startCol, int endRow, int endCol, int rows, int cols) {
std::queue<Position> q;
q.push(Position(startRow, startCol, 0, 0));
visited[startRow][startCol] = true;
while (!q.empty()) {
Position current = q.front();
q.pop();
if (current.row == endRow && current.col == endCol) {
std::cout << "Steps from start to end: " << current.steps << std::endl;
std::cout << "Total cost from start to end: " << current.cost << std::endl;
return current.steps;
}
for (int i = 0; i < 4; ++i) {
int newRow = current.row + rowMoves[i];
int newCol = current.col + colMoves[i];
if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols &&
maze[newRow][newCol] > 0 && !visited[newRow][newCol]) {
int newSteps = current.steps + 1;
int newCost = current.cost + maze[newRow][newCol];
q.push(Position(newRow, newCol, newSteps, newCost));
visited[newRow][newCol] = true;
}
}
}
std::cout << "No path exists from start to end." << std::endl;
return -1;
}
int main() {
int rows, cols;
std::cout << "Enter maze dimensions (rows columns): ";
std::cin >> rows >> cols;
std::cout << "Enter maze layout (0 for wall, positive numbers for cost):" << std::endl;
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
std::cin >> maze[i][j];
}
}
int startRow, startCol, endRow, endCol;
std::cout << "Enter start position (row col): ";
std::cin >> startRow >> startCol;
std::cout << "Enter end position (row col): ";
std::cin >> endRow >> endCol;
// Convert to 0-based indexing
startRow--; startCol--; endRow--; endCol--;
// Reset visited array
for (int i = 0; i < rows; ++i) {
for (int j = 0; j < cols; ++j) {
visited[i][j] = false;
}
}
findPath(startRow, startCol, endRow, endCol, rows, cols);
return 0;
}
Difference Array
- Xiao Ming's Colorful Lights - Lanqiao Cloud Course
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n, q;
long long x;
int left, right;
cin >> n >> q;
vector<long long> lights(n);
for (int i = 0; i < n; i++)
{
cin >> lights[i];
}
vector<long long> diff(n + 1, 0);
for (int i = 0; i < q; i++)
{
cin >> left >> right >> x;
left--;
right--;
diff[left] += x;
if (right + 1 < n)
{
diff[right + 1] -= x;
}
}
// Compute prefix sum to get the actual differences
for (int i = 1; i < n; i++)
{
diff[i] += diff[i - 1];
}
// Apply differences to original array
for (int i = 0; i < n; i++)
{
lights[i] += diff[i];
}
return 0;
}
Palindrome String
- Palindrome Check - Lanqiao Cloud Course
#include <iostream>
#include <string>
using namespace std;
bool isPalindrome(const string& text) {
int left = 0;
int right = text.length() - 1;
while (left <= right) {
if (text[left] != text[right]) {
return false;
}
left++;
right--;
}
return true;
}
int main()
{
string input;
cin >> input;
if (isPalindrome(input)) {
cout << 'Y' << endl;
} else {
cout << 'N' << endl;
}
return 0;
}
Longest Increasing Subsequence
- Blue Bridge Knights - Lanqiao Cloud Course
Dynamic Programming Approach
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
int n;
cin >> n;
vector<int> sequence(n);
for(int i = 0; i < n; i++){
cin >> sequence[i];
}
vector<int> dp(n, 1);
for(int i = 1; i < n; i++){
for(int j = 0; j < i; j++){
if(sequence[i] > sequence[j]){
dp[i] = max(dp[i], dp[j] + 1);
}
}
}
int maxLength = 0;
for(int i = 0; i < n; i++){
maxLength = max(maxLength, dp[i]);
}
cout << maxLength << endl;
return 0;
}
Binary Search + Greedy Approach
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
int n;
cin >> n;
vector<int> sequence(n);
for(int i = 0; i < n; i++){
cin >> sequence[i];
}
vector<int> tail;
tail.push_back(sequence[0]);
for(int i = 1; i < n; i++){
if(sequence[i] > tail.back()){
tail.push_back(sequence[i]);
} else {
int pos = lower_bound(tail.begin(), tail.end(), sequence[i]) - tail.begin();
tail[pos] = sequence[i];
}
}
cout << tail.size() << endl;
return 0;
}
0-1 Knapsack
2D Dynamic Programming
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int itemCount, capacity;
cin >> itemCount >> capacity;
vector<int> weights, values;
for (int i = 0; i < itemCount; i++) {
int w, v;
cin >> w >> v;
weights.push_back(w);
values.push_back(v);
}
// Initialize DP table
vector<vector<int>> dp(itemCount + 1, vector<int>(capacity + 1, 0));
// Fill DP table
for (int i = 1; i <= itemCount; i++) {
for (int j = 0; j <= capacity; j++) {
if (j >= weights[i-1]) {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1]);
} else {
dp[i][j] = dp[i-1][j];
}
}
}
cout << dp[itemCount][capacity] << endl;
return 0;
}
1D Dynamic Programming
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int itemCount, capacity;
cin >> itemCount >> capacity;
vector<int> weights, values;
for (int i = 0; i < itemCount; i++) {
int w, v;
cin >> w >> v;
weights.push_back(w);
values.push_back(v);
}
// Initialize 1D DP array
vector<int> dp(capacity + 1, 0);
// Fill DP array in reverse order
for (int i = 0; i < itemCount; i++) {
for (int j = capacity; j >= weights[i]; j--) {
dp[j] = max(dp[j], dp[j-weights[i]] + values[i]);
}
}
cout << dp[capacity] << endl;
return 0;
}
Union-Find Data Structure
#include <iostream>
#include <vector>
using namespace std;
// Structure to represent a node in the union-find data structure
struct Node {
int id;
int parent;
// Constructor
Node(int i) : id(i), parent(i) {}
};
// Find the root of a node with path compression
int findRoot(vector<Node>& nodes, int x) {
if (nodes[x].parent == x) return x;
return nodes[x].parent = findRoot(nodes, nodes[x].parent);
}
int main() {
int N, M;
cin >> N >> M;
// Initialize nodes
vector<Node> nodes(N + 1);
for (int i = 1; i <= N; ++i) {
nodes[i] = Node(i);
}
// Process operations
for (int i = 0; i < M; ++i) {
int op, x, y;
cin >> op >> x >> y;
if (op == 1) {
// Union operation
int rootX = findRoot(nodes, x);
int rootY = findRoot(nodes, y);
if (rootX != rootY) {
nodes[rootX].parent = rootY;
}
} else {
// Find operation - check if connected
int rootX = findRoot(nodes, x);
int rootY = findRoot(nodes, y);
if (rootX == rootY) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
}
return 0;
}
Single Source Shortets Path
Traditional Dijkstra Algorithm
// Traditional Dijkstra algorithm using a visited array
vector<int> distances(V, INF);
vector<bool> processed(V, false);
distances[start] = 0;
for(int i = 0; i < V; ++i) {
int u = -1;
int minDist = INF;
// Find the closest unprocessed vertex
for(int j = 0; j < V; ++j) {
if(!processed[j] && distances[j] < minDist) {
u = j;
minDist = distances[j];
}
}
if(u == -1) break;
processed[u] = true;
// Update distances to adjacent vertices
for(const auto& edge : graph[u]) {
int v = edge.first;
int weight = edge.second;
if(distances[u] + weight < distances[v]) {
distances[v] = distances[u] + weight;
}
}
}
Priority Queue Optimized Dijkstra Algorithm
// Priority queue optimized Dijkstra algorithm
vector<long long> distances(N, INF);
distances[start] = 0;
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
pq.push({0, start});
while (!pq.empty()) {
long long currentDist = pq.top().first;
int u = pq.top().second;
pq.pop();
// Skip if we've already found a better path
if (currentDist > distances[u]) continue;
// Process all adjacent vertices
for (const auto& edge : graph[u]) {
int v = edge.first;
long long weight = edge.second;
if (distances[u] + weight < distances[v]) {
distances[v] = distances[u] + weight;
pq.push({distances[v], v});
}
}
}
- Lanqiao Kingdom - Lanqiao Cloud Course
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const long long INF = 1e18; // Sufficiently large value to represent infinity
// Optimized Dijkstra algorithm
void dijkstra(const vector<vector<pair<int, long long>>>& graph, int start) {
int N = graph.size();
vector<long long> distances(N, INF); // Initialize distances as infinity
distances[start] = 0; // Distance to self is 0
// Priority queue storing {distance, vertex}, sorted by distance
priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
pq.push({0, start});
while (!pq.empty()) {
long long currentDist = pq.top().first;
int u = pq.top().second;
pq.pop();
// Skip if we've already found a better path
if (currentDist > distances[u]) continue;
// Process all adjacent vertices
for (const auto& edge : graph[u]) {
int v = edge.first;
long long weight = edge.second;
// If we found a shorter path to v, update it
if (distances[u] + weight < distances[v]) {
distances[v] = distances[u] + weight;
pq.push({distances[v], v});
}
}
}
// Output results
for (int i = 0; i < N; i++) {
if (distances[i] == INF) {
cout << -1 << " ";
} else {
cout << distances[i] << " ";
}
}
cout << endl;
}
int main() {
int N, M;
cin >> N >> M;
// Adjacency list representation of the graph
vector<vector<pair<int, long long>>> graph(N);
// Read edge information
for (int i = 0; i < M; i++) {
int u, v;
long long w;
cin >> u >> v >> w;
// Convert to 0-based indexing
u--;
v--;
graph[u].emplace_back(v, w);
}
// Calculate shortest paths from the palace (vertex 0)
dijkstra(graph, 0);
return 0;
}
Prefix Sum
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
int n;
cin >> n;
vector<long long> numbers(n+1);
vector<long long> prefixSum(n+1, 0);
for(int i = 1; i <= n; i++){
cin >> numbers[i];
prefixSum[i] = prefixSum[i-1] + numbers[i];
}
vector<long long> subarraySums;
for(int i = 1; i <= n; i++){
for(int j = i; j <= n; j++){
subarraySums.push_back(prefixSum[j] - prefixSum[i-1]);
}
}
sort(subarraySums.begin(), subarraySums.end());
long long minDiff = 1e9;
for(int i = 1; i < subarraySums.size(); i++){
minDiff = min(minDiff, subarraySums[i] - subarraySums[i-1]);
}
cout << minDiff;
return 0;
}