0x00 基本算法
位运算
A题:a^b
https://ac.nowcoder.com/acm/contest/996/A
题目描述
求 a 的 b 次方对 p 取模的值,其中 0 <= a,b,p <= 10^9
输入描述:
三个用空格隔开的整数a,b和p。
输出描述:
一个整数,表示a^b mod p的值。
实例:
输入: 2 3 9
输出: 8
思路:
这道题是要先算出a的b次幂再对其结果进行求模(取余),因为b最大可为1e+9,按普通做法来做时间复杂度就太大了,显然这样过不了题,
能快速算a的b次幂,就能减小时间复杂度,快速幂就是一种不错的方法。
什么是快速幂:
快速幂是一种简化运算底数的n次幂的算法,理论上其时间复杂度为 O(log₂N),而一般的朴素算法则需要O(N)的时间复杂度。简单来说快速幂其实就是抽取了指数中的2的n次幂,将其转换为时间复杂度为O(1)的二进制移位运算,所以相应地,时间复杂度降低为O(log₂N)。
代码原理:
以 \(a^{13}\) 为例,
先把指数13化为二进制就是1101,把二进制数字1101直观地表现为十进制则是如下的等式:
这样一来 \(a^{13}\) 可以如下算出:
完整AC代码如下:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;//将long long类型取个别名:ll类型,为了方便
int power(int a, int b, int mod) {
ll ans = 1 % mod;
for (; b; b >>= 1) {
if (b & 1) ans = ans * a % mod;
a = (ll)a * a % mod;//显式转化为ll类型进行高精度计算,再隐式转化为int
}
return ans;
}
int main() {
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(false), cin.tie(0);
int a, b, mod;
cin >> a >> b >> mod;
cout << power(a, b, mod) << endl;
}
B题:Raising Modulo Numbers
与上面A题写法一样
typedef long long ll;
int _;
// 稍微优化下上方代码:update 21/01/28
ll qpow(ll a, ll b, ll mod) {
ll ans = 1;
a %= mod;
for (; b; a = a * a % mod, b >>= 1)
if (b & 1) ans = ans * a % mod;
return ans;
}
int main() {
// freopen("in.txt", "r", stdin);
ios_base::sync_with_stdio(false), cin.tie(0);
ll M, N;
for (cin >> _; _--;) {
cin >> M >> N;
ll a, b, ans = 0;
while (N--) {
cin >> a >> b;
ans = (ans + qpow(a, b, M)) % M;
}
cout << ans << endl;
}
}
C题:64位整数乘法
链接:https://ac.nowcoder.com/acm/contest/996/C
思路:
类似快速幂的思想,把整数b用二进制表示,即
typedef long long ll;
int main() {
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(false), cin.tie(0);
ll a, b, p; cin >> a >> b >> p;
ll ans = 0;
for (; b; b >>= 1) {
if (b & 1)ans = (ans + a) % p;
a = (a << 1) % p;
}
cout << ans << endl;
}
⭐D题:最短Hamilton路径
链接:https://ac.nowcoder.com/acm/contest/996/D
解题思路
AC代码:
#define ms(a,b) memset(a,b,sizeof a)
int e[21][21], b[1 << 21][21], n;
int main() {
//freopen("in.txt", "r", stdin);
ios::sync_with_stdio(false), cin.tie(0);
cin >> n;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
cin >> e[i][j];
ms(b, 0x3f); b[1][0] = 0;
for (int i = 0; i < 1 << n; ++i)
for (int j = 0; j < n; ++j) if (i >> j & 1)
for (int k = 0; k < n; ++k) if (~(i >> k) & 1)//if ((i ^ 1 << j) >> k & 1)
b[i + (1 << k)][k] = min(b[i + (1 << k)][k], b[i][j] + e[j][k]);
cout << b[(1 << n) - 1][n - 1] << endl;
}
⭐例题:[NOI2014]起床困难综合征
题意:
贪心从高位到低位枚举,检验当前位在初始值为\(0\) 情况下的答案是否可以为\(1\) ,如果不能则检验当前位初始值能否为 \(1\),并检验当前位在初始值为 \(1\) 情况下的答案是否可以为 \(1\)。
int n, m, x;
string str;
pair<string, int> a[100005];
int work(int bit, int now) { // 用参加的第 bit 位进行n次运算
for (int i = 1; i <= n; ++i) {
int x = a[i].second >> bit & 1;
if (a[i].first == "AND")
now &= x;
else if (a[i].first == "OR")
now |= x;
else
now ^= x;
}
return now;
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
cin >> str >> x;
a[i] = make_pair(str, x);
}
int val = 0, ans = 0;
for (int bit = 29; bit >= 0; bit--) {
int res0 = work(bit, 0), res1 = work(bit, 1);
if (val += (1 << bit) <= m && res0 < res1)
val += (1 << bit), ans += (res1 << bit);
else
ans += (res0 << bit);
}
cout << ans << "\n";
return 0;
}
递推与递归
递归实现指数型枚举
int _, n, m, k, x, y;
vector<int> vec;
void calc(int x) {
if (x == n + 1) {
for (int i = 0; i < vec.size(); ++i) cout << vec[i] << " ";
cout << "\n"; // 注意一下,以后输出回车用 "\n" 而不是 endl
return;
}
calc(x + 1), vec.push_back(x);
calc(x + 1), vec.pop_back();
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
cin >> n;
calc(1);
}
递归实现组合型枚举
int n, m;
vector<int> vec;
void calc(int x) {
// 剪枝,如果已经选取了超过m个数,
// 或者即使选上剩下所有数也不够m个就要提前结束搜索了 ↓
if (vec.size() > m || vec.size() + (n - x + 1) < m) return;
if (x == n + 1) {
for (int i = 0; i < vec.size(); ++i) cout << vec[i] << " ";
cout << "\n"; // 注意一下,以后输出回车用 "\n" 而不是 endl
return;
}
calc(x + 1), vec.push_back(x);
calc(x + 1), vec.pop_back();
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
cin >> n >> m;
calc(1);
}
递归实现排列型枚举
int n, m;
int order[20];
bool chosen[20];
void cal(int k) {
if (k == n + 1) {
for(int i = 1;i<=n;++i)
cout << order[i] << " ";
cout << endl; return;
}
for (int i = 1;i <= n; ++i) {
if (chosen[i])continue;
chosen[i] = true;
order[k] = i;
cal(k + 1);
chosen[i] = false;
}
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
cin >> n;cal(1);
}
费解的开关
const int N = 6;//因为后续操作读取的是字符串
char g[N][N];
char backup[N][N];//备份 --- 用于记录每次枚举第1行的情况
int n;
int dx[5] = {-1,0,1,0,0}, dy[5] = {0,0,0,-1,1};//用于表示当前位置及该位置的上下左右位置的偏移量
//改变当前灯及其上下左右灯的状况
void turn(int x, int y){
for(int i = 0; i < 5; i ++){
int a = x + dx[i], b = y + dy[i];//用于表示当前位置或该位置的上下左右位置
if(a >= 0 && a < 5 || b >= 0 && b < 5){
g[a][b] ^= 1;//用于'0' 和'1'的相互转换 -----根据二者的Ascll码值特点
}
}
}
int main(){
cin >> n;
while(n --){
for(int i = 0; i < 5; i ++) cin >> g[i];//读取数据
int res = 10;//用于记录操作的结果
for(int op = 0; op < 32; op ++){//枚举第1行灯的状态 ---- 也可以采用递归实现指数型枚举
int step = 0;//用于记录当前情况的操作步数
memcpy(backup, g, sizeof g);//备份原数组数据 ---- 因为每次枚举都是一种全新的情况
//枚举第一行,若灯灭,则点亮
for(int j = 0; j < 5; j ++){
if(!(op >> j & 1)){//也可以是 if(op >> j & 1) ,因为二者情况数量相同
step ++;
turn(0, j);//翻转当前灯的状况
}
}
//从第一行向下递推至倒数第二行
for(int i = 0; i < 4; i ++){
for(int j = 0; j < 5; j ++){
if(g[i][j] == '0'){//当前行当前位置灯灭
step ++;
turn(i + 1, j);//改变当前行的下一行该列灯的状况,使当前行灯亮
}
}
}
//检验最后一行灯是否全亮,若存在暗灯,则此方案不成立
bool dark = false;
for(int j = 0; j < 5; j ++){
if(g[4][j] == '0'){
dark = true;
break;
}
}
if(!dark) res = min(step, res);
memcpy(g, backup, sizeof backup);//还原数据,用于下次方案的操作
}
if(res > 6) res = -1;
cout << res << endl;
}
return 0;
}
// 另一种解
int _, a[6], ans, aa[6];
string s;
void dj(int x, int y) {
aa[x] ^= (1 << y);
if (x != 1) aa[x - 1] ^= (1 << y);
if (x != 5) aa[x + 1] ^= (1 << y);
if (y != 0) aa[x] ^= (1 << (y - 1));
if (y != 4) aa[x] ^= (1 << (y + 1));
}
void pd(int p) {
int k = 0;
memcpy(aa, a, sizeof(a));
for (int i = 0; i < 5; ++i)
if (!((p >> i) & 1)) {
dj(1, i);
if (++k >= ans) return;
}
for (int x = 1; x < 5; ++x)
for (int y = 0; y < 5; ++y)
if (!((aa[x] >> y) & 1)) {
dj(x + 1, y);
if (++k >= ans) return;
}
if (aa[5] == 31) ans = k;
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
for (cin >> _; _--;) {
memset(a, 0, sizeof(a));
for (int i = 1; i <= 5; ++i) {
cin >> s; // 字符串读入更便利处理
for (int j = 1; j <= 5; ++j) a[i] = a[i] * 2 + (s[j - 1] - '0');
}
ans = 7;
for (int p = 0; p < (1 << 5); p++) pd(p);
cout << (ans == 7 ? -1 : ans) << "\n";
}
return 0;
}
Strange Towers of Hanoi
#define Fi(i, a, b) for (int i = a; i <= b; ++i)
int d[13], f[13];
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
Fi(i, 1, 12) d[i] = d[i - 1] * 2 + 1;
memset(f, 0x3f, sizeof f), f[1] = 1;
Fi(i, 2, 12) Fi(j, 1, i) f[i] = min(f[i], 2 * f[j] + d[i - j]);
Fi(i, 1, 12) cout << f[i] << "\n";
return 0;
}
⭐Sumdiv (AcWing 97. 约数之和)(数论)(分治)
const int p = 9901;
int pow(int x, int y) {
int ret = 1;
for (; y; y >>= 1) {
if (y & 1) ret = 1ll * ret * x % p;
x = (ll)x * x % p;
}
return ret;
}
int main() {
ios::sync_with_stdio(false), cin.tie(0);
int a, b, ans = 1;
cin >> a >> b;
if (!a) return !puts("0");
for (int i = 2, num; i * i <= a; i++) {
num = 0;
while (a % i == 0) a /= i, num++;
if (num)
ans =
ans * (pow(i, num * b + 1) - 1 + p) % p * pow(i - 1, p - 2) % p;
}
if (a > 1) ans = ans * (pow(a, b + 1) - 1 + p) % p * pow(a - 1, p - 2) % p;
cout << ans << "\n";
return 0;
}
⭐Fractal Streets
题解来源:Click Here
题意:
给你一个原始的分形图,t组数据,对于每组数据,输入3个数n,h,o (n为在第n级,h,o为两个房子的编号),求在第n级情况下,编号为h和o的两个点之间的距离*10为多少。
其中,第n级分形图形成规则如下:
- 首先先在右下角和右上角复制一遍n-1情况下的分形图
- 然后将n-1情况下的分形图顺时针旋转90度,放到左上角
- 最后将n-1情况下的分形图逆时针旋转90度 ,放到左下角
编号是从左上角那个点开始计1,沿着道路计数。
这是著名的通过一定规律无限包含自身的分形图。为了计算方便,我们将题目中房屋编号从0开始编号,那么S与D也都减掉1.
大体思路:设calc(n,m)求编号为m的房屋编号在n级城市中的坐标位置,那么距离是:calc(n,s-1) 与 calc(n,d-1)的距离。
从n(n > 1)级城市由四座n-1级城市组成,其中:
1.左上的n-1级城市由城市结构顺时针旋转90度,从编号的顺序看,该结构还做水平翻转,坐标转换至n级时如下图。
2与3.右上和右下和原始城市结构一样,坐标转换至n级时如下图。
市由城市结构逆时针旋转90度,从编号的顺序看,该结构也做了水平翻转。
旋转坐标的变化可通过公式:
(设len = 2(n-1))当旋转角度是逆时针90度时,也就是顺时针270度时,(x,y)->(y, -x),然后再进行水平翻转,(y,-x)->(-y,-x)。然后再将图形平移到n级图形的左下角,在格子上的坐标变化是,水平方向增加len - 1个位置,垂直方向增加2len - 1个位置。因此坐标(x,y)按照规则转移到了(2len-1-y,len-1-x).
注意:n-1级格子里拥有的房子数量是cnt = 22n /4,即22n-2.
当前编号m在N级格子的哪个方位是:m / cnt.
当前编号m在n-1级格子里的编号是: m %cnt;
详细代码如下:
using ll = long long;
pair<ll, ll> calc(ll n, ll m) {
if (n == 0) return make_pair(0, 0); //边界
ll len = 1ll << (n - 1), cnt = 1ll << (2 * n - 2);
pair<ll, ll> zb = calc(n - 1, m % cnt);
ll x = zb.first, y = zb.second;
ll z = m / cnt;
switch (z) {
case 0: return make_pair(y, x); break;
case 1: return make_pair(x, y + len); break;
case 2: return make_pair(x + len, y + len); break;
case 3: return make_pair(2 * len - y - 1, len - x - 1); break;
}
}
int main() {
int t;
cin >> t;
while (t--) {
ll n, s, d;
cin >> n >> s >> d;
pair<ll, ll> zb;
pair<ll, ll> bz;
double ans = 0;
zb = calc(n, s - 1); //记得-1 QWQ
bz = calc(n, d - 1);
ll x, y;
x = (zb.first - bz.first), y = (zb.second - bz.second); //边长居然是10
ans = sqrt(x * x + y * y) * 10; //喜闻乐见 勾股定理
printf("%.0f\n", ans); //四舍五入
}
return 0;
}
非递归实现组合型枚举
#include <iostream>
#include <vector>
using namespace std;
vector<int> chosen;
int n, m;
void dfs(int x);
int main() {
cin >> n >> m;
dfs(1);
}
void dfs(int x) {
if (chosen.size() > m || chosen.size() + (n - x + 1) < m) return;
if (x == n + 1) {
// if(chosen.size() == 0) return;
for (int i = 0; i < chosen.size(); i++) printf("%d ", chosen[i]);
puts("");
return;
}
chosen.push_back(x);
dfs(x + 1);
chosen.pop_back();
dfs(x + 1);
return;
}
前缀和与差分
A题:HNOI2003]激光炸弹
按照蓝书上的教程做即可,注意这道题卡空间用int
而不是 long long
。
int g[5010][5010];
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
int N, R;
cin >> N >> R;
int xx = R, yy = R;
for (int i = 1; i <= N; ++i) {
int x, y, w;
cin >> x >> y >> w, ++x, ++y;
g[x][y] = w, xx = max(xx, x), yy = max(y, yy);
}
for (int i = 1; i <= xx; ++i)
for (int j = 1; j <= yy; ++j)
g[i][j] = g[i - 1][j] + g[i][j - 1] - g[i - 1][j - 1] +
g[i][j]; //求前缀和
int ans = 0;
for (int i = R; i <= xx; ++i)
for (int j = R; j <= yy; ++j)
//用提前算好的前缀和减去其他部分再补上多剪的那部分
ans =
max(ans, g[i][j] - g[i - R][j] - g[i][j - R] + g[i - R][j - R]);
cout << ans << "\n";
return 0;
}
B题:IncDec Sequence
设 a 的差分序列为 b.
则对区间 [l, r] 的数都加 1,就相当于 b[l]++, b[r + 1]--.
操作分为 4 种.
① 2 ≤ l ≤ r ≤ n (区间修改)
② 1 == l ≤ r ≤ n(修改前缀)
③ 2 ≤ l ≤ r == n + 1 (修改后缀)
④ 1 == l ≤ r == n + 1 (全修改)
其中操作 ④ 显然无用.
操作 ① 性价比最高.
于是可得出方案:先用操作 ① ,使得只剩下 正数 或 负数 ,剩下的用操作 ② 或 ③ 来凑.
using ll = long long;
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
int n;
cin >> n;
vector<ll> a(n + 1, 0), b(n + 2);
for (int i = 1; i <= n; ++i) cin >> a[i], b[i] = a[i] - a[i - 1];
ll p = 0, q = 0;
for (int i = 2; i <= n; ++i) { // 2~n的正负数和统计
if (b[i] > 0) p += b[i];
else if (b[i] < 0) q -= b[i];
}
cout << max(p, q) << "\n" << llabs(p - q) + 1 << "\n";
return 0;
}
C题:Tallest Cow
差分数组,对于给出第一个区间a,b,他们之间的人肯定比他们矮,最少矮1,那么就在a+1位置-1,b位置加1,计算前缀和,a+1以及之后的都被-1了,b及以后的不变。
重复的区间,不重复计算。
另一种思路:先将所有的牛的高度都设为最大值 然后在输入一组数A B时 将A B之间的牛的高度都减一。
map<pair<int, int>, bool> vis;
int c[10010], d[10010];
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
int n, p, h, m;
cin >> n >> p >> h >> m;
while (m--) {
int a, b;
cin >> a >> b;
if (a > b) swap(a, b);
if (vis[make_pair(a, b)]) continue; // 避免重复计算
vis[{a, b}] = true, d[a + 1]--, d[b]++;
}
for (int i = 1; i <= n; ++i) {
c[i] = c[i - 1] + d[i];
cout << h + c[i] << "\n";
}
return 0;
}
二分
⭐二分A题:Best Cow Fences
二分答案,判定是否存在一个长度不小于L的子段,平均数不小于二分的值。如果把数列中的每个数都减去二分的值,就转换为判定“是否存在一个长度不小于L的子段,子段和非负”。
先分别考虑两种情况的解法(1、子段和最大【无长度限制】,2、子段和最大,子段长度不小于L)
<==>求一个子段,使得它的和最大,且子段的长度不小于L。
子段和可以转换为前缀和相减的形式,即设\(sumj\)表示\(Ai 到 Aj\)的和,
则有:\(max{A[j+1]+A[j+2].......A[i] } ( i-j>=L ) \\ = max{ sum[i] - min{ sum[j] }(0<=j<=i-L) }(L<=i<=n)\)
仔细观察上面的式子可以发现,随着i的增长,j的取值范围 0~i-L 每次只会增大1。换言之,每次只会有一个新的取值进入 \(min\{sum_j\}\) 的候选集合,所以我们没必要每次循环枚举j,只需要用一个变量记录当前的最小值,每次与新的取值 sum[i-L] 取min 就可以了。
double a[100001], b[100001], sum[100001];
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
int n, L;
cin >> n >> L;
for (int i = 1; i <= n; ++i) cin >> a[i];
double eps = 1e-5;
double l = -1e6, r = 1e6;
while (r - l > eps) {
double mid = (l + r) / 2;
for (int i = 1; i <= n; ++i) b[i] = a[i] - mid;
for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + b[i];
double ans = -1e10;
double min_val = 1e10;
for (int i = L; i <= n; ++i) {
min_val = min(min_val, sum[i - L]);
ans = max(ans, sum[i] - min_val);
}
if (ans >= 0)
l = mid;
else
r = mid;
}
cout << int(r * 1000) << "\n";
return 0;
}
排序
A题: Cinema
经典离散化例题,把电影的语言与字幕和观众懂的语言放进一个数组,然后离散化。
最后统计快乐人数。
const int N = 200006;
int n, m, a[N], x[N], y[N], cinema[N * 3], tot = 0, k, ans[N * 3];
int find(int f) { return lower_bound(cinema + 1, cinema + k + 1, f) - cinema; }
int main() {
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i], cinema[++tot] = a[i];
cin >> m;
for (int i = 1; i <= m; ++i) cin >> x[i], cinema[++tot] = x[i];
for (int i = 1; i <= m; ++i) cin >> y[i], cinema[++tot] = y[i];
sort(cinema + 1, cinema + tot + 1);
k = unique(cinema + 1, cinema + tot + 1) - (cinema + 1);
memset(ans, 0, sizeof(ans));
for (int i = 1; i <= n; i++) ans[find(a[i])]++;
int ans0 = 1, ans1 = 0, ans2 = 0;
for (int i = 1; i <= m; i++) {
int ansx = ans[find(x[i])], ansy = ans[find(y[i])];
if (ansx > ans1 || (ansx == ans1 && ansy > ans2)) {
ans0 = i;
ans1 = ansx;
ans2 = ansy;
}
}
cout << ans0 << endl;
return 0;
}
当然不用离散化也可以做。
简单使用 unordered_map
映射个数即可
const int N = 2e5 + 10;
int _, n, x, y, tmp, a[N];
unordered_map<int, int> mp;
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
for (cin >> _; _--;) cin >> tmp, mp[tmp]++;
cin >> n;
for (int i = 1; i <= n; ++i) cin >> a[i];
for (int i = 1; i <= n; ++i) {
int t;
cin >> t;
if (mp[a[i]] > x)
tmp = i, x = mp[a[i]], y = mp[t];
else if (mp[a[i]] == x && mp[t] > y)
tmp = i, y = mp[t];
}
cout << tmp << "\n";
return 0;
}
B题:货仓选址
排序一下,利用中位数的性质
int n, ans, sum;
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
cin >> n;
vector<int> v(n);
for (auto &t : v) cin >> t;
sort(v.begin(), v.end());
ans = v[n / 2];
for (auto &t : v) sum += abs(t - ans);
cout << sum << "\n";
return 0;
}
C题:⭐七夕祭
题解
这个题其实是两个问题:
1.让摊点上下移动,使得每行的摊点一样多
2.左右移动摊点,使得每列的摊点一样多
两个问题是等价的,就讨论第一个
r[i]表示每行的摊点数
然后使得r[i]的一些摊点移动到r[i - 1]和r[i + 1], 类似于"均摊纸牌"
均摊纸牌
显然, 纸牌总数T能被M整除有解,在有解的情况下, 考虑第一个人:
到这里就可以发现,有一段是前缀和, 但再仔细化简以下可以发现
我们可以让A[i] = C[i] - T/M, S[i]为A[i]的前缀和,
那么对于"均摊纸牌"这道题的答案就是
∑ni=1∑i=1n|S[i]|
对于本题来说,无非是变成了环形问题
直接无脑dp就可以
我们随便选取一个人k最为断环的最后一名(即第一个人变为为k + 1),
则从这个人开始的持有的牌数(这行的摊点数), 前缀和为
A[k + 1] S[k + 1] - S[k]
A[k + 2] S[k + 2] - S[k]
...
A[M] S[M] - S[k]
A[1] S[M] - S[k] + S[1]
A[2] S[M] - S[k] + S[2]
...
A[k] S[M] - S[k] + S[k]
我们发现S[M] = 0, 所以答案为
|S[k + 1] - S[k]| + ... + |S[M] - S[k]| + |s[M] - S[k] + S[1]| + ... + |S[M] - S[K] + S[k]|
=|S[k + 1] - S[k]| + ... + |S[M] - S[k]| + |-S[k] + S[1]| + ... + |-S[k] + S[k]|
=∑ni=1∑i=1n |S[i] - S[k]|
答案已经很明显了,像不像"仓货选址"?
仓货选址
不就是∑ni=1∑i=1n |D[i] - D[k]| 为答案吗?
当然是选中位数了啦,
设k左边有P家店,右边有Q家店
如果P<Q,那必然将k右移, ans - Q + P,答案明显变小了
Q>P,同理,故选择中位数
所以本题的答案就已经近在眼前了, 前缀和,求中位数
using ll = long long;
const int maxn = 1e5 + 5;
int n, m, k;
int c[maxn], r[maxn], s[maxn];
ll work(int a[], int n) {
for (int i = 1; i <= n; ++i) s[i] = s[i - 1] + a[i] - k / n;
sort(s + 1, s + 1 + n);
ll ans = 0;
for (int i = 1; i <= n; ++i) ans += abs(s[i] - s[(n >> 1) + 1]);
return ans;
}
int main() {
cin >> n >> m >> k;
for (int i = 1; i <= k; ++i) {
int a, b;
cin >> a >> b, ++c[b], ++r[a];
}
if (k % n + k % m == 0)
cout << "both " << work(c, m) + work(r, n);
else if (k % n == 0)
cout << "row " << work(r, n);
else if (k % m == 0)
cout << "column " << work(c, m);
else
cout << "impossible";
return 0;
}