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

当前栏目

《算法竞赛进阶指南》0x05 排序

算法排序指南进阶竞赛

2023-06-13 09:14:15 时间

排序基本概念

程序设计中，常用排序共分为三类：

选择排序、插入排序、冒泡排序
堆排序、归并排序、快速排序
计数排序、基数排序、桶排序

前两类是 基于比较的排序算法

对

的元素排序时，若元素比较大小的时间复杂度为

O(1)

，则

第一类排序算法的时间复杂度为

O(n^2)

第二类排序算法的时间复杂度为

O(n\log n)

基于比较的排序算法 的时间复杂度下界为

O(n\log n)

第三类算法不是直接比较大小，而是对被排序的数值采取按位划分、分类映射等处理方式

其时间复杂度不仅与

有关，还与数值的大小范围

有关

离散化

排序算法的第一个应用时离散化

离散化就是把无穷大集合中的若干个元素映射为有限集合以便于统计的方法

在很多情况下，问题的范围虽然定义在整数集合

\mathbb{Z}

，但是只涉及其中

个有限数值，并且与数值的绝对大小无关（只把这些数值作为代表，或只与它们的相对顺序有关）

此时，我们就可以把整数集合

\mathbb{Z}

中的这

个整数与

1 \sim m

建立映射关系

如果有一个时间、空间复杂度与数值范围

\mathbb{Z}

大小有关，在离散化后，该算法的时间、空间复杂度就降低为与

有关

并且离散化以后，我们仍然保持原数据映射到新数据后相对大小不变

vector<int> xs;
void discrete(vector<int> &a)
{
    sort(a.begin(), a.end());
    a.erase(unique(a.begin(), a.end()), a.end());
}
int query(int x)
{
    return lower_bound(a.begin(), a.end(), x) - a.begin();
}

第k个数

如何求解一个长度为

的序列的第

个数

一个较为简单的做法是直接排序，然后输出从小到大的第

个数，时间复杂度为

O(n \log n)

实际上利用快速排序的思想，可以在

O(n)

的时间即可求出第

个数

快排思想是：每一层递归中，随机选取一个数为基准，把比他小的交换到左边，比他大的交换到右边

然后递归左右两边继续处理，平均情况下的时间复杂度为

O(n \log n)

实际上，每次选取基准值以后，可以统计出小于基准值的数的数量

cnt

如果

k \le cnt

，就去左边寻找第

小数；否则，去右边寻找第

k - cnt

大数

这样递归求解，平均意义下的时间复杂度为

O(n + \frac{n}{2} + \frac{n}{4} + \cdots + 1) = O(2n) = O(n)

int calc(int l, int r, int k)
{
    if (l >= r) return a[l];
    int i = l - 1, j = r + 1, pivot = a[l + r >> 1];
    while (i < j)
    {
        do ++ i; while (a[i] < pivot);
        do -- j; while (a[j] > pivot);
        if (i < j) swap(a[i], a[j]);
    }
    if (j - l + 1 >= k) return calc(l, j, k);
    return calc(j + 1, r, k - (j - l + 1));
}

若要求解第 k 大数，直接调用 calc(l, r, n - k) 找第

n-k

小数即可

逆序对

对于一个序列

，若

i < j

且

a_i > a_j

，则称

a_i

与

a_j

构成逆序对

使用归并排序可以在

O(n\log n)

的时间里求出一个长度为

的序列中逆序对个数

归并排序递归处理好左

[l, mid]

右

[mid + 1, r]

两边序列后，进行合并时，可以求解

(a_i,a_j)

的逆序对个数，其中

i \in [l, mid]

，

j \in [mid + 1, r]

由数学归纳法，读者自证不难，每次合并两个序列，可以求出整个序列中全部的逆序对数量

