提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

《算法竞赛进阶指南》0x08 总结与练习

算法 指南 总结 进阶 练习 竞赛
2023-06-13 09:14:15 时间

章节总结

任何问题都有其涉及的范围，称之为问题的“状态空间”，求解一个问题，就是在这个状态空间里的遍历与映射

递推与递归是遍历状态空间的两种基本形式

接下来的章节探讨的各种算法，则是对于 “遍历顺序” “遍历过程中的决策方法” “状态空间中各状态之间的映射方式” 给出的指导

  1. 枚举与模拟是按照问题的直接表述形式对状态空间进行朴素的遍历
  2. 搜索则是带有一定的选择性、决策性的遍历
  3. 贪心是在每步决策时采取局部最优策略的遍历
  4. 动态规划则是基于全局考量的分阶段、按维度、无重复遍历
  5. 二分、倍增以及与排序相关的一些算法会对状态空间实施划分、等价、代表、拼接等手段，直接降低遍历时需要面对的时空规模

本章知识点汇总：

  1. 位运算
    1. 补码表示法，理解 C++ 无符号、有符号整数在计算机中的存储方式
    2. 各种按位运算，包括取位、置位、移位等，以及一些常用技巧
    3. 快速幂，64位整数乘法
    4. 二进制状态压缩，使用二进制数对状态进行压缩、提取的方法
  2. 枚举、模拟、递推
    1. 能想象问题 “状态空间”，理解各种基本算法其实是对状态空间的遍历与映射
    2. 常见的枚举形式，无法设计有效算法时能够通过美剧的方式直接遍历状态空间
    3. 通过模拟，主要侧重代码实现能力的训练
    4. 递推边界、目标、递推公式的发现与设计
    5. 一维、二维前缀和的递推与应用
  3. 递归
    1. 理解递归思想、子问题、递归边界、回溯时还原现场
    2. 递归实现常见规模的状态空间的遍历
    3. 分治思想，对问题进行划分、递归、再合并
    4. 分形，主要练习对子问题的划分、提取、抽象
    5. 递归的机器实现，转化成非递归的通用方式
  4. 二分
    1. 整数集合二分法、实数域二分法
    2. 单峰函数的三分法
    3. 二分答案，把求解转化为判定
  5. 排序
    1. 各种排序算法
    2. 离散化
    3. 中位数相关问题，包括货仓选址、环形均分纸牌、动态维护中位数等
    4. 求第 k 个数的线性算法
    5. 逆序对相关问题，使用归并排序求逆序对
  6. 倍增
    1. 序列上的倍增算法及其应用
    2. RMQ-ST 算法
  7. 贪心
    1. 贪心思想及其证明手段，主要通过较多题目开拓视野、归纳总结

习题

飞行员兄弟

题目描述

“飞行员兄弟”这个游戏，需要玩家顺利的打开一个拥有

16

个把手的冰箱。

已知每个把手可以处于以下两种状态之一：打开或关闭。

只有当所有把手都打开时，冰箱才会打开。

把手可以表示为一个

4×4

的矩阵，您可以改变任何一个位置

[i,j]

上把手的状态。

但是，这也会使得第

i

行和第

j

列上的所有把手的状态也随着改变。

请你求出打开冰箱所需的切换把手的次数最小值是多少。

输入格式

输入一共包含四行，每行包含四个把手的初始状态。

符号 + 表示把手处于闭合状态，而符号 - 表示把手处于打开状态。

至少一个手柄的初始状态是关闭的。

输出格式

第一行输出一个整数

N

，表示所需的最小切换把手次数。

接下来

N

行描述切换顺序，每行输出两个整数，代表被切换状态的把手的行号和列号，数字之间用空格隔开。

注意：如果存在多种打开冰箱的方式，则按照优先级整体从上到下，同行从左到右打开。

数据范围

1≤i,j≤4

输入样例：

-+--
----
----
-+--

输出样例：

6
1 1
1 3
1 4
4 1
4 3
4 4

解析

显然最优解中，每个位置至多操作一次

因此直接二进制枚举即可

for (int op = 0; op < 1 << n * n; op ++ )
{
    memcpy(a, b, sizeof b);
    int cnt = 0;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            if (op >> i * n + j & 1)
                turn(i, j), cnt ++ ;
    if (cnt >= res) continue;
    bool ok = true;
    for (int i = 0; i < n; i ++ )
        for (int j = 0; j < n; j ++ )
            if (a[i][j] == '+')
                ok = false;
    if (ok) res = cnt, state = op;
}

占卜DIY

题目描述

达达学会了使用扑克 DIY 占卜。

方法如下：

一副去掉大小王的扑克共

52

张，打乱后均分为

13

堆，编号

1∼13

，每堆

4

张，其中第

13

堆称作“生命牌”，也就是说你有

4

条命。

这里边，

4

张

K

被称作死神。

初始状态下，所有的牌背面朝上扣下。

