要学会把真正的问题抽象出来…才可能去解决Orz

懵逼的 题目

BZOJ

扯淡的 题解

看的LYD神仙的书Orz

对于环和抽象问题我一直不擅长来着…

我们发现这题其实就是在行和列上分别进行环状均分纸牌…因为行之间交换不会影响列上[喜爱店铺的数目], 所以这个[交换相邻的店铺]其实就是均分纸牌里相邻两个人传纸牌…

(顺便一说为什么一定可以把一行移动想移动的喜爱店铺去另一行: 因为如果要移动的话这行上的喜爱店铺会比下一行的多, 这样就不会出现”两个喜爱店铺挨着交换后没影响的情况了”)

很好 环状均分纸牌我也不会 T_T

我们发现 普通均分纸牌的交换次数是$\sum {|i \cdot aver - fr_i|}$: 即$i$前面需要的纸牌总数和$i$前面拥有的纸牌总数
如果把每个人的纸牌数都提前减掉$aver$, 那么答案就变成了$\sum |fr_i|$

而环上的均分纸牌 一定有两人之间没有发生互动, 我们可以从这两个人之间把环变成链…怎么变呢…

我们发现如果$k$变成了链头, 那么$fr$数组就变成了
$$
fr_k - fr_{k - 1}, fr_{k + 1} - fr_k , \cdots, fr_{k - 2} + fr_n - fr_{k - 1}, fr_{k - 1} + fr_n - fr_{k - 1}
$$
因为我们已经把所有的数都减去了$aver$, 所以这个数列的和$fr_n = 0$, 所以这个数列又变成了
$$
fr_k - fr_{k - 1}, fr_{k + 1}- fr_k, \cdots, fr_{k - 2} - fr_{k - 1}, fr_{k - 1} - fr_{k - 1}
$$
也就是之前所有的$fr$都减去了$fr_{k - 1}$

也就是说 我们要在$fr$里找一个数, 让其他所有数和他差的绝对值和最小 显然我们找中位数就可以了Orz

沙茶的 代码

代码倒是肥肠好写…

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAXN (100000 + 5)
#define int long long
#define mabs(x) ((x) > 0 ? (x) : (-(x)))
using namespace std;
int n, m, t, a[MAXN], b[MAXN];
int solve(int xn, int* xa)
{
    int f[MAXN], re = 0, aver = 0;
    for (int i = 1; i <= xn; i++)
        aver += xa[i];
    aver /= xn;
    for (int i = 1; i <= xn; i++)
        f[i] = f[i - 1] + xa[i] - aver;
    sort(f + 1, f + xn + 1);
    for (int i = 1; i <= xn; i++)
        re += mabs(f[i] - f[(xn + 1) >> 1]);
    return re;
}
main()
{
    scanf("%lld%lld%lld", &n, &m, &t);
    for (int i = 1, srx, sry; i <= t; i++)
        scanf("%lld%lld", &srx, &sry), ++a[srx], ++b[sry];
    if (t % n == 0 && t % m == 0)
        printf("both %lld", solve(n, a) + solve(m, b));
    else if (t % n == 0)
        printf("row %lld", solve(n, a));
    else if (t % m == 0)
        printf("column %lld", solve(m, b));
    else
        puts("impossible");
    return 0;
}

By Cansult