P4380:[USACO18OPEN]Multiplayer Moo S – 题解

主要思路

这个题有点 nb。

按道理来讲直接做第二问得要 \(\Theta(n^4)\) 的时间,而且看上去也没有什么搞头。我们考虑处理出所有的接壤位置 \( (x, y, c_a, c_y) \) 代表颜色为 \(c_x\) 、编号 \(x\) 的点和颜色为 \(c_y\) 、编号 \(y\) 的点接壤。这样的接壤位置只有 \(\Theta(n^2)\) 个,所以我们分类出来之后再用并查集搞即可。

继续阅读P4380:[USACO18OPEN]Multiplayer Moo S – 题解

「杂题集」- 2019年9月19日

方格取数

看一眼复杂度,\(O(nm)\)级别的,考虑两个循环的 DP。分析整个题面之后发现,我们穿过边界时,当且仅当另一个连通块的权值比当前的大,否则便不会为了穿过边界而损失当前金块。所以,我们做一个 DP 一样的东西:因为发现每个格子只能走一遍,那么在每一列你只能选择一直向上走和一直向下走,所以这个 DP 便没了后效性,然后再处理连通块之间的连接判断就做完了。

继续阅读「杂题集」- 2019年9月19日

[Fortuna OJ]Jul 5th – Group A 解题报告 / 集训队互测 2013

A – 家族

这道题真的是送分题(快要想出来直接暴力枚举+并查集的时候去看了题解,最后发现就是这么 sb)。

考虑枚举频段区间\([L, R]\)(将边进行排序,确定下界之后再枚举上界),这个地方是\(O(m^2)\)的。每次枚举下界的时候都要初始化并查集,然后合并两个集合的时候按照大小来修改答案就行了。

继续阅读[Fortuna OJ]Jul 5th – Group A 解题报告 / 集训队互测 2013

[Fortuna OJ]Mar 4th – Group A 解题报告

A – 漆黑列车载运数个谎言

这道题应该是并查集域的裸题,不讲。

// A.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e6 + 200;
int n, m, fa[MAX_N << 2];
int find(int x) { return fa[x] == x ? fa[x] : fa[x] = find(fa[x]); }
void unite(int x, int y) { fa[find(x)] = fa[find(y)]; }
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= 2 * n; i++)
        fa[i] = i;
    while (m--)
    {
        int opt, x, y;
        scanf("%d%d%d", &opt, &x, &y);
        if (opt == 0)
            unite(x, y), unite(x + n, y + n);
        else if (opt == 1 || opt == 2)
            unite(x, y + n), unite(x + n, y);
        else if (find(x) == find(y) || find(x + n) == find(y + n))
            puts("1");
        else
            puts("0");
    }
    return 0;
}

继续阅读[Fortuna OJ]Mar 4th – Group A 解题报告