流程如下：

  1. 抽取生命牌中的最上面一张(第一张)。
  2. 把这张牌翻开，正面朝上，放到牌上的数字所对应编号的堆的最上边。(例如抽到
2

，正面朝上放到第

2

堆牌最上面，又比如抽到

J

，放到第

11

堆牌最上边，注意是正面朝上放)

  1. 从刚放了牌的那一堆最底下(最后一张)抽取一张牌，重复第
2

步。（例如你上次抽了

2

，放到了第二堆顶部，现在抽第二堆最后一张发现是

8

，又放到第

8

堆顶部.........）

  1. 在抽牌过程中如果抽到
K

，则称死了一条命，就扔掉

K

再从第

1

步开始。

  1. 当发现四条命都死了以后，统计现在每堆牌上边正面朝上的牌的数目，只要同一数字的牌出现
4

张正面朝上的牌(比如

4

个

A

)，则称“开了一对”，当然

4

个

K

是不算的。

  1. 统计一共开了多少对，开了
0

对称作”极凶”，

1∼2

对为“大凶”，

3

对为“凶”，

4∼5

对为“小凶”，

6

对为“中庸”，

7∼8

对“小吉”，

9

对为“吉”，

10∼11

为“大吉”，

12

为“满堂开花，极吉”。

输入格式

一共输入

13

行数据，每行四个数字或字母，表示每堆牌的具体牌型(不区分花色只区分数字)，每堆输入的顺序为从上到下。

为了便于读入，用

0

代表

10

。

同行数字用空格隔开。

输出格式

输出一个整数，代表统计得到的开出的总对数。

输入样例：

8 5 A A
K 5 3 2
9 6 0 6
3 4 3 4
3 4 4 5
5 6 7 6
8 7 7 7
9 9 8 8
9 0 0 0
K J J J
Q A Q K
J Q 2 2
A K Q 2

输出样例：

9

解析

模拟题，我是用双端队列来模拟的

void dfs(int t)
{
    if (!t) return;
    cnt[t] ++ ;
    int ne = cards[t].back(); cards[t].pop_back();
    dfs(ne);
}

分形

题目描述

分形，具有以非整数维形式充填空间的形态特征。

通常被定义为“一个粗糙或零碎的几何形状，可以分成数个部分，且每一部分都（至少近似地）是整体缩小后的形状”，即具有自相似的性质。

现在，定义“盒子分形”如下：

一级盒子分形：

X

二级盒子分形：

X X
 X
X X

如果用

B(n−1)

代表第

n−1

级盒子分形，那么第

n

级盒子分形即为：

B(n - 1)        B(n - 1)

        B(n - 1)

B(n - 1)        B(n - 1)

你的任务是绘制一个

n

级的盒子分形。

输入格式

输入包含几个测试用例。

输入的每一行包含一个不大于

7

的正整数

n

，代表要输出的盒子分形的等级。

输入的最后一行为

−1

，代表输入结束。

输出格式

对于每个测试用例，使用 X 符号输出对应等级的盒子分形。

请注意 X 是一个大写字母。

每个测试用例后输出一个独立一行的短划线。

输入样例：

1
2
3
4
-1

输出样例：

X
-
X X
 X
X X
-
X X   X X
 X     X
X X   X X
   X X
    X
   X X
X X   X X
 X     X
X X   X X
-
X X   X X         X X   X X
 X     X           X     X
X X   X X         X X   X X
   X X               X X
    X                 X
   X X               X X
X X   X X         X X   X X
 X     X           X     X
X X   X X         X X   X X
         X X   X X
          X     X
         X X   X X
            X X
             X
            X X
         X X   X X
          X     X
         X X   X X
X X   X X         X X   X X
 X     X           X     X
X X   X X         X X   X X
   X X               X X
    X                 X
   X X               X X
X X   X X         X X   X X
 X     X           X     X
X X   X X         X X   X X
-

解析

分形图

假设当前绘制第

n

级分形图，则边长为

3^{n-1}

，设当前分形图左上角坐标为

(x,y)

则

n-1

级分形图的五个坐标应为：

\begin{cases} (x,y)\\ (x+2 \cdot 3^{n-2}, y)\\ (x+3^{n-2},y+3^{n-2}) \\ (x,y+2 \cdot 3^{n-2})\\ (x+2 \cdot 3^{n-2},y+2 \cdot 3^{n-2}) \end{cases}

然后递归处理即可，属于入门分形图难度

void dfs(int x, int y, int k)
{
    if (k == 1)
    {
        g[x][y] = 'X';
        return;
    }
    k /= 3;
    dfs(x, y, k);
    dfs(x, y + 2 * k, k);
    dfs(x + k, y + k, k);
    dfs(x + 2 * k, y, k);
    dfs(x + 2 * k, y + 2 * k, k);
}

袭击

题目描述

在与联盟的战斗中屡战屡败后，帝国撤退到了最后一个据点。

依靠其强大的防御系统，帝国击退了联盟的六波猛烈进攻。

