前言

alt

思路讲解

D. 小苯的排列计数

非常好的一道组合数学题

先来看下，如何判定合法性

  1. 该序列必然严格非递增
  2. 最后一个元素必然为1

但仅具备这2个条件还是不够的, 这个需要和计算组合个数一起讲

如何计算解

按序求解，对于序列中的位置i的值v

  1. 如果第一次出现，则该值就是固定唯一
  2. 如果非第一次出现，其剩下的选择为 n - v + 1 - i 种，如果此时 n - v + 1- i <= 0, 即为非法序列

根据乘法原理即可

mod = 998244353

def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    
    # 保证严格非递增, 最后一个元素为1
    for i in range(n):
        if i != 0 and arr[i - 1] < arr[i]:
            return 0
    if arr[-1] != 1:
        return 0
    
    ans = 1
    for i in range(1, n):
        if arr[i - 1] == arr[i]:
            # 候选个数 = n - 下限 - 前排个数
            x = n - arr[i] + 1 - i
            if x <= 0:
                return 0;
            ans = ans * x % mod

    return ans

t = int(input())
for _ in range(t):
    print (solve())

F. 怎么写线性SPJ

感觉有两种思路来求解，也可以通过打表找规律，这题容易就容易在贪心构建刚好是最佳解。

最重要的观察

1. 递推

令S(n)为n个不同数字构建的最长数组，f(n)为n个不同数字构建的数组长度

那么S(n+1)的构造解，一定是

从长度来说，就是

所以从递推构造的角度

n = int(input())

arr = []
i = 1
while len(arr) < n:
    arr = arr + [i] + arr
    i += 1

print (i - 1)
print (*arr[:n], sep=' ')

2. 分治

从题意出发，对于字符串s，必然存在一个某个数字唯一，设其位置为m

那么区间 [0, m - 1], [m + 1, n - 1] 分别为一个独立的子问题，进而

因为g函数是一个严格非递减的函数

要使g(0, n - 1)最小，需要左侧两个区间大小尽量 一致，那么该m点最好是中点

这样就构建了分治的核心理论基石。

n = int(input())

arr = [0] * n

def dfs(s, e, x):
    if s == e:
        arr[s] = x + 1
        return
    if s > e:
        return
    m = s + (e - s) // 2
    arr[m] = x + 1
    dfs(s, m - 1, x + 1)
    dfs(m + 1, e, x + 1)

dfs(0, n - 1, 0)

print (len(set(arr)))
print (*arr, sep=' ')

上述两个时间复杂度皆为 ，第二种更容易想到，第一种更容易写

写在最后