CF1994D Funny Game

前言

妙不可言~~~

思路

想不到啊想不到

观察到样例全输出 \(YES\) ，则我们从最不容易满足的 \(n-1\) 开始，一直到 \(1\)，暴力匹配边

然后发现是正解

仔细想想才发现，每次操作后相当于减少一个连通块，而对于第 \(i\) 次操作，则会剩下 \(i-1\) 个连通块，根据 鸽巢原理 必定有存在两个连通块可以连边，即 \(mod\) \(i\) 的余数相同

实现的话怎么实现都可以 我用 \(set\) 和 \(map\) 乱搞

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2005;
int a[N];
int fa[N];
pair<int,int> b[N];
set<int> s[N];
int find(int x)
{
	//cout<<x<<"\n";
    if(fa[x]==x)
    {
        return fa[x];
    }
    fa[x]=find(fa[x]);
    return fa[x];
}
int main()
{
    int _;
    cin>>_;
    while(_--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=1;i<=n;i++) fa[i]=i;
        for(int i=n-1;i>=1;i--)
        {
        	//cout<<i<<"\n";
            for(int j=0;j<=n;j++) s[j].clear();
            for(int j=1;j<=n;j++)
            {
            	//cout<<a[j]%i<<" "<<u<<"\n";
                s[a[j]%i].insert(j);
            }
            //puts("");
            for(int j=0;j<i;j++)
            {
                if(s[j].size()>=2)
                {
                    int u=*s[j].begin();
                    int v=*(--s[j].end());
                    //cout<<u<<" "<<v<<"\n";
                    fa[find(u)]=find(v);
                    b[i]={u,v};
                    break;
                }
            }
        }
        //cout<<find(1)<<"\n";
        puts("YES");
        for(int i=1;i<n;i++)
        {
            printf("%d %d\n",b[i].first,b[i].second);
        }
    }
}