2023.1.9
2023.1.10 太痛苦了，一道题写了一天还不会写，艹……
y总写leetcode题是爽题，我写是送命题，%%%……
算法复杂度
衡量算法性能得主要对象是时间复杂度，一般不讨论空间复杂度。
尺取法(双指针)优化序列区间问题
O(n2)->O(n)
指针i,j方向相反：左右指针；方向相同：快慢指针(产生一个大小可变的滑动窗口)。
朴素算法
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
//O(n^2)
}//双指针算法：将上述朴素算法优化到O(n)
双指针算法
for(i=0,j=0;i<n;i++)
{
while(j<i&&check(i,j))j++;
//每道题目的具体逻辑
}
反向扫描
同向扫描
Subsequence
Bound Found
最长连续不重复子序列
数组去重
1)哈希(利用哈希函数有冲突的特点去重，哈希表需要空间较大)
2)尺取法
#数组去重
a=list(map(int,input().split()))
n=len(a)
a.sort()#排序后重复元素会挤到一起
i=0#快指针
j=0#慢指针，指向不重复的最后一个元素
while i<n-1:
i+=1
if a[i]!=a[j]:#若a[i]!=a[j],则将a[i]放到a[j]后面
j+=1
a[j]=a[i]
print(a[:j+1])
多指针
A-B 数对
三数之和
尺取法在链表中的应用：常用的双指针技巧
双指针知识点题库
2023.1.11
二分法
整数二分
找x的后继
def bisearch(a,x):
l=0
r=len(a)-1
while l<r:
mid=l+r>>1
if a[mid]>=x:
r=mid
else:
l=mid+1
return l
找x的前驱
def bisearch(a,x):
l=0
r=len(a)-1
while l<r:
mid=l+r+1>>1
if a[mid]<=x:
l=mid
else:
r=mid-1
return l
二分STL(bisect)
from bisect import bisect_left,bisect#二分库
a=[1,2,3,3,4,5,6,7,7,7,8,8]
print(bisect_left(a,3))#若x已存在，则返回能插入的最左边的位置->升序序列中，返回>=x的第一个数的下标->bisect_left(a,x)-1即返回最后一个<x的数下标
print(bisect(a,3))#若x已存在，则返回能插入的最右边的位置->升序序列中，返回>x的第一个数的下标->bisect(a,x)-1即返回最后一个<=x的数下标
整数二分建模
while l<r:
mid=l+r>>1
if check(mid):
ans=mid
else:
pass
进击的奶牛
跳石头
聪明的质监员
Monthly Expense S
实数二分
eps=1e-7 #精度，需要仔细设计
while r-l>eps:
mid=(l+r)/2
if check(mid):
r=mid
else:
l=mid
Pie
Expanding Rods
2023.1.12 被迫打了一天工，啥也没学，中午拿办公室电脑A了一题……
2023.1.13
三分法
注意：单峰（单谷）函数两边要严格单调，否则可能在一边f(mid1)==f(mid2)，无法缩小区间。
实数三分
【模板】三分法
函数
UmBasketella
整数三分
while l<r:
mid1=l+(r-l)//3
mid2=r-(r-l)//3
if check(mid1)>check(mid2):
l=mid1+1
else:
r=mid2-1
2023.1.14
倍增法与ST算法
1.倍增法O(2n)从小区间到大区间；从小数值到大数值
把一个数二进制展开：N=a020+a121+a222+a323+a424+……
二进制划分反映了一种快速增长的特性：2i=2i−1+2i−2+……+21+20+1
局限性：需要提前计算1,2,4,……,2k个跳板，数据必须是静态的，如果变化，那么所有跳板必须重新计算。
国旗计划
2.ST算法适用于静态空间的RMQ
天才的记忆
Balanced Lineup G
2023.1.15
前缀和与差分
前缀和是差分的逆运算；差分数组对“区间修改”高效，但对“单点查询”不高效。
一维：
前缀和
Subsequences Summing to Sevens S
激光炸弹
差分
最高的牛
二维：
子矩阵的和
差分矩阵
地毯
Monitor
三维：压维
三维前缀和与三维差分
三体攻击
离散化 用相对值代替绝对值
步骤：1.排序；2离散化；3.归位
离散化手工编码
n=int(input())
a=[0]+list(map(int,input().split()))
old=[(0,0)]*(n+1)
new=[(0,0)]*(n+1)
for i in range(1,n+1):
old[i]=(a[i],i)
old.sort(key=lambda x:x[0])
for i in range(1,n+1):
new[old[i][1]]=i
# 若两个元素值相同，赋成同样的值
# if old[i][0]==old[i-1][0]:
# new[old[i][1]]=new[old[i-1][1]]
for i in range(1,n+1):
print(new[i],end=' ')
STL实现离散化 不去重
from bisect import bisect_left
n=int(input())
old=[0]+list(map(int,input().split()))
new=old.copy()
old.sort()
for i in range(1,n+1):
new[i]=bisect_left(old,new[i])
for i in range(1,n+1):
print(new[i],end=' ')
排序与排列
排序函数
sort()
sorted()
奖学金
排列
全排列的算法复杂度为O(n!)
1.Python的排列组合函数
2.自写排列函数
Ann
def dfs(s,t):
if s==t:
for i in range(t):
print(b[i],end=' ')
print()
return
for i in range(t):
if not vis[i]:
b[s]=a[i]
vis[i]=True
dfs(s+1,t)
vis[i]=False
a=[1,2,3,4,5,6,7,8,9,10,11,12,13]
vis=[False]*20
b=[0]*20
n=3
dfs(0,n)
Amn
def dfs(s,t,m):
if s==m:
for i in range(m):
print(b[i],end=' ')
print()
return
for i in range(t):
if not vis[i]:
b[s]=a[i]
vis[i]=True
dfs(s+1,t,m)
vis[i]=False
a=[1,2,3,4,5,6,7,8,9,10,11,12,13]
vis=[False]*20
b=[0]*20
n=4
m=3
dfs(0,n,m)
分治法
最大子段和
南蛮图腾
2的幂次方
分形
1.汉诺塔
汉诺塔
2.快速幂(标准写法不是分治，而是二进制倍增)
def fastpow(a,n,m):
if n==0:
return 1
if n==1:
return a
temp=fastpow(a,n//2,m)
if n%2:
return temp*temp*a%m
return temp*temp%m
a,n,m=map(int,input().split())
print(fastpow(a,n,m))
贪心法与拟阵
贪心法
特征：
1.最优子结构性质。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质，也称此问题满足最优性原理。局部最优扩展到全局最优。
2.贪心选择性质。问题的整体最优解可以通过一系列局部最优的选择得到。
拟阵
如果一个问题满足拟阵结构，那么贪心能得到最优解。
最大不相交区间数量
游戏预言
Hero
Aaronson
搭配牛奶
跳跳！
纪念品分组
三国游戏
推销员
2023.1.18 又一章结束了，真就差不多10天一章，而且还有好多题不会……
