CF 1994 D. Funny Game(*1900) 鸽巢原理+并查集

showball / 2024-09-04 / 原文

CF 1994 D. Funny Game(*1900) 鸽巢原理+并查集

题意：

给你一个长度为 $n$ 的操作，你可以进行 $n-1$ 次操作，操作数从 $1$ 开始递增。每次操作你可以选择两个数字

$u$ 和 $v$ ，如果 $|a_x-a_y|$ 能够整除操作数 $x$，那么就可以向 $u,v$ 之间连一条无向边。

询问是否可以在 $n-1$ 操作后使其成为一个连通图，如果可以，输出方案。

思路：

首先，一定是可以构造出连通图的。将条件转换成 $|a_x-a_y| \equiv 0\ mod(n-1)$ 。根据鸽巢原理， $n$ 个数里一定可以凑出两个数是同余的。联通块的数量就从 $n$ 个变成了 $n-1$ 个。显然根据数学归纳法。我们把问题分解成更小的依然成立。所以只需要从大到小构造即可。用并查集判断是否属于同一联通块即可。

代码：

#include<bits/stdc++.h>

using namespace std;

#define ff first
#define ss second
#define pb push_back
#define all(u) u.begin(), u.end()
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;

typedef pair<int, int> PII;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 10, M = 105;
const int mod = 1e9 + 7;
const int cases = 1;

struct DSU{
    vector<int> p, sz1, sz2;
    DSU(int n) : p(n + 1), sz1(n + 1, 1), sz2(n + 1, 0){ 
        iota(p.begin(), p.end(), 0); 
    }

    int find(int x){
        return p[x] == x ? x : p[x] = find(p[x]);
    }

    bool same(int x, int y) { 
        return find(x) == find(y); 
    }

    bool merge(int x, int y){
        x = find(x), y = find(y);
        sz2[x] += 1;
        if (x == y) return false;
        if (sz1[x] < sz1[y]) swap(x, y);
        sz1[x] += sz1[y];
        sz2[x] += sz2[y];
        p[y] = x;
        return true;
    }

};
void Showball(){
  int n;
  cin>>n;
  vector<int> a(n);
  for(int i=0;i<n;i++) cin>>a[i];
  DSU dsu(n);
  vector<PII> ans;
  for(int i=n-1;i>=1;i--){
    vector<int> p(i,-1);
    for(int j=0;j<n;j++){
      if(dsu.find(j)!=j) continue;
      int num=a[j]%i;
      if(p[num]==-1) p[num]=j;
      else{
        ans.pb({p[num]+1,j+1});
        dsu.merge(p[num],j);
        break;
      }
    }
  }

  cout<<"YES\n";
  reverse(all(ans));
  for(auto [u,v]:ans) cout<<u<<" "<<v<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T=1;
    if(cases) cin>>T;
    while(T--)
    Showball();
    return 0;
}