1551专题

二分总结:HDU 1551,4190;POJ 1905,3273,3122,3518;CF 371C

感觉:首先,先总结这两天做的二分题目。 因为根据这几个月以来做的CF还有组队赛,里面似有似无的存在着二分的影子,而二分以前还没有系统的做过,所以总是自己的弱项。再在终于狠下心来学习了。 学了两天,收获还是挺多的。 二分的用处太大了,不管是求简单的方程,还是求最优解方面都是不错的解题思想。 只要在线性,顺序或者有序的数据里就可以用二分来找最优的答案,而且时间平均都是O(log2 n)。题目中

洛谷_1551 亲戚

题目 题意: 给出n个人的亲戚关系,之后给出p对人,判断这两个人之间有没有亲属关系。 思路: 因为这是并查集的例题,所以这里用并查集,每次读入都让它们合并起来,可以压缩路径。 代码: #include<cstdio>int n,m,p,x,y,father[50001];int find(int a){if (father[a]!=a) father[a]=find(f