第一题90%

给一个n<=10，按字典序输出1...n，相邻数字绝对值不为1，的排列。

输入：
4
输出：
2 4 1 3
3 1 4 2

递归。n=10的情况卡python语言，没意思。只能90%。（c++貌似能递归100%）。
或许python换个写法也能100%。python这门语言其实挺恶心，一种操作有多种写法，时间复杂度还相差很悬殊

import sys
def f(vst, cur, lv):
    if lv == 0:
        print(' '.join(map(str, cur)))
    for i in range(1, len(vst)):
        if vst[i] or (len(cur) and i in [cur[-1]-1, cur[-1]+1]):
            continue
        vst[i] = 1
        f(vst, cur+[i], lv-1)
        vst[i] = 0
while True:
    iline = sys.stdin.readline()
    if iline == "":
        break
    n = int(iline)
    f([0]*(n+1), [], n) 

第二题100%

第一行两个整数n,m。m<=n<=400000。第二行是长度为n的数组a，a_i<=n。
计算a有多少个区间（子数组）满足：存在某个数字v，使得v在数组区间出现次数大于等于m。

输入：
5 2
1 2 1 2 5
输出：
5
解释：区间[1,3][1,4][1,5][2,4][2,5]，要么1出现2次以上，要么2出现超过2次以上。

线性扫描。计算以i结尾的满足条件的区间数cnt[i]。

根据题意有一个结论：对于以i结尾的区间，若j使得a[j...i]满足条件，则对j'<j，a[j'...i]都满足条件。所以只要找到满足条件最大的j记作pt，cnt[i]就等于pt+1了（不是pt）。

这样问题就转化成循环维护pt值。方法是，对已扫描的每个值v，记录其出现过的位置列表pos。扫描到a[i]时，查看到目前为止倒数第m-1次出现a[i]的位置pre_m（如果存在），且pre_m大于pt，则更新pt为pre_m。

O(N)时间，O(N)空间

import sys
def f(a, m):
    pt = -1
    ans = 0
    pos = [[] for i in range(len(a)+111)]
    for i in range(len(a)):
        v = a[i]
        pos[v].append(i)
        if len(pos[v]) >= m:
            pre_m = pos[v][-m]
            pt = max(pt, pre_m)
        ans += pt+1
    return ans
while True:
    iline = sys.stdin.readline()
    if iline == "":
        break
    n, m = list(map(int, iline.strip().split()))
    a = list(map(int, sys.stdin.readline().strip().split()))
    print(f(a, m))