论坛 › 综合交流区 › [心之碎片] - 20240809模拟赛

柿子饼同学 发表于 2024-8-9 21:45:19

[心之碎片] - 20240809模拟赛

总结与反思{:10_297:}
F- 最小生成树相关优先考虑按照边权分类
G - 不好枚举, 可以考虑构造搜索答案, 要注意阶段的区分, 数字太大考虑同余
H - 求很多点之间的最短路我们可以建立超级源点向每个关键点连边, 图论相关一定要注意图是否连通, 构建新图考虑一个点到另外一个点的花费等等

F - MST Unification
简单题, 考试时候用 kruskal 重构树水过去了, 后来才发现大家边求 mst 边求答案...{:10_266:}
考虑什么时候会发生 mst 不唯一的情况, 当然也就是两个边权值一样, 但是一个边加了另一个边加不了的时候, 所以没了
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;

struct DSU{
    int f;

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

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

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

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

struct Edge{
    int u, v, w;
} e;

int n, m, ans;
int stk, 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 = {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.w == e.w) r++;
      r--;

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

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

      i = r;
    }

    cout << ans;
   
    return 0;
}

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

    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){
            f = cur.sum;
            q.push_front({temp, cur.sum});
      }
      
      temp = (cur.num + 1) % k;
      if(cur.sum + 1 < f){
            f = 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;
int cnt;

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

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

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

      if (vis)
            continue;
      vis = 1;

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

struct DSU {
    int f, tot;

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

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

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

      tot++;
      f = tot;
      f = tot;

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

void Kruskal() {
    dsu.Init();

    for (int i = 1; i <= n; i++) {
      for (auto j : g) {
            if (j.id > 0) {
                edges[++cnt] = { i, j.id, dist + dist + 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.u;
      v = edges.v;
      w = edges.w;
      cur = dsu.Merge(u, v);

      if (cur)
            val = w;
    }
}

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

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

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

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

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

    if (x == y)
      return x;

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

    return f;
}

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.push_back({ v, w });
      g.push_back({ u, w });
    }
    for (int i = 1; i <= k; i++) {
      g.push_back({ i, 0 });
      g.push_back({ 0, 0 });
    }

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

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

    return 0;
}

学习编程中的Ben 发表于 2024-8-9 22:33:01

大佬收下我的膝盖

sfqxx 发表于 2024-8-9 23:22:04

@zhangjinxuan {:10_256:}

简柠啦 发表于 2024-8-10 09:44:30

{:10_256:}{:10_256:}

lwh0602 发表于 2024-8-11 19:13:10

{:10_243:}

很cool的阳 发表于 2024-8-18 10:00:04

{:7_113:}

lwh0602 发表于 2024-8-18 11:30:56

{:10_254:}

18408238295 发表于 2024-8-20 09:57:57

学习学习

曾热爱这世界 发表于 2024-8-24 11:49:05

&#128076;

zsy0226 发表于 2024-8-29 09:23:15

膜拜大佬/orz/orz

trinityee 发表于 2024-9-1 10:02:53

唉，高山啊高山{:10_254:}

森林格格屋 发表于 2024-9-4 17:16:21

谢谢

查看完整版本: [心之碎片] - 20240809模拟赛