题面
TYVJ七夕祭和11区的夏祭的形式很像。矩形的祭典会场由N排M列共计N×M个摊点组成。虽然摊点种类繁多，不过cl只对其中的一部分摊点感兴趣，比如章鱼烧、苹果糖、棉花糖、射的屋……什么的。Vani预先联系了七夕祭的负责人zhq，希望能够通过恰当地布置会场，使得各行中cl感兴趣的摊点数一样多，并且各列中cl感兴趣的摊点数也一样多。
不过zhq告诉Vani，摊点已经随意布置完毕了，如果想满足cl的要求，唯一的调整方式就是交换两个相邻的摊点。两个摊点相邻，当且仅当他们处在同一行或者同一列的相邻位置上。由于zhq率领的TYVJ开发小组成功地扭曲了空间，每一行或每一列的第一个位置和最后一个位置也算作相邻。现在Vani想知道他的两个要求最多能满足多少个。在此前提下，至少需要交换多少次摊点。
输入
第一行包含三个整数N和M和T。T表示cl对多少个摊点感兴趣。
接下来T行，每行两个整数x, y，表示cl对处在第x行第y列的摊点感兴趣。
输出
首先输出一个字符串。如果能满足Vani的全部两个要求，输出both；如果通过调整只能使得各行中cl感兴趣的摊点数一样多，输出row；如果只能使各列中cl感兴趣的摊点数一样多，输出column；如果均不能满足，输出impossible。
如果输出的字符串不是impossible， 接下来输出最小交换次数，与字符串之间用一个空格隔开。
解析
此题我们可分析得交换左右相邻的摊点只会改变某两列cl感兴趣的摊点数，不会改变每一行cl感兴趣的摊点数，同理交换上下相邻的摊点只会改变某两行cl感兴趣的摊点数，不会改变每一列cl感兴趣的摊点数。也就是说左右交换和上下交换是两个相互独立的过程，故可以独立求解，此问题就被划分为两个问题。
1.通过最少次数的左右交换使每列中cl感兴趣的摊点数相同。
2.通过最少次数的上下交换使每行中cl感兴趣的摊点数相同。
显然当且仅当m|T时1问题有解，n|T时2问题有解，我们的目的就是让每行都有T/n个cl感兴趣的摊点,每列都有T/m个cl感兴趣的摊点。此时问题就类似于前面 均分纸牌的拓展
(以下简称均分纸牌问题)
此题又与均分纸牌有一些区别，它可看作是一个环形的均分纸牌问题我们便可以去枚举它的断点。
(以下的A[i]是减去了T/m的,S[i]是A[i]的前缀和，即 S[i]=\(\sum_{j=1}^i\)A[i] )
一般均分纸牌问题每个人持有的纸牌数A[1] \(\cdots\) A[m] 和前缀和S[i] \(\cdots\) S[m]
如果在第k个人断开这m个人持有的纸牌和前缀和是
A[K+1],A[K+2] \(\cdots\) A[m],A[1] \(\cdots\) A[K]。
S[K+1],S[K+2] \(\cdots\) S[m],S[1] \(\cdots\) S[K]。
故可求的公式 \(\sum_{i=1}^m\) \(\mid\)S[i]-S[k]\(\mid\)，我们就要求得其最小值,此时问题又变为了前面的货仓选址排序后求得最小值即可。
代码
#include<bits/stdc++.h>
using namespace std;
int n,m,T,xi[100010],yi[100010],A[100010],S[100010],nx,ny,u,v,k;
int main(){
scanf("%d %d %d",&n,&m,&T);
for(int i=1;i<=T;i++){
scanf("%d %d",&u,&v);
xi[u]++;
yi[v]++;
}
if(!(T%n)){
nx=T/n;
for(int i=1;i<=n;++i){
A[i]=xi[i]-nx;
S[i]=S[i-1]+A[i];
}
sort(S+1,S+1+n);
k=n>>1;
if(n&1)k++;
u=0;
for(int i=1;i<=n;++i){
u+=abs(S[i]-S[k]);
}
}
if(!(T%m)){
ny=T/m;
for(int i=1;i<=m;++i){
A[i]=yi[i]-ny;
S[i]=S[i-1]+A[i];
}
sort(S+1,S+1+m);
k=m>>1;
if(m&1)k++;
v=0;
for(int i=1;i<=m;++i){
v+=abs(S[i]-S[k]);
}
}
if((!(T%m))&&(!(T%n))) printf("both %lld",(long long)u+v);//此处要强制类型转换防止溢出
else if(!(T%n)) printf("row %d",u);
else if(!(T%m)) printf("column %d",v);
else printf("impossible");
}