前言

72 是个伞兵,他每次基础算法都不能好好运用。所以开了一篇博客,记录一些他平时用到的基础算法

并查集

目标

  • 将两个集合合并
  • 查询两个元素是否在同一集合内

构造

每个集合用一棵树表示,用根节点的编号表示整个集合的编号,开一个数组 \(p[x]\) ,表示编号为 \(x\) 的元素的父节点编号

  • \(p[x] = = x, x\) 为树根。
  • \(x\) 的集合编号:while(p[x] != x) x = p[x]
  • 合并两个元素所在集合,设 \(px,py\) 表示 \(x,y\) 的集合编号,p[px]=py

路径压缩

这样的确可以达成目的,但是显然效率实在太低。为什么呢?因为我们使用了太多没用的信息,我的祖先是谁与我父亲是谁没什么关系,这样一层一层找太浪费时间,不如我直接当祖先的儿子,问一次就可以出结果了。甚至祖先是谁都无所谓,只要这个人可以代表我们家族就能得到想要的效果。 把在路径上的每个节点都直接连接到根上 ,这就是路径压缩。——OI-Wiki

代码

int n, p[N];
void init()//初始化
{
    for(int i = 1; i <= n; i++) p[i]=i;
}
int find(int x)//查询x的集合编号
{
    if(p[x]!=x) p[x] = find(p[x]);
    return p[x];
}
void merge(int x, int y)//合并xy所在集合
{
    x = find(x), y = find(y);
    if(x == y) return;
    p[x] = y;
}

扩展

维护 size 的并查集

    int p[N], size[N];
    //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义,表示祖宗节点所在集合中的点的数量

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化,假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        size[i] = 1;
    }

    // 合并a和b所在的两个集合:
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);

维护到祖宗节点距离的并查集

    int p[N], d[N];
    //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x)
        {
            int u = find(p[x]);
            d[x] += d[p[x]];
            p[x] = u;
        }
        return p[x];
    }

    // 初始化,假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        d[i] = 0;
    }

    // 合并a和b所在的两个集合:
    p[find(a)] = find(b);
    d[find(a)] = distance; // 根据具体问题,初始化find(a)的偏移量

CF731C-Socks

题意

有 n 只袜子,k 种颜色,给定每只袜子的颜色,在 m 天中,问最少修改几只袜子的颜色,可以使每天要穿的袜子颜色相同。

分析

用并查集维护需要保证是同一个颜色的集合,由题意,同一天的两个编号必定在同一个集合内。

而后统计每个集合内哪一个颜色的数量最多,集合的大小减去最大的数量即为这个集合需要修改的数量。

将所有集合的贡献累加即为答案

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 200010;
int p[N], c[N], cnt[N], n, m, k;
vector<int> v[N];
int find(int x)
{
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; i++)
    {
        p[i] = i;
        scanf("%d", &c[i]);
    }
    for (int i = 1, l, r; i <= m; i++)
    {
        scanf("%d%d", &l, &r);
        int pl = find(l), pr = find(r);
        if (pl != pr)
            p[pl] = pr;
    }

    for (int i = 1; i <= n; i++)
    {
        int tmp = find(i);
        v[tmp].push_back(c[i]);
    }
    int res = 0;
    for (int i = 1; i <= n; i++)
    {
        int tn = v[i].size(), mx = 0;
        if (!tn)
            continue;
        for (int j = 0; j < tn; j++)
        {
            cnt[v[i][j]]++;
            mx = max(mx, cnt[v[i][j]]);
        }
        for (int j = 0; j < tn; j++)
            cnt[v[i][j]]--;
        res += tn - mx;
    }
    printf("%d\n", res);
    return 0;
}

CF362D Fools and Foolproof Roads

题意

给定 n 个点 m 条边的无向图,问是否能在图里添加 p 条边使得加边后存在恰好 q 个连通分量,同时请求出边权总和最小的方案。

新增边的边权为 \(min(10^{9}, S+1)\) ,其中 S 为这条边连接的两个联通块的边权之和。

分析

维护一个并查集来表示联通块,由题意要额外维护联通块的大小去计算连边的代价。

判断无解的情况:

  1. 将联通块进行了 p 次连边后依然联通块的数量大于 q
  2. 未连边前联通块数量小于 q
  3. 点的数量为 q ,且不存在边,此时若 p 非 0,由于不允许自环,故无解

求最优的方案时,将联通块压入优先队列,每次取最小的两个联通块合并,保证每次合并的边权最小

