*动态规划

樱花

dp[]

逻辑拆解：选 vs 不选

对于每个时间 t，我们有两个选择：

• 不选当前树：dp[t] 保持原来的值（之前处理其他树得到的最大价值）；
• 选当前树：前提是 t >= T（时间够），此时价值是 dp[t - T] + C（用 t-T 分钟的最大价值，加上选当前树的价值）；
• 取两者的最大值，更新 dp[t] → 这就是 max(dp[t], dp[t-T]+C) 的含义。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;

struct Tree {
    int T, C, P;
};

int main() {
    // 读取时间并转换为分钟
    int h1, m1, h2, m2, n;
    char colon;
    cin >> h1 >> colon >> m1 >> h2 >> colon >> m2 >> n;
    int total_time = (h2 * 60 + m2) - (h1 * 60 + m1);

    vector<Tree> trees(n);
    for (int i = 0; i < n; ++i) {
        cin >> trees[i].T >> trees[i].C >> trees[i].P;
    }

    // 初始化DP数组：dp[t]表示时间t的最大美学值
    vector<int> dp(total_time + 1, 0);

    for (const Tree& tree : trees) {
        int T = tree.T, C = tree.C, P = tree.P;
        if (T == 0) continue;  // 时间为0的树不处理（题目中T>0）

        if (P == 0) {
            // 完全背包：正序遍历时间
            for (int t = T; t <= total_time; ++t) {
                dp[t] = max(dp[t], dp[t - T] + C);
            }
        } else {
            // 01背包或多重背包：二进制拆分
            int cnt = P;
            for (int k = 1; k <= cnt; k *= 2) {
                int kT = k * T;
                int kC = k * C;
                // 按01背包处理：逆序遍历时间
                for (int t = total_time; t >= kT; --t) {
                    dp[t] = max(dp[t], dp[t - kT] + kC);
                }
                cnt -= k;
            }
            // 处理剩余次数
            if (cnt > 0) {
                int kT = cnt * T;
                int kC = cnt * C;
                for (int t = total_time; t >= kT; --t) {
                    dp[t] = max(dp[t], dp[t - kT] + kC);
                }
            }
        }
    }

    // 取最大美学值
    int max_c = 0;
    for (int t = 0; t <= total_time; ++t) {
        max_c = max(max_c, dp[t]);
    }
    cout << max_c << endl;

    return 0;
}

*图论-MST最小生成树

bool operator<(const Edge& other) const { return z < other.z; }

结构体运算符重载，核心目的只有一个：让结构体（比如 Edge 边）能像普通变量一样比较大小—— 这样调用 sort 函数时，才能自动按边的权值 z 从小到大排序（Kruskal 算法的关键一步）

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// 1. 边结构体：存储两个节点和权值
struct Edge {
    int x, y, z;  // x和y是节点，z是边的权值
    // 重载<运算符，用于边按权值从小到大排序
    bool operator<(const Edge& other) const {
        return z < other.z;
    }
};

// 2. 并查集：维护连通性（核心！）
vector<int> parent;  // parent[u]表示u的父节点

// 查找u的根节点（带路径压缩，加速查询）
int find(int u) {
    if (parent[u] != u) {  // 如果u不是根节点
        parent[u] = find(parent[u]);  // 路径压缩：让u直接指向根节点
    }
    return parent[u];
}

// 合并u和v所在的连通集
void unite(int u, int v) {
    u = find(u);  // 找u的根
    v = find(v);  // 找v的根
    if (u != v) {  // 若根不同，合并（让v的根指向u的根）
        parent[v] = u;
    }
}

int main() {
    // 加速输入输出（必须加！否则M=2e5会超时）
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    vector<Edge> edges(M);  // 存储所有边
    for (int i = 0; i < M; ++i) {
        cin >> edges[i].x >> edges[i].y >> edges[i].z;
    }

    // 3. 初始化并查集：每个节点的父节点是自己
    parent.resize(N + 1);  // 节点编号从1开始（题目输入是1-based）
    for (int i = 1; i <= N; ++i) {
        parent[i] = i;
    }

    // 4. 排序所有边（按权值从小到大）
    sort(edges.begin(), edges.end());

    int total = 0;  // MST的总权值
    int cnt = 0;    // 已选入MST的边数

    // 5. 依次选边，构建MST
    for (const Edge& e : edges) {
        int u = e.x, v = e.y, w = e.z;
        if (find(u) != find(v)) {  // 两个节点不连通，选这条边
            unite(u, v);           // 合并连通集
            total += w;            // 累加权值
            cnt++;                 // 边数+1
            if (cnt == N - 1) {    // 选够N-1条边，提前退出（优化）
                break;
            }
        }
    }

    // 6. 判断是否连通：边数是否为N-1
    if (cnt == N - 1) {
        cout << total << endl;
    } else {
        cout << "orz" << endl;
    }

    return 0;
}

