European Championship 2024 题解

European Championship 2024 - Online Mirror

A. Grove#

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

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

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

B. Charming Meals#

队友写了一题就走了。

C. Annual Ants' Gathering#

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

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

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

F. Dating#

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

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

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

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

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

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

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

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