蓝桥杯大纲知识点详解

大学C组

1. 枚举[1-3]

模板

// 枚举模板
for (int i = 0; i < n; i++) {
    // 枚举逻辑
}

解题思路

• 遍历所有可能的情况
• 适用于数据规模较小的问题

题目特征

• 数据范围小(n ≤ 20)
• 需要穷举所有可能性

时间复杂度

• O(n) 或 O(n^k)

例题

1. Codeforces 1A - Theatre Square

static void solve() {
    	long n = FIO.l();
    	long k = FIO.l();
    	Map<Long,Long> m = new HashMap<>();
  
    	long minn = Integer.MAX_VALUE;
    	for(long i = 0 ; i < n ; i++) {
        	long x = FIO.l();
        	long t = Math.min(i + 1, n - i);
        	if(m.containsKey(k - x) && x * 2 != k) {
        		minn = Math.min(minn,Math.max(m.get(k - x),t));
        	}
        	if(m.containsKey(x)){
        		m.put(x, Math.min(m.get(x), t));
        	}
        	else m.put(x,t);
    	}
        FIO.P(minn == Integer.MAX_VALUE ? -1 : minn);
    }

2. LeetCode 78 - 子集
   枚举所有子集

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> path  = new ArrayList<>();
    int [] nums;
    int n;
    void dfs(int i) {
    	if(i == n) {
    		ans.add(new ArrayList<>(path));
            return;
    	}
        dfs(i + 1);
        path.add(nums[i]);
        dfs(i + 1);
        path.remove(path.size() - 1);
    }
    void solve() {
    	n = nums.length;
    	dfs(0);
    }
    public List<List<Integer>> subsets(int[] nums) {
        this.nums = nums;
        solve();
        return ans;
    }
}

二进制枚举

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        int n = nums.length;
    	List<List<Integer>> ans = new ArrayList<>();
    	for(int i = 0 ; i < 1<<n;i++) {
    	    List<Integer> path = new ArrayList<>(); 
    		for(int j = 0 ; j < n ; j ++ ) {
    			if((i >> j  & 1 )== 1) {
    				path.add(nums[j]);
    			}
    		}
    		ans.add(path);
    	}
    	return ans;
    }
}

3. Codeforces 1A - Theatre Square

static void solve() {
    	long n = FIO.l();
    	long m = FIO.l();
    	long a = FIO.l();
    	FIO.P(((m + a - 1) / a) * ((n + a - 1) / a));
    }

2. 排序

(1) 冒泡排序[2]

// 冒泡排序模板
for (int i = 0; i < n-1; i++) {
    for (int j = 0; j < n-i-1; j++) {
        if (arr[j] > arr[j+1]) {
            // 交换
            int temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
        }
    }
}

解题思路

• 相邻元素两两比较
• 每一轮将最大的元素冒泡到最后

题目特征

• 需要稳定排序
• 数据规模小(n ≤ 1000)

时间复杂度

• O(n^2)

例题

1. Codeforces 451B - Sort the Array

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(); // 输入数组的大小
        int[] a = new int[n];
        int[] b = new int[n];

        // 读取数组元素
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
            b[i] = a[i];
        }

        // 使用TreeMap来存储元素及其索引
        Map<Integer, Integer> mp = new HashMap<>();
        Arrays.sort(b);

        // 建立元素值到索引的映射
        for (int i = 0; i < n; i++) {
            mp.put(b[i], i);
        }

        // 将原数组元素替换为其在排序数组中的索引
        for (int i = 0; i < n; i++) {
            a[i] = mp.get(a[i]);
        }

        int L = -1;
        for (int i = 0; i < n; i++) {
            if (a[i] != i) {
                L = i;
                break;
            }
        }

        int R = -1;
        for (int i = n - 1; i >= 0; i--) {
            if (a[i] != i) {
                R = i;
                break;
            }
        }

        if (L == -1 || R == -1) {
            System.out.println("yes");
            System.out.println(1 + " " + 1);
        } else {
            // 反转子数组
            reverse(a, L, R);
            boolean ok = true;
            for (int i = 0; i < n; i++) {
                if (a[i] != i) {
                    ok = false;
                    break;
                }
            }
            if (ok) {
                System.out.println("yes");
                System.out.println((L + 1) + " " + (R + 1));
            } else {
                System.out.println("no");
            }
        }
    }

    // 反转数组的辅助方法
    private static void reverse(int[] a, int L, int R) {
        while (L < R) {
            int temp = a[L];
            a[L] = a[R];
            a[R] = temp;
            L++;
            R--;
        }
    }
}

(2) 选择排序[3]

// 选择排序模板
for (int i = 0; i < n-1; i++) {
    int minIndex = i;
    for (int j = i+1; j < n; j++) {
        if (arr[j] < arr[minIndex]) {
            minIndex = j;
        }
    }
    // 交换
    int temp = arr[minIndex];
    arr[minIndex] = arr[i];
    arr[i] = temp;
}

解题思路

• 每次找到未排序部分的最小元素
• 将其放到已排序部分的末尾

题目特征

• 需要不稳定排序
• 数据规模小(n ≤ 1000)

时间复杂度

• O(n^2)

(3) 插入排序[3]

// 插入排序模板
for (int i = 1; i < n; i++) {
    int key = arr[i];
    int j = i-1;
    while (j >= 0 && arr[j] > key) {
        arr[j+1] = arr[j];
        j--;
    }
    arr[j+1] = key;
}

解题思路

• 将元素插入到已排序部分的适当位置
• 适用于部分有序的数据

题目特征

• 需要稳定排序
• 数据规模小(n ≤ 1000)

时间复杂度

• O(n^2)

3. 搜索(bfs, dfs)[1-5]

// BFS模板
Queue<Node> queue = new LinkedList<>();
queue.offer(startNode);
visited[start] = true;

