Q779’s Blog

洛谷P2387 [NOI2014] 魔法森林 题解 题目链接：P2387 [NOI2014] 魔法森林 题意：每条边有边权 \(a,b\) 两个，求 \(1\) 到 \(n\) 的路径使得所经过的边中 \(\max\{a\}+\max\{b\}\) 尽可能小 由于下面写了很多解题思路上的东西，导致有些冗长，因此这里先放简化版题解 如果不理解可以跳过这一段简化版，直接看下面的完整版 简化版 因为不方便同时处理 \(a,b\) 两维，我们可以枚举 \(a\) 然后尽可能的选择较小的 \(b\) 这个 \(b\) 的一定在连接 \(1\) 和 \(n\) 的最小生成树上 因此这道题就是个动态加边的 LCT 裸题了 代码在后面，时间复杂度 \(O(m\log m)\) 完整版 这种“二维”的问题常见的解法就是枚举第一维，然后优化第二维 不知道这个套路也没关系 首先看到这个题意，最大值的和最小，显然我们无法确定这是个多大的值 似乎可以二分？但是再一想，二分 \(a+b\) 肯定是不对的 那先二分 \(a\) 再二分 \(b\) （二分套二分）呢？ 看上去似乎也不行，这个 \(b\)...

洛谷P4234 最小差值生成树 题解 题目链接：P4234 最小差值生成树 题意：给定一个点标号从 \(1\) 到 \(n\) 的、有 \(m\) 条边的无向图，求边权最大值与最小值的差值最小的生成树，图可能存在自环 这个题不太好利用kruskal来维护（其实kruskal来做就是暴力枚举） 考虑使用LCT动态维护生成树 可以先回顾一下如何用LCT来求解最小生成树 link 因为边之间没有什么本质区别，我们可以先把边按大小排序，以保证编号越小的边点，权值越小 然后我们可以从小到大枚举生成树中的最大值（从大到小其实是类似的） 那么我们只要保证生成树中边权的最小值尽可能的大即可 也就是说，在枚举最大边的时候，如果两结点未连通，我们可以直接将这两点连接 如果已经连通，那么就将当前生成树中x,y所成的链中的最小边扔掉，然后用最大边连接这两点 显然这个最小值就是生成树中编号最小的那一个，而且随着枚举会单调不降，那我们可以整个变量记录它，而由于它的单调不降性质，寻找这个最小值是不会影响到复杂度的 对于已经不在生成树的边（包括构成自环和被更新掉的边），我们直接让那个维护最小值的变量跳过它...

LCT求解最小生成树 前言 最小生成树模板： P3366 【模板】最小生成树 朴素的kruskal为主流最小生成树算法 而LCT(link cut tree)也是可以维护最小生成树的 由于LCT动态维护最小生成树，加上常数较大 在实际测试中比kruskal慢了很多倍 最小生成树 维护结点的连通性 可以看看这个 显然我们不是把它和kruskal连用，那样反倒变成了 \(\log^2\) 的劣解了 而LCT它是动态的，因此难以使用树链剖分的做法，将边权映射到点权上 那么我们可以把通过建“边点”将边权转化为点权 所谓的边点指直接将每条边当做点，那么连边的操作就变成了 w[idx+n]=z; // 记录边权 ,idx = 1 to m link(x,idx+n),link(idx+n,y); // 和边所连接的两结点与该边所建结点相连 因为没有对边权排序，那如果 x,y 已经连通怎么办呢？ 由于x,y都在LCT上，因此我们可以维护它们所成的链中最大的那一条边 如果当前处理到的边比那条边边权更小，就可以将那条极大边断掉 如何断边？直接t[t[now].ch[0]].fa=t[t[now]...

洛谷P2147 [SDOI2008] 洞穴勘测 题解 题目链接：P2147 [SDOI2008] 洞穴勘测 题意：给定若干个点，动态连接（无向边），询问连通性 由于它有删边的操作，因此用并查集并不可行 于是想到LCT（？ 由于LCT有 find_root() 操作 说明LCT确实可以动态判定连通性 那么就变成简单的模板题了（ 代码如下 #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f #define N (int)(1e4+5) int n,Q; namespace LCT { struct node { int ch[2],fa,tag; }t[N]; #define isroot(x) ((t[t[x].fa].ch[0]!=x)&&(t[t[x].fa].ch[1]!=x)) void pushr(int x) ...

