OneKuma

OneKuma's Blog

One Lonely Kuma.
github
bilibili
twitter
主页归档作品集关于

European Championship 2024 题解

#XCPC300
AI 生成的摘要
欧洲锦标赛2024 - 在线镜像，包括几个问题和解决方法，如在方格内放圆、将蚂蚁集中到一个点、找到匹配集合、调整圆的半径等。

European Championship 2024 - Online Mirror

image

A. Grove#

给你一个 20×2020 \times 20 的方格，往里面的整点上尽可能放半径为 rr 的圆（rr 是个三位小数），最多放几个。

看过一些密铺问题的结论，感觉排列方法似乎没啥道理可讲。

大概感觉是个怎么记忆化 + 启发式 + 爆搜的题。显然应该尽可能的放近的，记忆化去除一些重复的搜索。因为没有队友写，瞎几把口胡的好像完全没啥能过的道理啊？

B. Charming Meals#

队友写了一题就走了。

C. Annual Ants' Gathering#

给你一棵树，每个点上有一个蚂蚁，每次你可以让点 uu 上的所有蚂蚁沿着一条边走到 vv，满足 uu 上的蚂蚁数量小于等于 vv 上的数量。问最后能不能把所有蚂蚁集中到一个电上。

显然，你把一个点留空了，那这棵树就断掉了，所以你每次只能缩一个叶子。并且由于小的点才更有可能缩，小点缩完才会产生大点让其它东西有机会走。

所以，大概维护小顶堆，模拟一个拓扑排序的东西，就行了。

F. Dating#

给你 nn 个人，每个人有一个集合。定义好匹配是，两个人的集合有交，但是不互相包含。找一个好匹配，或者报告没有。

胡编乱造了一个做法，基于这个集合大小的种类数是根号量级的（600 种）。

首先，对于每种集合大小，看下这里面是否重复的完全相同集合，去掉（使用无序集合哈希）。然后，看一下有没有两人的集合有交，也就是看看有没数字重复出现，有的话就有交，又因为长度相同而且不是完全相同，所以就是答案。

于是，我们现在得到了 600 种长度，每个长度里有一堆不相交的集合。

然后，从大到小枚举长度，构建一个包含集合关系的森林，然后维护每种树最后一次被哪个节点覆盖。

对于当前长度中的每一个集合，遍历集合拿出每个数最后一次被覆盖的节点是哪个，对于这个覆盖节点集合，有几种情况：

  1. 存在两个点在森林里的两棵树上，那么我们找到了一组答案，当前集合和两个点中任意其一：因为，找到了点说明有交，在不同的树上说明当前集合中的数必定不在另一个里面，又由于长度限制当前集合必定不包含之间所有集合。
  2. 存在两个点在森林里的同一棵树上，那么由于包含关系，这两者一定有祖先关系，选择当前集合和最深的那个作为答案：因为，找到了点说明有交，能找到两种最后覆盖的点上说明这个数在祖先集合里，而不再子孙集合里，又由于长度限制当前集合必定不包含之间所有集合。
  3. 存在一个点在森林里的同一棵树上，那么连一条边，找到了父子关系。

G. Scooter#

没有队友愿意写。

感觉大概对着题意构造下就行了，比如 -m mc cm mc c- -c cm m- -c cm m- 这样弄弄。

I. Disks#

给你一堆可能相切可能相离的圆，问你是否可能通过调整所有圆的半径，使得原本的相切相离关系不变，且所有圆的半径和变小。

大概观察一下可以发现，因为你要保持相切关系，所以你缩一个圆，必然带来另外一个圆变大，两者抵消。

然后在观察一下样例给了个长度为 3 的链，可以弄成一个 "小 - 大 - 小" 的样子，就会减小半径和了。然后考虑复杂的图会怎么样，比如有环，偶环可以，但是奇环不行，自然联想到二分图。因此大概就是对原图二分图染色，相当于减小和加大两种变化，看一下有没有连通块左右两部点数不同。

J. Amanda the Amoeba#

没有队友愿意写。

