思路 求从 1 到 n 的最短路，需注意的是 图上所有边的边权会实时改变如何改变：每次走过一条边之后，所有的 x 都会 执行一次操作：x = 1/(1-x)，x 是 边权，所有的 x 指所有边即 边权会随着走过的边的数目的改变而改变 所以该题 不再仅仅是最短路问题，而是变成了 最短路 + dp 问题 不妨令 dist[i][j]：表示 从 1 到 i 经过了 j 条边的最短路所以 我们最终只需求 min（ dist[n][0]，dist[n][1]，dist[n][2]，...... ，dist[n][M] ） M 代表最多走过的边的数目 但是 因为边是双向边，所以理论上来讲 我们可走过无穷条...

思路 求能从 1 号点到达 n 号点 并且 满足相关条件的最短路条件：穿过的被***城镇 不能超过 K 个 解法：最短路 ＋ dp dist[i][j]：从起点开始 穿过了j个被***的城市 到达i点的 最短距离ps：dist 最后一定是最短距离，但中间过程的值不一定是，因为后续可能被再次更新 所以我们只需要求 min( dist[n][0] , dist[n][1] , dist[n][2] , ...... , dist[n][k] ) 至于 dist ，我们在 dijkstra 中求得为了求得 dist 我们需额外 将 当前穿过被***城市的数量 加入到队列中去，这点与 以往的 dij...

根本不需要分层图，其实是dijkstra模板题 思路 让我们求从 s 到 t 的最短路关键点在于建边 有手就行 很简单一题，不废话了，代码如下 Code #include <bits/stdc++.h> using namespace std; const int N = 1e3+10; bool st[N]; int a[N]; int dist[N]; int g[N][N]; int n,m,s,t; int dijkstra(){ memset(dist,0x3f,sizeof dist); dist[s]=0; for(int i=0...

题意 删除一些边，使得最小生成树唯一，问删除的边的权值和最小是多少？ 思路 为什么最小生成树不唯一：因为连接相同两个集合的边，权值相同的可能有多个所以，我们只需要删除 权重相同的 且 连接同两个集合的 那些边即可 ：这些边中留一个 用于维持最小生成树，其余的均删掉。 因为是 稀疏图，所以使用 Kruskal , 在里面进行操作即可 关于在 Krustral 中 res 先加 w 后来再 减 w 的解释：加：为了保证最小生成树唯一，假设权值相同的这一波边都必须删除为什么 a == b 的不删： a == b 说明在前几波 权重相同的边中，a 所在集合 和 b 所在集合 已经连接，此时这一波边的权...

思路 并查集 即可 .问题在于如何 求两个战舰之间的 战舰数目 ? 我们使用 d[ ] 和 num[ ]来辅助我们解决上面的问题d[i]：i 距离根节点（队头）的距离num[i]：i 所在的连通块有多少个元素（ i 所在那一列的战舰数目 ） Code #include <bits/stdc++.h> using namespace std; const int N = 30010; int d[N],num[N]; int fa[N]; int find(int x){ if(x==fa[x]) return x; int root=find(fa[x])...

题意 求从城市 A 到城市 B 的最少花费：最短路 已知一个城市 有四个机场，不妨令 A 城市中的四个机场 为 a1 , a2 , a3 , a4 ，B 城市的为 b1 , b2 , b3 , b4 又因为 各个机场彼此互通，所以本质是求: min ( d[a1][b1], d[a1][b2], d[a1][b3], d[a1][b4], d[a2][b1], d[a2][b2], d[a2][b3], d[a2][b4], ...... , d[a4][b4] ) d[i][j]：i 点到 j 点的 “最短距离” ，即最少的花费 思路 ① 建边 以每个机场为点...

题意 求出 满足条件的猴子的数目，满足的条件是：能在这个地区的所有树冠上觅食换成用数学语言来描述条件 ：猴子的最大跳跃距离 MaxD 需大于或等于 最小生成树 边集 中最长的那条边 最小生成树：联通该地区所有的树冠 所形成的最小生成树 思路 prim 算法扫一遍，在这个过程中，求出 最小生成树 边集中 的最大边长 ，统计 最大跳跃距离 大于或等于其的 猴子的数目 注意： double 类项 不能用memset 初始化 （ wa了好久 最后发现的 ） 综上，Code 如下 . Code #include <bits/stdc++.h> using namespace std; ...

