歐洲錦標賽 2024 題解

歐洲錦標賽 2024 - 在線鏡像

A. 樹叢#

給你一個 $20 \times 20$ 的方格，往裡面的整點上盡可能放半徑為 $r$ 的圓（ $r$ 是個三位小數），最多放幾個。

看過一些密鋪問題的結論，感覺排列方法似乎沒啥道理可講。

大概感覺是個怎麼記憶化 + 啟發式 + 爆搜的題。顯然應該盡可能的放近的，記憶化去除一些重複的搜索。因為沒有隊友寫，瞎幾把口胡的好像完全沒啥能過的道理啊？

B. 迷人的餐點#

隊友寫了一題就走了。

C. 年度螞蟻聚會#

給你一棵樹，每個點上有一隻螞蟻，每次你可以讓點 $u$ 上的所有螞蟻沿著一條邊走到 $v$ ，滿足 $u$ 上的螞蟻數量小於等於 $v$ 上的數量。問最後能不能把所有螞蟻集中到一個點上。

顯然，你把一個點留空了，那這棵樹就斷掉了，所以你每次只能縮一個葉子。並且由於小的點才更有可能縮，小點縮完才會產生大點讓其它東西有機會走。

所以，大概維護小頂堆，模擬一個拓撲排序的東西，就行了。

F. 約會#

給你 $n$ 個人，每個人有一個集合。定義好匹配是，兩個人的集合有交，但是不互相包含。找一個好匹配，或者報告沒有。

胡編亂造了一個做法，基於這個集合大小的種類數是根號量級的（600 種）。

首先，對於每種集合大小，看下這裡面是否重複的完全相同集合，去掉（使用無序集合哈希）。然後，看一下有沒有兩人的集合有交，也就是看看有沒數字重複出現，有的話就有交，又因為長度相同而且不是完全相同，所以就是答案。

於是，我們現在得到了 600 種長度，每個長度裡有一堆不相交的集合。

然後，從大到小枚舉長度，構建一個包含集合關係的森林，然後維護每種樹最後一次被哪個節點覆蓋。

對於當前長度中的每一個集合，遍歷集合拿出每個數最後一次被覆蓋的節點是哪個，對於這個覆蓋節點集合，有幾種情況：

存在兩個點在森林裡的兩棵樹上，那麼我們找到了一組答案，當前集合和兩個點中任意其一：因為，找到了點說明有交，在不同的樹上說明當前集合中的數必定不在另一個裡面，又由於長度限制當前集合必定不包含之間所有集合。
存在兩個點在森林裡的同一棵樹上，那麼由於包含關係，這兩者一定有祖先關係，選擇當前集合和最深的那個作為答案：因為，找到了點說明有交，能找到兩種最後覆蓋的點上說明這個數在祖先集合裡，而不再子孫集合裡，又由於長度限制當前集合必定不包含之間所有集合。
存在一個點在森林裡的同一棵樹上，那麼連一條邊，找到了父子關係。

G. 滑板車#

沒有隊友願意寫。

感覺大概對著題意構造下就行了，比如 -m mc cm mc c- -c cm m- -c cm m- 這樣弄弄。

I. 圓盤#

給你一堆可能相切可能相離的圓，問你是否可能通過調整所有圓的半徑，使得原本的相切相離關係不變，且所有圓的半徑和變小。

大概觀察一下可以發現，因為你要保持相切關係，所以你縮一個圓，必然帶來另外一個圓變大，兩者抵消。

然後在觀察一下樣例給了個長度為 3 的鏈，可以弄成一個 "小 - 大 - 小" 的樣子，就會減小半徑和了。然後考慮複雜的圖會怎麼樣，比如有環，偶環可以，但是奇環不行，自然聯想到二分圖。因此大概就是對原圖二分圖染色，相當於減小和加大兩種變化，看一下有沒有連通塊左右兩部點數不同。

J. 阿曼達變形蟲#

沒有隊友願意寫。

就感覺枚舉目標方格中的每個點，然後刪除一些邊界上的、沒放好的點，一步一步地走過去。

代碼#

C. 年度螞蟻聚會#

#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. 約會#

#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. 圓盤#

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