就感觉枚举目标方格中的每个点，然后删除一些边界上的、没放好的点，一步一步地走过去。

代码#

C. Annual Ants' Gathering#

#include <cmath>
#include <cstdio>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <queue>
#include <vector>

using namespace std;

const int inf = 1e9 + 7;
const int maxn = 300000 + 5;

int n, deg[maxn], cnt[maxn], visited[maxn];
vector<int> edge[maxn];

int main() {
#ifdef DEBUG
  freopen("../assets/in.txt", "r", stdin);
#endif

  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    edge[u].push_back(v);
    edge[v].push_back(u);
    deg[u]++;
    deg[v]++;
  }

  priority_queue<pair<int,int>> pq;
  for (int i = 1; i <= n; i++) {
    cnt[i] = 1;
    if (deg[i] == 1) {
      visited[i] = true;
      pq.push({ -1, i });
    }
  }

  bool ok = true;
  while (!pq.empty() && ok) {
    auto cur = pq.top();
    pq.pop();

    int u = cur.second;
    assert(visited[u]);

//    printf("F %d\n", u);

    for (int v: edge[u]) {
      if (visited[v]) continue;

      if (cnt[u] <= cnt[v]) {
        deg[v]--;
        cnt[v] += cnt[u];
        cnt[u] = 0;
        if (deg[v] == 1) {
          visited[v] = true;
//          printf("PUSH %d -> %d\n", u,v);
          pq.push({ -cnt[v], v });
        }
      } else {
        ok = false;
        break;
      }
    }
  }

  puts(ok ? "YES" : "NO");

  return 0;
}

F. Dating#

#include <cmath>
#include <cstdio>
#include <cassert>
#include <ctime>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <random>
#include <vector>

using namespace std;

const int inf = 1e9 + 7;
const int maxn = 200000 + 5;
const int maxm = 1000000 + 5;

int n, m;

unsigned int hsh[maxn], key[maxm];
int dep[maxn], fa[maxn], bel[maxm];

vector<int> bag[maxn];
vector<int> lens[maxm];

bool check(int x, int y) {
  set<int> mp1, mp2;
  for (int t: bag[x]) mp1.insert(t);
  for (int t: bag[y]) mp2.insert(t);
  int cond1 = false, cond2 = false, cond3 = false;
  for (int t: mp1) {
    if (mp2.count(t)) cond1 = true;
    else cond2 = true;
  }
  for (int t: mp2) {
    if (mp1.count(t)) cond1 = true;
    else cond3 = true;
  }
  return cond1 && cond2 && cond3;
}