题意 在 从 1号点到 n号点 的路径中， 选择两个城市 A 和 B，必须先选 A 再选 B，问 能赚取的差价最大是多少A：买入水晶球B：卖出水晶球 ps：1 号点到 n 号点的路径可能不止一条 . 思路 不妨遍历 n 个点，对于每个点求出 res_i = w2[i] - w1[i]w1[i]：买入。在从 1 到 i 的路径中，水晶球的最小价格 (若从 1 到不了 i ，则 w1[i] = 正无穷 )w2[i]：卖出。在从 n 到 i 的路径中，水晶球的最大价格 (若从 n 到不了 i ，则 w2[i] = 0 ) // 要求我们建立反向边 因此最后的 ans = max( 0, r...

B题 思路分析 题意：选三个互不相交的满足条件的区间，问这三个区间的长度之和最大是多少？ 使用方法：尺取法（双指针） 思路如下： 不妨令三个区间为 左边的区间:A，中间的区间:B，右边的区间:C 令 res 为 三个区间的长度之和的最大值 我们枚举中间的区间:B 假设B区间的范围为[l,r]，则对于该区间而言 le[l-1] + r-l+1 + ri[r+1] 为res ps ： le[i]: 区间[1,i] 内 满足条件的一个区间的最大长度 ri[i]: 区间[i,n] 内 满足条件的一个区间的最大长度 若共枚举到 num 个 B 区间，对于每一个 B 区间 我们会得...

D题题解 思路 k为奇数时显然无解，所以k只能为偶数 k为偶数时，若满足题意则有： 对于 s[1]~s[k] num[0]=num[1]=k/2; 对于 s[2]~s[k+1] num[0]=num[1]=k/2 所以 s[1]=s[k+1] => s[i] 应该等于 s[i+k] , i+k<=n (字符串下标从1开始) 所以我们让i%k，余数相同的为一组，共由k组（余数:1~k-1或0）.显然同一组内不可以同时出现字符0和字符1 若出现了这种情况则无解. 继续对一组内不同时出现字符0和字符1的情况 进行分析： 若一组内，有一个字符为0则该组的字符全部变为0，若1则全变...

c题题解 思路 状态表示：f[i] => 组成正整数i的方案数 （组成i：若干个正整数相加得到的和为i） 由题意知：相加序列中的每个数都大于或者等于k 所以可进行集合划分如下： case 1：相加序列中的最后一个数为k.因为减去k之后和为i-k，所以此时的方案数为 f[i-k] case 2：相加序列中的最后一个数大于k，最后一个数减去1之和和为i-1，所以此时的方案数为f[i-1] 综上 Code如下.Code #include <cstdio> #include <iostream> #include <algorithm> #define m...

F题题解 思路 线性dp (1)状态表示： f[i][0]：长度为i且第i个珠子为蓝色时的最大价值，若第i个珠子不可以为蓝色，则值为负无穷 f[i][1]：长度为i且第i个珠子为红色时的最大价值，若第i个珠子不可以为红色，则值为负无穷 w[i][0]：第i个位置 蓝色珠子的最大价值，若无蓝色珠子则取负无穷代表取不到 w[i][1]: 第i个位置 红色珠子的最大价值，若无红色珠子则取负无穷代表取不到 (2)集合划分 case 1：第一个珠子取红色时 初始化： f[1][1]=w[1][1] , f[1][0]=负无穷 状态计算: f[i][0]=max(f[i-1][...

A题题解 思路 使用动态规划。 我们不妨令 L[i] 来表示长度为i的且含序列"us"的字符串的种类 对于L[i]进行集合划分： ① 在第i个字符前“us”已经产生，所以第i个字符可以任意取 => L[i-1]*26 ② 在第i个字符时才产生“us”，此时第i个字符一定是‘s’ => x[i-1]:长度为i-1的且含‘u’但不含“us”的字符串的种类 => L[i] = L[i-1]*26 + x[i-1] 所以这就要求我们记录 一个 x 数组 不妨令x[i]：长度为i的且含'u'但不含“us”的字符串的种类 集合划分： ① 在第i个字符前出现过了'u'，所以第i...

c题题解 思路 思路：使用优先队列 --> 大根堆 ，因为它会动态更新， 所以我们每次把里面的最大值也就是队头给减去p就行了 但是 因为一次一次的减去p，总共需要减去k次，k很大 会超时。 所以我们对于每一个取出的最大值 让他减去cnt次p。 cnt：减去cnt次p 后，该最大值 被 第二大的值 反超 但这样也有局限性，若我们得到的每个cnt都为1，最后还是需要执行k次减去p的操作。 比如 n个数均相同，我们会发现 每个cnt都是1。 但是 最后竟然过了，所以这题的数据还是挺水的ba。。。 综上：Code如下。Code #include <iostream> #inclu...