七夕祭

七夕祭

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

于是 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$

输入样例:

1
2
3
4
5
2 3 4
1 3
2 1
2 2
2 3

输出样例:

1
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、给出牌,或者拿走牌之后 第二个牌堆的牌数为零,那么此时第二堆牌不需要再给或拿第三个堆牌,在进行第二堆到第三堆的操作时不需要使答案数增加

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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;
}

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

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

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

紧接着是第二个问题(难点)

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

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

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

最后一个问题(难点)

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

1
9 8 17 6

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

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

1
-1 -2 7 -4

然后计算前缀和,得到

1
-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了。

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

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#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;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!