while (!queue.isEmpty()) {
    Node current = queue.poll();
    // 处理当前节点
  
    for (Node neighbor : current.neighbors) {
        if (!visited[neighbor]) {
            visited[neighbor] = true;
            queue.offer(neighbor);
        }
    }
}

解题思路

• 使用队列实现
• 按层次遍历图或树
• 适合寻找最短路径问题

题目特征

• 需要寻找最短路径或最少步骤
• 图或树的遍历问题

时间复杂度

• O(V+E) (V是顶点数，E是边数)

例题

1. LeetCode 200 - 岛屿数量
2. Codeforces 580C - Kefa and Park

(2) DFS模板

// DFS模板
void dfs(Node node) {
    visited[node] = true;
    // 处理当前节点
  
    for (Node neighbor : node.neighbors) {
        if (!visited[neighbor]) {
            dfs(neighbor);
        }
    }
}

解题思路

• 使用递归或栈实现
• 深度优先遍历图或树
• 适合寻找所有可能解的问题

题目特征

• 需要遍历所有可能路径
• 排列组合问题
• 回溯问题

时间复杂度

• O(V+E) (V是顶点数，E是边数)

4. 贪心[1-5]

// 贪心算法模板
while (问题未解决) {
    // 选择当前最优解
    Solution best = selectBestOption();
  
    // 应用最优解
    applySolution(best);
  
    // 更新问题状态
    updateProblemState();
}

解题思路

• 每一步选择当前最优解
• 不回溯，不重新考虑之前的选择
• 需要证明贪心选择的正确性

题目特征

• 问题具有最优子结构
• 贪心选择能得到全局最优解
• 常见于区间调度、背包问题等

时间复杂度

• 通常为O(n)或O(nlogn)

例题

1. LeetCode 455 - 分发饼干
2. Codeforces 1353B - Two Arrays And Swaps

5. 模拟[1-3]

// 模拟算法模板
while (条件满足) {
    // 按照题目要求逐步执行
    step1();
    step2();
    // ...
  
    // 更新状态
    updateState();
}

解题思路

• 严格按照题目描述实现
• 逐步模拟题目描述的过程
• 注意边界条件和特殊情况

题目特征

• 题目描述详细且步骤明确
• 需要精确实现特定规则
• 常见于游戏规则模拟、物理过程模拟等

时间复杂度

• 通常为O(n)或O(n^2)

例题

1. 蓝桥杯练习系统 - 模拟题
2. LeetCode 54 - 螺旋矩阵
3. Codeforces 4A - Watermelon

6. 二分[2-5]

// 二分查找模板
int left = 0, right = n - 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; // 未找到

解题思路

• 适用于有序数组的查找
• 每次将搜索范围缩小一半
• 注意边界条件的处理

题目特征

• 数据已排序或可以排序
• 需要高效查找(优于O(n))
• 常见于查找特定值或满足条件的极值

时间复杂度

• O(logn)

例题

1. LeetCode 704 - 二分查找
2. Codeforces 812C - Sagheer and Nubian Market

7. DP(普通一维问题)[3-5]

// 一维DP模板
int[] dp = new int[n];
// 初始化
for (int i = 0; i < n; i++) {
    dp[i] = initialValue;
}

// 状态转移
for (int i = 1; i < n; i++) {
    dp[i] = Math.max(dp[i-1] + nums[i], nums[i]); // 示例状态转移方程
}

// 结果
return Arrays.stream(dp).max().getAsInt();

解题思路

• 定义状态dp[i]表示问题在i处的解
• 找出状态转移方程
• 初始化边界条件
• 按顺序计算dp数组

题目特征

• 问题可以分解为子问题
• 子问题之间有重叠
• 有最优子结构性质

时间复杂度

• 通常为O(n)

例题

1. 蓝桥杯练习系统 - 动态规划题
2. LeetCode 53 - 最大子数组和
3. Codeforces 580A - Kefa and First Steps

8. 高精度[1-5]

// 高精度加法模板
public static String add(String num1, String num2) {
    StringBuilder sb = new StringBuilder();
    int carry = 0;
    int i = num1.length() - 1, j = num2.length() - 1;
  
    while (i >= 0 || j >= 0 || carry != 0) {
        int x = i >= 0 ? num1.charAt(i--) - '0' : 0;
        int y = j >= 0 ? num2.charAt(j--) - '0' : 0;
        int sum = x + y + carry;
        sb.append(sum % 10);
        carry = sum / 10;
    }
    return sb.reverse().toString();
}

解题思路

• 使用字符串或数组表示大数
• 模拟手工计算过程
• 注意进位处理

题目特征

• 数字超出基本数据类型范围
• 需要精确计算
• 常见于大数加减乘除运算

时间复杂度

• O(n) 其中n为数字的位数

例题

1. 蓝桥杯练习系统 - 高精度计算题
2. LeetCode 415 - 字符串相加
3. Codeforces 1016A - Death Note

9. 数据结构

// 栈模板
Stack<Integer> stack = new Stack<>();
stack.push(1); // 入栈
int top = stack.peek(); // 获取栈顶元素
int pop = stack.pop(); // 出栈
boolean isEmpty = stack.isEmpty(); // 判断栈是否为空

解题思路

• 后进先出(LIFO)的数据结构
• 适用于需要回溯的场景
• 常用于括号匹配、表达式求值等问题

题目特征

• 需要记录访问顺序
• 需要撤销操作
• 需要匹配对称结构

时间复杂度

• 基本操作均为O(1)

例题

1. 蓝桥杯练习系统 - 数据结构题
2. LeetCode 20 - 有效的括号
3. Codeforces 546A - Soldier and Bananas

(2) 队列[2-5]

// 队列模板
Queue<Integer> queue = new LinkedList<>();
queue.offer(1); // 入队
int front = queue.peek(); // 获取队首元素
int poll = queue.poll(); // 出队
boolean isEmpty = queue.isEmpty(); // 判断队列是否为空