long long cal_revpair(int a[], int l, int r)
{
    if (l >= r) return 0;
    
    int mid = (l + r) >> 1;
    long long cnt = cal_revpair(a, l, mid) + cal_revpair(a, mid + 1, r);
    
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)
    {
        if (a[i] > a[j]) cnt += mid - i + 1, b[k ++ ] = a[j ++ ];
        else b[k ++ ] = a[i ++ ];
    }
    while (i <= mid) b[k ++ ] = a[i ++ ];
    while (j <= r) b[k ++ ] = a[j ++ ];
    
    for (int i = 0; i < k; i ++ ) a[l + i] = b[i];
    return cnt;
}

求逆序对还可以用树状数组，稍微有点复杂，必要的时候还要先离散化再用树状数组，之后会提及

中位数

有序序列中，中位数具有一些很优美的性质，可以引出一系列与它相关的问题

动态维护序列的中位数也非常值得探讨，在后续例题中会进行具体讲解

习题

电影

题目描述

莫斯科正在举办一个大型国际会议，有

个来自不同国家的科学家参会。

每个科学家都只懂得一种语言。

为了方便起见，我们把世界上的所有语言用

到

10^9

之间的整数编号。

在会议结束后，所有的科学家决定一起去看场电影放松一下。

他们去的电影院里一共有

部电影正在上映，每部电影的语音和字幕都采用不同的语言。

对于观影的科学家来说，如果能听懂电影的语音，他就会很开心；如果能看懂字幕，他就会比较开心；如果全都不懂，他就会不开心。

现在科学家们决定大家看同一场电影。

请你帮忙选择一部电影，可以让观影很开心的人最多。

如果有多部电影满足条件，则在这些电影中挑选观影比较开心的人最多的那一部。

输入格式

第一行输入一个整数

，代表科学家的数量。

第二行输入

个整数

a_1,a_2,…,a_n

，其中

a_i

表示第

个科学家懂得的语言的编号。

第三行输入一个整数

，代表电影的数量。

第四行输入

个整数

b_1,b_2,…,b_m

，其中

b_i

表示第

部电影的语音采用的语言的编号。

第五行输入

个整数

c_1,c_2,…,c_m

，其中

c_i

表示第

部电影的字幕采用的语言的编号。

请注意对于同一部电影来说，

bi≠ci

。

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

输出格式

输出一个整数，代表最终选择的电影的编号。电影编号

1∼m

。

如果答案不唯一，输出任意一个均可。

数据范围

1≤n,m≤2 \times 10^5

1≤ai,bi,ci≤10^9

输入样例：

输出样例：

解析

虽然语言范围在 int 以内，但是这

部电影与

个人最多涉及

2m + n

种语言

不妨将所有有效语言离散化处理，用

0 \sim 2m+n-1

之间的整数代替每种语言

接着用一个数组直接统计会每种语言的人的数量，从而选择满足题意的电影

时间复杂度：

O((n+m)\log(n+m))

discrete();
for (int i = 1; i <= n;i ++ )
{
    int x = query(a[i]);
    cnt[x] ++ ;
}
int s1 = 0, s2 = 0, res = 1;
for (int i = 1; i <= m; i ++ )
{
    int x1 = query(b[i]), x2 = query(c[i]);
    if (cnt[x1] > s1) s1 = cnt[x1], s2 = cnt[x2], res = i;
    else if (cnt[x1] == s1 && cnt[x2] > s2) s2 = cnt[x2], res = i;
}
cout << res << endl;

货仓选址

题目描述

在一条数轴上有

家商店，它们的坐标分别为

A_1∼A_N

现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品

为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小

输入格式

第一行输入整数

第二行

个整数

A_1∼A_N

输出格式

输出一个整数，表示距离之和的最小值。

数据范围

1≤N≤10^5

0≤A_i≤4\times 10^4

输入样例：

4
6 2 9 1

输出样例：

解析

这里给出蓝书上的证明

将

A_1 \sim A_n

排序，设货仓建在

处，

处左侧的商店有

家，

处右侧的商店有

家

P < Q

