博客地址 Nicoppa的个人博客

七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。

于是 TYVJ 今年举办了一次线下七夕祭。

Vani 同学今年成功邀请到了 cl 同学陪他来共度七夕，于是他们决定去 TYVJ 七夕祭游玩。

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， 接下来输出最小交换次数，与字符串之间用一个空格隔开。

数据范围

$1≤N,M≤100000$,
$0≤T≤min(N∗M,100000)$,
$1≤x≤N$,
$1≤y≤M$

输入样例：

2 3 4
1 3
2 1
2 2
2 3

输出样例：

row 1

解析

引入一个前置题 均分纸牌

此题就是在均分纸牌上加了三个条件

1、变成一个二维题

2、将链变成环（首尾可交换）

3、每次只能转移一个点

简化模型，先解决均分纸牌，简述一下题意，有 $n$ 个牌堆，每个牌堆里有 $a_i$ 个牌，现在要将每个牌堆的牌数变为相同的，每次操作可以将任意牌堆的任意张牌移动到相邻的牌堆中，请问最少需要多少个操作将所有牌堆的牌数变为相同的。

那么我们可以很容易的得到一个解决办法：首先得到最后我们所有牌堆中应当有多少张牌，很简单T = $\frac{\Sigma_{i = 1}^n a_i}{n}$ ，然后将每个牌堆的牌数 $a_i$ 减去这个 $T$，就可以得到每个牌堆的牌数距离满足条件的牌数还差多少张牌，每个牌堆想要获得牌只能由相邻的牌堆进行提供，所以我们只需要从第一个牌堆开始考虑，按照多出少补的原则进行递推，比如：第一个牌堆缺 5 张牌，那么一定是从第二个牌堆中得到 5 张牌，或者第一个牌堆多 5 张牌，那么一定是给第二个牌堆 5 张牌。得到 5 张牌很好处理，因为第一个牌堆缺 5 张牌，所以第一个牌堆的当前数一定是 -5，直接将 -5 加到第二个牌堆上即可，给出 5 张牌也是同理。

那么此时就会出现两种情况

1、给出牌，或者拿走牌之后 第二个牌堆的牌数不为零，那么继续以上操作 并且记录答案+1

2、给出牌，或者拿走牌之后 第二个牌堆的牌数为零，那么此时第二堆牌不需要再给或拿第三个堆牌，在进行第二堆到第三堆的操作时不需要使答案数增加

代码如下

#include <cstdio>

const int N = 105;
int arr[N];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &arr[i]);

    int t = 0;
    for (int i = 1; i <= n; i++) t += arr[i]; t /= n;
    for (int i = 1; i <= n; i++) arr[i] -= t;

    int tnt = 0, ans = 0;
    for (int i = 1; i <= n; i++) {
        tnt += arr[i];
        ans++; if(tnt == 0) ans--;
    } printf("%d\n", ans);
    return 0;
}

那么解决这个问题之后，我们再来解决这道 七夕祭

三个问题依次解决，首先是第一个问题

由样例画图易得，无论摊点的位置如何变化，总行和总列上的摊点总数不会变，那么我们只需要将行和列看成一条线单独处理就好了

紧接着是第二个问题（难点）

这道题将链变为了环，事情好像一下就变得非常复杂了，似乎我们不能再从第一个点递推了，产生了非常多的情况。为了解决这个问题，我们仍然使用简化模型的方式将所有情况列举出来。我们可以发现，所有情况都可以简化为三个摊点的移动情况，那么可得证明（如图）

未列举所有摊点的关系，但都同理，注意：不存在三个都大于零与三个都小于零的情况。

由图我们可以得到，即使图形为环，为了保证结果最优总会有两个摊点间不会进行交换，那么我们将这个环从这两点间断开当成链处理，就和 均分纸牌 一样了。

最后一个问题（难点）

每次只能移动一个点，假如将这个条件加入到 均分纸牌 中，借用均分纸牌的样例

9 8 17 6

我们最后要得到的数为 10 10 10 10，直接数的话我们可以得到操作数为 8