解题思路

• 先进先出(FIFO)的数据结构
• 适用于需要按顺序处理的场景
• 常用于BFS、滑动窗口等问题

题目特征

• 需要按顺序处理元素
• 需要维护一个处理序列
• 需要广度优先遍历

时间复杂度

• 基本操作均为O(1)

(3) 链表 [2-5]

// 链表节点定义
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

// 链表遍历模板
ListNode current = head;
while (current != null) {
    // 处理当前节点
    current = current.next;
}

解题思路

• 动态数据结构，节点通过指针连接
• 适用于频繁插入删除的场景
• 常用于实现其他数据结构

题目特征

• 需要频繁插入删除操作
• 数据规模动态变化
• 需要灵活的内存分配

时间复杂度

• 遍历为O(n)
• 插入删除为O(1)（已知位置）

10. 数学

// 判断质数模板
boolean isPrime(int n) {
    if (n <= 1) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

// 最大公约数模板(欧几里得算法)
int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

// 最小公倍数模板
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

解题思路

• 质数判断: 试除法
• 最大公约数: 欧几里得算法
• 最小公倍数: 基于最大公约数计算
• 适用于数论相关题目

题目特征

• 涉及质数、因数、倍数等问题
• 需要计算公约数或公倍数
• 常见于数学计算类题目

时间复杂度

• 质数判断: O(√n)
• 最大公约数: O(log(min(a,b)))

例题

1. 蓝桥杯练习系统 - 数学题
2. LeetCode 204 - 计数质数
3. Codeforces 231A - Team

大学B组

11. 排序算法

（1）归并排序[4-5]

// Java实现模板
public class MergeSort {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            merge(arr, left, mid, right);
        }
    }
  
    private static void merge(int[] arr, int left, int mid, int right) {
        // 合并两个有序子数组
    }
}

解题思路：

• 分治思想，先递归分解数组，再合并有序子序列
• 典型题目：逆序对问题、外部排序
• 时间复杂度：O(nlogn)

（2）快速排序[4-5]

// Java实现模板
public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivot = partition(arr, low, high);
            quickSort(arr, low, pivot - 1);
            quickSort(arr, pivot + 1, high);
        }
    }
  
    private static int partition(int[] arr, int low, int high) {
        // 分区操作
    }
}

解题思路：

• 选取基准值，将数组分为两部分
• 典型题目：TopK问题、中位数问题
• 时间复杂度：平均O(nlogn)，最坏O(n²)

（3）桶排序[4]

// Java实现模板
public class BucketSort {
    public static void bucketSort(int[] arr, int bucketSize) {
        // 创建桶并分配元素
        // 对每个桶进行排序
        // 合并所有桶
    }
}

解题思路：

• 将数据分到有限数量的桶里
• 典型题目：数据范围已知且分布均匀的情况
• 时间复杂度：O(n+k)

（4）堆排序[4]

// Java实现模板
public class HeapSort {
    public static void heapSort(int[] arr) {
        // 构建最大堆
        // 交换堆顶元素与末尾元素
        // 调整堆
    }
}

解题思路：

• 利用堆这种数据结构设计的排序算法
• 典型题目：优先级队列、实时求TopK
• 时间复杂度：O(nlogn)

（5）基数排序[4~5]

// Java实现模板
public class RadixSort {
    public static void radixSort(int[] arr) {
        // 获取最大位数
        // 按位进行计数排序
    }
}

解题思路：

• 按照低位先排序，然后收集；再按高位排序
• 典型题目：多关键字排序（如日期、电话号码）
• 时间复杂度：O(n*k)

12. 搜索算法

（1）剪枝[4-6]

解题思路：

• 在搜索过程中提前排除不可能的分支
• 典型题目：数独、八皇后问题

（2）双向BFS[5-6]

解题思路：

• 从起点和终点同时开始BFS
• 典型题目：单词接龙、迷宫最短路径

（3）记忆化搜索[5]

// Java实现模板
public class Memoization {
    int[] memo;
  
    public int dfs(int state) {
        if (memo[state] != 0) return memo[state];
        // 计算并存储结果
        memo[state] = result;
        return result;
    }
}

解题思路：

• 存储中间结果避免重复计算
• 典型题目：斐波那契数列、爬楼梯问题

（4）迭代加深搜索[5-6]

解题思路：

• 结合DFS和BFS，逐步增加深度限制
• 典型题目：IDA*算法、拼图问题

（5）启发式搜索[7]

解题思路：

• 使用估价函数指导搜索方向
• 典型题目：A*算法、八数码问题

13. 动态规划

（1）背包DP[4-6]

// 01背包模板
public class Knapsack {
    public static int knapsack(int[] weights, int[] values, int capacity) {
        int n = weights.length;
        int[][] dp = new int[n + 1][capacity + 1];
  
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= capacity; j++) {
                if (j >= weights[i - 1]) {
                    dp[i][j] = Math.max(dp[i - 1][j], 
                                      dp[i - 1][j - weights[i - 1]] + values[i - 1]);
                } else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        return dp[n][capacity];
    }
}

解题思路：

• 状态转移方程：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w]+v)
• 典型题目：01背包、完全背包、多重背包

（2）树形DP[4-6]

解题思路：

• 在树结构上进行动态规划
• 典型题目：二叉树中的最大路径和、树的最小支配集

题目描述
给定一棵树，每个节点有权值，选择节点时不能选相邻节点，求最大权值和。

定义 dp[i][0] 表示不选节点 i 时的最大值，dp[i][1] 表示选择节点 i 时的最大值。
状态转移：
dp[i][1] = sum(dp[child][0]) + val[i]
dp[i][0] = sum(max(dp[child][0], dp[child][1]))