，则每把货仓的选址向右移动

单位距离，距离之和就会变小

Q - P

P > Q

，则每把货仓的选址向左移动

单位距离，距离之和就会变小

P - Q

然后再分奇偶讨论：

为奇数时，显然建在

A[(N + 1) / 2]

处最优，此时

P = Q

为偶数时，建在

\big[A[N / 2], A[N / 2 + 1] \big]

之间的任何位置都是最优

对于第二种情况，不妨建在

A[N / 2]

处，这样无论奇偶都可以统一处理成

A[(N + 1) / 2]

了

对于下标从

开始，就是

A[N / 2]

sort(a, a + n);
int s = 0;
for (int i = 0; i < n; i ++ ) s += abs(a[n / 2] - a[i]);
cout << s << endl;

七夕祭

题目描述

七夕节因牛郎织女的传说而被扣上了「情人节」的帽子。

于是 TYVJ 今年举办了一次线下七夕祭。

Vani 同学今年成功邀请到了 cl 同学陪他来共度七夕，于是他们决定去 TYVJ 七夕祭游玩。

TYVJ 七夕祭和 11 区的夏祭的形式很像。

矩形的祭典会场由

排

列共计

N×M

个摊点组成。

虽然摊点种类繁多，不过 cl 只对其中的一部分摊点感兴趣，比如章鱼烧、苹果糖、棉花糖、射的屋……什么的。

Vani 预先联系了七夕祭的负责人 zhq，希望能够通过恰当地布置会场，使得各行中 cl 感兴趣的摊点数一样多，并且各列中 cl 感兴趣的摊点数也一样多。

不过 zhq 告诉 Vani，摊点已经随意布置完毕了，如果想满足 cl 的要求，唯一的调整方式就是交换两个相邻的摊点。

两个摊点相邻，当且仅当他们处在同一行或者同一列的相邻位置上。

由于 zhq 率领的 TYVJ 开发小组成功地扭曲了空间，每一行或每一列的第一个位置和最后一个位置也算作相邻。

现在 Vani 想知道他的两个要求最多能满足多少个。

在此前提下，至少需要交换多少次摊点。

输入格式

第一行包含三个整数

和

，

表示 cl 对多少个摊点感兴趣。

接下来

行，每行两个整数

x,y

，表示 cl 对处在第

行第

列的摊点感兴趣。

输出格式

首先输出一个字符串。

如果能满足 Vani 的全部两个要求，输出 both；

如果通过调整只能使得各行中 cl 感兴趣的摊点数一样多，输出 row；

如果只能使各列中 cl 感兴趣的摊点数一样多，输出 column；

如果均不能满足，输出 impossible。

如果输出的字符串不是 impossible，接下来输出最小交换次数，与字符串之间用一个空格隔开。

数据范围

1≤N,M≤100000

0≤T≤min(N∗M,100000)

1≤x≤N

1≤y≤M

输入样例：

输出样例：

row 1

解析

观察易得：

只做列相邻交换时，不会改变每行的兴趣摊点数；
只做行相邻交换时，不会改变每列的兴趣摊点数；

那不妨把原问题拆分成两个相似的子问题，先后计算列相邻交换和行相邻交换的最小次数，从而求解原问题

思考如何只做列相邻交换，使得每列的兴趣摊点数相等

由于我们只关心每列中，兴趣摊点总数，因此不妨把每列压缩成一个点，兴趣摊点总数表示该点的值

于是该模型就变成，在一个环形图上，每次只能相邻传递一件物品，求传递最小次数使得每个点的物品数相同

这就是经典的：“环形纸牌均分问题”，推导方式有两种，我先给出 蓝书上的推导：

考虑 “纸牌均分问题” 如何解决？

设一共有

个人，每个人初始的纸牌数量为

c_i

，纸牌总数为

显然当

M \nmid T

时，方案不存在，现只考虑方案存在的情况

第 1 个人为了达到平均持有数，需要向第 2 个人传递

