本文共 3679 字，大约阅读时间需要 12 分钟。

0x01

有一天，小易把1到n的所有排列按字典序排成一排，小易从中选出了一个排列，假设它是正数第Q个排列，小易希望你能回答他倒数第Q个排列是什么。

例如1到3的所有排列是：

1 2 31 3 22 1 32 3 13 1 23 2 1

若小易选出的排列是1 2 3，则Q = 1，而你应该输出排列3 2 1。

输入描述：

第一行数字n，表示排列长度接下来一行n个数字，表示选出的排列1 <= n <= 300000

输出描述：

一行n个数字，表示所求的排列。

示例1：

31 2 3

输出：

3 2 1

示例2：

53 1 5 2 4

输出：

3 5 1 4 2

解题思路

观察样例不难看出倒排结果即为$o_i=n+1-x_i$

n = int(input())data = list(map(int, input().split()))for i in data:    print(n + 1 - i, end=" ")

0x02

小易有一个长度为n的数字数组$a_1,a_2,...a_n$。

问你是否能用这n个数字构成一个环（首尾相连），使得环中的每一个数字都小于它相邻的两个数字的和（每个数字都必须使用并且只能使用一次）。

输入描述：

第一行包含一个整数t(1 <= t <= 10)，表示测试用例的组数。每个测试用例输入如下：第一行一个整数n，表示数字的个数；第二行n个整数a1,a2,...an，每两个整数之间用一个空格分隔。输入数据保证3 <= n <= 10^51 <= ai <= 10^9

输出描述：

输出应该包含t行，对于每组用例，若能则输出"YES"，否则输出"NO"

示例1：

1517 6 17 11 17

输出：

YES

示例2：

131 2 4

输出：

NO

解题思路

我们不难得到下面的式子

• $a_1+a_3>a_2$

我们假设此时的$a_2>a_3$并且$a_2>a_1$，那么此时我们考虑$a_4$放哪个数，由于此时$a_2>a_3$了，所以此时我们$a_4$不论放哪个数都可以满足条件，那么我们放最小的哪个最好啦（贪心）。接着考虑$a_5$放哪个数，还是按照$a_4$的思考，我们应该放一个很小的数，此时我们知道$a_2>a_3>a_4$的，所以我们希望放一个比$a_4$更小的数，但是由于前面已经提到$a_4$是最小的数了（没有比它更小的了），所以我们此时可以将$a_4$变为第二小的数，然后$a_5$变成最小的数。按照这个规律递归下去就可以得到

• $a_2>a_3...>a_n$

此时我们的$a_2$应该是数组中最大的数，我们希望$a_1+a_3>a_2$的话，我们就希望$a_1$尽可能大，我们不妨取$a_2$是第二大的数。也就是数组按照这种规律排列是最优的，我们只需判断这种情况下是不是合法即可。

t = int(input())while t:    n = int(input())    data = list(map(int, input().split()))    data.sort()    data[-1], data[-2] = data[-2], data[-1]    for i in range(n):        pre, pos = (i - 1 + n)%n, (i + 1) % n        if data[i] >= data[pre] + data[cur]:            print("NO")            break    else:        print("YES")    t -= 1

注意此题的一个陷阱，我们不能通过判断最大的三个数得出合法的结论，因为如下情况

0 1 1 1 1

0x03

小易给你一个包含n个数的数组$a_1,a_2,...,a_n$。你可以对这个数组执行任意次以下交换操作：

对数组中的两个下表$i,j(1\le i,j\le n)$，如果$a_i+a_j$为奇数，就可以交换$a_i$和$a_j$。

现在允许你使用操作次数不限，小易希望你能求出在所有能通过若干次操作可以得到的数组中字典序最小的一个是什么。

输入描述：

第一行一个整数n；第二行n个整数a_1,a_2,...,a_n，表示数组，每两个数之间用空格分开输入保证1<=n<=10^5;1<=a_i<=10^9

输出描述：

n个整数，每两个整数之间用一个空格分开，表示得到的字典序最小的数组。

示例1：

4 7 3 5 1

输出：

7 3 5 1

示例2：

1053941 38641 31525 75864 29026 12199 83522 58200 64784 80987

输出：

12199 29026 31525 38641 53941 58200 64784 75864 80987 83522

解题思路

首先我们知道如果数组全是奇数或者全是偶数的话，那么此时$a_i+a_j$必定是偶数，此时我们只要将数组直接输出即可。

如果数组中既包含偶数也包含奇数的话，我们不妨设数组$a_1,a_2,...,a_n$其中$a_1$是奇数，其他都是偶数，那么我们知道数组最小的字典序显然就是数组排好的情况，那么此时的数组能不能达到这种状态呢？显然是可以的，我们可以通过$a_1$去和其他数交换。简单说明一下，假设我们$a_1$和$a_k$交换后，此时$a_1$的位置恰好就是排好序后的位置，那么我们此时可以通过$a_1$和其他任意没有排好序的元素交换，直到最后一个没有排好序的元素$a_j$，此时我们只需要交换$a_1$和$a_j$的元素位置，那么一定就是所有元素都排好序的状态。

那么当存在两个奇数的时候这个规律依旧成立吗？成立，实际上我们可以现将一个奇数排到排好序的位置，然后再考虑另外一个奇数即可（按照前面的思想考虑）。同理我们可以将这个结论推进到$n-1$个奇数的情况。

n = int(input())data = list(map(int, input().split()))odd, even = False, Falsefor i in data:    if i & 1:        odd = True    else:        even = Trueif not odd or not even:    print(data)else:    print(sorted(data))

0x04

给定01序列S，序列S是优秀的01序列，优秀的01序列定义如下：

• 如果序列S、T是优秀的，则序列S+T也是有序的，+被定义为按顺序链接两个序列。例如，“010”+“110”=“010110”。

• 如果序列S是优秀的，则序列rev(S)也是优秀的。rev(S)被定义为按位反转（0变1,1变0）序列S，并删除前面的0。例如，rev(“1100101”)=“11010”。

现在请你判断序列T是不是优秀的

输入描述：

第一行一个整数T，表示输入T组数据。每组数组的第一行是一个01序列，表示序列S。第二行是另一个01序列，表示序列T。1<=|S|,|T|<=1000，S,T不含前导零

输出描述：

对于每组数据，一行输出"YES"或者"NO",表示序列T是不是优秀的。

示例1：

11100110011

输出：

YES

示例2：

11000100001111

输出：

NO

解题思路

首先我们知道S是优秀的，那么我们需要通过S的一些操作看能不能得到T即可。

暂时没有想到什么简洁的思路，以后再写QAQ

如有问题，希望大家指出！！！

转载地址：https://coordinate.blog.csdn.net/article/details/98514359 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！