最短路算法及其时间复杂度 单源最短路 D i j k s t r a Dijkstra Dijkstra O ( n 2 ) O(n^2) O(n2) 堆优化版的 D i j k s t r a Dijkstra Dijkstra O ( m l o g n ) O(mlogn) O(mlogn) S P F A SPFA SPFA O ( m ) O(m) O(m) 最坏 O ( n m ) O(nm) O(nm) 多源最短路 F l o y d Floyd Floyd O ( n 3 ) O(n^3) O(n3) AcWing1129. 热浪 德克萨斯纯朴的民...

Acwing 1135 新年好 重庆城里有 n 个车站，m 条 双向 公路连接其中的某些车站。 每两个车站最多用一条公路连接，从任何一个车站出发都可以经过一条或者多条公路到达其他车站，但不同的路径需要花费的时间可能不同。 在一条路径上花费的时间等于路径上所有公路需要的时间之和。 佳佳的家在车站 1，他有五个亲戚，分别住在车站 a,b,c,d,e 过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。 怎样走，才需要最少的时间？ 输入格式 第一行：包含两个整数 n,m 分别表示车站数目和公路数目。 第二行：包含五个整数 a,b,c,d,e 分别表示五个亲...

A. String Generation 题意 构造一个只包含’a’ ‘b’ 'c’的字符串 此字符串中最大回文子串的长度不超过k 思路 'abcabcabc…'这样输出 可以保证最大的回文子串的长度为1 代码 #include<bits/stdc++.h> using namespace std; typedef long long LL; const int N = 100010; void solve() { int n, k; cin >> n >> k; for (int i = 0; i < n; ++i)...

功能 ①：合并两个集合 void merge(int a, int b) { f[Find(a)] = Find(b); } ②：查询某个元素的祖宗节点 int Find(int x) { return x == f[x] ? x : f[x] = Find(f[x]); } 扩展 ① 记录每个集合的大小(绑定到根节点) int pa = Find(a); int pb = Find(b); if(){ s[pb] += s[pa] } ②每个点到根节点的距离(绑定到每一个元素身上) int n, p[N], s[N], d[N]; ...

AcWing1250. 格子游戏 Alice和Bob玩了一个古老的游戏：首先画一个 n×n 的点阵（下图 n=3）。 接着，他们两个轮流在相邻的点之间画上红边和蓝边： 直到围成一个封闭的圈（面积不必为 1）为止，“封圈”的那个人就是赢家。因为棋盘实在是太大了，他们的游戏实在是太长了！ 他们甚至在游戏中都不知道谁赢得了游戏。 于是请你写一个程序，帮助他们计算他们是否结束了游戏？ 输入格式 输入数据第一行为两个整数 n 和 m。n表示点阵的大小，m 表示一共画了 m 条线。 以后 m 行，每行首先有两个数字 (x,y)，代表了画线的起点坐标，接着用空格隔开一个字符，假如字符是 ...

AcWing1252. 搭配购买 思路 先分组 再做01背包 Joe觉得云朵很美，决定去山上的商店买一些云朵。 商店里有 n 朵云，云朵被编号为 1,2,…,n，并且每朵云都有一个价值。 但是商店老板跟他说，一些云朵要搭配来买才好，所以买一朵云则与这朵云有搭配的云都要买。 但是Joe的钱有限，所以他希望买的价值越多越好。 输入格式 第 1 行包含三个整数 n，m，w表示有 n 朵云，m 个搭配，Joe有 w 的钱。 第 2∼n+1行，每行两个整数 c i c_{i} ci​， d i d_{i} di​ 表示 i 朵云的价钱和价值。 第 n+2∼n+1+m行，每行两个整...

AcWing237. 程序自动分析 思路 先把相等的合并 再判断不相等是否与已知条件矛盾 在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。 考虑一个约束满足问题的简化版本：假设 x 1 , x 2 , x 3 x_{1},x_{2},x_{3} x1​,x2​,x3​,…代表程序中出现的变量，给定n个形如 x i = x j x_{i}=x_{j} xi​=xj​或 x i ≠ x j x_{i}≠x_{j} xi​​=xj​的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。 例如，一个问题中的约束条件...