经过几天的苦思冥想，联盟将军亚瑟终于注意到帝国防御系统唯一的弱点就是能源供应。

该系统由

N

个核电站供应能源，其中任何一个被摧毁都会使防御系统失效。

将军派出了

N

个特工进入据点之中，打算对能源站展开一次突袭。

不幸的是，由于受到了帝国空军的袭击，他们未能降落在预期位置。

作为一名经验丰富的将军，亚瑟很快意识到他需要重新安排突袭计划。

他现在最想知道的事情就是哪个特工距离其中任意一个发电站的距离最短。

你能帮他算出来这最短的距离是多少吗？

输入格式

输入中包含多组测试用例。

第一行输入整数

T

，代表测试用例的数量。

对于每个测试用例，第一行输入整数

N

。

接下来

N

行，每行输入两个整数

X

和

Y

，代表每个核电站的位置的

X

，

Y

坐标。

在接下来

N

行，每行输入两个整数

X

和

Y

，代表每名特工的位置的

X

，

Y

坐标。

输出格式

每个测试用例，输出一个最短距离值，结果保留三位小数。

每个输出结果占一行。

数据范围

1≤N≤10^5

,

0≤X,Y≤10^9

输入样例：

2
4
0 0
0 1
1 0
1 1
2 2
2 3
3 2
3 3
4
0 0
0 0
0 0
0 0
0 0
0 0
0 0
0 0

输出样例：

1.414
0.000

解析

平面最近点对，这是一个 K-D Tree 的裸题，也称为“邻域查询”问题，我们采用分治思想来求解

本质和 K-D Tree 解法没有区别，都是根据坐标对点进行分类，然后分治

本题真正难点在于邻域查询后的合并，理解这个合并可以为日后学 K-D Tree 打好基础，让我们开始

首先，我们先将所有点按照横坐标递增排序，然后采用分治的思路

每次将一个区间

[l, r]

分成

[l, mid]

和

[mid + 1, r]

两个区间，其中

mid = \lfloor\dfrac{l + r}{2}\rfloor

那么多有的点对可以简单分为三类：

  1. 两个点都在区间
[l, mid]

里

  1. 两个点都在区间
[mid + 1, r]

里

  1. 一个点在区间
[l, mid]

里，一个点在区间

[mid + 1, r]

里

对于第一类点对和第二类的点对，我们递归下去处理即可，现讨论如何统计第三类点对

先递归处理左右两个子区间，统计好第一、第二类点对的平面最近距离，递归处理好后设该距离为

\delta

于是，第三类点对可以分为：点对距离大于

\delta

和点对距离小于

\delta

的两类

显然距离大于

\delta

的点对对答案的贡献为

0

，我们只需去关心距离小于

\delta

的点对

而距离小于

\delta

的点对的任意点一定位于区间

[x_{mid} - \delta, x_{mid} + \delta]

，否则点对距离必定大于

\delta

PNG图像.png

我们枚举一侧的点，然后找出枚举的点

x

配对的最近点对

y

，

y

一定位于以

x

为圆心半径为

\delta

的圆内，不妨把圆放宽成矩形

假设：任意左侧点的矩形范围内，至多只有 6 个点

证明： 我们将矩形长二等分，宽三等分，获得的 6 个子矩阵长为

\dfrac{1}{2}\delta

，宽为

\dfrac{2}{3}\delta

，如下图所示：

PNG图像 2.png

反证法：假设存在 7 个点，根据抽屉原理，则必然存在一个子矩形内有两个点

根据子矩阵的长宽，易推得子矩阵内最远的两个点距离为子矩阵的对角线，即

\dfrac{5}{6}\delta

而

\delta

定义是邻域内部的最近点对最小距离，如果存在第 7 个点，必然使右侧邻域内存在距离小于

\delta

的点对，与先前的假设矛盾

故得证，对于左侧每个点，至多枚举 6 个右侧的点，便可以遍历出第三类点中的最近点对

设当前点坐标为

(x,y)

，则要枚举的 6 个点的坐标范围为：

x_i \in [x, x+\delta], y_i\in[y-\delta,y+\delta]

考虑如何枚举这些点对，显然暴力枚举的时间复杂度为

O(n^2)

如果按照横坐标来枚举，由于横坐标的跨度为

2\delta

，每次会枚举

[x,x+\delta]

范围内的点，因此点会很密集

很容易导致一层内枚举的时间复杂度变成

O(n^2)

，而纵坐标范围是

[-\infty,+\infty]

，考虑按他来枚举

因此不妨对所有在每次递归回溯之后，将所有点按纵坐标排好序，当然如果直接排序，时间复杂度为

O(n\log^2n)

用到之前在 “天才ACM” 里的技巧，观察发现回溯之后，左右两个子区间都已经排好序了

因此可以直接在原地做一遍 二路归并，这样最终排序的总时间复杂度就只有

O(n\log n)

了

最终的总时间复杂度也为

