test

枚举数字a,b和区间$[l,r]$,计算$[l,r]$中a和b的个数$cnt_a$和$cnt_b$,$ans=max(cnt_a−cnt_b)$显然这样是$O(10^2n^2)$的,需要优化。考虑换一种方式,先枚举a,然后同时对所有b做DP,定义$dp[b][i]$表示$[1,i]$的所有子段中,$cnt_a−cnt_b$的最大值,为了确保这当中的a,b数量均大于0,考虑记录两个东西:$dpb[0

- 阅读全文 -

区间异或-区间最值 阿里天池超级码力初赛第2场第2题

题目链接:区间异或题目描述的很糟糕,这里直接举一个例子,对于第$i$个询问 $ask[i] = [l1,r1,l2,r2]$ ,我们要做的就是从$num$数组中得到$getmax(l1,r1)+getmin(l2,r2)$,然后我们将所有的$ask[i]$的结果异或起来,就是答案。例子输入: num = [1,2,3,4,5] ask = [[1,2,3,4],[1,2,4,5]]输出: 3说明:

- 阅读全文 -

房屋染色-dp 阿里天池超级码力初赛第3场第3题

题目链接:房屋染色描述有n个房子在一列直线上,现在Bob需要给房屋染色,共有k种颜色。每个房屋染不同的颜色费用也不同,Bob希望有一种染色方案使得相邻的房屋颜色不同。但Bob计算了使相邻房屋颜色不同的最小染色费用,发现花费非常高。 于是Bob想选择一个区间作为主题步行街,在这个区间中的所有房子必须染成同一个颜色。Bob觉得这样可能能降低总花费,但是也不想让这个步行街太长。Bob认为步行街的长度最多

- 阅读全文 -

博弈论-Nim博弈

题目链接:集合-Nim游戏给定$n$堆石子以及一个由$k$个不同正整数构成的数字集合$S$。现在有两位玩家轮流操作,每次操作可以从任意一堆石子中拿取石子,每次拿取的石子数量必须包含于集合$S$,最后无法进行操作的人视为失败。问如果两人都采用最优策略,先手是否必胜。输入格式第一行包含整数$k$,表示数字集合$S$中数字的个数。第二行包含$k$个整数,其中第$i$个整数表示数字集合$S$中的第$i$个

- 阅读全文 -

手写堆

堆(下标从1开始插入和删除都从堆的末尾开始所有操作都是up和down的组合up操作 只和父节点比较down操作 和最小的儿子交换(最小堆)插入一个数heap[++size] = x; up(size);求最小值heap[1];删除最小值 heap[1] = heap[size--]; down(1);删除任意一个元素 heap[k] = heap[size--]; down(k)

- 阅读全文 -