c_1 - T / M

数量的牌（正数是给，负数是拿）

第 2 个人为了达到平均持有数，需要向第 3 个人传递

c_2 - T / M + c_1 - T / M

数量的牌

......

第 n-1 个人为了达到平均持有数，需要向第 n 个人传递

\sum_{i=1}^{n-1} c_i - (n-1) \times T / M

数量的牌

此时前 n-1 人都达到了平均数，则第 n 个人必然也达到了平均数

统计易得，最小交换次数为：

[ \sum_{i=1}^{n-1} \Big| { \sum_{j = 1}^i (c_j - \frac{T}{M}) } \Big| ]

不妨设

A_i = c_i - T / M

，于是化简可得：

[ \sum_{i=1}^{n-1} \Big| { \sum_{j=1}^i A_j } \Big| = \sum_{i=1}^{n-1} | { S_i } | \quad\text{其中 } S_i \text{ 为 } A_i \text{ 的前缀和，即 } S_i = \sum_{j=1}^i A_j ]

考虑 “纸牌均分问题” 如何延伸到 “环形纸牌均分问题” ？

环形区间的问题，第一想到的就是 破环成链 了

经过思考发现，一定存在一个最优解方案，环上有相邻的两个人之间没有发生交换

这部分证明如下：如果环上相邻两人全部发生交换，则会出现两种情形：（正数传递为有向边的正向方向） 1. 出现一个环这种方案肯定不是最优解，因为给出去的纸牌经过一圈收回来了，显然浪费了操作次数我们在这个环上断开交易数量最小的一条交换边，并使其他边减少该边的交换数量，必然不会使方案变差 2. 出现一个点到达另一个点有两条路径我们可以断开起点两条出边中

val = cnt \times w

最小的那一套边，并该边权值累加到另一条路径的每一条边上，其结果不会变差（其中

cnt

是起点到终点路径上经过的点数，

是这条边的权重）

一个朴素的做法是直接枚举断点的位置，然后做一遍线性纸牌均分，但是时间复杂度为

O(n^2)

不可取，需要推导

现将这

个人的

A_i

和

S_i

罗列出来

(A_i = \sum\limits_{j=1}^n (c_j - \dfrac{T}{M}), S_i = \sum\limits_{j = 1}^i A_j)

[ \begin{matrix} A_1 & S_1 \\ A_2 & S_2 \\ \cdots & \cdots \\ A_k & S_k \\ A_{k+1} & S_{k+1} \\ \cdots & \cdots \\ A_n & S_n \end{matrix} ]

考虑在第

个人之后断开，则环化成链有：

[ \begin{matrix} A_{k+1} & S_{k+1} - S_k \\ \cdots & \cdots \\ A_n & S_n - S_k \\ A_1 & S_1 + S_n - S_k \\ A_2 & S_2 + S_n - S_k \\ \cdots & \cdots \\ A_k & S_k + S_n - S_k \\ \end{matrix} ]

又易知

S_n = \sum c_j - n \times T / m = 0

，故求得最小步数为：

[ \sum_{i=1}^n |S_i - S_k| \quad\text{其中 } S_i \text{ 为 } A_i \text{ 的前缀和，即 } S_i = \sum_{j=1}^i A_j ]

该绝对值不等式最小值的求解，就同上一题 “货仓选址” 异曲同工了

因此

S_k

的选择，就取

S_i

排序后的中位数即可

第二种推导方式

这种推导方式相较于上一种，思维量小，但对公式的变形要求高，是直接统计每个点

考虑直接在环上求解，环的顺时针方向设为正方向，若边权为正，表示左向右传递；反之则是右向左传递

设

d_i

表示第

个人向第

(i+1)\bmod n

传递的所有纸牌数量

传递完成后的结束是所有人的纸牌数量变成平均数，以此建立方程组有：