O(n \log n)
struct Point
{
    double x, y;
    int type;
    bool operator< (const Point& t) const
    {
        return x < t.x;
    }
    bool operator == (const Point& t) const
    {
        return x == t.x && y == t.y && type == t.type;
    }
};

Point points[N], temp[N];

double get_dist(Point a, Point b)
{
    if (a.type == b.type) return INF;
    double dx = a.x - b.x, dy = a.y - b.y;
    return sqrt(dx * dx + dy * dy);
}
double dfs(int l, int r)
{
    if (l >= r) return INF;
    int mid = l + r >> 1;
    double mid_x = points[mid].x;
    double res = min(dfs(l, mid), dfs(mid + 1, r));
    
    // 按照纵坐标进行归并
    {
        int k = 0, i = l, j = mid + 1;
        while (i <= mid && j <= r)
            if (points[i].y < points[j].y) temp[k ++ ] = points[i ++ ];
            else temp[k ++ ] = points[j ++ ];
        while (i <= mid) temp[k ++ ] = points[i ++ ];
        while (j <= r) temp[k ++ ] = points[j ++ ];
        for (int i = 0; i < k; i ++ ) points[i + l] = temp[i];
    }
    
    // 取出 [x_mid - delta, x_mid + delta] 区间内的点
    int k = 0;
    for (int i = l; i <= r; i ++ )
        if (mid_x - res <= points[i].x && points[i].x <= mid_x + res)
            temp[k ++ ] = points[i];
    
    for (int i = 0; i < k; i ++ )
        for (int j = i - 1; ~j && temp[i].y - temp[j].y <= res; j -- )
            res = min(res, get_dist(temp[i], temp[j]));
            
    return res;
}
void solve()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
    {
        scanf("%lf%lf", &points[i].x, &points[i].y);
        points[i].type = 0;
    }
    for (int i = n; i < 2 * n; i ++ )
    {
        scanf("%lf%lf", &points[i].x, &points[i].y);
        points[i].type = 1;
    }
    sort(points, points + 2 * n);
    n = unique(points, points + 2 * n) - points;
    printf("%.3lf\n", dfs(0, n));
}

防线

题目描述

达达学习数学竞赛的时候受尽了同仁们的鄙视，终于有一天......受尽屈辱的达达黑化成为了黑暗英雄怪兽达达。

就如同中二漫画的情节一样，怪兽达达打算毁掉这个世界。

数学竞赛界的精英 lqr 打算阻止怪兽达达的阴谋，于是她集合了一支由数学竞赛选手组成的超级行动队。

由于队员们个个都智商超群，很快，行动队便来到了怪兽达达的黑暗城堡的下方。

但是，同样强大的怪兽达达在城堡周围布置了一条“不可越过”的坚固防线。

防线由很多防具组成，这些防具分成了

N

组。

我们可以认为防线是一维的，那么每一组防具都分布在防线的某一段上，并且同一组防具是等距离排列的。

也就是说，我们可以用三个整数

S

，

E

和

D

来描述一组防具，即这一组防具布置在防线的

S，S+D，S+2D，…，S+KD(K∈Z，S+KD≤E，S+(K+1)D>E)

位置上。

黑化的怪兽达达设计的防线极其精良。

如果防线的某个位置有偶数个防具，那么这个位置就是毫无破绽的(包括这个位置一个防具也没有的情况，因为

0

也是偶数)。

只有有奇数个防具的位置有破绽，但是整条防线上也最多只有一个位置有奇数个防具。

作为行动队的队长，lqr 要找到防线的破绽以策划下一步的行动。

但是，由于防具的数量太多，她实在是不能看出哪里有破绽。

作为 lqr 可以信任的学弟学妹们，你们要帮助她解决这个问题。

输入格式

输入文件的第一行是一个整数

T

，表示有

T

组互相独立的测试数据。

每组数据的第一行是一个整数

N

。

之后

N

行，每行三个整数

Si，Ei，Di

，代表第

i

组防具的三个参数，数据用空格隔开。

输出格式

对于每组测试数据，如果防线没有破绽，即所有的位置都有偶数个防具，输出一行 There's no weakness.。

否则在一行内输出两个空格分隔的整数

P

和

C

，表示在位置

P

有

C

个防具。当然

C

应该是一个奇数。

数据范围

防具总数不多于

10^8

,

Si≤Ei

,

1≤T≤5

,

N≤200000

,

0≤Si，Ei，Di≤2^{31}−1

输入样例：

3
2
1 10 1
2 10 1
2
1 10 1 
1 10 1 
4
1 10 1 
4 4 1 
1 5 1 
6 10 1

输出样例：

1 1
There's no weakness.
4 3

解析

题目中保证了 "整条防线上最多只有一个位置有奇数个防具"

因此很容易想到前缀和的性质：

  1. 若前缀中有偶数个奇数，则前缀和为偶数；
  2. 若前缀中有奇数个奇数，则前缀和为奇数；

