互诺科技做网站怎么样,php网站访问很慢,商务网站开发工具,北京vi设计培训这篇文章的所有题目均来自于自行整理#xff0c;代码均来自于自行梳理调试#xff08;思路可能比较暴力#xff09;。初衷在于整理练习思路#xff0c;且起到督促自己学习的作用
本文分成将三个模块
1.普及组 #xff08;洛谷黄题#xff09;
2.提高组 #xff08;洛…这篇文章的所有题目均来自于自行整理代码均来自于自行梳理调试思路可能比较暴力。初衷在于整理练习思路且起到督促自己学习的作用
本文分成将三个模块
1.普及组 洛谷黄题
2.提高组 洛谷绿题
3.省选组 洛谷蓝题及以上
一、普及
1.P3367 【模板】并查集
普通并查集纯板子不加解释
传送门https://www.luogu.com.cn/problem/P3367
// Problem:
// P3367 【模板】并查集
//
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3367
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#includeiostream
using namespace std;
const int N1e410;
int e[N];int find(int x){if(x!e[x]) e[x]find(e[x]);return e[x];//返回根节点
}void merge(int a,int b){int xfind(a);int yfind(b);//e[x]y;连接到另外一个上我看了看板子更加复杂但是符合原理都能过这里前面加一个if(x!y)会更好若不然可能增加路径压缩的次数
}int main(){int n,m;cinnm;for(int i1;in;i) e[i]i;while(m--){int a,b,c;cinabc;if(a1){merge(b,c);}else{int k1find(b);int k2find(c);if(k1k2) coutYendl;else coutNendl;}}return 0;
} 2.P1551 亲戚
传送门https://www.luogu.com.cn/problem/P1551
一道算是应用场景的题目可以拿来熟熟手
// Problem:
// P1551 亲戚
//
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1551
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#includeiostream
using namespace std;
const int N5005;
int fa[N];int find(int x){if(x!fa[x]) fa[x]find(fa[x]);return fa[x];//返回根节点
}void merge(int a,int b){int xfind(a);int yfind(b);fa[x]y;
}int main(){int n,m,p;cinnmp;for(int i1;in;i) fa[i]i;while(m--){int a,b;cinab;merge(a,b);}while(p--){int a,b;cinab;int xfind(a),yfind(b);if(xy) coutYesendl;else coutNoendl;}return 0;
} 3.P1111 修复公路
传送门https://www.luogu.com.cn/problem/P1111
五花八门的答案结合了一点排序知识
本人用了结构体排序后全遍历Onm的时间复杂度1e8擦边过了
// Problem:
// P1111 修复公路
//
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1111
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#includeiostream
#includealgorithm
using namespace std;
const int N1e310;
int fa[N];
struct node{int a,b,c;bool operator (const node p)const {return cp.c;};//重载
}nodes[100005];int find(int x){if(x!fa[x]) fa[x]find(fa[x]);return fa[x];
}void merge(int x,int y){int afind(x),bfind(y);if(a!b) fa[a]b;//还是这么写吧时间更优一点
}int main(){int n,m;cinnm;for(int i1;in;i) fa[i]i;for(int i1;im;i){cinnodes[i].anodes[i].bnodes[i].c;}sort(nodes1,nodes1m);for(int i1;im;i){merge(nodes[i].a,nodes[i].b);bool checktrue;for(int i2;in;i){if(find(i)!find(i-1)){//这里注意合并完没有merge的fa是没有直接更新的不能直接比较fa[i]checkfalse;break;}}if(check){coutnodes[i].cendl;return 0;}}cout-1endl;return 0;
}
这个地方有更优的方法Om遍历一遍如果遇到根节点不同连通块数量减一并合并这样连通块数量等于1的时候输出答案就好了只需要操作n-1次 4.P2814 家谱
传送门https://www.luogu.com.cn/problem/P2814
这道题我个人结合了map调到吐血越改越复杂细节还是蛮多的不熟练
#includeiostream
#includemap
using namespace std;
const int N5e410;
int fa[N];
mapstring,int mp;//记录每个点的标记
mapint,string mpp;//在最后返回根节点的字符串
int cnt;int find(int x){if(x!fa[x]) fa[x]find(fa[x]);return fa[x];
}void merge(int f,int a){int xfind(f),yfind(a);if(x!y) fa[y]x;
}int main(){string s;int now;while(cins){string ks.substr(1);if(s$) break;else if(s[0]#){if(!mp[k]){mp[k]cnt;fa[cnt]cnt;nowcnt;mpp[cnt]k;}else nowmp[k]; }else if(s[0]){if(!mp[k]){mp[k]cnt;fa[cnt]cnt;mpp[cnt]k;}merge(now,mp[k]);}else{int tfind(mp[k]);
//这个地方WA了n发因为最后步find这里还保留的是上一次的father要find一次才能更新coutk mpp[t]endl;}} return 0;
}
除了我的代码外这里奉上大佬的一个题解一样的思路但是代码简单炉火纯青。
我被板子局限了思路确实没想到路径压缩可以直接压缩map 5.P1536 村村通
传送门https://www.luogu.com.cn/problem/P1536
这道题如果把前面的吃透了想起本文第三题结尾大佬的一个办法计算连通块数量如果find查找的根节点不同就连通块数量-1并合并连通块开始初始化为n-1。
// Problem:
// P1536 村村通
//
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1536
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#includeiostream
using namespace std;
const int N1005;
int fa[N];int find(int x){if(x!fa[x]) fa[x]find(fa[x]);return fa[x];
}void merge(int a,int b){int xfind(a),yfind(b);if(x!y) fa[x]y;
}int main(){int a,b;while(cina){if(a0) break;for(int i1;ia;i) fa[i]i;cinb;int ansa-1;while(b--){int x,y;cinxy;if(find(x)!find(y)) ans--,merge(x,y);}if(ans0) coutansendl;else cout0endl;} return 0;
}
这种方法的初衷其实更适合实时在某一刻卡断一类的就是说能知道各时刻连通块的数量这道题其实暴力就可以解决掉因为给的全部都要操作 6.P3958 [NOIP2017 提高组] 奶酪
传送门https://www.luogu.com.cn/problem/P3958非常伤心这道题卡了我两个钟最终发现原因h的范围是1e9不能直接暴力写假了
其实就是一段算成一个点合并集合最后把上下两个面再维护一下看看上下两个面在不在一个集合里可以配合这篇远古大神 食用~
// Problem:
// P3958 [NOIP2017 提高组] 奶酪
//
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3958
// Memory Limit: 250 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#includeiostream
#includevector
#includealgorithm
using namespace std;
const int N1003;
#define int long long
int fa[N];
int n,h,r;
struct node{int a,b,c;
}nodes[N];
bool check(node x,node y){int num(x.a-y.a)*(x.a-y.a)(x.b-y.b)*(x.b-y.b)(x.c-y.c)*(x.c-y.c);if(num(2*r*r*2)) return false;return true;
}
int find(int x){if(x!fa[x]) fa[x]find(fa[x]);return fa[x];
}
void merge(int a,int b){int xfind(a),yfind(b);if(x!y) fa[y]x;//高的往低处接
}
signed main(){int t;cint;while(t--){cinnhr;for(int i1;in2;i) fa[i]i;for(int i1;in;i){cinnodes[i].anodes[i].bnodes[i].c;}for(int i1;in;i){for(int ji1;jn;j){if(check(nodes[i],nodes[j])){merge(i,j);}}}for(int i1;in;i){if(nodes[i].c-r0) merge(i,n1);if(nodes[i].crh) merge(i,n2);//看看能不能串起来}if(find(n1)find(n2)) coutYesendl;else coutNoendl;}return 0;
} 二、提高
