鱼C论坛

 找回密码
 立即注册
查看: 626|回复: 13

[心之碎片] - 20240803模拟赛

[复制链接]
发表于 2024-8-4 15:08:48 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
总结与反思

A - 数据结构维护前缀和要提前加一个 0, 不然 1 是取不到的
C - 最小生成树相关问题两种思考: 按照边权分类 或者 建一个树然后树剖加边
D - 思考问题先想降维的情况, 本题的思路就是由 l == r 的情况想出来的

C - 又见最小生成树
现在给出一幅个节点条边的无向连通图, 请判断原图中的每条边是否一定在最小生成树中
对于每条边 :
如果这条边一定出现在任意一棵最小生成树中, 输出 1
如果一定不会出现在最小生成树中, 输出 2
如果无法确定, 输出 0


最小生成树问题我们一般想到按照边权分类, 同边权的一起考虑
这里有一个建图技巧就是 *2 + 1
假设前面的边都加进去, 现在有一些边连接这些连通块
如果是割边, 就一定经过
如果在连通块里面, 由于连通块里面的边都比现在的边小, 所以一定不经过
剩下的是可能的
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

const int N = 1e5 + 5;

struct Edge {
    int u, v, w, id;
} e[N];

int n, m, ans[N];

struct DSU {
    int pa[N];

    DSU() {
        for (int i = 1; i < N; i++) pa[i] = i;
    }

    int Find(int x) {
        if (x == pa[x])
            return x;
        return (pa[x] = Find(pa[x]));
    }

    void Merge(int x, int y) { pa[x] = y; }
} dsu;

// 每次循环新建图和加入的点
vector<int> point;
vector<pii> g[N];

int dfn[N], low[N], tot;