因此，若我们用前缀和来维护前缀里的防具的数量，那么显然答案具有单调性质

即，由于数组中至多只有一个奇数，则必然前缀和在答案位置之前为偶数，之后为奇数

在二分答案位置的时候，考虑如何统计前缀和，这是一个难题

由于答案范围是

[1, 2^{31}-1]

，且最坏情况下，每个位置都会有数字，因此不能直接统计，也不能离散化

但是每个防具放置的位置是一个等差数列递推公式

因此我们可以直接遍历所有的防具，利用等差数列公式，反向统计出当前防具在二分的

limit

前缀中是第几项之后的数

int calc(int limit)
{
    int res = 0;
    for (int i = 0; i < n; i ++ )
        if (limit >= s[i])
            res += (min(limit, e[i]) - s[i]) / d[i] + 1;
    return res;
}
void solve()
{
    cin >> n;
    for (int i = 0; i < n; i ++ ) cin >> s[i] >> e[i] >> d[i];
    int l = 1, r = (1 << 31) - 1;
    while (l < r)
    {
        int mid = ((long long)l + r) >> 1;
        if (calc(mid) & 1) r = mid; else l = mid + 1;
    }
    if (calc(l) & 1 ^ 1) puts("There's no weakness.");
    else cout << l << " " << calc(l) - calc(l - 1) << endl;
}

赶牛入圈

题目描述

农夫约翰希望为他的奶牛们建立一个畜栏。

这些挑剔的畜生要求畜栏必须是正方形的，而且至少要包含

C

单位的三叶草，来当做它们的下午茶。

畜栏的边缘必须与

X，Y

轴平行。

约翰的土地里一共包含

N

单位的三叶草，每单位三叶草位于一个

1×1

的土地区域内，区域位置由其左下角坐标表示，并且区域左下角的

X,Y

坐标都为整数，范围在

1

到

10000

以内。

多个单位的三叶草可能会位于同一个

1×1

的区域内，因为这个原因，在接下来的输入中，同一个区域坐标可能出现多次。

只有一个区域完全位于修好的畜栏之中，才认为这个区域内的三叶草在畜栏之中。

请你帮约翰计算一下，能包含至少

C

单位面积三叶草的情况下，畜栏的最小边长是多少。

输入格式

第一行输入两个整数

C

和

N

。

接下来

N

行，每行输入两个整数

X

和

Y

，代表三叶草所在的区域的

X,Y

坐标。

同一行数据用空格隔开。

输出格式

输出一个整数，代表畜栏的最小边长。

数据范围

1≤C≤500

,

C≤N≤500

输入样例：

3 4
1 2
2 1
4 1
5 2

输出样例：

4

解析

二维离散化 + 二维前缀和

bool valid(int len)
{
    for (int x1 = 0, x2 = 1; x2 < xs.size(); x2 ++ )
    {
        while (xs[x2] - xs[x1 + 1] + 1 > len) x1 ++ ;
        for (int y1 = 0, y2 = 1; y2 < xs.size(); y2 ++ )
        {
            while (xs[y2] - xs[y1 + 1] + 1 > len) y1 ++ ;
            if (s[x2][y2] - s[x1][y2] - s[x2][y1] + s[x1][y1] >= m)
                return true;
        }
    }
    return false;
}
int main()
{
    for (int i = 0; i < n; i ++ )
    {
        int x, y;
        cin >> x >> y;
        xs.push_back(x);
        xs.push_back(y);
        temp[i] = {x, y};
    }
    discrete();
    for (int i = 0; i < n; i ++ )
    {
        int x = get(temp[i].x), y = get(temp[i].y);
        s[x][y] ++ ;
    }
    for (int i = 1; i < xs.size(); i ++ )
        for (int j = 1; j < xs.size(); j ++ )
            s[i][j] += s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1];
    
    int l = 1, r = 10000;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (valid(mid)) r = mid; else l = mid + 1;
    }
}

糖果传递

题目描述

有

n

个小朋友坐成一圈，每人有

a[i]

个糖果。

每人只能给左右两人传递糖果。

每人每次传递一个糖果代价为

1

。

求使所有人获得均等糖果的最小代价。

输入格式

第一行输入一个正整数

n

，表示小朋友的个数。

接下来

n

行，每行一个整数

a[i]

，表示第

i

个小朋友初始得到的糖果的颗数。

输出格式

输出一个整数，表示最小代价。

数据范围

1≤n≤1000000

,

0≤a[i]≤2×109

,

数据保证一定有解。

输入样例：

4
1
2
5
4

输出样例：

4

解析

详情见 0x05排序 章节的 “环形均分纸牌” 问题

long long calc(int c[], int n)
{
    int avg = t / n;
    for (int i = 1; i <= n; i ++ ) a[i] = c[i] - avg;
    for (int i = 1; i <= n; i ++ ) s[i] = s[i - 1] + a[i];
    sort(s + 1, s + n + 1);
    long long res = 0;
    for (int i = 1; i <= n; i ++ ) res += abs(s[i] - s[(n + 1) / 2]);
    return res;
}

