记录一下算法模板题，这样方便查阅和学习，希望好好加油
线段树
import os import sys N,Q = map(int,input().split()) arr = [0] arr.extend(list(map(int,input().split()))) def ls(p):return p<<1 # p//2 def rs(p):return p<<1|1 # p//2 + 1 tree = [0 for _ in range(N<<2)] # 一共有2n个节点 tag = [0 for _ in range(N<<2)] # lazy_tag标记 def pushdown(p,pl,pr): if tag[p]!=0: mid = pl + pr >> 1 addtag(ls(p),pl,mid,tag[p]) addtag(rs(p),mid+1,pr,tag[p]) tag[p] = 0 # tree[p] = tree[lr(p)] + tree[rs(p)] def push_up(p): tree[p] = tree[ls(p)] + tree[rs(p)] # 搭建线段树 节点的值是求和 def bulid(p,pl,pr): if pl == pr: # tree[p] = float('-inf') tree[p] = arr[pl] return mid = pl + pr>>1 bulid(ls(p),pl,mid) bulid(rs(p),mid+1,pr) # tree[p] = tree[pl] + tree[pr] push_up(p) # 增加lazy_tag标记 def addtag(p,pl,pr,d): tag[p] += d tree[p] += d*(pr-pl+1) def query(p,pl,pr,L,R): # L,R是查询区间 # 当前节点在查询区间内 if L <= pl and pr <= R: return tree[p] pushdown(p,pl,pr) # 标记向下传递 res = 0 mid = pl + pr >>1 if L <= mid: res+=query(ls(p),pl,mid,L,R) if R > mid: res+=query(rs(p),mid+1,pr,L,R) return res # 更新线段树，也就是加上k L,R是更新区间 def update(p,pl,pr,L,R,d): if L<=pl and pr<=R: addtag(p,pl,pr,d) return pushdown(p,pl,pr) # 标记向下传递 mid = pl + pr >> 1 if L <= mid: update(ls(p),pl,mid,L,R,d) if R > mid: update(rs(p),mid+1,pr,L,R,d) push_up(p) bulid(1,1,N) for _ in range(Q): q = list(map(int,input().split())) if q[0] == 1: update(1,1,N,q[1],q[2],q[3]) elif q[0] == 2: print(query(1,1,N,q[1],q[2]))
import os import sys def ls(p):return p<<1 def rs(p):return p<<1|1 def push_up(p):tree[p]=tree[rs(p)]+tree[ls(p)] def build(p,pl,pr): if pl==pr: tree[p]=1 return mid=(pl+pr)>>1 build(ls(p),pl,mid) build(rs(p),mid+1,pr) push_up(p) def addtag(p,pl,pr,d): tag[p]=d tree[p]=d*(pr-pl+1) def push_down(p,pl,pr): if ~tag[p]!=0: mid=(pl+pr)>>1 addtag(ls(p),pl,mid,tag[p]) addtag(rs(p),mid+1,pr,tag[p]) tag[p]=-1 # 把1变成0 def update0(p,pl,pr,cnt): if cnt==0:return if tree[p]==cnt: addtag(p,pl,pr,0) return mid=(pl+pr)>>1 push_down(p,pl,pr) if tree[ls(p)]>cnt:update0(ls(p),pl,mid,cnt) else: cnt-=tree[ls(p)] addtag(ls(p),pl,mid,0) update0(rs(p),mid+1,pr,cnt) push_up(p) # 把0变成1 def update1(p,pl,pr,cnt): if cnt==0:return if pr-pl+1-tree[p]==cnt: addtag(p,pl,pr,1) return mid=(pl+pr)>>1 push_down(p,pl,pr) if mid-pl+1-tree[ls(p)]>cnt:update1(ls(p),pl,mid,cnt) else: cnt-=(mid-pl+1-tree[ls(p)]) addtag(ls(p),pl,mid,1) update1(rs(p),mid+1,pr,cnt) push_up(p) def query(p,pl,pr,L,R): if L<=pl and pr<=R:return tree[p] push_down(p,pl,pr) mid=(pl+pr)>>1 res=0 if L<=mid:res+=query(ls(p),pl,mid,L,R) if R>mid:res+=query(rs(p),mid+1,pr,L,R) return res n,m=map(int,input().split()) tree=[0 for _ in range(n<<2)] tag=[-1 for _ in range(n<<2)] build(1,1,n) for _ in range(m): op,num=map(int,input().split()) if op==0: pos=n-tree[1] cnt=max(0,num-pos) update0(1,1,n,cnt) elif op==1: pos=tree[1] cnt=max(0,n-num+1-pos) update1(1,1,n,cnt) ans1,ans2=[],[] for i in range(1,n+1): if query(1,1,n,i,i)==0:ans1.append(i) else:ans2.append(i) for x in ans1[::-1]+ans2: print(x,end=' ')
DP 动态规划
dp, LIS **
''' https://www.lanqiao.cn/problems/1188/learning/ 难度: 中等 标签: dp, LIS ''' import os import sys import bisect # 请在此输入您的代码 n = int(input()) a = list(map(int,input().split())) dp = [float('inf')]*(n+1) dp[0] = a[0] for i in range(1,n): t = bisect.bisect_left(dp,a[i]) dp[t] = a[i] print(bisect.bisect_left(dp,float('inf')))
01背包
动态转移方程
# https://www.lanqiao.cn/problems/1174/learning/ # 难度: 简单 标签: dp, 背包, 01背包 import os import sys # 请在此输入您的代码 N,V = map(int,input().split()) # f[N][V] # f[i][j] 代表 i 件物品 ， 容量为 j 的时候，得到最大的价值 f = [[0]*(V+1) for _ in range(N+1)] for i in range(1,N+1): # v为体积， w为价值 v, w = map(int, input().split()) for j in range(1,V+1): # 第i件物品有两种选择， # 第1种是选第i件物品，f[i-1][j] # 第2种是不选第i件物品，f[i-1][j] if j < v: f[i][j] = f[i-1][j] else: f[i][j] = max(f[i-1][j], f[i-1][j-v] + w) print(f[N][V])
完全背包
一般就是
不过可以转化为动态转移方程
''' https://www.lanqiao.cn/problems/1175/learning/ 难度: 简单 标签: DP, 背包, 完全背包 ''' import os import sys # 请在此输入您的代码 N,V = map(int,input().split()) # f[i][j]表示前i种，总体积不超过j，最大的总价值 f = [[0]*(V+1) for _ in range(N+1)] # 完全背包问题，可以买多个 for i in range(1,N+1): v,w = map(int,input().split()) for j in range(1,V+1): # 这里是体积的范围 # t = j//v # f[i][j] = f[i-1][j] # for x in range(1,t+1): # x是第i件物品的数量 # f[i][j] = max(f[i][j],f[i-1][j-x*v]+w*x) # 优化后写法，已经把所有的也考虑进去了 if j < v: f[i][j] = f[i-1][j] # 相当于不买第 i 件物品 else: f[i][j] = max(f[i-1][j],f[i][j-v] + w) # 这里是比较买i件物品和不买i件物品 print(f[N][V]) # 压缩成一维 # dp = [0]*(V+1) # v,w = [],[] # for i in range(N): # v,w = map(int,input().split()) # for j in range(1,V+1): # if j >= v: # dp[j] = max(dp[j-v] + w, dp[j]) # print(dp[V])
多重背包
对于多重背包来说，实际上与一般是一样的情形的构造，就是数量受限制了而已
不过多重背包也有一种二进制的压缩写法，复杂度就会更低一点
''' https://www.lanqiao.cn/problems/1176/learning/ 难度: 简单 标签: dp, 背包, 多重背包 ''' import os import sys # 请在此输入您的代码 N,V = map(int,input().split()) # 多重背包和完全背包是一样的构造方式 f = [[0]*(V+1) for _ in range(N+1)] for i in range(1,N+1): v,w,s = map(int,input().split()) for j in range(1,V+1): # 多重背包的区别就是，不可以直接简化，因为数量已经有了限制，所以说独立一个循环进行判断和更新 for k in range(s+1): if k*v <= j: # 这一部分判断，是否买k个 f[i][j] = max(f[i][j],f[i-1][j-k*v] + k*w) else: break print(f[N][V])
二进制写法
多重背包二进制还可以进行优化，要不然上一部分的复杂度有 On的三次方
会把多重背包转化为01背包，对于01背包就稍微简单一点
比如200个数量的物体，可以转为为1,2,4,8,…,64,74这么多组
因为1127的数可以由164构成，然后200-127 = 73
（1~127 都可以表示出来，选出任意一种与 73 组合就可以表示出 74 ~ 200 ，所以合起来就可以表示 1~200）。
相当于每个数量的为一组
# 多重背包二进制还可以进行优化，要不然上一部分的复杂度有 On的三次方 # 会把多重背包转化为01背包，对于01背包就稍微简单一点 # 比如200个数量的物体，可以转为为1,2,4,8,....,64,74这么多组 # 因为1~127的数可以由1~64构成，然后200-127 = 73 # （1~127 都可以表示出来，选出任意一种与 73 组合就可以表示出 74 ~ 200 ，所以合起来就可以表示 1~200）。 # 相当于每个数量的为一组 N,V = map(int,input().split()) v = [0]*12010 w = [0]*12010 cnt = 0 for i in range(N): a,b,s = map(int,input().split()) k = 1 # 按照二进制的形式分组 while k <= s: cnt += 1 v[cnt] = k*a w[cnt] = k*b s = s - k k = k*2 # 不能按照二进制分组的物体数量单独划分为一组。 if k > 0: cnt += 1 v[cnt] = a*s w[cnt] = b*s f = [0]*(cnt+1) # 分组后就等同于0 1 背包 for i in range(1,cnt + 1): for j in range(V,0,-1): if j >= v[i]: f[j] = max(f[j],f[j-v[i]] + w[i]) else: break print(f[V])
混合背包
其中又有混合背包问题，混合背包问题就是，我们的数量变成无限了，对于无限来说，我们就不可以直接利用二进制进行计算。
不过我思考了一下，除非说以我们的体积作为我们的上界，还是可以进行的
首先就是先根据一个无限的情况进行一个判断，这里是改完全背包的，因为这些都是变体
''' https://www.lanqiao.cn/problems/1177/learning/ 难度: 简单 标签: dp, 背包, 混合背包 ''' N,V = map(int,input().split()) # f[i][j]表示前i种，总体积不超过j，最大的总价值 f = [[0]*(V+1) for _ in range(N+1)] for i in range(1,N+1): v,w,s = map(int,input().split()) for j in range(1,V+1): # 多重背包的区别就是，不可以直接简化，因为数量已经有了限制，所以说独立一个循环进行判断和更新 if s != 0: for k in range(s+1): if k*v <= j: # 这一部分判断，是否买k个 f[i][j] = max(f[i][j],f[i-1][j-k*v] + k*w) else: break else: k = 0 while k*v <= j: f[i][j] = max(f[i][j],f[i-1][j-k*v] + k*w) k += 1 print(f[N][V])
如果s=0表示该商品有无限个，但实际背包不可能放入无限多个，在此假设最大个数为能够全部放入背包的数量
所以这个也可以通过调整一个上界进行，因为我们的体积是有限的，所以也可以调整多重背包的二进制进行修改
''' https://www.lanqiao.cn/problems/1177/learning/ 难度: 简单 标签: dp, 背包, 混合背包 ''' N,V = map(int,input().split()) v = [0]*12010 w = [0]*12010 cnt = 0 for i in range(N): a,b,s = map(int,input().split()) if s == 0: s = V//a # 设置上界即可 k = 1 # 按照二进制的形式分组 while k <= s: cnt += 1 v[cnt] = k*a w[cnt] = k*b s = s - k k = k*2 # 不能按照二进制分组的物体数量单独划分为一组。 if k > 0: cnt += 1 v[cnt] = a*s w[cnt] = b*s f = [0]*(cnt+1) # 分组后就等同于0 1 背包 for i in range(1,cnt + 1): for j in range(V,0,-1): if j >= v[i]: f[j] = max(f[j],f[j-v[i]] + w[i]) else: break print(f[V])
分组背包
其实就类似于01背包，对于一个物品有两种决策选或不选，但是分组背包是在01背包的基础上对物品进行了分组，并且每一组只能最多选择一个物品，所以我们不妨用01背包的思想去思考分组背包.
分析：我们设f[i][j]为当前考虑到了第i组物品，剩余容里为j的背包能装物品的最大价值，那么很容易想到我们需要去枚举第i组物品，考虑选哪一个物品时最优的(或者不选)，状态转移方程就是
v[i][k]和w[i][k]分别表示第i组物品中第k个物品的体积和价值
for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) for(int k=1;k<=s[i];k++)//s[i]表示第i组物品的个数 if(j>=v[i][k])//剩余的背包容量j大于第i组的第k个物品的体积 { f[i][j] = max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]); }
''' https://www.lanqiao.cn/problems/1178/learning/ 难度: 简单 标签: dp, 背包, 分组背包 ''' N,V = map(int,input().split()) f = [0]*(V+1) v = [[0]] w = [[0]] s = [0] for i in range(1,N+1): s.append(int(input())) # 一组物品只能买一件 vi = [0] wi = [0] for _ in range(s[i]): a,b = map(int,input().split()) vi.append(a) wi.append(b) v.append(vi) w.append(wi) # f[i][j] 代表在选择i组中， 体积不超过j的最大价值 f = [[0]*(V+1) for _ in range(N+1)] for i in range(1,N+1): # 1~N 组数 for j in range(V,-1,-1): # V~0 体积数 for k in range(1,s[i]+1): # 1~i 分组的物品数 if j >= v[i][k]: f[i][j] = max(f[i][j],f[i-1][j - v[i][k]] + w[i][k]) print(f[N][V])
还可以进行压缩成一维的，减少空间
for 所有的组k for v=V..0 for 所有的i属于组k f[v]=max{f[v],f[v-c[i]]+w[i]}
# 压缩成一维 N,V = map(int,input().split()) f = [0]*(V+1) v = [[0]] w = [[0]] s = [0] for i in range(1,N+1): s.append(int(input())) # 一组物品只能买一件 vi = [0] wi = [0] for _ in range(s[i]): a,b = map(int,input().split()) vi.append(a) wi.append(b) v.append(vi) w.append(wi) # f[i][j] 代表在选择i组中， 体积不超过j的最大价值 f = [0]*(V+1) for i in range(1,N+1): # 1~N 组数 for j in range(V,-1,-1): # V~0 体积数 for k in range(1,s[i]+1): # 1~i 分组的物品数 if j >= v[i][k]: f[j] = max(f[j],f[j - v[i][k]] + w[i][k]) print(f[V])
区间DP
一.什么是区间dp?
顾名思义：区间dp就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的 最优解进而得出整个大区间上最优解的dp算法。
二.核心思路
既然让我求解在一个区间上的最优解，那么我把这个区间分割成一个个小区间，求解每个小区间的最优解，再合并小区间得到大区间即可。所以在代码实现上，我可以枚举区间长度len为每次分割成的小区间长度（由短到长不断合并），内层枚举该长度下可以的起点，自然终点也就明了了。然后在这个起点终点之间枚举分割点，求解这段小区间在某个分割点下的最优解。板子如下：
for(int len = 1;len<=n;len++){//枚举长度 for(int j = 1;j+len<=n+1;j++){//枚举起点，ends<=n int ends = j+len - 1; for(int i = j;i<ends;i++){//枚举分割点，更新小区间最优解 dp[j][ends] = min(dp[j][ends],dp[j][i]+dp[i+1][ends]+something); } } }
三.朴素区间dp（n^3)
转移方程
dp[j][ends] = min(dp[j][ends],dp[j][i]+dp[i+1][ends]+weigth[i][ends]);
j~ends堆合并 = 较小的（原来， 分割点i坐部分重量 + 分割点i右边部分重量 + 合并后两堆总重量）
注：可以用sum[j] - sum[i - 1]表示i~j堆的重量！
博弈论
nim博弈
这实际上是一个尼姆博弈的问题，尼姆博弈就是一个两人博弈，2名玩家轮流从数堆物品中拿取一定数量的物品，每次拿取时先选择某一堆，再从中拿取任意数量个物品，至少拿1个，至多将这一堆物品全部拿走，不能不拿。拿到最后一个物品的玩家获胜。
尼姆博弈是一个两人博弈，2名玩家轮流从数堆物品中拿取一定数量的物品，每次拿取时先选择某一堆，再从中拿取任意数量个物品，至少拿1个，至多将这一堆物品全部拿走，不能不拿。拿到最后一个物品的玩家获胜。
两堆的情形
我们从最简单的两堆物品的情形开始分析，并使用二元组（n，m）来表示这两堆物品当前的数量。当（n，m）情形下先手方\后手方有必胜策略时，我们称（n，m）为制胜位置。
我们将说明：当n=m时，后手有必胜策略，否则先手有必胜策略。
当n=m=1时，先手方仅能够将其中一堆完全取走，故后手方只需要将另一堆的1个物品取走即可获胜。即（1，1）是后手方的制胜位置。
当n=m=k>1时，无论先手方选择哪一堆，取走多少数量的物品，后手方只需要选择另一堆，并取走相同数量的物品，就可以将物品堆的状态从（k，k）转换到（j，j），其中j<k。如此操作下去，由于两堆物品的数量保持相等且严格递减，故后手方玩家总能将物品堆的数量转换为（1，1）或（0，0）。由上面的讨论与游戏规则知，后手方必胜。即（n，m），n=m是后手方的制胜位置。
当时，先手方只需要从较多的一堆物品中拿取适量的物品，使得两物品堆物品数量一致，就将情形转换为了上述两种情况之一，且自身处于后手方。由上面的讨论知，先手方必胜。即（n，m），是先手方的制胜位置。
定义：物品堆的尼姆和是一个二进制数，它是由所有物品堆中物品的数量转换为二进制后，进行异或运算得到的。设有k个物品堆，分别有