// 树形DP核心（DFS遍历）
void dfs(int u, int parent) {
    dp[u][1] = val[u];
    for (int v : tree[u]) {
        if (v != parent) {
            dfs(v, u);
            dp[u][1] += dp[v][0];
            dp[u][0] += Math.max(dp[v][0], dp[v][1]);
        }
    }
}

（3）状压DP[5-6]

解题思路：

• 使用位运算表示状态
• 典型题目：旅行商问题、棋盘覆盖问题
• 例如，给定一个 n 个元素的集合，求所有子集的和。

例题

1. LeetCode 78 - 子集

// 位运算枚举所有子集
class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        int n = nums.length;
        for (int mask = 0; mask < (1 << n); mask++) {
            List<Integer> subset = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                if ((mask & (1 << i)) != 0) {
                    subset.add(nums[i]);
                }
            }
            res.add(subset);
        }
        return res;
    }
}

LeetCode 464 - 我能赢吗

// 状态压缩+记忆化搜索
class Solution {
    private Boolean[] memo;
    
    public boolean canIWin(int maxChoosableInteger, int desiredTotal) {
        if (maxChoosableInteger >= desiredTotal) return true;
        if ((1 + maxChoosableInteger) * maxChoosableInteger / 2 < desiredTotal) return false;
        
        memo = new Boolean[1 << (maxChoosableInteger + 1)];
        return dfs(0, maxChoosableInteger, desiredTotal);
    }
    
    private boolean dfs(int state, int max, int remain) {
        if (memo[state] != null) return memo[state];
        
        for (int i = 1; i <= max; i++) {
            if ((state & (1 << i)) != 0) continue;
            
            if (remain - i <= 0 || !dfs(state | (1 << i), max, remain - i)) {
                return memo[state] = true;
            }
        }
        return memo[state] = false;
    }
}

（4）数位DP[5-6]

解题思路：

• 处理数字位上的计数问题
• 典型题目：统计区间内满足条件的数字个数

题目描述
统计区间内满足特定条件的数字个数（如不含某数字）。
记忆化搜索：记录当前位数、前导零状态、限制状态等。
例如，统计 [a, b] 中不含数字 4 的数。

int dfs(int pos, boolean limit, boolean leadZero) {
    if (pos == num.length) return 1;
    if (!limit && !leadZero && dp[pos] != -1) return dp[pos];
    int res = 0;
    int up = limit ? num[pos] : 9;
    for (int i = 0; i <= up; i++) {
        if (i == 4) continue; // 排除数字4
        res += dfs(pos + 1, limit && (i == up), leadZero && (i == 0));
    }
    if (!limit && !leadZero) dp[pos] = res;
    return res;
}

区间DP

解题思路

• 在区间上进行动态规划
• 典型题目：区间合并、区间最小值
• 例如，给定一个区间 [l, r]，求区间内的最小值和最大值。

例题

1. LeetCode 312 - 戳气球

class Solution {
    public int maxCoins(int[] nums) {
        int n = nums.length;
        
        // 创建一个新的数组，两端添加1，方便处理边界条件
        // 例如，原数组是 [3,1,5,8]，扩展后变为 [1,3,1,5,8,1]
        int[] arr = new int[n + 2];
        System.arraycopy(nums, 0, arr, 1, n);
        arr[0] = arr[n + 1] = 1;
        
        // 创建动态规划表，dp[l][r] 表示从索引 l 到 r 的气球中能获得的最大硬币数
        int[][] dp = new int[n + 2][n + 2];
        
        // 遍历所有可能的区间长度，从1到n
        for (int len = 1; len <= n; len++) {
            // 遍历所有可能的左边界 l
            for (int l = 1; l + len - 1 <= n; l++) {
                // 计算右边界 r
                int r = l + len - 1;
                
                // 尝试每个中间点 k 作为最后一个被戳破的气球
                for (int k = l; k <= r; k++) {
                    // 状态转移方程：
                    // dp[l][r] = max(dp[l][r], dp[l][k-1] + dp[k+1][r] + arr[l-1] * arr[k] * arr[r+1])
                    // dp[l][k-1]：左边部分的最大硬币数
                    // dp[k+1][r]：右边部分的最大硬币数
                    // arr[l-1] * arr[k] * arr[r+1]：戳破第 k 个气球时获得的硬币数
                    dp[l][r] = Math.max(dp[l][r], 
                        dp[l][k - 1] + dp[k + 1][r] + arr[l - 1] * arr[k] * arr[r + 1]);
                }
            }
        }
        
        // 返回从索引1到n的最大硬币数
        return dp[1][n];
    }
}

516. 最长回文子序列 - 力（LeetCode）

