【UVA12036】 Stable Grid 题解：鸽笼原理的应用
sker114514
·
·
题解
前言
这里有详细的鸽笼原理讲解！
进入博客食用更佳
翻译
### 鸽笼原理及证明
这是一道经典的鸽笼原理结论题。
首先分析无解样例：
```
1 1 2
1 1 1
2 2 2
```
样例一共 $n=3$ 列，但是 $1$ 的数量和 $2$ 的数量都超过了 $n$，所以无解。
我们可以发现，当某一个数字的数量 $k>n$ 时，即为无解。
为了证明，我们可以造出当 $k=n$ 时操作后的情况：
```
1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3
```
容易发现，此时，每行的同种数字可以各占一列，相互不会影响；而当 $k<n$ 时，根本就占不了所有的 $n$ 列；可 $k>n$ 时，总有至少两个数字出现在一列，所以无解。
另外，这里提出一个假设，如果想要每行和每列都没有相同数字，也需要满足 $k\le n$ 的基本条件。
### 思路
通过刚刚的分析，可以发现思路：
1. 对于每种数字的总数量 $k$ 进行查询。
2. 如果发现 $k>n$，即为无解。
其中，如果想要查询每种数字的总数量，可以将相同数字数字连续起来，方便查找，这时候我们就可以用到排序。而此时我们需要将矩阵转换为一维数组，方便排序。
另外，输出时别忘了有空格~~（因为这个 WA 了）~~
## AC C++ CODE:
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[10010];
int main(){
int t;
cin>>t;
for(int j=1;j<=t;j++){//需要用到
memset(a,0,sizeof(a));//数据千万条，清空第一条。多测不清空，爆零两行泪。
int n;
int q=-1;
int k=0;//相同数字总个数
cin>>n;
for(int i=1;i<=n*n;i++)cin>>a[i];//需要用到一维数组
sort(a+1,a+n*n+1);//排序操作
bool f=0;
for(int i=1;i<=n*n;i++){
if(a[i]!=q){//判断是否连续为同一数字
if(k>n){//满足无解条件
f=1;
break;
}
k=0;//清空
q=a[i];
}
k++;//别忘了累加
}
cout<<"Case "<<j<<": "<<(f?"no":"yes")<<'\n';//别漏空格
}
return 0;
}
```
By ImNot6Dora