杂项整理

¶位运算

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(\sum_{i=1}^n{\frac{n}{i}})=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())#返回由分子分母组成的元组

¶做题注意点

1. 双指针维护区间时要明确区间的含义，注意处理边界。
2. 注意数据范围，值域范围。
3. 对数列排序，若数列值域$A$较小，数量大，可以计数排序$O(n+A)$；若值域大而数量少，可用快排$(sort)O(nlogn)$。
4. 单调栈：动态维护一段具有单调性的区间；若区间递减，可找到每个元素右侧第一个比其大的元素（第一个将其弹出栈的元素）；若区间递增，可找到每个元素右侧第一个比其小的元素。$O(n)$
5. 单调队列：动态维护一段具有单调性的区间；动态查询固定长度区间内的极值：极大值：区间单调递减；极小值：区间单调递增。
6. DP多个决策之间难以处理时，可以先对所有阶段的部分决策进行求解，全部处理完后，再对剩下决策再求解一遍。 守望者的逃离
7. 求总分是某个值的倍数的方案数：设DP的每个决策为模该值的余数。注意初始化。 Cow Frisbee Team S