位运算
x>>k #把x的第k位数字移到最后一位
x%1 #看x的最后一位是几
x>>k&1 #获取x的第k位数字
def lowbit(x): #返回x的最后一位1
return x&-x
#return x&(~x+1)
时间复杂度
for i in range(n):
j=i
while j<n:
pass
j+=i
时间复杂度O(∑ni=1ni)=O(nlogn),俗称调和级数复杂度。
python库
python 有处理分数的库fractions
from fractions import Fraction
x=Fraction(312,888)#返回分数形式
print(x)
x=Fraction('7.78')#将字符串小数转化成分数形式
print(x)
print(x.denominator)#返回分母
print(x.numerator)#返回分子
print(x.as_integer_ratio())#返回由分子分母组成的元组
做题注意点
- 双指针维护区间时要明确区间的含义,注意处理边界。
- 注意数据范围,值域范围。
- 对数列排序,若数列值域A较小,数量大,可以计数排序O(n+A);若值域大而数量少,可用快排(sort)O(nlogn)。
- 单调栈:动态维护一段具有单调性的区间;若区间递减,可找到每个元素右侧第一个比其大的元素(第一个将其弹出栈的元素);若区间递增,可找到每个元素右侧第一个比其小的元素。O(n)
- 单调队列:动态维护一段具有单调性的区间;动态查询固定长度区间内的极值:极大值:区间单调递减;极小值:区间单调递增。
- DP多个决策之间难以处理时,可以先对所有阶段的部分决策进行求解,全部处理完后,再对剩下决策再求解一遍。 守望者的逃离
- 求总分是某个值的倍数的方案数:设DP的每个决策为模该值的余数。注意初始化。 Cow Frisbee Team S
- Gray Code生成:以二进制为0值的格雷码为第零项,第一项改变最右边的位元,第二项改变右起第一个为1的位元的左边位元,第三、四项方法同第一、二项,如此反复,即可排列出n个位元的格雷码。