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直观地表现为十进制则是如下的等式:

\[13 = 1 * (2^3) + 1 * (2^2) + 0 * (2^ 1) + 1 * (2^0)\]

这样一来 \(a^{13}\) 可以如下算出:

\[a^{13} = a ^ {(2^3)} * a ^ {(2^2)} * a ^ {(2^0)}\]

完整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用二进制表示,即

\[b = c_{k - 1}2^{k - 1} + c_{k -2}2^{k - 2} + ... + c_02^0\]
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

解题思路

《算法竞赛进阶指南》蓝书重做记录-LMLPHP《算法竞赛进阶指南》蓝书重做记录-LMLPHP

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]起床困难综合征

题意:

《算法竞赛进阶指南》蓝书重做记录-LMLPHP

链接:[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. 约数之和)(数论)(分治)

《算法竞赛进阶指南》蓝书重做记录-LMLPHP

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级分形图形成规则如下:

  1. 首先先在右下角和右上角复制一遍n-1情况下的分形图
  2. 然后将n-1情况下的分形图顺时针旋转90度,放到左上角
  3. 最后将n-1情况下的分形图逆时针旋转90度 ,放到左下角
    编号是从左上角那个点开始计1,沿着道路计数。

《算法竞赛进阶指南》蓝书重做记录-LMLPHP

这是著名的通过一定规律无限包含自身的分形图。为了计算方便,我们将题目中房屋编号从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度,从编号的顺序看,该结构也做了水平翻转。
 
  旋转坐标的变化可通过公式:

《算法竞赛进阶指南》蓝书重做记录-LMLPHP

 (设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;
}
04-16 01:42