洛谷P1501 [国家集训队]Tree II 题解 题目链接：P1501 [国家集训队]Tree II 题意：树上区间加&乘&link&cut 显然LCT模板题，因为树链剖分并不能维护动态连边 考虑如何维护区间乘 不知道大家有没有做过洛谷的线段树2，没做过也没关系 对于每个结点，维护一个 \(kx+b\) 的懒标记 每次做乘法就整体（包括两个部分）乘上 \(c\) ，每次做加法就直接加上 \(c\) 就可以维护标记了 由于加法的维护需要知道这条链的长，那我们只要维护每个结点的子树大小即可 那么这题就很容易解决了（就是函数有点多） 时间复杂度 \(O(n\log n)\) #include <bits/stdc++.h> using namespace std; #define int long long #define INF 0x3f3f3f3f3f3f3f3f #define gc() getchar() #define pc(a) putchar(a) #define N (int)(1e5+5) const int mod=51061; ...

浅谈快速乘 前言 想必大家都听说过快速幂 那快速乘是个什么东西呢？ 考虑取模操作a*b%p，1^10 ≤ a,b,p ≤ 2^10 可以发现在 long long情况下，我们直接取模会溢出 那么怎么办呢？ 题目链接：https://www.luogu.com.cn/problem/U203580 快速乘 注：本文根据q779本人的习惯，所有的int都宏定义为了long long 标准快速乘 时间复杂度 \(O(\log b)\)，且正确性完备 类似于快速幂，具体见代码 #define int long long int ksc(int a,int b,int p) { int ans=0; while(b) { if(b&1)ans=(ans+a)%p; a=(a<<1)%p;b>>=1; } return ans; } __int128_t 这是个自带的数据类型，而且根据我查阅到的资料来看，有一点点不太靠谱的感觉 它能存到 \(2^{128}...

AT4284 [ABC116C] Grand Garden & 洛谷 P1969 P3078 P5019 题解 题目链接：AT4284 P1969 P3078 P5019 题意：若干次区间减一，使所有数相等，求最小次数 这几道题就是一个std编出来的吧 \(😅\) 对于相邻两数 \(a_i>a_{i-1}\) ，显然在一次操作中将它们同时减去是最优的 对答案的贡献为 \(a_i-a_{i-1}\) 推广一下其实是等价的，故时间复杂度 \(O(n)\) 即可解决 代码如下 #include <bits/stdc++.h> using namespace std; #define int long long #define MAXN (int)(1e5+5) int n; int a[MAXN],ans; signed main() { ios::sync_with_stdio(0); cin >> n; for(int i=1; i<=n; i++) { cin >> a[i]; ...

洛谷P1234 小A的口头禅 题解 题目链接：P1234 小A的口头禅 给出了一个矩形，让你求出里面有几个hehe（方向无所谓，斜着不算） 数据范围很良心，嗯~ 所以暴力枚举即可 值得注意的是 \(\tt{eheh}\) 这种也算 顺便说一句，关了同步流的cin,cout还是很快的 qwq 鬼畜的代码如下 #include <bits/stdc++.h> using namespace std; #define int long long #define MAXN (int)(1005) #define A (j+3<=m&&a[i][j]=='h'&&a[i][j+1]=='e'&&a[i][j+2]=='h'&&a[i][j+3]=='e') #define B (j-3>=1&&a[i][j-3]=='e'&&a[i][j-2]=='h'&&a[i][j-1]=='e'&&a[i][j]=='h') #define C (i+3&l...

