# 题目：数列还原

## 输入描述:

`每个输入包含一个测试用例。每个测试用例的第一行包含两个整数 n 和 k（1 <= n <= 100, 0 <= k <= 1000000000），接下来的 1 行，包含 n 个数字表示排列 A，其中等于0的项表示看不清的位置（不超过 10 个）。`

## 输出描述:

`输出一行表示合法的排列数目。`

```5 5
4 0 0 2 0```

`2`

# 解答：

```n,k=[int(each) for each in input().split()]
arrs=[int(each) for each in input().split()]
unused_arr=[i for i in range(1,n+1)]
for i in arrs:
if i in unused_arr:
unused_arr.remove(i)

import itertools
unused_arr_ordered=[]
for i in itertools.permutations(unused_arr):
unused_arr_ordered.append(i)

def getOrderedPairs(arrs):
tmp_c=0
for i in range(n):
for j in range(i,n):
if arrs[i]<arrs[j]:
tmp_c+=1
return tmp_c

count=0
for unused_arr_tmp in unused_arr_ordered:
tmp_arrs=[ele for ele in arrs]
for i in unused_arr_tmp:
tmp_index=tmp_arrs.index(0)
tmp_arrs[tmp_index]=i
if getOrderedPairs(tmp_arrs)==k:
count+=1

print(count)```

```# 获取没有在输入数组中的数组，并且进行全排列，并且每个全排列内的顺序对数
# 给出例子中为：[([1, 3, 5], 3), ([1, 5, 3], 2), ([3, 1, 5], 2), ([3, 5, 1], 1), ([5, 1, 3], 1), ([5, 3, 1], 0)]
def gothrough(result, picked, rest):
if len(rest) == 0:
count = 0
for i in range(len(picked)):
for j in range(i + 1, len(picked)):
if picked[i] < picked[j]:
count += 1
result.append((picked, count))
return
else:
for each in rest:
nextpick = picked + [each]
nextrest = rest - {each}
gothrough(result, nextpick, nextrest)
return

n, kk = [int(each) for each in input().split()]
d = [int(each) for each in input().split()]
# 获取不在d中的数字
loss = list(set([i for i in range(1, n + 1)]) - set(d))
# print(loss)

# 获取d中为0的位置数目
loss_p = []
for i in range(n):
if d[i] == 0:
loss_p.append(i)
# print(loss_p)

# d中原始的顺序对数
settlecount = 0
for i in range(n - 1):
if d[i] != 0:
for j in range(i + 1, n):
if d[i] < d[j]:
settlecount += 1
# print(settlecount)

# 缺失的数字在每个对应位置时的顺序对数
# 给出例子的结果为：{1: [1, 1, 0], 3: [0, 0, 1], 5: [1, 1, 2]}
countonposition = {}
# [[0 for i in range(len(loss_p))] for j in range(len(loss))]
for i in range(len(loss)):
count = 0
k = 0
countonposition[loss[i]] = [0 for _ in range(len(loss_p))]
# 先从前到后
for j in range(n):
if d[j] != 0:
if d[j] < loss[i]:
count += 1
else:
countonposition[loss[i]][k] = count
k += 1
if k == len(loss_p):
break
count = 0
k = len(loss_p) - 1
# 再从后向前遍历
for j in range(n - 1, -1, -1):
if d[j] != 0:
if d[j] > loss[i]:
count += 1
else:
countonposition[loss[i]][k] += count
k -= 1
if k == -1:
break
# print(countonposition)

self_result = []
gothrough(self_result, [], set(loss))
# print(self_result)

possible = 0
for picked, count in self_result:
# print(picked, count)
# 每种全排列本身的顺序对数，加上每个数字在对应位置产生的新的顺序对数
for i in range(len(picked)):
count += countonposition[picked[i]][i]
# 再加上原始d中的顺序对数
count += settlecount
if count == kk:
possible += 1
# print(picked)

print(possible)```

0 条评论

• ### 牛客网 跳石板

小易来到了一条石板路前，每块石板上从1挨着编号为：1、2、3....... 这条石板路要根据特殊的规则才能前进：对于小易当前所在的编号为K的 石板，小易单次只...

• ### 每周一总结（4） 分布式ID 学习笔记

趋势递增：分布式ID用来标识数据的唯一性，往往会被用作主键或者是唯一索引。常用的MySQL InnoDB，使用的索引往往是BTree索引，自增的数据在插入时会有...

• ### 8-18 Android学习ing

getSharedPreferences("1234", Context.MODE_PRIVATE)  之中的名字不能带有后缀名，比如1234.xml

• ### python中的推导式

首先看 for i in range(10):当 i 依次取 range(10) (0,1,2,3,4,5,6,7,8,9)时

• ### Python学习没有捷径，但可以加速，零基础九天你也可以会编程

在小学生都学Python了，你还不知道怎么开始文中介绍了Python的应用广泛，功能强大，提供了Python的在线学习视频和资料等 (收集资料是我们的最爱)。...

• ### python 编程实例 1

#题目：有 1、2、3、4 个数字，能组成多少个互不相同且无重复数字的三位数？都是多

• ### 18.Python中的for...range循环

Python的for循环很灵活，可以实现很多定制的功能。可以使用for循环进行遍历的对象被称为可迭代对象，序列就是一种可迭代对象。 迭代（遍历）特定范围的数值...

• ### python中for in的用法详解

到此这篇关于python中for in的用法详解的文章就介绍到这了,更多相关python for in内容请搜索ZaLou.Cn