[ \begin{cases} avg =& c_1 - d_1 + d_n \\ avg =& c_2 - d_2 + d_1 \\ \cdots \\ avg =& c_{n-1} - d_{n-1} + d_{n-2} \\ avg =& c_{n} - d_{n} + d_{n-1} \end{cases} \qquad \Rightarrow \qquad \begin{cases} d_1 &= c_1 - avg + d_n \\ d_2 &= c_2 - avg + d_1 \\ \cdots \\ d_{n-1} &= c_{n-1} - avg + d_{n-2} \\ d_n &= c_{n} - avg + d_{n-1} \end{cases} ]

观察易得，相邻两个等式之间，有可以代入的项，从上到下用滚动相消法可得：

[ \begin{cases} d_1 =& c_1 - avg + d_n \\ d_2 =& \sum\limits_{i=1}^2 c_i - 2 \times avg + d_n \\ \cdots \\ d_{n-1} =& \sum\limits_{i=1}^{n-1} c_i - (n-1) \times avg + d_n \\ d_n =& \sum\limits_{i=1}^{n} c_i - n \times avg + d_n \end{cases} ]

易得通项：

d_i = \sum\limits_{j=1}^{i} c_j - i \times avg + d_n = d_n + \sum\limits_{j=1}^{i} (c_j - avg) = d_n - \sum\limits_{j=1}^{i} (avg - c_j)

不妨设

A_i = avg - c_i, S_i = \sum\limits_{j = 1}^i A_j

，则通项可以化简为：

d_i = d_n - \sum\limits_{j=1}^{i}A_j

则总共的操作数为：

[ \sum_{i=1}^n d_i = \sum_{i=1}^n |d_n - \sum_{j=1}^i A_j| = \sum_{i=1}^n |d_n - S_i| ]

由 绝对值不等式 易得：

d_n

应取

S_i

排序后的中位数

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;
}

动态中位数

题目描述

依次读入一个整数序列，每当已经读入的整数个数为奇数时，输出已读入的整数构成的序列的中位数。

输入格式

第一行输入一个整数

，代表后面数据集的个数，接下来若干行输入各个数据集。

每个数据集的第一行首先输入一个代表数据集的编号的整数。

然后输入一个整数

，代表数据集中包含数据的个数，

一定为奇数，数据之间用空格隔开。

数据集的剩余行由数据集的数据构成，每行包含

个数据，最后一行数据量可能少于

个，数据之间用空格隔开。

输出格式

对于每个数据集，第一行输出两个整数，分别代表数据集的编号以及输出中位数的个数（应为数据个数加一的二分之一），数据之间用空格隔开。

数据集的剩余行由输出的中位数构成，每行包含

个数据，最后一行数据量可能少于

个，数据之间用空格隔开。

输出中不应该存在空行。

数据范围

1≤P≤1000

1≤M≤99999

, 所有

相加之和不超过

5×10^5

。

输入样例：

3 
1 9 
1 2 3 4 5 6 7 8 9 
2 9 
9 8 7 6 5 4 3 2 1 
3 23 
23 41 13 22 -3 24 -31 -11 -8 -7 
3 5 103 211 -311 -45 -67 -73 -81 -99 
-33 24 56

输出样例：

1 5
1 2 3 4 5
2 5
9 8 7 6 5
3 12
23 23 22 22 13 3 5 5 3 -3 
-7 -3

解析

动态中位数的经典做法的就是 对顶堆

建立两个堆，一个 大根堆，一个 小根堆，依次读入整个序列的过程中，设当前序列长度为

，维护：

序列中从小到大排名为

1 \sim \lfloor M / 2 \rfloor

的整数存储在大根堆中

序列中从小到大排名为

\lfloor M / 2 \rfloor + 1 \sim M

的整数存储在小根堆中

任何时候，如果某一个堆中元素个数过多，打破这一性质，就取出该堆堆顶元素放入另一个堆

这样一来，序列的中位数就是小根堆的堆顶元素

