奇数码问题

奇数码问题你一定玩过八数码游戏，它实际上是在一个 $3×3$ 的网格中进行的，$1$ 个空格和 $1∼8$ 这 $8$ 个数字恰好不重不漏地分布在这 $3×3$ 的网格中。 例如： 1235 2 81 3 _4 6 7 在游戏过程中，可以把空格与其上、下、左、右四个方向之一的数字交换（如果存在）。 例如在上例中，空格可与左、上、下面的数字交换，分别变成： 1235 2 8 5 2 _

算法
算法 归并排序 逆序对 有解性判定

超快速排序

超快速排序在这个问题中，您必须分析特定的排序算法—-超快速排序。 该算法通过交换两个相邻的序列元素来处理 $n$ 个不同整数的序列，直到序列按升序排序。 对于输入序列 9 1 0 5 4，超快速排序生成输出 0 1 4 5 9。 您的任务是确定超快速排序需要执行多少交换操作才能对给定的输入序列进行排序。 输入格式输入包括一些测试用例。 每个测试用例的第一行输入整数 $n$，代表该用例中输入序列的长

算法
算法 归并排序 逆序对

动态中位数

动态中位数依次读入一个整数序列，每当已经读入的整数个数为奇数时，输出已读入的整数构成的序列的中位数。 输入格式第一行输入一个整数 $P$，代表后面数据集的个数，接下来若干行输入各个数据集。 每个数据集的第一行首先输入一个代表数据集的编号的整数。 然后输入一个整数 $M$，代表数据集中包含数据的个数，$M$ 一定为奇数，数据之间用空格隔开。 数据集的剩余行由数据集的数据构成，每行包含 $10$ 个数

算法
算法 堆

七夕祭

七夕祭七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。 于是 TYVJ 今年举办了一次线下七夕祭。 Vani 同学今年成功邀请到了 cl 同学陪他来共度七夕，于是他们决定去 TYVJ 七夕祭游玩。 TYVJ 七夕祭和 11 区的夏祭的形式很像。 矩形的祭典会场由 $N$ 排 $M$ 列共计 $N×M$ 个摊点组成。 虽然摊点种类繁多，不过 cl 只对其中的一部分摊点感兴趣，比如章鱼烧、苹果糖、棉

算法
算法 前缀和 中位数

货仓选址

货仓选址在一条数轴上有 $N$ 家商店，它们的坐标分别为 $A_1…A_N$。现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。 为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。 输入格式 第一行输入整数$N$。 第二行$N$个整数$A_1…A_N$。 输出格式 输出一个整数，表示距离之和的最小值。 数据范围 $1≤N≤100000$ 输入样例 124

算法
算法 中位数

电影

电影莫斯科正在举办一个大型国际会议，有 $n$ 个来自不同国家的科学家参会。 每个科学家都只懂得一种语言。 为了方便起见，我们把世界上的所有语言用 $1$ 到 $10^9$ 之间的整数编号。 在会议结束后，所有的科学家决定一起去看场电影放松一下。 他们去的电影院里一共有 $m$ 部电影正在上映，每部电影的语音和字幕都采用不同的语言。 对于观影的科学家来说，如果能听懂电影的语音，他就会很开心；如果能

算法
算法 二分 离散化

最佳牛围栏

最佳牛围栏农夫约翰的农场由 $N$ 块田地组成，每块地里都有一定数量的牛，其数量不会少于 $1$ 头，也不会超过 $2000$ 头。 约翰希望用围栏将一部分连续的田地围起来，并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。 围起区域内至少需要包含 $F$ 块地，其中 $F$ 会在输入中给出。 在给定条件下，计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。 输入格式 第一行输

算法
算法 前缀和 二分

最高的牛

最高的牛有 $N$ 头牛站成一行，被编队为 $1、2、3…N$，每头牛的身高都为整数。 当且仅当两头牛中间的牛身高都比它们矮时，两头牛方可看到对方。 现在，我们只知道其中最高的牛是第 $P$ 头，它的身高是 $H$ ，剩余牛的身高未知。 但是，我们还知道这群牛之中存在着 $M$ 对关系，每对关系都指明了某两头牛 $A$ 和 $B$ 可以相互看见。 求每头牛的身高的最大可能值是多少。 输入格式 第一

算法
算法 差分数组

增减序列

增减序列给定一个长度为 $n$ 的数列 $a_1,a_2,…,a_n$，每次可以选择一个区间 $[l,r]$，使下标在这个区间内的数都加一或者都减一。 求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。 输入格式 第一行输入正整数 $n$。 接下来 $n$ 行，每行输入一个整数，第 $i+1$ 行的整数代表 $ai$。 输出格式 第一行输出最

算法
算法 差分数组