比赛链接：https://codeforces.com/contest/1156

C

二分、贪心

题目链接：https://codeforces.com/contest/1156/problem/C

题面

image.png

题意

输入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

并查集，图论

赛后看官方题解补的题

题意

image.png

给一棵n个顶点n - 1条边的树，这些边中有的标记为1，有的标记为0。如果一对顶点(x, y)，从x走到y，绝对没有在经过0边之后经过1边，那么它就是合法的。

官方题解翻译

把所有合法的对分成3类

1. 只有0边的
2. 只有1边的
3. 两种都有的

• 为了计算只有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;
}