每次插入新数值

时，若

比中位数小，则插入大顶堆；否则插入小顶堆，然后检查并维护上述性质

void adjust(priority_queue<int> &up, priority_queue<int, vector<int>, greater<>> &dw)
{
    if (up.size() > dw.size())
    {
        dw.push(up.top());
        up.pop();
    }
    else if (dw.size() > up.size() + 1)
    {
        up.push(dw.top());
        dw.pop();
    }
}
void solve()
{
    priority_queue<int> up;
    priority_queue<int, vector<int>, greater<int>> dw;
    int cnt = 0;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> t;
        if (up.size() && up.top() > t) up.push(t);
        else dw.push(t);
        
        adjust(up, dw);
        
        if (i & 1)
        {
            cout << dw.top() << " ";
            if ( ++ cnt % 10 == 0) cout << endl;
        }
    }
    if (cnt % 10) cout << endl;
}

超快速排序

题目描述

在这个问题中，您必须分析特定的排序算法----超快速排序。

该算法通过交换两个相邻的序列元素来处理

个不同整数的序列，直到序列按升序排序。

对于输入序列 9 1 0 5 4，超快速排序生成输出 0 1 4 5 9。

您的任务是确定超快速排序需要执行多少交换操作才能对给定的输入序列进行排序。

输入格式

输入包括一些测试用例。

每个测试用例的第一行输入整数

，代表该用例中输入序列的长度。

接下来

行每行输入一个整数

a_i

代表用例中输入序列的具体数据，第

行的数据代表序列中第

个数。

当输入用例中包含的输入序列长度为

时，输入终止，该序列无需处理。

输出格式

对于每个需要处理的输入序列，输出一个整数 op，代表对给定输入序列进行排序所需的最小交换操作数，每个整数占一行。

数据范围

0≤n<500000

, 一个测试点中，所有 n 的和不超过

500000

。

0≤ai≤999999999

输入样例：

输出样例：

6
0

解析

只通过比较和交换相邻两个数值的排序方法，实际上就是冒泡排序

排序过程中，每找到大小颠倒的相邻数值，就把他们交换

每次交换就会使整个序列的逆序对个数减少 1 且排好序后，逆序对个数为 0

于是能得出人尽皆知的结论：序列冒泡排序过程中的交换操作的次数 = 序列中逆序对个数

本题就等价于求逆序对个数，套模板即可

long long cal_revpair(int l, int r)
{
    if (l == r) return 0;
    
    int mid = (l + r) >> 1;
    long long cnt = cal_revpair(l, mid) + cal_revpair(mid + 1, r);
    
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)
    {
        if (a[i] > a[j]) cnt += mid - i + 1, b[k ++ ] = a[j ++ ];
        else b[k ++ ] = a[i ++ ];
    }
    while (i <= mid) b[k ++ ] = a[i ++ ];
    while (j <= r) b[k ++ ] = a[j ++ ];
    
    for (int i = 0; i < k; i ++ ) a[l + i] = b[i];
    return cnt;
}

奇数码问题

题目描述

你一定玩过八数码游戏，它实际上是在一个

3×3

的网格中进行的，

个空格和

1∼8

这

个数字恰好不重不漏地分布在这

3×3

的网格中。

例如：

5 2 8
1 3 _
4 6 7

在游戏过程中，可以把空格与其上、下、左、右四个方向之一的数字交换（如果存在）。

例如在上例中，空格可与左、上、下面的数字交换，分别变成：

5 2 8       5 2 _      5 2 8
1 _ 3       1 3 8      1 3 7
4 6 7       4 6 7      4 6 _

奇数码游戏是它的一个扩展，在一个

n×n

的网格中进行，其中

为奇数，

个空格和

1∼n^2−1

这

n^2−1

个数恰好不重不漏地分布在

n×n

的网格中。

空格移动的规则与八数码游戏相同，实际上，八数码就是一个

n=3

的奇数码游戏。

