第一题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))
全部评论
(18) 回帖