士兵

题目描述

格格兰郡的

N

名士兵随机散落在全郡各地。

格格兰郡中的位置由一对

(x,y)

整数坐标表示。

士兵可以进行移动，每次移动，一名士兵可以向上，向下，向左或向右移动一个单位（因此，他的

x

或

y

坐标也将加

1

或减

1

）。

现在希望通过移动士兵，使得所有士兵彼此相邻的处于同一条水平线内，即所有士兵的

y

坐标相同并且

x

坐标相邻。

请你计算满足要求的情况下，所有士兵的总移动次数最少是多少。

需注意，两个或多个士兵不能占据同一个位置。

输入格式

第一行输入整数

N

，代表士兵的数量。

接下来的

N

行，每行输入两个整数

x

和

y

，分别代表一个士兵所在位置的

x

坐标和

y

坐标，第

i

行即为第

i

个士兵的坐标

(x[i],y[i])

。

输出格式

输出一个整数，代表所有士兵的总移动次数的最小值。

数据范围

1≤N≤10000

,

−10000≤x[i],y[i]≤10000

输入样例：

5
1 2
2 2
1 3
3 -2
3 3

输出样例：

8

解析

这题比较简单，简单讲一下我分析的过程，因为士兵每次只能向四相邻格子移动

因此当前士兵抵达他在最优解中的位置所走的路程，就是当前坐标与最终坐标的曼哈顿距离

因此我们可以先处理所有点的横坐标移动，使其都在一条轴线上，再处理纵坐标移动，使其相邻

考虑第一步，是让所有点都移动到同一个坐标，反向思考，就是找一个点到所有点距离最短

自然联想到 “货仓选址” 这题，直接找纵坐标中位数即可

考虑第二步，是让所有点都移动到相邻位置，也是一个找中位数的过程，证明如下：

先将点按

x_i

递增排序，设第一个点

x_1

移动到的最终位置为

k

，则可以列出如下式子：

[ |x_1 - k| + |x_2 - k - 1| + |x_3 - k - 2| + \cdots + |x_n - k - n + 1| ]

不妨设

y_i = x_i - i + 1

，则原式可化为：

[ |y_1 - k| + |y_2 - k| + \cdots + |y_n - k| ]

就变成 “货仓选址” 原题了，这一题是某一场 cf 的 t5，还是比较送分的一道题目

int calc(int a[])
{
    int res = 0;
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; i ++ ) res += abs(a[i] - a[n + 1 >> 1]);
    return res;
}
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> x[i] >> y[i];
    sort(x + 1, x + n + 1);
    for (int i = 1; i <= n; i ++ ) x[i] = x[i] - i + 1;
    cout << calc(x) + calc(y) << endl;
    return 0;
}

数的进制转换

题目描述

编写一个程序，可以实现将一个数字由一个进制转换为另一个进制。

这里有

62

个不同数位

{0−9,A−Z,a−z}

。

输入格式

第一行输入一个整数，代表接下来的行数。

接下来每一行都包含三个数字，首先是输入进制（十进制表示），然后是输出进制（十进制表示），最后是用输入进制表示的输入数字，数字之间用空格隔开。

输入进制和输出进制都在

2

到

62

的范围之内。

（在十进制下）

A=10，B=11，…，Z=35，a=36，b=37，…，z=61

(

0−9

仍然表示

0−9

)。

输出格式

对于每一组进制转换，程序的输出都由三行构成。

第一行包含两个数字，首先是输入进制（十进制表示），然后是用输入进制表示的输入数字。

第二行包含两个数字，首先是输出进制（十进制表示），然后是用输出进制表示的输入数字。

第三行为空白行。

同一行内数字用空格隔开。

输入样例：

8
62 2 abcdefghiz
10 16 1234567890123456789012345678901234567890
16 35 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2
35 23 333YMHOUE8JPLT7OX6K9FYCQ8A
23 49 946B9AA02MI37E3D3MMJ4G7BL2F05
49 61 1VbDkSIMJL3JjRgAdlUfcaWj
61 5 dl9MDSWqwHjDnToKcsWE1S
5 10 42104444441001414401221302402201233340311104212022133030

输出样例：

62 abcdefghiz
2 11011100000100010111110010010110011111001001100011010010001

10 1234567890123456789012345678901234567890
16 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2

16 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2
35 333YMHOUE8JPLT7OX6K9FYCQ8A

35 333YMHOUE8JPLT7OX6K9FYCQ8A
23 946B9AA02MI37E3D3MMJ4G7BL2F05

23 946B9AA02MI37E3D3MMJ4G7BL2F05
49 1VbDkSIMJL3JjRgAdlUfcaWj

49 1VbDkSIMJL3JjRgAdlUfcaWj
61 dl9MDSWqwHjDnToKcsWE1S