1. 边结构体（Edge）

• 存储每条边的两个节点（x,y）和权值（z）；
• 重载 < 运算符：排序时会自动按 z 从小到大排，不用写额外的排序函数。

2. 并查集（find + unite）

并查集是 Kruskal 算法的核心，用于快速判断两个节点是否连通，避免选边形成环：

• 路径压缩（find 函数）：每次查找根节点时，让节点直接指向根，下次查找更快（比如原来的链状结构 u→v→w→根，压缩后 u→根）；
• 合并（unite 函数）：找到两个节点的根，若不同则合并（让一个根指向另一个根），表示两个连通集合并。

3. 主逻辑（按步骤来）

• 输入加速：ios::sync_with_stdio(false); cin.tie(nullptr); 必须加！否则 M=2e5 时输入会超时；
• 初始化并查集：节点编号是 1-based（题目输入的节点是 1 到 N），所以 parent 数组大小是 N+1，每个节点初始父节点是自己；
• 排序边：调用 sort 函数，利用 Edge 重载的 < 运算符自动按权值排序；
• 选边构建 MST：遍历排序后的边，只选 “两个节点不连通” 的边，直到选够 N-1 条边（提前退出，优化效率）；
• 判断连通：若选了 N-1 条边，说明所有节点连通（形成树），输出总权值；否则图不连通，输出 orz。

*珠宝染色问题

1. 埃氏筛法：快速标记 2~n+1 中所有合数（素数的反面）；
2. 确定最少颜色 K：n<3 时 K=1（只有 1 件或 2 件珠宝，无冲突），否则 K=2（二分图特性，2 种颜色足够）；
3. 染色输出：素数染 1，合数染 2（或反过来，合法即可）。

#include <bits/stdc++.h>  // 万能头文件：包含所有常用头文件（比赛常用，省时间）
using namespace std;

const int maxn = 1e5 + 10;  // 最大范围：n≤1e5，价格最大是n+1≤1e5+1，所以开1e5+10足够
int n;  // 输入的珠宝数量
bool flag[maxn];  // 标记数组：flag[x]=1表示x是合数，flag[x]=0表示x是素数

int main() {
	scanf("%d", &n);  // 读入珠宝数量n（比cin快，比赛常用）
	flag[0] = flag[1] = 1;  // 0和1不是素数，直接标记为合数（1）

	// 埃氏筛核心循环：i从2到sqrt(n+1)（优化点！）
	for (int i = 2; i * i <= n + 1; i++) {
		if (!flag[i]) {  // 如果i是素数（没被标记为合数）
			// 把i的所有倍数（2i,3i,...）标记为合数（1）
			for (int j = i << 1; j <= n + 1; j += i) {  // i<<1 等价于 2*i，位运算更快
				flag[j] = 1;
			}
		}
	}

// 输出最少颜色数K：n<3时K=1，否则K=2
	puts(n < 3 ? "1" : "2");  // puts等价于cout<<...<<endl，更快

// 遍历价格2~n+1（珠宝的价格序列），输出颜色
	for (int i = 2; i <= n + 1; i++) {
		printf("%d ", flag[i] + 1);  // 核心染色逻辑！
	}
	return 0;
}

*最短路径

priority_queue<PII, vector<PII>, greater<PII>> pq;

模板参数	含义
PII	优先队列中存储的 元素类型（这里是 pair<int, int>，即 “距离 + 顶点”）
vector<PII>	优先队列的 底层存储容器（必须是支持随机访问的容器，默认就是 vector，不用改）
greater<PII>	优先队列的 排序规则（核心！greater 表示 “小的元素优先级高”，即最小堆）

模板拆解

1. 数据类型与全局定义

cpp

运行

typedef long long ll;  // 关键！w_i≤1e9，m≤2e5，最大距离可能达2e14，超int范围，必须用ll
typedef pair<ll, int> PII;  // 优先队列的元素：first=距离（ll），second=节点编号（int）

const int MAXN = 1e5 + 10;  // 节点数最多1e5，数组开1e5+10避免越界
const ll INF = LLONG_MAX;   // 无穷大（long long的最大值，代表初始时未可达）

vector<vector<PII>> adj;  // 邻接表：存储图的结构。adj[u]是vector，每个元素是(v, w)，表示u→v的边权w
ll dist[MAXN];            // 距离数组：dist[i]记录s到i的最短距离
bool vis[MAXN];           // 标记数组：避免重复处理已确定最短路径的节点

2. 输入处理与初始化

cpp