class Solution {
    public int longestPalindromeSubseq(String s) {
        int n = s.length();
        
        // 创建一个二维动态规划表 dp，其中 dp[i][j] 表示从索引 i 到 j 的子串中最长回文子序列的长度
        int[][] dp = new int[n][n];
        
        // 填充动态规划表
        // 从右向左填充，确保计算 dp[i][j] 时，dp[i+1][j-1] 已经被计算过
        for (int i = n - 1; i >= 0; i--) {
            // 初始化 dp[i][i] 为 1，因为单个字符本身就是回文
            dp[i][i] = 1;
            
            // 获取当前字符
            char c1 = s.charAt(i);
            
            // 遍历从 i+1 到 n-1 的所有 j
            for (int j = i + 1; j < n; j++) {
                // 获取当前字符
                char c2 = s.charAt(j);
                
                // 如果字符相等，说明可以扩展一个回文子序列
                if (c1 == c2) {
                    // 状态转移方程：dp[i][j] = dp[i+1][j-1] + 2
                    // dp[i+1][j-1] 表示中间部分的最长回文子序列长度
                    // +2 是因为当前两个字符相等，可以扩展
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    // 如果字符不相等，取左右两边的最大值
                    // dp[i+1][j] 表示去掉左边字符后的最长回文子序列
                    // dp[i][j-1] 表示去掉右边字符后的最长回文子序列
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        
        // 返回整个字符串的最长回文子序列长度
        return dp[0][n - 1];
    }
}

（5）DP的常见优化[7]

1. 斜率优化（任务安排问题）
   洛谷P2365
   斜率优化解法

// 洛谷P2365 完整题解代码（需导入java.util.*）
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long S = sc.nextLong();
        
        // 前缀和数组（从1开始存储）
        long[] T = new long[n+1]; // 时间前缀和
        long[] C = new long[n+1]; // 费用前缀和
        for(int i = 1; i <= n; i++) {
            T[i] = T[i-1] + sc.nextLong();
            C[i] = C[i-1] + sc.nextLong();
        }
        
        // DP数组初始化
        long[] dp = new long[n+1];
        Arrays.fill(dp, Long.MAX_VALUE);
        dp[0] = 0; // 初始状态
        
        Deque<Integer> q = new ArrayDeque<>();
        q.addLast(0); // 初始决策点
        
        for(int i = 1; i <= n; i++) {
            // 维护队列头部的决策最优性（斜率比较）
            while(q.size() >= 2) {
                int j1 = q.pollFirst();
                int j2 = q.peekFirst();
                // 若斜率 (dp[j2]-dp[j1])/(C[j2]-C[j1]) <= S + T[i]
                if((dp[j2]-dp[j1]) <= (S + T[i]) * (C[j2]-C[j1])) {
                    continue; // 说明j1不是最优解
                } else {
                    q.addFirst(j1); // 恢复队列
                    break;
                }
            }
            
            int j = q.peekFirst();
            // 状态转移方程
            dp[i] = dp[j] + S*(C[n] - C[j]) + T[i]*(C[i] - C[j]);
            
            // 维护队列的凸包性质（后部斜率检查）
            while(q.size() >= 2) {
                int j1 = q.pollLast();
                int j2 = q.peekLast();
                // 比较两段斜率：j2->j1 与 j1->i
                long dy1 = dp[j1] - dp[j2];
                long dx1 = C[j1] - C[j2];
                long dy2 = dp[i] - dp[j1];
                long dx2 = C[i] - C[j1];
                
                // 若 dy1/dx1 >= dy2/dx2（避免除法，交叉相乘）
                if(dy1 * dx2 >= dy2 * dx1) {
                    continue; // 需要删除j1保持下凸
                } else {
                    q.addLast(j1); // 恢复队列
                    break;
                }
            }
            q.addLast(i); // 加入当前决策点
        }
        System.out.println(dp[n]);
    }
}

2. 四边形不等式优化（石子合并）

// 石子合并 O(n²)优化版
int[][] dp = new int[n+1][n+1];
int[][] s = new int[n+1][n+1]; // 决策点数组
int[] sum = new int[n+1]; // 前缀和

for (int i = 1; i <= n; i++) {
    sum[i] = sum[i-1] + a[i];
    s[i][i] = i; // 初始化决策点
}

for (int len = 2; len <= n; len++) {
    for (int i = 1; i <= n-len+1; i++) {
        int j = i + len - 1;
        dp[i][j] = Integer.MAX_VALUE;
        // 利用四边形不等式优化的决策范围
        for (int k = s[i][j-1]; k <= s[i+1][j]; k++) {
            int cost = dp[i][k] + dp[k+1][j] + sum[j] - sum[i-1];
            if (cost < dp[i][j]) {
                dp[i][j] = cost;
                s[i][j] = k; // 记录最优决策点
            }
        }
    }
}

3. 单调队列优化（滑动窗口最大值）

// 滑动窗口最大值 O(n)解法
public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    int[] res = new int[n - k + 1];
    Deque<Integer> q = new ArrayDeque<>(); // 存储下标
    
    for (int i = 0; i < n; i++) {
        // 移除超出窗口范围的元素
        while (!q.isEmpty() && q.peekFirst() <= i - k) {
            q.pollFirst();
        }
        
        // 维护单调递减队列
        while (!q.isEmpty() && nums[q.peekLast()] <= nums[i]) {
            q.pollLast();
        }
        
        q.offerLast(i);
        
        // 记录窗口最大值
        if (i >= k - 1) {
            res[i - k + 1] = nums[q.peekFirst()];
        }
    }
    return res;
}

14. 字符串算法

（1）哈希[4-5]

// 字符串哈希模板
public class StringHash {
    public static long getHash(String s) {
        long hash = 0;
        for (char c : s.toCharArray()) {
            hash = hash * 131 + c;
        }
        return hash;
    }
}

解题思路：

• 将字符串映射为唯一数值
• 典型题目：字符串匹配、重复子串检测

（2）KMP[4-6]

// KMP算法模板
public class KMP {
    public static int kmp(String text, String pattern) {
        // 构建next数组
        // 匹配过程
    }
}

解题思路：

• 利用部分匹配信息跳过不必要比较
• 典型题目：字符串匹配、循环节问题

（3）Manacher[4-6]

// Manacher算法模板
public class Manacher {
    public static String longestPalindrome(String s) {
        // 预处理字符串
        // 计算回文半径数组
    }
}

解题思路：

• 线性时间求最长回文子串
• 典型题目：最长回文子串、回文分割

15. 图论算法

（1）欧拉回路[5-7]

解题思路：

• 图中存在经过每条边恰好一次的回路
• 典型题目：一笔画问题、邮路问题

（2）最小生成树[5-7]

// Kruskal算法模板
public class Kruskal {
    public static int kruskal(int n, int[][] edges) {
        // 并查集实现
        // 按边权排序
        // 选择边
    }
}

解题思路：

• 连接所有顶点的最小权值子图
• 典型题目：城市道路建设、网络布线

