算法过程:(路径压缩) 1.最开始每个人都是自己的父亲节点 2.递归找根节点. (非递归也可) 如果f[x] != x(不是根节点) f[x] = getf(f[x]); -----路径压缩 否则 返回 x; 3.查询x,y是否在同一个集合. 3.1 先找出x,y所在集合的两棵树的根节点.fx,fy(擒贼先擒王原则) 3.2 判断fx == fy 3.2.1(真) 返回真. 3.2.2(假) 3.2.2.1 将fy的父节点变为fx (靠左原则) 解释: ①代码看Kursal算法模板. ②复杂度:O(logn) 数学分析:https://blog.csdn.net/wang3312362136/...

思想:贪心+并查集 算法过程: 最开始图为一个一个独立的点. 1.将边的权值从小到大排序. --贪心 2.从权值小的开始往图中添加边. 如果这个边的起点和终点在之前选的边的影响下就已经连通 --并查集 不选此边(选了也多余) --贪心 否则 将此边添加到图中. 3.直到选完n-1条边.(选不完代表此图不连通) 解释: ①复杂度:快排MlogM,N-1次并查集LogN => O(MlogM) --- 通常M远大于N ②检查两点的连通性可用dfs,bfs,但复杂度太高，转换成集合，使用并查集. 代码(洛谷模板题): #include<bits/stdc++.h> using na...

算法过程:（贪心，动态规划） 将图中点分成两个集合，一个是在最小生成树中，一个尚不在。称为P,Q集合（用book数组标记） dis[i]代表某个阶段第i个点到最小生成树的最近的距离(实质是边的权值).最开始都为INF. 最开始P集合为空，Q为全集 最终态P为全集，Q集合为空 1.将任意一个点放入优先队列W.对应dis值置0. 2.当W不为空时，从里面拿出一个离最小生成树最近的一个边.(最开始为0) 3.对这个边的终点E进行拓展，将所有能够更新dis数组的边推入W（边的终点S要在Q集合中）. 4.跳到2. 解释: 复杂度:O(MlogM) ----M为边数 ①过程大致是从邻接着现阶段最小生成树的...

传送门: https://blog.csdn.net/nka_kun/article/details/80488297 A.换钞票 题意: x星球的钞票的面额只有：100元，5元，2元，1元，共4种。 小明去x星旅游，他手里只有2张100元的x星币，太不方便，恰好路过x星银行就去换零钱。 小明有点强迫症，他坚持要求200元换出的零钞中2元的张数刚好是1元的张数的10倍， 剩下的当然都是5元面额的。 银行的工作人员有点为难，你能帮助算出：在满足小明要求的前提下，最少要换给他多少张钞票吗？ （5元，2元，1元面额的必须都有，不能是0） 太水了。。一个循环判一下就好. B.激光样式 x星球的盛大节日...

传送门: https://blog.csdn.net/nka_kun/article/details/80488297 A.换钞票 题意: x星球的钞票的面额只有：100元，5元，2元，1元，共4种。 小明去x星旅游，他手里只有2张100元的x星币，太不方便，恰好路过x星银行就去换零钱。 小明有点强迫症，他坚持要求200元换出的零钞中2元的张数刚好是1元的张数的10倍， 剩下的当然都是5元面额的。 银行的工作人员有点为难，你能帮助算出：在满足小明要求的前提下，最少要换给他多少张钞票吗？ （5元，2元，1元面额的必须都有，不能是0） 太水了。。一个循环判一下就好. B.激光样式 x星球的盛大节日...

近几天看了一下2019省赛的题目，其他题基本没什么营养。 最后一题还是有难度的，有CF思维题内味儿了.特此记录一下. 题面:          思路: 发现一次操作,整体的和是不变的.观察其前缀和.  a1 a2 a3 -> s1 s2 s3.   观察对a2操作.   s1 变为 s1 + a2 = s2 s2 变为 s2 - 2*a2 +a2 = s1. s3 不变. 转换成前缀和S后就相当于让你合理安排顺序使得两个相邻的数的差值的最大值最小.显然将其排序可做到这一点. 又发现:对某个点i操作以后相当于si-1 和 si 互换.所以直接排序可行。 最后注意一点,由题意可知Sn是不能参...

题面: 把0~9这10个数字，分成多个组，每个组恰好是一个平方数，这是能够办到的。 比如：0, 36, 5948721 再比如： 1098524736 1, 25, 6390784 0, 4, 289, 15376 等等… 反思：很早就想出思路，但是打代码的时候太多细节没想清楚,dfs的过程也是改来改去的。不过做了这道题，还是有学到点东西的，特此记录. 思路: 首先肯定是一道dfs题，所以可行解肯定不多，所以先预处理一下O(nlogn)0~9876543210之间，有多少i^2符合数位里没有重复数字。得出来611.可写。 因为0~9每个值都只出现一次.自然想到将上述那些数编码成一个二进制数,第...

传送门:https://ac.nowcoder.com/acm/contest/2272#question 我的第一篇博客。。之前都是自己在电脑上写总结. emm,比赛的时候只做出四道，后来发现其实还有2.3道都是很水的题。。哎，太久没刷题,思路都不够快了。今天爆肝补完只剩一道了。. A:水题  题意:给你n个数,每个数取值在[1,1000],这n个数都严格递增。问你最多能去掉多少个数，使得删掉之后依旧能推出每个删掉的数. 例如: 1 2 3 4 5 ,那么可以删除2 3 4.输出3. 思路;观察到数据范围很小,n^2枚举所有起始点，看从这个点开始能往后拓展多少个数.要求当前区间的第一个数之前...

所以大佬们是怎么推出那个递推式子的呢,这也太难凑了吧