不要为打翻的牛奶哭泣

分类

题解(1)

/ 注册

全部文章（共95篇）

题解 | 【模板】单源最短路Ⅰ ‖ 无权图

step1：创建一个数组，表示从起点s到每个顶点的最短路径。初始化值为-1。step2：创建一个队列，起点s的最短路径设为0，将起点s加入队列中。step3：从队列首部取出一个顶点u，依次判断该顶点连接到的每一个顶点v。若v的最短路径为-1，则更新为u的最短路径+1，并将v加入到队列末尾。step4...

2025-05-28

0 18

题解 | 【模板】单源最短路Ⅲ ‖ 非负权图

和上一道题基本一样，改一下边权就行了 #include <bits/stdc++.h> using namespace std; #define int long long const int INF = 1e18; const int N = 2e6 + 5; int __t = 1,...

2025-05-28

0 18

题解 | 【模板】最小生成树

最小生成树：将所有节点连接起来用到的最小的权重。（图必须是联通图）Prim算法：考虑任意一个点，和这个点连接的所有边中，最短的那一条一定在最小生成树的结果（因为假如别的边都已经连接好了，只差这一个节点，那么连接这个节点最好的办法就是连接他最短的那一条边。这对于任意一个节点都适合）。在将一个节点和距离...

2025-05-28

0 16

题解 | 【模板】二分

二分模板，按照题意模拟即可，记得讨论清楚边界 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + 5; int __t = 1, n, q, op, l, r, x...

2025-05-28

0 16

题解 | 【模板】整数域三分

函数 f(x) = | kx + a | + b，当x = -a/k 时最小，函数图像是一个V字形，有最小值。看到这个形状，我们很容易想到用三分法寻找最小值的位置。然而题目中的F(x) 是多个f(x) 的和，如果要用三分法，就必须保证F(x)在最小值左边单调递减（或平），在右边单调递增（或平），否则...

2025-05-28

0 17

题解 | 游游的排列构造

确定好元素的位置：选择k个不相邻的位置，例如前k个奇数位置（1, 3, 5, ..., 2k-1）。这些位置必须保证互不相邻。填充好元素的值：在这些位置中填入最大的k个数，按从小到大的顺序排列。最后一个位置填入最大的数n，以确保后续元素不会成为好元素。填充剩余数值：剩下的数（...

2025-05-26

0 22

题解 | 游游的最小公倍数

lcm尽可能大，代表gcd尽可能小，所以一定是a和b互质时的 a*b 是最大的lcm，同时因为是二者的乘积，所以二者要尽可能的靠近 n/2 才行，所以从中间情况开始检查这一组a和b是否合法即可 #include <bits/stdc++.h> using namespace std; #...

2025-05-26

0 17

题解 | 小红的取模构造

我们发现如果a和b都是正数，相同的时候无解，不同的时候只需要给小的数加上大的数即可，然后特判一下和0有关的情况 #include <bits/stdc++.h> using namespace std; #define int long long const int N = 2e5 + ...

2025-05-26

0 19

题解 | Y型树

这是一个数学问题，可以通过以下步骤解决：数学推导：设 n-1 个点分成三组，每组至少一个点每组点数的和为 n-1（除去分叉点）最大组的点数不能超过 (n-1)/3计算策略：使用等差数列求和公式计算部分结果通过快速幂计算逆元使用补集的思想避免复杂的组合数计算具体步骤：计算 k = (n-1)/3使用 ...

2025-05-26

0 17

题解 | 小红的蛋糕切割

这是一个枚举问题，可以通过以下步骤解决：预处理：计算整个蛋糕的总美味度 total使用二维前缀和数组加速区域和的计算枚举策略：枚举正方形的边长 len（从1到min(n,m)）枚举正方形左上角的位置 (i,j)计算正方形区域的美味度和剩余区域的美味度更新最小差值具体步骤：构建二维前缀和数组对每个可能...

2025-05-26

0 15