（3）单源最短路及差分约束系统[5-7]

// Dijkstra算法模板
public class Dijkstra {
    public static int[] dijkstra(int[][] graph, int start) {
        // 优先队列实现
        // 松弛操作
    }
}

解题思路：

• 求从一个点到其他所有点的最短路径
• 典型题目：路由选择、差分约束系统

（4）拓扑序列[5-7]

解题思路：

• 有向无环图的线性排序
• 典型题目：课程安排、任务调度

（5）二分图匹配[7]

// 匈牙利算法模板
public class Hungarian {
    public static int maxMatch(int[][] graph) {
        // 匹配过程
    }
}

解题思路：

• 求二分图的最大匹配
• 典型题目：任务分配、婚姻匹配问题

（6）图的连通性问题[7]

解题思路：

• 割点、桥、强连通分量
• 典型题目：关键节点检测、网络脆弱性分析

（7）DFS序[5-7]

解题思路：

• 对树进行深度优先遍历得到的顺序
• 典型题目：子树查询、树链剖分

（8）最近共同祖先[5-7]

// LCA模板
public class LCA {
    public static int lca(int u, int v) {
        // 倍增法实现
    }
}

解题思路：

• 求树中两个节点的最近公共祖先
• 典型题目：家族关系查询、树路径问题

16. 数学

(1) 排列组合[5-6]

// 排列数模板
int permutation(int n, int k) {
    int res = 1;
    for (int i = 0; i < k; i++) {
        res *= (n - i);
    }
    return res;
}

// 组合数模板(递推法)
int combination(int n, int k) {
    if (k > n - k) k = n - k;
    int res = 1;
    for (int i = 1; i <= k; i++) {
        res = res * (n - k + i) / i;
    }
    return res;
}

// 组合数模板(动态规划)
int[][] initCombinationDP(int maxN) {
    int[][] C = new int[maxN + 1][maxN + 1];
    for (int i = 0; i <= maxN; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
        }
    }
    return C;
}

解题思路

• 排列: 考虑顺序的选择
• 组合: 不考虑顺序的选择
• 递推法和动态规划预处理

题目特征

• 需要计算选择方式数量
• 涉及概率或统计问题
• 常见于计数类题目

时间复杂度

• 递推法: O(k)
• 动态规划预处理: O(n^2)

(2) 二项式定理[6]

// 二项式展开模板
int[] binomialExpansion(int n) {
    int[] coefficients = new int[n + 1];
    coefficients[0] = 1;
  
    for (int i = 1; i <= n; i++) {
        coefficients[i] = coefficients[i - 1] * (n - i + 1) / i;
    }
    return coefficients;
}

解题思路

• 计算(x+y)^n展开式的系数
• 使用组合数计算各项系数
• 适用于多项式展开问题

题目特征

• 需要多项式展开
• 涉及组合数学问题
• 需要高效计算系数

时间复杂度

• O(n)

17. 数据结构

(1) ST表[5-6]

// ST表模板(区间最大值查询)
class SparseTable {
    int[][] st;
    int[] log;
  
    public SparseTable(int[] arr) {
        int n = arr.length;
        log = new int[n + 1];
        for (int i = 2; i <= n; i++) {
            log[i] = log[i / 2] + 1;
        }
  
        int k = log[n] + 1;
        st = new int[n][k];
  
        for (int i = 0; i < n; i++) {
            st[i][0] = arr[i];
        }
  
        for (int j = 1; j < k; j++) {
            for (int i = 0; i + (1 << j) <= n; i++) {
                st[i][j] = Math.max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
            }
        }
    }
  
    public int query(int l, int r) {
        int j = log[r - l + 1];
        return Math.max(st[l][j], st[r - (1 << j) + 1][j]);
    }
}

解题思路

• 预处理区间最值
• 支持O(1)查询
• 适用于静态区间查询

题目特征

• 需要频繁查询区间最值
• 数据静态不修改
• 查询次数远大于预处理时间

时间复杂度

• 预处理O(nlogn)
• 查询O(1)

(2) 堆[5-6]

// 堆模板(优先队列实现)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

// 自定义比较器
PriorityQueue<Item> customHeap = new PriorityQueue<>((a, b) -> a.priority - b.priority);

// 堆操作
heap.offer(1); // 插入
int top = heap.peek(); // 获取堆顶
int pop = heap.poll(); // 弹出堆顶

解题思路

• 完全二叉树结构
• 父节点优于子节点
• 高效获取极值

题目特征

• 需要频繁获取极值
• 需要动态维护有序集合
• 常见于调度问题

时间复杂度

• 插入O(logn)
• 获取极值O(1)
• 删除极值O(logn)

(3) 树状数组[5-6]

// 树状数组模板
class FenwickTree {
    int[] tree;
  
    public FenwickTree(int size) {
        tree = new int[size + 1];
    }
  
    public void update(int index, int delta) {
        while (index < tree.length) {
            tree[index] += delta;
            index += index & -index;
        }
    }
  
    public int query(int index) {
        int sum = 0;
        while (index > 0) {
            sum += tree[index];
            index -= index & -index;
        }
        return sum;
    }
}

解题思路

• 高效维护前缀和
• 支持单点更新和区间查询
• 二进制索引技术

题目特征

• 需要频繁更新和查询前缀和
• 数据动态变化
• 需要高效统计

时间复杂度

• 更新O(logn)
• 查询O(logn)

研究生及大学A组

19. 字符串

(1) AC自动机[7-8]

// AC自动机模板
class ACNode {
    ACNode[] children = new ACNode[26];
    ACNode fail;
    List<Integer> output;
}

class ACAutomaton {
    ACNode root;
  