若还没有用完 p 次连边就已经满足条件,则在任意一联通块内找任意两点,将剩下所有连边加在这两个点上

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 1e5 + 10, inf = 1e9;
typedef pair<ll, ll> pii;
ll p[N], w[N], n, m, pp, q, cnt;
struct cmp
{
    bool operator()(const pii p1, const pii p2)
    {
        return p1.first > p2.first;
    }
};
priority_queue<pii, vector<pii>, cmp> blk;
ll find(ll x)
{
    if (x != p[x])
        p[x] = find(p[x]);
    return p[x];
}
void merge(ll x, ll y, ll l)
{
    ll px = find(x), py = find(y);
    if (px == py)
        w[px] += l;
    else
    {
        p[px] = py;
        w[py] += l + w[px];
        cnt--;
    }
}
int main()
{
    scanf("%lld%lld%lld%lld", &n, &m, &pp, &q);
    cnt = n;
    for(ll i = 1; i <= n; i++) p[i] = i;
    for (ll i = 1, x, y, l; i <= m; i++)
    {
        scanf("%lld%lld%lld", &x, &y, &l);
        merge(x, y, l);
    }
    if(cnt - pp > q || cnt < q)
    {
        puts("NO");
        return 0;
    }
    if(!m && !(q - n) && pp)
    {
        puts("NO");
        return 0;
    }
    puts("YES");
    for (ll i = 1; i <= n; i++)
        if (i == find(i))
            blk.push({w[p[i]], i});
    while (cnt > q)
    {
        pii b1 = blk.top();
        blk.pop();
        pii b2 = blk.top();
        blk.pop();
        pp--, cnt--;
        printf("%lld %lld\n", b1.second, b2.second);
        p[b2.second] = b1.second;
        w[b1.second] += min(inf, b1.first + b2.first + 1) + b2.first;
        blk.push({w[b1.second], b1.second});
    }
    ll ran;
    for(ran = 1; ran <= n; ran++) if(find(ran) != ran) break;
    while(pp--) printf("%lld %lld\n", ran, p[ran]);
    return 0;
}

二分和差分

二分答案和差分构造上我一直是苦手,写这一篇存档记录一下可用的模板。

Problem1

题意:

给定升序排列数组 \(a[n]\) 以及 \(q\) 个查询,每次查询 \(k\) 在数组中的区间端点。

分析:

二分查找,贴一个模板

模板:

#include<bits/stdc++.h>
using namespace std;

const int N = 100010;
int a[N];
int n, q;

int main()
{
    cin >> n >> q;
    for(int i = 1; i <= n; i ++) scanf("%d", a + i);
    while(q--)
    {
        int k;
        scanf("%d", &k);
        int l = 1, r = n;
        while(l < r)// 区间[l, r]被划分成[l, mid]和[mid + 1, r]时使用:
        {
            int mid = l + r >> 1;
            if(a[mid] >= k)
            {
                r = mid;
            }
            else
            {
                l = mid + 1;
            }
        }
        if(a[l] != k)
        {
            printf("-1 -1\n");
            continue;
        }
        else
        {
            printf("%d ", l - 1);
            r = n;
            while(l < r)// 区间[l, r]被划分成[l, mid - 1]和[mid, r]时使用:
            {
                int mid = l + r + 1 >> 1;
                if(a[mid] <= k) l = mid;
                else r = mid - 1;
            }
            printf("%d\n", r - 1);
        }
    }
}

Problem2

题意:

输入一个 n 行 m 列的整数矩阵,再输入 q 个询问,每个询问包含四个整数 x1, y1, x2, y2,表示一个子矩阵的左上角坐标和右下角坐标,对于每个询问输出子矩阵中所有数的和。

分析:

二维前缀和模板,举个例子画一下就知道怎么做了

模板:

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;

int a[N][N], s[N][N];
int n, m, q;

int main()
{
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i ++)
    {
        for(int j = 1; j <= m; j ++)
        {
            scanf("%d", &a[i][j]);
            s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
        }
    }
    int x1, y1, x2, y2;
    while(q--)
    {
        scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
        int ans = s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1];
        printf("%d\n", ans);
    }
}

Problem3

题意:

输入一个长度为 n 的整数序列,接下来输入 m 个操作,每个操作包含三个整数 l, r, c,表示将序列中[l, r]之间的每个数加上 c,输出进行完所有操作后的序列。

题解:

一维差分模板,构造数组 \(b[n]\) ,使其满足 \(a[i]\)\(b[i]\) 的前缀和

你当然可以用线段树解决

模板:

#include<bits/stdc++.h>
using namespace std;

const int N = 100010;
int a[N], b[N];
int n, m;

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        scanf("%d", a + i);
        b[i] = a[i] - a[i - 1];
    }

    int l, r, c;
    while(m --)
    {
        scanf("%d%d%d", &l, &r, &c);
        b[l] += c;
        b[r + 1] -= c;
    }

    for(int i = 1; i <= n; i ++)
    {
        b[i] = b[i] + b[i - 1];
        printf("%d ", b[i]);
    }
    return 0;
}

Problem4 机器人跳跃问题

题意:

字节跳动 2019 校招题,此处代码为\(O(nlogn)\)的二分,还有更优的\(O(n)\)算法下面链接自取

https://www.nowcoder.com/questionTerminal/7037a3d57bbd4336856b8e16a9cafd71

分析:

第一想法就是二分答案,但是被右边界坑了两发,check 函数竟然最终会爆 long long,所以只要超过范围就直接返回即可。

代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100010;

ll n, h[N];

bool check(ll x)
{
    for(int i = 1; i <= n; i ++)
    {
        x += x - h[i];
        if(x < 0) return false;
        if(x > N) return true;
    }
    return true;
}

int main()
{
    scanf("%lld", &n);
    for(int i = 1; i <= n; i ++) scanf("%lld", h + i);

    ll l = 0, r = N;
    while(l < r)
    {
        ll mid = l + r >> 1;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }

    cout<<l<<endl;
}

间歇性踌躇满志,持续性混吃等死