void Tarjan(int u, int eid) {
    dfn[u] = low[u] = ++tot;

    for (auto ed : g[u]) {
        int v = ed.first;
        if (!dfn[v]) {
            Tarjan(v, ed.second);

            low[u] = min(low[u], low[v]);
            // 如果这个新边是割边, 就必须经过
            if (dfn[u] < low[v]) {
                ans[ed.second >> 1] = 1;
            }
        } else if ((eid >> 1) != (ed.second >> 1)) {
            low[u] = min(dfn[v], low[u]);
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    freopen("mstagain.in", "r", stdin);
    freopen("mstagain.out", "w", stdout);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;

        e[i] = { u, v, w, i };
    }

    sort(e + 1, e + m + 1, [](Edge& a, Edge& b) { return a.w < b.w; });

    for (int i = 1; i <= m; i++) {
        // 找出权值相等的区间
        int l = i, r = i;
        while (r <= m && e[r].w == e[l].w) r++;
        r--;

        // Kruskal
        for (int j = l; j <= r; j++) {
            int u = dsu.Find(e[j].u), v = dsu.Find(e[j].v);

            if (u == v) {
                // 已经成连通块了, 里面的任何边都小于现在的权值, 一定不取
                ans[e[j].id] = 2;
                continue;
            }

            // 如果没成就连边(新图)
            point.emplace_back(u);
            point.emplace_back(v);
            // 编号小技巧轻松判断反边, 更新答案也好
            g[u].emplace_back(v, e[j].id << 1);
            g[v].emplace_back(u, e[j].id << 1 | 1);
        }

        for (auto j : point) {
            if (!dfn[j])
                Tarjan(j, 0);
        }

        for (int j = l; j <= r; j++) {
            int u = dsu.Find(e[j].u), v = dsu.Find(e[j].v);
            // 把所有边权一样的边都连起来, 变成新的图
            if (u == v)
                continue;
            dsu.Merge(u, v);
        }

        // 清零等着复用
        for (auto j : point) {
            g[j].clear();
            dfn[j] = low[j] = 0;
        }
        point.clear();
        tot = 0;
        i = r;
    }

    for (int i = 1; i <= m; i++) {
        cout << ans[i] << '\n';
    }

    return 0;
}
D - 排列
给你 n 个点, 有点权
你需要构造一个排列, 使得最终的满足条件的点的权值之和最大
每个点都有一个前置区间 [l, r] , 表示如果范围内的某个点排在 i 的前面了,那么 i 点的权值就要被累加进去
应该如何排列, 使得点权和才能最大


当 n <= 20 时, 可以状压 dp 拿 30 分
接下来考虑 l == r 的情况 (先考虑一维的问题) , 发现本质上是区间内的点向 i 连边
在一个 scc 中, 每个点都可以互通, 所以权值都可以加, 入度为 0 的 scc 需要牺牲一个最小的权值当作第一个数, 后面的都能加
然后区间的连边需要线段树优化建图
#include <bits/stdc++.h>
using namespace std;

const int N = 4e5 + 5;
const int M = 1e5 + 5;

vector<int> e[N];
int n, ans, val[M];

struct SGT {
#define lc u << 1
#define rc u << 1 | 1

    int tot, t[N];

    void Build(int u, int l, int r) {
        if (l == r) {
            t[u] = l;
            return;
        }

        int mid = (l + r) >> 1;
        Build(lc, l, mid);
        Build(rc, mid + 1, r);
        t[u] = ++tot;

        e[t[lc]].emplace_back(t[u]);
        e[t[rc]].emplace_back(t[u]);
    }

    void Modify(int u, int l, int r, int ql, int qr, int to) {
        if (ql <= l && r <= qr) {
            e[t[u]].emplace_back(to);
            return;
        }
        int mid = (l + r) >> 1;

        if (ql <= mid)
            Modify(lc, l, mid, ql, qr, to);
        if (qr > mid)
            Modify(rc, mid + 1, r, ql, qr, to);
    }
} sgt;

int dfn[N], low[N], tot;
int stk[N], top;
int scc, bel[N], minv[N], din[N];
bitset<N> instk;

void Tarjan(int u) {
    dfn[u] = low[u] = ++tot;
    stk[++top] = u;
    instk[u] = 1;

    for (auto v : e[u]) {
        if (!dfn[v]) {
            Tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (instk[v])
            low[u] = min(low[u], dfn[v]);
    }

    if (dfn[u] == low[u]) {
        int v;
        scc++;

        do {
            v = stk[top--];
            instk[v] = 0;
            bel[v] = scc;
            if (v <= n)
                minv[scc] = min(minv[scc], val[v]);
        } while (v != u);
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    freopen("permutation.in", "r", stdin);
    freopen("permutation.out", "w", stdout);

    cin >> n;
    sgt.tot = n;
    sgt.Build(1, 1, n);

    for (int i = 1; i <= n; i++) {
        int l, r;
        cin >> l >> r >> val[i];

        ans += val[i];
        sgt.Modify(1, 1, n, l, r, i);
    }

    memset(minv, 0x3f, sizeof(minv));

    for (int i = 1; i <= sgt.tot; i++) {
        if (!dfn[i])
            Tarjan(i);
    }

    // 入度
    for (int i = 1; i <= tot; i++) {
        for (auto j : e[i]) {
            if (bel[i] != bel[j]) {
                din[bel[j]]++;
            }
        }
    }

    // 前面没有人, 必须牺牲一个最小值
    for (int i = 1; i <= scc; i++) {
        if (!din[i])
            ans -= minv[i];
    }
    cout << ans;

    return 0;
}

评分

参与人数 1鱼币 +5 收起 理由
某一个“天” + 5 鱼C有你更精彩^_^

查看全部评分

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-8-4 15:09:02 | 显示全部楼层
这段代码是在处理最小生成树(MST)中的边的判断问题。换句话说,给定一张无向连通图,我们需要判断每条边是否一定在任何一棵最小生成树中。这是一个典型的图论问题,我们可以通过以下几点来理解它,带点幽默感哦:

1. **边的分类**:首先,当我们面临一个众多边的图时,就像在一个派对上,所有的朋友都在聊天。我们可以按照“边权”来分类,低价位边在一块,高价位边在另一块。这样,有助于我们更清晰地分析每条边的重要性。就像你在选择餐馆时,会先查查菜单上的价格一样。

2. **割边的重要性**:如果这条边是一个割边(也称为桥),那么它是连接两个不同的连通部分的关键。如果你把它剪断,图就成两半了,因此这条边一定出现在最小生成树中。就像是你在居家办公时,家里Wi-Fi信号是多么的关键,没了它你就变成孤岛。

3. **连通块内的边**:如果一条边在连通块内,那么它可能是不必要的,因为该块内部的其他边都比它便宜,最小生成树自然会选择那些更便宜的。想象一下,一个派对上,你已经有了免费饮料,谁还要去买贵的鸡尾酒呢?

4. **不确定边**:最后,还有一些边是无法确定的,像是一张悬疑片的剧情一样复杂。对于这些边,如果没有足够的信息我们就只能输出0,表示不确定。这就像你在看电影时猜测反转情节,但仍然得留到结局才知道。

然后,代码实现的部分涉及如何通过并查集(DSU)和Tarjan算法来完成这些检测工作。该算法就像一位侦探,通过不断查找和合并,帮助我们判断各个边的位置和重要性。

总的来说,这道题考的是对图的理解和对算法的应用,就像是在料理比赛中,每一样食材都要搭配得当,才能做出最佳的菜肴!希望这番解析能帮到你,让你在最小生成树的世界里游刃有余!如果你还有什么问题,尽管问吧,准备好笑料,咱们继续聊!

以上回复来自 FishC AI 小助理,如未能正确解答您的问题,请继续追问。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-8-4 17:49:39 | 显示全部楼层

回帖奖励 +3 鱼币

加油
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-8-4 23:51:34 | 显示全部楼层

回帖奖励 +3 鱼币

cy
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-8-5 11:19:07 | 显示全部楼层

回帖奖励 +3 鱼币

学习一下
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-8-7 09:23:08 | 显示全部楼层

回帖奖励 +3 鱼币

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-8-8 16:42:45 | 显示全部楼层
加油
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-8-9 14:30:06 | 显示全部楼层

回帖奖励 +3 鱼币

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-8-16 08:33:32 | 显示全部楼层

回帖奖励 +3 鱼币

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-8-16 10:45:15 From FishC Mobile | 显示全部楼层

回帖奖励 +3 鱼币

加油
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-8-16 12:03:25 | 显示全部楼层
学习一下
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-8-18 09:57:05 | 显示全部楼层

回帖奖励 +3 鱼币

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2024-8-24 11:50:05 | 显示全部楼层

回帖奖励 +3 鱼币

&#128076;
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2024-8-29 09:22:43 | 显示全部楼层

回帖奖励 +3 鱼币

&#128076;
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-11-5 04:54

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表