现在给定两个奇数码游戏的局面，请判断是否存在一种移动空格的方式，使得其中一个局面可以变化到另一个局面。

输入格式

多组数据，对于每组数据：

第

行输入一个整数

，

为奇数。

接下来

行每行

个整数，表示第一个局面。

再接下来

行每行

个整数，表示第二个局面。

局面中每个整数都是

0∼n^2−1

之一，其中用

代表空格，其余数值与奇数码游戏中的意义相同，保证这些整数的分布不重不漏。

输出格式

对于每组数据，若两个局面可达，输出 TAK，否则输出 NIE。

数据范围

1≤n<500

输入样例：

输出样例：

TAK
TAK

解析

n \times m

数码问题的优解性判定，可以转化为归并排序求逆序对来解决

奇数码游戏两个局面可达，当且仅当两个局面下网格中的数依次写成

行

n^2 - 1

个元素序列后，逆序对个数的奇偶性相同

充分性简单证明：奇数码游戏两个局面可达，则它们对应序列的逆序对奇偶性相等

空格 左右移动 时，序列中逆序对个数显然不变
空格 上下移动 时，不妨设区间

(a_{i,j}, a_{i+1,j})

内与

a_{i,j}

构成逆序对的元素个数为

则交换后，减少的逆序对个数为

，增加的逆序对个数为

n - 1 - k

则该边的逆序对个数为

|n - 1 - 2k|

，由于

为奇数，故该值为偶数

必要性证明较为复杂，是一个拓扑学问题，找了一圈，没有一个人解释的明白，自己能力也不够，故略

综上，奇数码的任意操作，都不会改变奇数码元素序列的逆序对个数

因此，如果初始奇数码序列逆序对为偶数，则无论怎么操作，都不能变成奇数对逆序对

偶数码游戏两个局面可达，当且仅当两个网格写成序列后，“逆序对数之差” 和 “两个局面下空格所在的行数之差” 奇偶性相同 事实上，

n \times m

数码问题的有解性判定，根据列数奇偶性也可分为上述两个结论之一

n *= n;
for (int i = 0, t, d = 0; i < n; i ++ )
{
    cin >> t;
    if (t) a[d ++ ] = t;
}
int s1 = cal_revpair(a, 0, n - 2) & 1;
for (int i = 0, t, d = 0; i < n; i ++ )
{
    cin >> t;
    if (t) a[d ++ ] = t;
}
int s2 = cal_revpair(a, 0, n - 2) & 1;
puts(s1 ^ s2 ? "NIE" : "TAK");

猜你喜欢

mt4电脑版安装教程_mt4电脑版安装教程
Python之ruamel.yaml模块详解（二）
字段内容过多，隐藏内容，鼠标移上…详解编程语言
ORA-16261: Identification key mismatch for table “string”.”string”. ORACLE 报错故障修复远程处理
Chrome 78 (谷歌浏览器 ) 进入暗黑模式
Apache配置ssl支持https
AMD锐龙5000G APU核心裸片首曝：180m㎡封装 107亿晶体管
深入理解javaScript中的事件驱动
WordPress美化标签
Oracle有多少库（oracle 几个库）
GC垃圾回收机制详解编程语言
ORA-38852: cannot mark the current instance (redo thread) as disabled ORACLE 报错故障修复远程处理
2054年MySQL突破新边界（2054 mysql）
Excel转Json方法
创建Linux文件夹间软链接ln（linux文件夹ln）
8种常见机器学习算法比较
如何在MySQL中删除序列号（mysql中删除序列号）

zl程序教程

当前栏目

《算法竞赛进阶指南》0x05 排序

排序基本概念

离散化

第k个数

逆序对

中位数

习题

电影

题目描述

解析

货仓选址

题目描述

解析

七夕祭

题目描述

解析

动态中位数

题目描述

解析

超快速排序

题目描述

解析

奇数码问题

题目描述

解析

相关文章