61 dl9MDSWqwHjDnToKcsWE1S
5 42104444441001414401221302402201233340311104212022133030

5 42104444441001414401221302402201233340311104212022133030
10 1234567890123456789012345678901234567890

解析

进制转换，用短除法，然后倒叙输出余数

需要上高精度，这题是清华某一年的机试原题

int div(vector<int> &a, int b)
{
    int r = 0;
    for (int i = a.size() - 1; ~i; i -- )
    {
        r = r * n + a[i];
        a[i] = r / b;
        r %= b;
    }
    while (a.size() && a.back() == 0) a.pop_back();
    return r;
}
void solve()
{
    string line, res;
    vector<int> num;
    cin >> n >> m >> line;
    cout << n << " " << line << endl << m << " ";
    for (int i = line.size() - 1; ~i; i -- ) num.push_back(get(line[i]));
    
    while (num.size()) res.push_back(put(div(num, m)));
    
    reverse(res.begin(), res.end());
    cout << res << endl;
}

耍杂技的牛

题目描述

农民约翰的

N

头奶牛（编号为

1..N

）计划逃跑并加入马戏团，为此它们决定练习表演杂技。

奶牛们不是非常有创意，只提出了一个杂技表演：

叠罗汉，表演时，奶牛们站在彼此的身上，形成一个高高的垂直堆叠。

奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。

这

N

头奶牛中的每一头都有着自己的重量

W_i

以及自己的强壮程度

S_i

。

一头牛支撑不住的可能性取决于它头上所有牛的总重量（不包括它自己）减去它的身体强壮程度的值，现在称该数值为风险值，风险值越大，这只牛撑不住的可能性越高。

您的任务是确定奶牛的排序，使得所有奶牛的风险值中的最大值尽可能的小。

输入格式

第一行输入整数

N

，表示奶牛数量。

接下来

N

行，每行输入两个整数，表示牛的重量和强壮程度，第

i

行表示第

i

头牛的重量

W_i

以及它的强壮程度

S_i

。

输出格式

输出一个整数，表示最大风险值的最小可能值。

数据范围

1≤N≤50000

,

1≤W_i≤10,000

,

1≤S_i≤1,000,000,000

输入样例：

3
10 3
2 5
3 3

输出样例：

2

解析

次序影响答案，显然是一道贪心的排序题，我们试着用微扰法找出贪心策略

原先相邻两项的风险值分别为：

t_i = \sum\limits_{j=1}^{i-1} w_j - s_i

和

t_{i+1} = \sum\limits_{j=1}^{i-1} w_j + w_i - s_{i+1}

交换两项后，风险值分别为：

t_i = \sum\limits_{j=1}^{i-1} w_j - s_{i+1}

和

t_{i+1} = \sum\limits_{j=1}^{i-1} w_j + w_{i+1} - s_{i}

对交换前后的最大风险值做差，可得：

\max(s_{i+1}, w_i+s_{i}) - \max(s_{i}, w_{i+1}+s_{i+1})

我们希望该式子可以小于等于 0，这样交换前效果更好，才符合我们的预期，因此开始分类讨论

若

s_{i+1} < w_i+s_{i}

且

s_{i} < w_{i+1}+s_{i+1}

，则原式为

s_i + w_i < w_{i+1} + s_{i+1}

不与条件矛盾

若

s_{i+1} < w_i+s_{i}

且

s_{i} \ge w_{i+1}+s_{i+1}

，则原式为

w_i < 0

矛盾

若

s_{i+1} \ge w_i+s_{i}

且

s_{i} < w_{i+1}+s_{i+1}

，则原式为

0 < w_{i+1}

不与条件矛盾

若

s_{i+1} \ge w_i+s_{i}

且

s_{i} \ge w_{i+1}+s_{i+1}

，则原式为

s_{i+1} < s_i

矛盾

综上易得当条件

s_i + w_i \le w_{i+1} + s_{i+1}

成立时，交换前效果更好

这也就是我们的排序规则，每次减少一个逆序对，都会使答案变好，因此启发式策略成立

struct Cow
{
    int w, s;
    bool operator< (const Cow& t) const
    {
        return s + w < t.w + t.s;
    }
}cows[N];
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ ) cin >> cows[i].w >> cows[i].s;
    sort(cows + 1, cows + n + 1);
    int prefix_w = 0, res = -INF;
    for (int i = 1; i <= n; i ++ )
    {
        res = max(res, prefix_w - cows[i].s);
        prefix_w += cows[i].w;
    }
    cout << res << endl;
    return 0;
}

最大的和

题目描述

给定一个包含整数的二维矩阵，子矩形是位于整个阵列内的任何大小为

1×1

或更大的连续子阵列。

矩形的总和是该矩形中所有元素的总和。

在这个问题中，具有最大和的子矩形被称为最大子矩形。

例如，下列数组：

0 -2 -7 0 
9 2 -6 2 
-4 1 -4 1 
-1 8 0 -2

其最大子矩形为：

9 2 
-4 1 
-1 8