AcWing238. 银河英雄传说 有一个划分为N列的星际战场，各列依次编号为1,2,…,N。 有N艘战舰，也依次编号为1,2,…,N,其中第i号战舰处于第i列。 有T条指令，每条指令格式为以下两种之一： 1、M i j，表示让第i号战舰所在列的全部战舰保持原有顺序，接在第j号战舰所在列的尾部。 2、C i j，表示询问第i号战舰与第j号战舰当前是否处于同一列中，如果在同一列中，它们之间间隔了多少艘战舰。 现在需要你编写一个程序，处理一系列的指令。 输入格式 第一行包含整数T，表示共有T条指令。 接下来T行，每行一个指令，指令有两种形式：M i j或C i j。 其中M和C...

AcWing239. 奇偶游戏 思路 s i = a 1 + a 2 + ⋯ + a i s_{i} = a_{1} + a_{2} +\dots +a_{i} si​=a1​+a2​+⋯+ai​ 前i个数中1的个数 s [ l − r ] s[l-r] s[l−r]中有奇数个1    ⟺    \iff ⟺ s r − s l − 1 s_{r} - s_{l-1} sr​−sl−1​为奇数    ⟺    \iff ⟺ s r s_{r} sr​与 s l − 1 s_{l-1} sl−1​奇偶性不同 偶数个1    ⟺    \iff ⟺ s r s_{r} ...

01背包 每件物品只有一个 朴素算法 分为两种情况：①不选第i个物品 f [ i − 1 ] [ j ] f[i-1][j] f[i−1][j] ​ ②选第i个物品 状态方程可以由 f [ i − 1 ] [ j − v ] + w f[i-1][j-v] + w f[i−1][j−v]+w得到 f [ i − 1 ] [ j − v ] + w f[i-1][j-v] + w f[i−1][j−v]+w表示前 i − 1 i - 1 i−1个物品取总体积不超过 j − v j - v j−v的最大价值加上第 i i i个物品的价值( v , w v,w v,w)分别表示第 i i...

多重背包 每件物品的个数有限制 朴素算法 与完全背包的朴素算法类似 时间复杂度 O ( N ∗ V ∗ S ) O(N*V*S) O(N∗V∗S) 状态转移方程 f [ i ] [ j ] = m a x ( f [ i ] [ j ] , f [ i − 1 ] [ j − k ∗ v [ i ] ] + k ∗ w [ i ] ) f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]) f[i][j]=max(f[i][j],f[i−1][j−k∗v[i]]+k∗w[i]) 优化成一维时需要从大到小枚举 j j j f...

分组背包 类似多重背包，只是将每件物品选几个变成每组物品选哪一个 状态转移方程 f [ i ] [ j ] = M a x ( f [ i − 1 ] [ j ] , f [ i − 1 ] [ j − v [ i ] [ k ] ] + w [ i ] [ k ] ) f[i][j] = Max(f[i-1][j],f[i-1][j-v[i][k]] + w[i][k]) f[i][j]=Max(f[i−1][j],f[i−1][j−v[i][k]]+w[i][k]) 所以优化成一维时需要从大到小枚举 j j j int n, m; int f[N]; int v[N][N], w[...

线性DP 数字三角形 给定一个如下图所示的数字三角形，从顶部出发，在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点，一直走到底层，要求找出一条路径，使路径上的数字的和最大。 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 状态表示 f [ i ] [ j ] f[i][j] f[i][j] : 所有从起点走到 ( i , j ) (i,j) (i,j)的路径最大值 状态计算 f [ i ] [ j ] = M a x ( f [ i − 1 ] [ j − 1 ] , f...

区间DP 石子合并 设有N堆石子排成一排，其编号为1，2，3，…，N。 每堆石子有一定的质量，可以用一个整数来描述，现在要将这N堆石子合并成为一堆。 每次只能合并相邻的两堆，合并的代价为这两堆石子的质量之和，合并后与这两堆石子相邻的石子将和新堆相邻，合并时由于选择的顺序不同，合并的总代价也不相同。 问题是：找出一种合理的方法，使总的代价最小，输出最小代价。 状态表示 f [ i ] [ j ] f[i][j] f[i][j]所有将第 i i i堆石子到第 j j j堆石子合并成一堆石子的合并方式 状态计算 f [ l ] [ r ] = M i n ( f [ l ] [...