本文主要是介绍POJ1182可能是史上最好懂的/.. ... 以及 并查集CodeForces - 722C，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目https://cn.vjudge.net/problem/POJ-1182
最开始看了个很长的_(:з」∠)_然后发现看不懂https://blog.csdn.net/c0de4fun/article/details/7318642
觉得好难_(:з」∠)_直到我发现这题抽特王两年前就轻轻松松过了.....(所以说我还是真不能没有抽特王(划掉))
下面上代码(参考的哪里的!!)
#include <iostream>
#include <cstdio>
using namespace std;
int rrank[50005];
int fa[50005];
int n, k;
void init()
{for (int i = 0; i < 50005; i++)rrank[i] = 0, fa[i] = i;
}
int find_father(int x)
{if (x == fa[x])return x;int temp = fa[x];fa[x] = find_father(fa[x]);rrank[x] = (rrank[x] + rrank[temp]) % 3;return fa[x];
}
int main()
{scanf_s("%d%d", &n, &k);init();int ans = 0;while (k--){int a, b, c;scanf_s("%d%d%d", &c, &a, &b);if (a > n || b > n){ ans++; continue; }int x = find_father(a);int y = find_father(b);if (x == y){if ((rrank[y] - rrank[x] + 3) % 3 != c - 1){ans++; continue;}}else{fa[y] = x;rrank[y] = (rrank[a] - rrank[b] + c - 1 + 3) % 3;continue;}}printf("%d\n", ans);return 0;
}(可能没那么详细但是比史上最详细那个还要好懂因为这来自于一个制杖闪避_(:з」∠)_)
//有三个关系呀,0 , 1,2
这个啊,就像是在圆环里面跑,每次都%3,就跑着跑着不会出去啦,并查集最开始初始化的时候把这个权值r都话成0
(0就是自己和自己一组,满足)
(然后,find_father的时候也是要把rank都%3以免越界)
网上看了很多都不太懂..())
所以 还是不要贪多 然后懂了要真懂_(:з」∠)_.......剩下那兜风的40分钟想这个就更好了_(:з」∠)_
就是说啊,我感觉这个并查集,有一点像是基于连通块的操作,比如,怎么维护呢?
(1)以1,2/1,3/1,4为例
首先,x和y嘛,x是y的爸爸,然后rank相加一下(但是这里加的是c-1,为了统一起来)
这个时候,1和2就在一个大家族里了,然后1还是0 ,因为他是长老啊,不用管事的,然后2变成了一名上士,rank是1(因为2-1,c=2是有阶级关系的代号-)
然后1和3,竟然1和3也在一个大家族里,这样1也是3的爸爸,3也是rank是1啦
如果是2和3呢?最后找到3的爸爸是2,2 的爸爸是1,但是这个家里只有三层关系,最低位的奴仆虽然受到上士的管辖,上士也受到长老的管辖,但这种奴仆偷看过长老洗澡!!!!他拥有让长老闭嘴的能力
(个人感觉这个可以扩展出很多...如果不止3个的话,是不是就会循环跑起来了?比如千里之堤毁于蚁穴-有待商榷)
这个时候呢,因为3是没被访问过的,最开始加进来所以要登记,就不去跑那个x==y
你是新加进来的，rrank[y] = (rrank[a] - rrank[b] + c - 1 + 3) % 3;
前面是2的rank是1，自己的rank是0，再加上（c-1=1）
就像这个2晃着自己的rank得意洋洋的说我已经有个官儿啦，你要是还是想当官儿的话只能当我后面的那个奴仆
又由于地球是圆的……那么1 的rank是0,3的rank是2,2+1%3又是0，那个奴仆其实也可以偷偷管到长老的嘿嘿嘿_(:з」∠)_
(如果x==y,就是后面又查询到的呀,要跟前面那个对应起来-比如又来到那个1,1,2,1和2是同一个集合吗?rank 1=0,rank2=1,(rank2=1是从属关系呀)然后1-0不等于0(0就是在一个集合里面),但是,2 和3 的话(由1 2 /1 3来的2和3,因为当时加的时候爸爸都是1,针对于1都是吃的关系,也就是对于1来说要么和他一样,要么吃他,要么被他吃呀。这样就可以很轻易地得到答案))
(2)以1,2/2,3/3,1
啊，写过了……
然后就是，如果你是刚加进来的话，fa肯定不相等，就初始化一下你这个ranka+rankb
如果后面再维护的话（我总觉得这个x==y就是他们肯定在这个大长老的淫威之下见过面……然后再验证一下是不是属于这三个阶级~）
好,下面上一下上个并查集的代码..
算了不上了,在前面一篇,你们自己去翻吧
诶呀呀，理解了和自己能写出来还差一大截子呢_(:з」∠)_
明天加油哦！୧(๑•̀◡•́๑)૭
====再更新====
和抽特王去吃了个晚饭，他听完大为震惊“啊，这个是很经典的模型啊，2001年xxx就出了吧”随即又冷静下来“这个不就是普通的并查集吗”我：“……”
然后就是，其实 啊我感觉上面那个（并不是加权并查集……）根本就用不到那个呀其实只要访问一下不就完了吗……
他说“哦，这个啊，这就是很多骚技巧了，当时很多人都不知道是并查集，就一堆乱搞然后就过了，……“ 我：“&*…￥##”
然后呢_(:з」∠)_大概解释一下上面非常详细的那个（非常详细也一样没用啊！一句话点醒你才是关键呀hh）
因为啊，因为只有朋友和敌人两种关系（假设是1 和2 两个集合的话），那就弄两个集合，如果他和你不是朋友关系，那么他的虚拟节点就和你是朋友关系。（就像另个时空~~~）
最后查一下就好了。。。
三个的话就是，它和你
……我不懂了。等会补充吧
（参考白皮-挑程）
return 0;}(choute wang de)
加权并查集的话就是多一个距离，不过也不难的，sf的时候多写一点就好啦。
====更新====(是个并查集但是和上面没啥关系-.-)
这题槽点满满啊=.=但还好吧我终于又一次体会到了A题的乐趣娃哈哈哈哈哈哈哈哈当你有什么不懂的时候就去放空自己逛校园吧.... 网址 https://vjudge.net/contest/229428#problem/E
虽然这个题zj写了十分钟就A掉了可我....差距嘛(摆手)
我的代码(自从爱上codeblocks我开始减少以前写一大堆的注释了_(:з」∠)_)
哎……是并查集，倒着，zj“好，我们已经ac了”然而我还在写不出来的边缘徘徊
有一个小地方，就是数据是包括0的，然后要用ll的，因为1e9嘛（其实这个开场的时候就要看，，，对数据敏感一点啊喂）
还有就是【不要耍小聪明，在实现这一方面】
追求更快更高以你现在的水平干嘛……（参见矩阵那个题），比如我最开始没用vis数组，直接sum代替了，但是有0的话就会对0 0 0 7 0 0 8 0 0 9这种造成影响_(:з」∠)_让你以为他没访问过，具体各种原因，再连的时候就连不对位置了！！！！很麻烦的！！！这时候就不要贪图小便宜！！！以及最开始，因为左边右边都要连接嘛，只想先连左边的的时候不药sf直接fa，（虽然没 想明白为什么，但是改掉之后样例就对了……）干嘛省去这点时间……你不知道出什么幺蛾子，既然下面写了上面也是统一成sf吧！！！
还有，就是，这里要先写sum+，然后再合并爸爸，否则就成了自己加自己了！！这种啥啥啥的能力很重要!!!
sum[sf(p-1)]+=sum[sf(p)];//sum[sf(p)];fa[sf(p)]=sf(p-1);#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll a[100005];
ll b[100005];
ll sum[100005];
ll ans[100005];
ll fa[100005];
int vis[100005];
//int sf(int x){x=fa[x]?x:fa[x]=sf(fa[x]);}
ll sf(int x) {return fa[x]==x?x:fa[x]=sf(fa[x]);
}//没有返回值都不报错！！！！
int main(){int n;cin>>n;ll maxn=0;for(int i=1;i<=n;i++){cin>>a[i];fa[i]=i;sum[i]=0;}for(int i=1;i<=n;i++)cin>>b[i];for(int i=n;i>=1;i--){ll p=b[i];vis[p]=1;sum[p]=a[p];//总感觉把sum写成p 多了点什么???if(vis[p-1]==1){sum[sf(p-1)]+=sum[sf(p)];//sum[sf(p)];fa[sf(p)]=sf(p-1);//他们现在是一个爸爸了}if(vis[p+1]==1){//如果他也访问过的话//这里如果还是写fa的话,前后就不能联系起来//因为你如果进行了初始化操作,你要连的是p-1的fa//而不是孤零零自己的fa,这时候这个p已经不是独立的个体 了sum[sf(p+1)]+=sum[sf(p)];//相应的,一旦这个p身上的担子更重了...就不能只加p他自己fa[sf(p)]=sf(p+1);}maxn=max(maxn,sum[sf(p)]);//你不得不承认什么都sf一下最保险了不是吗....ans[i]=maxn;}for(int i=2;i<=n;i++)cout<<ans[i]<<endl;cout<<"0"<<endl;return 0;
}好了zj的代码_(:з」∠)_(我没测)
#include<iostream>
#include<cstdio>
#include<algorithm>using namespace std;
typedef long long ll;const int mn = 1e5 + 5;
int n;
int f[mn];
int sf(int x) { return f[x] == x ? x : f[x] = sf(f[x]); }
ll s[mn];
int b[mn];
ll ans[mn];
bool vis[mn];int main() {ios::sync_with_stdio(0);//int u != 0;//cout << u << endl;cin >> n;for (int i = 1; i <= n; i++) cin >> s[i], f[i] = i;for (int i = 1; i <= n; i++) cin >> b[i];ll maxi = 0;for (int j = n; j > 1; j--) {int i = b[j];vis[i] = 1;//那么优秀的人的代码和 我差了多少呢if (i > 1 && vis[i - 1] == 1 && sf(i) != sf(i - 1)) {int u = sf(i); f[u] = sf(i - 1);s[sf(i - 1)] += s[u];s[u] = 0;//nothing}//简化了一点+1//serchfather 要记一下if (i < n &&vis[i + 1] == 1 && sf(i) != sf(i + 1)) {int u = sf(i);f[u] = sf(i + 1);s[sf(i + 1)] += s[u];s[u] = 0;//nothing}maxi = max(maxi, s[sf(i)]);ans[j - 1] = maxi;}for (int i = 1; i <= n; i++) cout << ans[i] << "\n";return 0;
}
这篇关于POJ1182可能是史上最好懂的/.. ... 以及 并查集CodeForces - 722C的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
