[心之碎片] - 20240809模拟赛

柿子饼同学

总结与反思

F  - 最小生成树相关优先考虑按照边权分类

G - 不好枚举, 可以考虑构造搜索答案, 要注意阶段的区分, 数字太大考虑同余

H - 求很多点之间的最短路我们可以建立超级源点向每个关键点连边, 图论相关一定要注意图是否连通, 构建新图考虑一个点到另外一个点的花费等等

F - MST Unification
简单题, 考试时候用 kruskal 重构树水过去了, 后来才发现大家边求 mst 边求答案...
考虑什么时候会发生 mst 不唯一的情况, 当然也就是两个边权值一样, 但是一个边加了另一个边加不了的时候, 所以没了

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

const int N = 2e5 + 5;

struct DSU{
    int f[N];

    DSU(){ iota(f, f + N, 0); }

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

    bool Iseq(int x, int y){
        x = Find(x), y = Find(y);
        return (x == y);
    }

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

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

int n, m, ans;
int stk[N], top;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n >> m;
    for(int i = 1; i <= m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        e[i] = {u, v, w};
    }

    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--;

        top = 0;
        for(int j = l; j <= r; j++){
            if(dsu.Iseq(e[j].u, e[j].v)) continue;
            stk[++top] = j;
        }

        // 相同边权, 本来有可能被加进去的, 现在加不进去所以必须让她边权 +1
        for(int j = 1; j <= top; j++){
            if(dsu.Iseq(e[stk[j]].u, e[stk[j]].v)){
                ans++;
                continue;
            }
            
            dsu.Merge(e[stk[j]].u, e[stk[j]].v);
        }

        i = r;
    }

    cout << ans;
    
    return 0;
}

G - [ABC077D] Small Multiple
没想出来, 后来发现很简单
枚举 d 会超时, 就想着构造答案
每次 K*d 这个数可以 *10 或者 +1, 后者会对数位和产生贡献, 然后广搜, 要求是 k 的倍数, 所以数字 %k, 最后 %k == 0 的状态就是最优解
解释一下为什么不用考虑进位：进位的情况一定对应一种其他的情况，我们发现另一种情况各位和更小，所以这种情况一定是不优的，所以存在f里的不存在进位的影响。

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

// K*d 不好枚举 d, 考虑构造答案
// 这时不仅要想到 dp 还要想到搜索(记忆化)
// 构造数字有 +1 *10 两个操作, 只需要判断 %K == 0 即可
// 代价分别是 1, 0, 用 deque 跑 0/1bfs 就行了
// 构造的阶段就是一位一位的枚举

const int N = 1e5 + 5;

struct St{
    // %k 的余数, 现在的数位和
    int num, sum;
};

int f[N];
deque<St> q;
int k;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> k;
    memset(f, 0x3f, sizeof(f));
    q.push_back({1, 1});
    f[1] = 1;

    int temp;
    while(!q.empty()){
        auto cur = q.front();
        q.pop_front();

        if(cur.num == 0){
            cout << cur.sum;
            return 0;
        }
        
        temp = cur.num*10 % k;
        if(cur.sum < f[temp]){
            f[temp] = cur.sum;
            q.push_front({temp, cur.sum});
        }
        
        temp = (cur.num + 1) % k;
        if(cur.sum + 1 < f[temp]){
            f[temp] = cur.sum + 1;
            q.push_back({temp, cur.sum + 1});
        }
    }
    
    return 0;
}

G - Cheap Robot
没啥好说的, 没考虑搞超级源点, 写暴力也没判断是否连通, 挂了
我用了 kruskal 重构树, 其实求个最小生成树倍增求边上最大值一样的, 考虑两个点之间怎么走就出来了

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

typedef long long ll;

const int N = 1e5 + 5;
const int K = 2e5 + 5;
const int M = 3e5 + 5;

struct Node {
    int id;
    ll w;

    bool operator<(const Node& t) const { return w > t.w; }
};

struct Kru {
    int u, v;
    ll w;
} edges[M << 1];
int cnt;

int n, m, k, q;
vector<Node> g[N];
vector<int> e[K];
ll dist[N], val[K];
bitset<N> vis;
priority_queue<Node> p;
int f[K][19], dep[K];

void Dijkstra() {
    memset(dist, 0x3f, sizeof(dist));
    p.push({ 0, 0 });
    dist[0] = 0;

    while (!p.empty()) {
        auto u = p.top().id;
        p.pop();

        if (vis[u])
            continue;
        vis[u] = 1;

        for (auto ed : g[u]) {
            int v = ed.id;
            ll w = ed.w;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                if (!vis[v])
                    p.push({ v, dist[v] });
            }
        }
    }
}

struct DSU {
    int f[K], tot;

    void Init() {
        iota(f, f + K, 0);
        tot = n;
    }

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

    int Merge(int x, int y) {
        x = Find(x), y = Find(y);
        if (x == y)
            return 0;

        tot++;
        f[x] = tot;
        f[y] = tot;

        e[tot].emplace_back(x);
        e[tot].emplace_back(y);
        e[x].emplace_back(tot);
        e[y].emplace_back(tot);
        return tot;
    }
} dsu;

void Kruskal() {
    dsu.Init();

    for (int i = 1; i <= n; i++) {
        for (auto j : g[i]) {
            if (j.id > 0) {
                edges[++cnt] = { i, j.id, dist[i] + dist[j.id] + j.w };
            }
        }
    }

    sort(edges + 1, edges + cnt + 1, [](Kru& a, Kru& b) { return a.w < b.w; });

    int u, v, w, cur;
    for (int i = 1; i <= cnt; i++) {
        u = edges[i].u;
        v = edges[i].v;
        w = edges[i].w;
        cur = dsu.Merge(u, v);

        if (cur)
            val[cur] = w;
    }
}

void dfs(int u, int pa) {
    f[u][0] = pa;
    dep[u] = dep[pa] + 1;

    for (int i = 1; i < 19; i++) {
        f[u][i] = f[f[u][i - 1]][i - 1];
    }

    for (auto ed : e[u]) {
        if (ed == pa)
            continue;
        dfs(ed, u);
    }
}

int lca(int x, int y) {
    if (dep[x] < dep[y])
        swap(x, y);

    int d = dep[x] - dep[y];
    for (int i = 18; i >= 0; i--) {
        if ((d >> i) & 1) {
            x = f[x][i];
        }
    }

    if (x == y)
        return x;

    for (int i = 18; i >= 0; i--) {
        if (f[x][i] != f[y][i]) {
            x = f[x][i];
            y = f[y][i];
        }
    }

    return f[x][0];
}

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

    cin >> n >> m >> k >> q;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].push_back({ v, w });
        g[v].push_back({ u, w });
    }
    for (int i = 1; i <= k; i++) {
        g[0].push_back({ i, 0 });
        g[i].push_back({ 0, 0 });
    }

    Dijkstra();
    Kruskal();
    dfs(dsu.tot, 0);

    while (q--) {
        int x, y;
        cin >> x >> y;
        cout << val[lca(x, y)] << '\n';
    }

    return 0;
}

学习编程中的Ben

大佬收下我的膝盖

sfqxx

@zhangjinxuan

简柠啦

lwh0602

很cool的阳

lwh0602

18408238295

学习学习

曾热爱这世界

👌

zsy0226

膜拜大佬/orz/orz

trinityee

唉，高山啊高山

森林格格屋

谢谢