    void buildTrie(String[] patterns) {
        root = new ACNode();
        for (int i = 0; i < patterns.length; i++) {
            ACNode current = root;
            for (char c : patterns[i].toCharArray()) {
                int index = c - 'a';
                if (current.children[index] == null) {
                    current.children[index] = new ACNode();
                }
                current = current.children[index];
            }
            if (current.output == null) {
                current.output = new ArrayList<>();
            }
            current.output.add(i);
        }
    }
  
    void buildFailureLinks() {
        Queue<ACNode> queue = new LinkedList<>();
        root.fail = null;
        queue.offer(root);
  
        while (!queue.isEmpty()) {
            ACNode current = queue.poll();
    
            for (int i = 0; i < 26; i++) {
                if (current.children[i] != null) {
                    ACNode child = current.children[i];
                    ACNode failNode = current.fail;
            
                    while (failNode != null && failNode.children[i] == null) {
                        failNode = failNode.fail;
                    }
            
                    child.fail = (failNode == null) ? root : failNode.children[i];
            
                    if (child.fail.output != null) {
                        if (child.output == null) {
                            child.output = new ArrayList<>();
                        }
                        child.output.addAll(child.fail.output);
                    }
            
                    queue.offer(child);
                }
            }
        }
    }
  
    List<Integer> search(String text) {
        List<Integer> result = new ArrayList<>();
        ACNode current = root;
  
        for (char c : text.toCharArray()) {
            int index = c - 'a';
            while (current != null && current.children[index] == null) {
                current = current.fail;
            }
            current = (current == null) ? root : current.children[index];
    
            if (current.output != null) {
                result.addAll(current.output);
            }
        }
        return result;
    }
}

解题思路

• 结合Trie树和KMP算法
• 构建失败指针实现高效多模式匹配
• 适用于大量模式串的匹配问题

题目特征

• 需要同时匹配多个模式串
• 文本串较长
• 模式串有公共前缀

时间复杂度

• 构建O(Σ|P|)
• 匹配O(|T| + m)

(2) 拓展kmp[7-8]

// 拓展kmp模板
int[] extendKMP(String s, String t) {
    int n = s.length(), m = t.length();
    int[] next = new int[m];
    int[] extend = new int[n];
  
    // 计算next数组
    next[0] = m;
    int a = 0, p = 0;
    for (int i = 1; i < m; i++) {
        if (i >= p || i + next[i - a] >= p) {
            if (i >= p) p = i;
            while (p < m && t.charAt(p) == t.charAt(p - i)) p++;
            next[i] = p - i;
            a = i;
        } else {
            next[i] = next[i - a];
        }
    }
  
    // 计算extend数组
    a = p = 0;
    for (int i = 0; i < n; i++) {
        if (i >= p || i + next[i - a] >= p) {
            if (i >= p) p = i;
            while (p < n && p - i < m && s.charAt(p) == t.charAt(p - i)) p++;
            extend[i] = p - i;
            a = i;
        } else {
            extend[i] = next[i - a];
        }
    }
    return extend;
}

解题思路

• 计算字符串每个位置的最长公共前缀
• 利用已匹配信息优化计算
• 适用于字符串匹配和比较问题

题目特征

• 需要比较字符串的所有后缀
• 需要高效计算最长公共前缀
• 常见于字符串匹配问题

时间复杂度

• O(n+m)

22. 字符串匹配算法

(1) KMP算法[7-8]

// KMP算法模板
int kmp(String text, String pattern) {
    int n = text.length(), m = pattern.length();
    int[] lps = computeLPS(pattern);
  
    int i = 0, j = 0;
    while (i < n) {
        if (text.charAt(i) == pattern.charAt(j)) {
            i++;
            j++;
            if (j == m) {
                return i - j; // 匹配成功
            }
        } else {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
    return -1; // 未匹配
}

int[] computeLPS(String pattern) {
    int m = pattern.length();
    int[] lps = new int[m];
    int len = 0, i = 1;
  
    while (i < m) {
        if (pattern.charAt(i) == pattern.charAt(len)) {
            lps[i++] = ++len;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i++] = 0;
            }
        }
    }
    return lps;
}

解题思路

• 预处理模式串生成部分匹配表
• 利用已匹配信息避免重复比较
• 线性时间复杂度

题目特征

• 需要高效字符串匹配
• 模式串有重复子串
• 适用于大文本搜索

时间复杂度

• O(n+m)

(2) Trie树[7-8]

// Trie树模板
class Trie {
    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isEnd;
    }
  
    private TrieNode root;
  
    public Trie() {
        root = new TrieNode();
    }
  
    public void insert(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new TrieNode();
            }
            node = node.children[idx];
        }
        node.isEnd = true;
    }
  
    public boolean search(String word) {
        TrieNode node = root;
        for (char c : word.toCharArray()) {
            int idx = c - 'a';
            if (node.children[idx] == null) {
                return false;
            }
            node = node.children[idx];
        }
        return node.isEnd;
    }
}

解题思路

• 前缀树数据结构
• 高效字符串存储和检索
• 支持前缀匹配

题目特征

• 需要处理大量字符串
• 需要前缀匹配或自动补全
• 适用于字典类问题

时间复杂度

• 插入和查询均为O(L)

23. 高级图论算法

(1) 最小生成树[7-8]

// Kruskal算法模板
int kruskal(int n, int[][] edges) {
    Arrays.sort(edges, (a, b) -> a[2] - b[2]);
    int[] parent = new int[n];
    for (int i = 0; i < n; i++) parent[i] = i;
  
    int res = 0, count = 0;
    for (int[] edge : edges) {
        int u = edge[0], v = edge[1], w = edge[2];
        int rootU = find(parent, u);
        int rootV = find(parent, v);
        if (rootU != rootV) {
            parent[rootU] = rootV;
            res += w;
            count++;
            if (count == n - 1) break;
        }
    }
    return res;
}