int main() {
#ifdef DEBUG
  freopen("../assets/in.txt", "r", stdin);
#endif

  scanf("%d%d", &n, &m);

  mt19937 rnd((unsigned) time(nullptr));
  for (int i = 1; i <= m; i++) {
    key[i] = rnd();
  }

  for (int i = 1; i <= n; i++) {
    int c;
    scanf("%d", &c);
    for (int j = 1, x; j <= c; j++) {
      scanf("%d", &x);
      bag[i].push_back(x);
      hsh[i] ^= key[x];
    }
    sort(bag[i].begin(), bag[i].end());
    lens[c].push_back(i);
  }

  for (int l = 1; l <= m; l++) {
    if (lens[l].empty()) continue;

    // Remove same
    {
      map<unsigned, int> mp;
      vector<int> uniqued;
      for (int id: lens[l]) {
        if (mp.count(hsh[id])) {
          continue;
        }
        mp[hsh[id]] = id;
        uniqued.push_back(id);
      }
      lens[l] = uniqued;
    }
    // Check intersect
    {
      memset(bel, 0, sizeof bel);
      for (int id: lens[l]) {
        for (int x: bag[id]) {
          if (bel[x]) {
            puts("YES");
            printf("%d %d\n", bel[x], id);
            assert(check(bel[x], id));
            return 0;
          }
          bel[x] = id;
        }
      }
    }
  }

  vector<int> groups;
  for (int l = m; l >= 1; l--) {
    if (lens[l].empty()) continue;

    if (groups.empty()) {
      // Largest length
      for (int id: lens[l]) {
        groups.push_back(id);
        for (int x: bag[id]) {
          bel[x] = id;
        }
      }
    } else {
      vector<int> ngroups;
      for (int id: lens[l]) {
        // bel[x]: the last bag id which covers x
        // visited: set of bel[x]
        // roots: set of the roots of bel[x]
        set<int> visited, roots;
        for (int x: bag[id]) {
          if (!visited.count(bel[x])) {
            visited.insert(bel[x]);

            int last = bel[x];
            if (bel[x]) {
              int f = bel[x];
              while (f) {
                last = f;
                f = fa[f];
              }
            }
            roots.insert(last);
          }
        }
        
        if (roots.size() == 0 || (roots.size() == 1 && *roots.begin() == 0)) {
          // Create a new tree in the forest
          fa[id] = 0;
          dep[id] = 1;
        } else if (roots.size() >= 2) {
          // Intersect with two tree chains
          int root = 0;
          for (int x: roots) {
            if (x) {
              root = x;
              break;
            }
          }
          puts("YES");
          printf("%d %d\n", root, id);
          assert(check(root, id));
          return 0;
        } else {
          // Intersect with one tree chain
          if (visited.size() == 1) {
            // Connect tree father
            int cur = *visited.begin();
            assert(cur != 0);
            fa[id] = cur;
            dep[id] = dep[cur] + 1;
          } else {
            // Intersect with multiple bags in one chain
            // That is to say that id is subset of the root, but intersect with the deepest node
            int tag = -1;
            for (int x: visited) {
              if (tag == -1 || dep[x] > dep[tag]) {
                tag = x;
              }
            }
            assert(tag != -1);
            puts("YES");
            printf("%d %d\n", tag, id);
            assert(check(tag, id));
            return 0;
          }
        }
      }
      
      for (int id: lens[l]) {
        ngroups.push_back(id);
        for (int x: bag[id]) {
          bel[x] = id;
        }
      }
      groups = ngroups;
    }
  }

  puts("NO");

  return 0;
}

I. Disks#

#include <cmath>
#include <cstdio>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <vector>

using namespace std;

const int inf = 1e9 + 7;
const int maxn = 300000 + 5;

int n, deg[maxn];

vector<int> edge[maxn];
int flag, cnt, visited[maxn], col[maxn];

struct Circle {
    int x, y, r;
} a[maxn];

void dfs(int u) {
  cnt += col[u] == 0 ? 1 : -1;
  for (int v: edge[u]) {
    if (visited[v]) {
      if (col[v] != !col[u]) {
        flag = false;
      }
      continue;
    }
    visited[v] = true;
    col[v] = !col[u];
    dfs(v);
  }
}

int main() {
#ifdef DEBUG
  freopen("../assets/in.txt", "r", stdin);
#endif

  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].r);
  }

  for (int i = 1; i <= n; i++) {
    for (int j = 1; j < i; j++) {
      long long dis = 1ll * (a[i].x - a[j].x) * (a[i].x - a[j].x) + 1ll * (a[i].y - a[j].y) * (a[i].y - a[j].y);
      if (dis == 1ll * (a[i].r + a[j].r) * (a[i].r + a[j].r)) {
        deg[i]++;
        deg[j]++;
        edge[i].push_back(j);
        edge[j].push_back(i);
      }
    }
  }

  for (int i = 1; i <= n; i++) {
    if (visited[i]) continue;

    visited[i] = true;
    flag = true;
    cnt = 0;
    dfs(i);
    if (flag && cnt > 0) {
      puts("YES");
      return 0;
    }
  }

  memset(visited, 0, sizeof visited);
  for (int i = 1; i <= n; i++) {
    if (visited[i]) continue;

    col[i] = 1;
    
    visited[i] = true;
    flag = true;
    cnt = 0;
    dfs(i);
    if (flag && cnt > 0) {
      puts("YES");
      return 0;
    }
  }

  puts("NO");

  return 0;
}
加载中...
此文章数据所有权由区块链加密技术和智能合约保障仅归创作者所有。