比赛链接：https://codeforces.com/contest/1156
C
二分、贪心
题目链接：https://codeforces.com/contest/1156/problem/C
题面
题意
输入n，z和n个数x[1]~x[n]。
然后判断这n个数里有几对不相等的i, j。使得|x[i] - x[j]| >= z
思路
这个题贪心也能过，但我赛后补题是学习了quailty二分的思想。
二分思想
经过这道题之后我对二分有了更进一步的理解。
如果对于某道题满足这个条件：答案m满足要求，并且大于m的数有可能也满足要求，并且比m要优，虽然小于m的数也满足要求，但小于m的数相对于m来说不如m优。在这个情况下我们就可以用二分。
联系题目
对于这道题来说，先对数组排序，然后如果存在前m个数和后m个数满足要求|a[i] - a[j]| >= z，那么可能存在l对数(l > k)也满足要求。
虽然说存在r对数(r < k)也满足要求，但相对于k来说，r不如k优。
所以这道题我们可以用二分
算法思想
可以先写一个函数，判断前m个数和后m个数是不是相等。
对于n个数，最好的情况下可以找到n / 2对数，每一对数的绝对值大于等于z，最坏情况是0。所以二分的范围就是0到n / 2。
令l = 0, r = n / 2为初值二分，每次算m = (l + r + 1) / 2(后面会解释为什么这里要写(l + r + 1) / 2而不是(l + r) / 2)，如果m满足要求，则让l = m(最后输出l，所以不能让l = m + 1，因为可能m就是最优解了)
如果m不满足要求，那么就直接让r = m - 1因为m已经不满足要求了，所以接下来的预选区间应该缩减到r = m - 1。
如此往复，直到l < r不满足为止。
二分需要注意的点（解释为什么写(l + r + 1) / 2）而不是(l + r) / 2)
一定要注意边界条件，也就是l和r只相差1的时候，要不然容易造成死循环
因为这里我们需要收缩右边界r = m - 1，所以求m的时候需要些
对于这道题来说,当r = l + 1时，为了说明方便，在此令l = 2, r = 3。
- 写
m = (l + r + 1) / 2的情况
当l = 2, r = 3时，m = (2 + 3 + 1) / 2 = 3，
如果m不满足要求，我们会修改右边界，令r = m - 1 = 2。然后l == r == 2，退出循环，最优解是2。
如果m满足要求，那么l = m = 3 = r，也退出循环，最优解是3。 - 写
m = (l + r) / 2的情况
当l = 2, r = 3时，m = (2 + 3) / 2 = 2。
如果m不满足要求，那么我们让r = m - 1 = 1，退出循环，虽然说出现了问题，但最后的结果l还是最优解
当m满足要求时，我们会让l = m = 2,在这次操作中，l和r的值没有改变，再来一次循环，求出来的还是m = (2 + 3) / 2 = 2，l = m = 2，这样就会造成死循环。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
const int inf = 0x3f3f3f3f;
#define LOCAL
const int maxn = 2e5 + 7;
long long n, z;
long long a[maxn];
bool ok(int m){
for (int i = 1, j = n - m + 1; j <= n; i++, j++){
// cout << i << " " << j << endl;
if (a[j] - a[i] < z){
return false;
}
}
return true;
}
int main(int argc, char * argv[])
{
while (cin >> n >> z){
for (int i = 1; i <= n; i++){
cin >> a[i];
}
sort(a + 1, a + 1 + n);
int l = 0, r = n / 2;
while (l < r){
int m = (l + r + 1) / 2;
if (ok(m)){
l = m;
}
else{
r = m - 1;
}
}
cout << l << endl;
}
return 0;
}
D
并查集，图论
赛后看官方题解补的题
题意
给一棵n个顶点n - 1条边的树，这些边中有的标记为1，有的标记为0。如果一对顶点(x, y)，从x走到y，绝对没有在经过0边之后经过1边，那么它就是合法的。
官方题解翻译
把所有合法的对分成3类
- 只有0边的
- 只有1边的
- 两种都有的
- 为了计算只有0边的，我们可以把原图的0边创建成一个森林。并且选择这个森林上所有属于相同联通分支的成对的边。我们可以用DSU算法或者任何图的遍历算法找所有的联通分支。
- 对于只有1的边也可以这样子。
- 如果一条从x到y的路径是合法的并且它包含两种类型的边，然后会存在一个点v，使得从x到v的边只包含0，从v到y的边只包含1.所以我们在这个v点上迭代，从0图中的组件选择其他顶点，从1图中选择其他顶点，并将选择他们的方法的数量添加到答案中。
解题思路
其实看了题解之后我也是很懵的，思路是这个思路，可怎么实现我还是搞不懂。
不如看官方给的代码吧，emmm看不懂，仔细一看，并查集？
对！就是并查集！
开两个并查集，一个是0边构成的并查集，一个是1边构成的并查集。也就相当于把一棵树拆分成两个子图，一个是1边构成的，一个是0边构成的（如果某个顶点没有被0边连接，则在0这个并查集里，它是个孤立的点，在1边也类似）。
参见官方题解翻译的“1”，我们对于0并查集，假设一个联通分支的元素个数是x，那它里面就含有x * (x - 1)个合法的对，1并查集也类似。
对于每个点来说，它在0并查集里所属的联通分支的元素个数为x，在1并查集里所属的联通分支的元素个数为y，那么它被当做v时合法的方案数就是(x - 1) * (y - 1)
// #pragma comment(linker, "/STACK:1024000000,1024000000")
#include <stdio.h>
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <string>
#include <cstring>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <ctime>
#include <vector>
#include <fstream>
#include <list>
#include <iomanip>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(s) memset(s, 0, sizeof(s))
const int inf = 0x3f3f3f3f;
#define LOCAL
const int maxn = 2e5 + 7;
long long p[2][maxn]; // 代表两个并查集
long long sz[2][maxn]; //
long long n;
long long x, y, c;
long long root(long long x, long long c){
while (x != p[c][x]){
p[c][x] = p[c][p[c][x]];
x = p[c][x];
}
return x;
}
void uni(long long x, long long y, long long c){
int x_root = root(x, c);
int y_root = root(y, c);
if (sz[c][x_root] > sz[c][y_root]){
swap(x_root, y_root);
}
p[c][x_root] = p[c][y_root];
sz[c][y_root] += sz[c][x_root];
}
void init(){
for (int i = 1; i <= n; i++){
p[0][i] = p[1][i] = i;
sz[0][i] = sz[1][i] = 1;
}
}
void print(){
printf("p[0]\n");
for (int i = 1; i <= n; i++){
printf("%lld%c", p[0][i], i == n ? '\n' : ' ');
}
printf("p[1]\n");
for (int i = 1; i <= n; i++){
printf("%lld%c", p[1][i], i == n ? '\n' : ' ');
}
printf("sz[0]\n");
for (int i = 1; i <= n; i++){
printf("%lld%c", sz[0][i], i == n ? '\n' : ' ');
}
printf("sz[1]\n");
for (int i = 1; i <= n; i++){
printf("%lld%c", sz[1][i], i == n ? '\n' : ' ');
}
}
int main(int argc, char * argv[])
{
while (cin >> n){
long long ans = 0;
init();
for (int i = 1; i <= n - 1; i++){
cin >> x >> y >> c;
uni(x, y, c);
// print();
// cout << i << " " << n << endl;
}
for (long long i = 1; i <= n; i++){ // 枚举每个点
if (p[0][i] == i){ // 如果在0并查集里，它的父亲等于它自己，那么它就可以代表它所在的联通分支（它是这个联通分支的祖先）
ans += sz[0][i] * (sz[0][i] - 1);
}
if (p[1][i] == i){// 如果在1并查集里，它的父亲等于它自己，那么它就可以代表它所在的联通分支（它是这个联通分支的祖先）
ans += sz[1][i] * (sz[1][i] - 1);
}
ans += (sz[1][root(i, 1)] - 1) * (sz[0][root(i, 0)] - 1); // 注意这里下标是root
}
cout << ans << endl;
}
return 0;
}