int find(int[] parent, int x) {
    while (parent[x] != x) {
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

解题思路

• 贪心选择最小权边
• 使用并查集检测环
• 适用于连通图

题目特征

• 需要连接所有节点
• 要求总权重最小
• 适用于网络设计问题

时间复杂度

• O(ElogE)

(2) 拓扑排序[7-8]

// 拓扑排序模板
List<Integer> topologicalSort(int n, int[][] edges) {
    List<List<Integer>> graph = new ArrayList<>();
    int[] inDegree = new int[n];
    for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
  
    for (int[] edge : edges) {
        graph.get(edge[0]).add(edge[1]);
        inDegree[edge[1]]++;
    }
  
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < n; i++) {
        if (inDegree[i] == 0) queue.offer(i);
    }
  
    List<Integer> res = new ArrayList<>();
    while (!queue.isEmpty()) {
        int u = queue.poll();
        res.add(u);
        for (int v : graph.get(u)) {
            if (--inDegree[v] == 0) {
                queue.offer(v);
            }
        }
    }
    return res.size() == n ? res : null; // 存在环则返回null
}

解题思路

• 计算节点入度
• 从入度为0的节点开始处理
• 适用于有向无环图

题目特征

• 需要处理依赖关系
• 检测有向图是否有环
• 适用于任务调度问题

时间复杂度

• O(V+E)

24. 数论算法

(1) 快速幂[7-8]

// 快速幂模板
long fastPow(long base, long power, long mod) {
    long result = 1;
    while (power > 0) {
        if ((power & 1) == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        power >>= 1;
    }
    return result;
}

解题思路

• 利用二进制分解指数
• 通过平方减少乘法次数
• 适用于大数幂运算

题目特征

• 需要计算大数幂
• 需要取模运算
• 常见于加密算法等问题

时间复杂度

• O(log n)

(2) 欧拉筛法[7-8]

// 欧拉筛法模板
List<Integer> eulerSieve(int n) {
    boolean[] isPrime = new boolean[n + 1];
    Arrays.fill(isPrime, true);
    List<Integer> primes = new ArrayList<>();
  
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            primes.add(i);
        }
        for (int j = 0; j < primes.size() && i * primes.get(j) <= n; j++) {
            isPrime[i * primes.get(j)] = false;
            if (i % primes.get(j) == 0) {
                break;
            }
        }
    }
    return primes;
}

解题思路

• 线性筛法求素数
• 每个合数只被最小质因数筛除
• 适用于大规模素数筛选

题目特征

• 需要高效生成素数表
• 需要处理大范围素数问题
• 适用于数论相关问题

时间复杂度

• O(n)

25. 高级搜索技巧

(1) 双向BFS[7-8]

// 双向BFS模板
int bidirectionalBFS(Node start, Node end) {
    Set<Node> visitedFromStart = new HashSet<>();
    Set<Node> visitedFromEnd = new HashSet<>();
    Queue<Node> queueFromStart = new LinkedList<>();
    Queue<Node> queueFromEnd = new LinkedList<>();
  
    queueFromStart.offer(start);
    visitedFromStart.add(start);
    queueFromEnd.offer(end);
    visitedFromEnd.add(end);
  
    int steps = 0;
    while (!queueFromStart.isEmpty() && !queueFromEnd.isEmpty()) {
        // 从起点扩展
        int size = queueFromStart.size();
        for (int i = 0; i < size; i++) {
            Node current = queueFromStart.poll();
            if (visitedFromEnd.contains(current)) {
                return steps * 2;
            }
            for (Node neighbor : current.neighbors) {
                if (!visitedFromStart.contains(neighbor)) {
                    visitedFromStart.add(neighbor);
                    queueFromStart.offer(neighbor);
                }
            }
        }
        steps++;
  
        // 从终点扩展
        size = queueFromEnd.size();
        for (int i = 0; i < size; i++) {
            Node current = queueFromEnd.poll();
            if (visitedFromStart.contains(current)) {
                return steps * 2 - 1;
            }
            for (Node neighbor : current.neighbors) {
                if (!visitedFromEnd.contains(neighbor)) {
                    visitedFromEnd.add(neighbor);
                    queueFromEnd.offer(neighbor);
                }
            }
        }
        steps++;
    }
    return -1; // 无解
}

解题思路

• 同时从起点和终点开始搜索
• 减少搜索空间
• 适用于已知起点和终点的最短路径问题

题目特征

• 需要寻找两点间最短路径
• 搜索空间较大
• 适用于对称性问题

时间复杂度

• O(b^(d/2))

(2) A*算法[7-8]

// A*算法模板
int aStar(Node start, Node end) {
    PriorityQueue<Node> openSet = new PriorityQueue<>((a, b) -> 
        (a.g + a.h) - (b.g + b.h));
    Set<Node> closedSet = new HashSet<>();
  
    start.g = 0;
    start.h = heuristic(start, end);
    openSet.add(start);
  
    while (!openSet.isEmpty()) {
        Node current = openSet.poll();
        if (current.equals(end)) {
            return current.g;
        }
  
        closedSet.add(current);
  
        for (Node neighbor : current.neighbors) {
            if (closedSet.contains(neighbor)) continue;
    
            int tentativeG = current.g + distance(current, neighbor);
    
            if (!openSet.contains(neighbor) || tentativeG < neighbor.g) {
                neighbor.g = tentativeG;
                neighbor.h = heuristic(neighbor, end);
                neighbor.parent = current;
        
                if (!openSet.contains(neighbor)) {
                    openSet.add(neighbor);
                }
            }
        }
    }
    return -1; // 无解
}

解题思路

• 使用启发式函数指导搜索方向
• 结合Dijkstra和贪心算法
• 适用于有启发信息的路径规划

题目特征

• 需要寻找最优路径
• 有可用的启发式函数
• 适用于地图导航等问题

时间复杂度

• 取决于启发式函数质量