标签：Funny int 2005 Game 鸽巢 sizeof
- 鸽巢原理/抽屉原理：假如有n+1个元素放到n个集合中去，其中必定有一个集合里至少有两个元素
- 首先，将\(x\)整除\(|a_u-a_v|\)转化为它们模x同余
- 有n个点，x=n-1时，根据鸽巢原理，一定可以找到这样的两个同余的点，将它们连边
- 以此类推，解毕
- 模拟样例以感受题意
点击查看代码
#include <bits/stdc++.h>
using namespace std;
int a[2005],u[2005],v[2005];
int h[2005];
bool b[2005];
int main()
{
int T;
cin>>T;
while(T--)
{
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
memset(b,false,sizeof(b));
for(int i=n-1;i>=1;i--)
{
memset(h,0,sizeof(h));
for(int j=1;j<=n;j++)
{
if(b[j]==true)
{
continue;
}
if(h[a[j]%i]==0)
{
h[a[j]%i]=j;
}
else
{
u[i]=h[a[j]%i];
v[i]=j;
b[j]=true;
break;
}
}
}
puts("YES");
for(int i=1;i<n;i++)
{
printf("%d %d\n",u[i],v[i]);
}
}
return 0;
}
标签：Funny,
int,
2005,
Game,
鸽巢,
sizeof
From： https://www.cnblogs.com/watersail/p/18312281