洛谷P2804 神秘数字 题解 题目链接：P2804 神秘数字 题意：询问有多少段连续区间的平均值大于 \(m\) 可以发现将每个数都减去 \(m\) 后任意和大于 \(0\) 的连续区间都满足题意 区间和可以用前缀和优化，记为 \(s\) 问题转化为了求 \(s_j-s_i>0,0\le i <j\) 移项可得 \(s_i<s_j,0\le i <j\) 问题又转化为了求顺序对（与逆序对相反） 于是可以用树状数组解决 更多解法？ 注意当 \(s_j>0\) 时 \(i=0\) 也是一个解 时间复杂度 \(O(n\log n)\) 代码如下 #include <bits/stdc++.h> using namespace std; #define int long long #define MAXN (int)(2e5+5) #define mod 92084931 int n,m,ans; int a[MAXN],bit[MAXN],b[MAXN]; int lowbit(int x){return x&(-x);
...

洛谷P1522 [USACO2.4]牛的旅行 Cow Tours 题解 题目链接：P1522 [USACO2.4]牛的旅行 Cow Tours 题意：给定一张无向图，有至少 \(2\) 个连通分量，定义直径为每个连通分量中任意两结点的最短路径的最大值，其中相邻结点边权为它们的欧几里德距离，现在要求添加一条边使得连通分量的数量减少 \(1\) ，并使得这个新连通分量的直径尽可能地小，求这个最小值 题意已经简化过了 应该很好懂 由于 \(N\le 150\) 显然我们可以用 Floyd 来求这个最短路径 任意两个连通块 \(A,B\) 连边，可能出现以下三种情况 \(A\) 的直径最大 \(B\) 的直径最大 \(A\) 和 \(B\) 相连后的新直径最大，即 \(w(i,j) + d(i) + d(j)\) ， 其中 \(d(i)\) 指从结点 \(i\) 出发的最长路径的长度 那我们求一下就好了 qwq 就这么简单 注意这个最大值不能在Floyd的时候更新，因为那个时候还不是最短路径… 时间复杂度 \(O(n^3)\) 代码如下（无视我的垃圾卡常） #include &l...

洛谷P5764 [CQOI2005]新年好 题解 题目链接：P5764 [CQOI2005]新年好 题意：从 \(1\) 号结点出发，要访问其他 \(5\) 个结点，顺序随意，访问一个结点后不用返回 注意到 \(5! = O(1)\) 那我们可以在 \(1\) 和其他 \(5\) 个点跑一下dijkstra，然后枚举所有可能的顺序即可 这里给出了两种枚举方式，分别为dfs和next_permutation() 实测（C++14 O2）后者快30ms左右，不过均可轻松通过此题 我才不会说我是因为先写后者没调出来才有的这篇题解呢 QAQ dfs #include <bits/stdc++.h> using namespace std; #define int long long #define INF (int)(5e10+233) #define gc() getchar() #define pc(a) putchar(a) #define MAXN (int)(5e4+5) template<typename T>void read(T &k) {...

洛谷P1462 通往奥格瑞玛的道路 题解 题目链接：P1462 通往奥格瑞玛的道路 题意：在艾泽拉斯，有 \(n\) 个城市。编号为 \(1,2,3,\ldots,n\) 。 城市之间有 \(m\) 条双向的公路，连接着两个城市，从某个城市到另一个城市，会遭到联盟的攻击，进而损失一定的血量。 每次经过一个城市，都会被收取一定的过路费（包括起点和终点）。路上并没有收费站。 假设 \(1\) 为暴风城，\(n\) 为奥格瑞玛，而他的血量最多为 \(b\) ，出发时他的血量是满的。 歪嘴哦不希望花很多钱，他想知道，在可以到达奥格瑞玛的情况下，他所经过的所有城市中最多的一次收取的费用的最小值是多少。 本题的数据是真的水，而且也没说清楚 \(b\) 最后可不可以为 \(0\) ，瞎搞的做法都能写 81pts qwq 看到最大值最小，首先可以想到二分 事实上，由于我们不清楚血量和最小值究竟有何关系（没关系），也只能用二分 注：二分的是这个最小值 在二分了一个值后，我们把伤害看作边权，然后跑个最短路，找一下最少伤害的路径，判断一下能不能到达终点即可 细节还是有点多的 qwq 懒得讲了看代码...