运行

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);  // 输入输出加速：必须加！否则1e5数据会超时

    int n, m, s;
    cin >> n >> m >> s;  // 读入节点数n、边数m、起点s

    adj.resize(n + 1);  // 邻接表大小设为n+1（节点1-based）
    for (int i = 0; i < m; ++i) {
        int u, v;
        ll w;
        cin >> u >> v >> w;  // 读入有向边u→v，权值w
        adj[u].emplace_back(v, w);  // 把边存入邻接表（emplace_back比push_back更高效）
    }

    // 初始化距离数组：所有节点初始距离为INF（未可达）
    for (int i = 1; i <= n; ++i) {
        dist[i] = INF;
    }
    dist[s] = 0;  // 起点s到自己的距离为0

    // 优先队列（小根堆）：greater<PII>表示按first元素升序排序（距离越小越先出堆）
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    pq.emplace(0, s);  // 起点入堆：(距离0, 节点s)

3. 核心迭代逻辑（Dijkstra 主循环）

cpp

运行

    while (!pq.empty()) {  // 堆不为空时循环
        // 取出堆顶：当前距离起点最近的节点（d是当前距离，u是节点编号）
        auto [d, u] = pq.top();
        pq.pop();

        // 关键优化：若u已确定最短路径（vis[u]=true），直接跳过
        // 原因：堆中可能有多个u的记录（不同距离），只需要处理距离最小的那个（第一次取出时）
        if (vis[u]) continue;
        vis[u] = true;  // 标记u的最短路径已确定，后续不再处理

        // 遍历u的所有出边（v是终点，w是边权）
        for (auto [v, w] : adj[u]) {
            // 松弛操作：若走u→v的边，到v的距离比当前dist[v]更短，就更新
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                pq.emplace(dist[v], v);  // 把新的距离和v存入堆，供后续处理
            }
        }
    }

4. 输出结果

cpp

运行

    // 输出s到1~n每个节点的最短距离
    for (int i = 1; i <= n; ++i) {
        cout << dist[i] << " ";
    }
    cout << endl;

    return 0;
}

样例验证（用模板一步步跑，看结果怎么来）

样例输入：

plaintext

4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

初始化：

• dist[1]=0，dist[2]=dist[3]=dist[4]=INF；
• 堆中初始：(0,1)。

迭代过程：

1. 取出堆顶 (0,1)，vis[1]=true（标记 1 的最短路径已确定）；

   • 遍历 1 的出边：
     • 1→2（w=2）：dist[2] = 0+2=2，堆中加入 (2,2)；
     • 1→3（w=5）：dist[3] =0+5=5，堆中加入 (5,3)；
     • 1→4（w=4）：dist[4] =0+4=4，堆中加入 (4,4)；
   • 堆中现在有：(2,2), (4,4), (5,3)。

2. 取出堆顶 (2,2)，vis[2]=true；

   • 遍历 2 的出边：
     • 2→3（w=2）：dist[3] = min(5, 2+2=4) → 更新为 4，堆中加入 (4,3)；
     • 2→4（w=1）：dist[4] = min(4, 2+1=3) → 更新为 3，堆中加入 (3,4)；
   • 堆中现在有：(3,4), (4,3), (4,4), (5,3)。

3. 取出堆顶 (3,4)，vis[4]=true；

   • 4 没有出边（样例中），无更新；
   • 堆中现在有：(4,3), (4,4), (5,3)。

4. 取出堆顶 (4,3)，vis[3]=true；

   • 遍历 3 的出边：3→4（w=3）：dist[4] = min(3,4+3=7) → 不更新；
   • 堆中剩余元素无需处理（所有节点已标记 vis=true）。

最终 dist 数组：

dist[1]=0，dist[2]=2，dist[3]=4，dist[4]=3 → 输出 0 2 4 3，和样例一致！

避坑指南（比赛常错点，提前规避）

1. 数据类型：必须用 long long 存储距离和边权！否则会溢出（比如 1e5 条边，每条边权 1e9，总和达 1e14，超 int 范围）；
2. 输入输出加速：ios::sync_with_stdio(false); cin.tie(nullptr); 必须加，否则 1e5 数据会超时；
3. 邻接表初始化：节点是 1-based，adj 要 resize 到 n+1，避免访问 adj[0] 或越界；
4. 标记数组 vis：必须加！否则会重复处理堆中同一节点的旧记录（长距离），导致超时；
5. 优先队列类型：必须是「小根堆」（greater<PII>），否则每次取出的是距离最大的点，算法逻辑错误。

同类题识别（下次遇到直接套模板）

只要题目满足以下条件，就用这个 Dijkstra 模板：

1. 有向 / 无向带权图（无向图只需存两条有向边：u→v 和 v→u）；
2. 边权非负；
3. 求单源最短路径（从一个起点到所有其他点的最短距离）。

常见变形：

• 无向图的最短路径（如 “城市间修路，求从 A 到所有城市的最短距离”）；
• 边权是时间 / 成本，求最小时间 / 成本（如 “快递配送，求从仓库到所有网点的最短时间”）。

*KMP