它拥有最大和

15

。

输入格式

输入中将包含一个

N×N

的整数数组。

第一行只输入一个整数

N

，表示方形二维数组的大小。

从第二行开始，输入由空格和换行符隔开的

N^2

个整数，它们即为二维数组中的

N^2

个元素，输入顺序从二维数组的第一行开始向下逐行输入，同一行数据从左向右逐个输入。

数组中的数字会保持在

[−127,127]

的范围内。

输出格式

输出一个整数，代表最大子矩形的总和。

数据范围

1≤N≤100

输入样例：

4
0 -2 -7 0
9 2 -6 2
-4 1 -4  1
-1 8  0 -2

输出样例：

15

解析

一维问题叫“最大连续区间和”，用的递推做的

本题是上面这个问题的二维衍生问题，“最大子矩阵和”，做法是在一维递推基础上的拓展

首先，朴素做法是直接枚举所有的子区间，时间复杂度为

O(n^4)

为了实现递推，首先需要划分阶段，考虑该问题在一维情况下得到了递推，思考能否把二维压缩成一维

我们考虑对每一列求一个前缀和，这样就可以在

O(1)

的时间内求出区间

[a_{i, y}, a_{j, y}]

元素总和

那么我们只需枚举二维，然后用

O(1)

时间递推第三维即可，时间复杂度为

O(n^3)

具体思路就是：每次枚举宽度

[x1, x2]

，然后将这个二维子矩阵压缩成一维数组，其中

b_i = \sum\limits_{j=x_1}^{x_2}a_{j,i}

递推：

f_{x_1,x_2,j} = max(0, f_{x_1,x_2,j - 1}) + b_i
for (int x1 = 0; x1 <= n; x1 ++ )
{
    for (int x2 = x1 + 1; x2 <= n; x2 ++ )
    {
        int val = 0;
        for (int y = 1; y <= n; y ++ )
        {
            val = max(val, 0) + s[x2][y] - s[x1][y];
            res = max(res, val);
        }
    }
}

任务

题目描述

今天某公司有

M

个任务需要完成。

每个任务都有相应的难度级别和完成任务所需时间。

第

i

个任务的难度级别为

y_i

，完成任务所需时间为

x_i

分钟。

如果公司完成此任务，他们将获得

（500×x_i+2×y_i）

美元收入。

该公司有

N

台机器，每台机器都有最长工作时间和级别。

如果任务所需时间超过机器的最长工作时间，则机器无法完成此任务。

如果任务难度级别超过机器的级别，则机器无法完成次任务。

每台机器一天内只能完成一项任务。

每个任务只能由一台机器完成。

请为他们设计一个任务分配方案，使得该公司能够最大化他们今天可以完成的任务数量。

如果有多种解决方案，他们希望选取赚取利润最高的那种。

输入格式

输入包含几个测试用例。

对于每个测试用例，第一行包含两个整数

N

和

M

，分别代表机器数量和任务数量。

接下来

N

行，每行包含两个整数

x_i,y_i

，分别代表机器最长工作时间和机器级别。

再接下来

M

行，每行包含两个整数

x_i,y_i

，分别代表完成任务所需时间和任务难度级别。

输出格式

对于每个测试用例，输出两个整数，代表公司今天可以完成的最大任务数以及他们将获得的收入。

数据范围

1≤N,M≤100000

,

0<x_i<1440

,

0≤y_i≤100

输入样例：

1 2
100 3
100 2
100 1

输出样例：

1 50004

解析

观察到

x

一个单位的影响大于最大差值下

y

的影响： △x × 500 > △y × 2，其中

\Delta x \in (1, 1440), \Delta y \in [0, 100]

因此，我们可以把

x

看做第一关键字，

y

看做第二关键字

原题就相当于求一个二分图的最大匹配，且点权关键字值最大

一般情况下，二分图的最大匹配，边权最大用 KM 算法，点权最大用 匈牙利 算法

然而本题二分图基本上类似于是完全图，用匈牙利算法的时间复杂度为

O(nm)=O(n^3)

因此我们要用贪心的思路，按双关键字排序从大到小枚举所有的任务，对于任务

i

设双关键字要求为

(x_i,y_i)

我们找到所有第一关键字大于等于

x_i

，且第二关键字大于

y_i

的机器中

y_i

最小的与其匹配

本题就是 “防晒” 这题的二维版本，证明上述启发式策略也与该题基本一致，用找增广路径的思路即可 

long long res = 0;
int cnt = 0;
sort(mach + 1, mach + n + 1);
sort(task + 1, task + m + 1);
multiset<int> level;
for (int i = m, j = n; i; i -- )
{
    while (j && mach[j].x >= task[i].x) level.insert(mach[j -- ].y);
    auto it = level.lower_bound(task[i].y);
    if (it != level.end())
    {
        cnt ++ ;
        res += 500 * task[i].x + 2 * task[i].y;
        level.erase(it);
    }
}

相关文章