为了好理解，我们模拟一遍从第一个牌堆到第三个牌堆的过程，我们现在要从第一个牌堆中拿 -1 个牌到第三个牌堆，要先经过第二个牌堆，再到第三个牌堆。这 -1 个牌我们是要经过第二个牌堆的，有什么方法能让我们一次性处理完全部牌堆呢？一个方法就呼之欲出 前缀和，我们将每个牌堆的牌数先 -10，得到

-1 -2 7 -4

然后计算前缀和，得到

-1 -3 4 0

然后将这些数的绝对值加起来，就得到了我们的总操作数 8。

这个前缀和的操作就相当于模拟了给牌的过程（关键，注意理解）

于是可以易得我们的答案方程 $ans = \Sigma_{i = 1}^n|G_i - i \times \frac{T}{n}|$ ，$T$ 为总牌数，$n$ 为牌堆数， $G_i$ 为第 $i$ 个牌堆的前缀和

解决完这三个问题，回到题目本身，对于题目的解决，我们仍需要得到一个数据，即断开点 $k$ 的位置。很简单的方法就是爆搜，但很明显对于这道题而言会超时，那么我们就需要从别处下手。对于一道有答案方程的题，可以考虑从答案方程入手。

假设已知断开点 $k$ 的位置（即 $S_k$ 为尾而 $S_{k+1}$ 为首），原前缀和为

$G_1,G_2,G_3,…,G_k,G_{k+1},…G_{n}$

断开后变为了

$G_{k+1} - G_{k},G_{k+2} - G_k,…,G_n - G_k,G_1 + G_n - G_k,…,G_k + G_n - G_k$

由于要想结果成立，可以得到 $G_n = T$ ，我们将原数组的每项先减去 $\frac{T}{n}$ ，那么就可以得到 $G_n = 0$

于是原式就可以看作为一个通项式 $G_i - G_k$，由于我们原数组的每项先减去了 $\frac{T}{n}$（注意对比，上面的答案方程的原数组并没有变化），所以我们的答案方程就是 $ans = \Sigma_{i = 1}^n|G_i - G_k|$

在一个一维线上（我们已经将二维图形转化了两条一维线，不懂可以回到我们解决的一问题），为了便于理解，我们假设 $G_i$ 数组变为了一段依次增大的代表当前坐标的x轴上的数（比如 -2 -1 0 1 2）， $\Sigma_{i=1}^n|G_i-G_k|$ 含义便是各点到 $k$ 点的距离总和，这个 $k$ 是未知的，我们的答案要求最小交换次数，在这里就是让各点到 $k$ 点的距离总和尽量的小。回忆一下，让各点到 $k$ 点的距离总和尽可能的小，这不就是 货仓选址 嘛，我们只需要让这个 $k$ 点在中点就可以让结果最优，前提是保证这个数列一定是单调的。

于是我们得到了这个 $k$ 的解决办法，直接把这个前缀和排序，将这个答案方程带入就可以AC了。

这道题融合了两道题的思路，并且提出了环状问题的解决思路，代码简单思路较难的好题，建议自己看完后隔一天再自己捋一遍这道题。

代码如下

#include <cstdio>
#include <iostream>
#include <algorithm>

const int N = 100005;
long long xl[N], yl[N], f[N]; //注意long long 会爆int

//懂了思路这里就是小模拟
long long handle(long long arr[N], int n) {
    for (int i = 1; i <= n; i++) f[i] = f[i - 1] + arr[i] - arr[0] / n;

    std::sort(f + 1, f + 1 + n);
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += std::abs(f[i] - f[(n + 1) >> 1]);
    } return ans;
}

int main() {
    int n, m, t;
    scanf("%d %d %d", &n, &m, &t);

    for (int i = 1; i <= t; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        xl[x]++, yl[y]++;
    }

    for (int i = 1; i <= n; i++) xl[0] += xl[i];
    for (int i = 1; i <= m; i++) yl[0] += yl[i];

    if(xl[0] % n == 0 && yl[0] % m == 0) {
        printf("both %lld", handle(xl, n) + handle(yl, m));
    } else if(xl[0] % n == 0) {
        printf("row %lld", handle(xl, n));
    } else if(yl[0] % m == 0) {
        printf("column %lld", handle(yl, m));
    } else puts("impossible");
    return 0;
}