输入输出优化
ios::sync_with_stdio(false);一般ACM或者笔试题的时间限制是1秒或2秒。 在这种情况下，C++代码中的操作次数控制在107~108 为最佳。
下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择：
- n≤30, 指数级别, dfs+剪枝，状态压缩dp
- n≤100 => O(n3)，floyd，dp，高斯消元
- n≤1000 => O(n2)，O(n2logn)，dp，二分，朴素版Dijkstra、朴素版Prim、Bellman-Ford
- n≤10000 => O(n∗$\sqrt n$)，块状链表、分块、莫队
- n≤100000 => O(
nlogn) => 各种sort，线段树、树状数组、set/map、heap、拓扑排序、dijkstra+heap、prim+heap、Kruskal、spfa、求凸包、求半平面交、二分、CDQ分治、整体二分、后缀数组、树链剖分、动态树 - n≤106 =>O(n), 以及常数较小的 O(
nlogn) 算法 => 单调队列、 hash、双指针扫描、并查集，kmp、AC自动机，常数比较小的 O(nlogn) 的做法：sort、树状数组、heap、dijkstra、spfa - n≤107 =>O(n)，双指针扫描、
kmp、AC自动机、线性筛素数 - n≤109 => O(
$\sqrt n$ )，判断质数 - n≤1018 => O(logn)，最大公约数，快速幂，数位DP
- n≤101000 =>O((logn)2)，高精度加减乘除
- n≤10100000 => O(logk×loglogk)，k表示位数，高精度加减、
FFT/NTT
# 算法题打表
import string
ls=list(string.ascii_letters)import math
print(math.pi)# Greatest Common Divisor）
# Least common multiple
def gcd(m,n):
'''
最大公因数
'''
return n if m%n==0 else gcd(n,m%n)
def lcm(m,n):
'''
最小公倍数
'''
return int(m*n/gcd(m,n))(1<<31)-1 不同于 1<<31-1业务题与技巧题
笔试主要考业务题
面试主要考技巧题
输入类型特别简单，输出类型也特别简单
输入一个整数，输出一个整数
找规律
四成
一次吃1，4，16…堆草，先手必赢或后手必赢；
先暴力，再找规律
def winner(x):
'''
0 1 2 3 4 5 6
后 先 后 先 先 后 先
'''
if x<5:
return '后手' if x==0 or x==2 else '先手'
base=1
while base<=x:
if winner(x-base) =='后手':
return '先手'
if base>x/4:
break
base*=4
return '后手'
for i in range(20):
print(winner(i))所有套路：
从左到右尝试模型
范围尝试模型：注意开头和结尾
样本对应模型：
业务对应模型
def factorial(n):
if n==1: return 1
else: return factorial(n-1)*n
print(factorial(4))1，2项分别为0，1
只使用递归，可以看到速度明显很慢
def fib(n):
if n==1 or n==2: return 1
else: return fib(n-1)+fib(n-2)
print(fib(15))
print(fib(35))加入哈希表记忆
def fib(n):
if hash.get(n,0): return hash[n]
res=fib(n-1)+fib(n-2)
hash[n]=res
return res
hash={1:1,2:1}
print(fib(15))
print(fib(50))def hanoi(n,a,b,c):
if n==1: print(a+"---->"+c)
else:
hanoi(n-1,a,c,b)
print(a+"---->"+c)
hanoi(n-1,b,a,c)
hanoi(2,'A','B','C')def arr_sum(l,n):
if n==0: return 0
return l[n-1]+arr_sum(l,n-1)
arr = [1,2,3,4,5,10]
print(arr_sum(arr,len(arr)))def power_x_y(x,y):
if y==0:return 1
if y&1:return x*power_x_y(x,(y-1)>>1)**2
return power_x_y(x,y>>1)**2
print(power_x_y(2,11))
print(power_x_y(2,12))def swap(x, y):
tmp=l[x]
l[x]=l[y]
l[y]=tmp
def reverse_list(l,start,end):
if start>=end:return
swap(start,end)
reverse_list(l,start+1,end-1)
l=[1,2,3,4,5,6,7,8,9]
reverse_list(l,0,len(l)-1)
print(l)def swap(left, right):
tmp=l[left]
l[left] = l[right]
l[right] = tmp
def all_sort(l,left, right):
if left==right:print(l)
else:
for i in range(left,right+1):
swap(left,i)
all_sort(l,left+1,right)
swap(left,i)
l=[1,2,3]
all_sort(l,0,len(l)-1)
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
int f(int x,int y){
if(x == 0) return 1;//没有苹果，全部盘子为0
if(y == 0) return 0;//没有盘子，没法放
if(y > x){//盘子数大于苹果数，至多只能x个盘子上都放一个
return f(x,x);
}
return f(x - y, y) + f(x, y - 1);//盘子数小于等于苹果数 -> 分类讨论： 有盘子为空，没有盘子为空
//有盘子为空的时候即至少有一个盘子为空，f(x,y-1);没有盘子为空即最少每个盘子都有一个,f(x-y,y)
}
int main(){
int t,n,m;//n个苹果分到m个盘子里去，允许盘子为空
cin >> t;
while(t --){
cin >> n >> m;
cout << f(n,m) << endl;
}
return 0;
}加入记忆化搜索：
#include<iostream>
#include<cstdio>
using namespace std;
int a[25][25],m,n;
int main()
{
int t,m,n;
for(m=0;m<=10;m++)
{
for(n=0;n<=10;n++)
{
if(m<n)a[m][n]=a[m][m];
else if(m==0)a[m][n]=1;
else if(n==0)a[m][n]=0;
else a[m][n]=a[m-n][n]+a[m][n-1];
}
}
scanf("%d",&t);
for(int i=1;i<=p;i++)
{
scanf("%d%d",&m,&n);
printf("%d\n",a[m][n]);
}
return 0;
}长度1-N，开始点start，结束点end，步数step，返回方法数n
# 长度1-N，开始点start，结束点end，步数step，返回方法数n
def jump(N,start,end,step):
if step==0:
if start==end:
return 1
else:
return 0
if start==1:
return jump(N,2,end,step-1)
if start ==N:
return jump(N,N-1,end,step-1)
return jump(N,start-1,end,step-1)+jump(N,start+1,end,step-1)
print(jump(5,2,4,6))给定一个数组
绝顶聪明的两人，轮流拿牌，只能拿最左或最右
def f(l,r):
if l==r:
return arr[l]
a1=arr[l]+b(l+1,r)
a2=arr[r]+b(l,r-1)
return max(a1,a2)
def b(l,r):
if l==r:
return 0
a1=f(l+1,r)
a2=f(l,r-1)
return min(a1,a2)
arr=[1,2,100,3,4]
print(f(0,len(arr)-1))
print(b(0,len(arr)-1))w数组，v数组，bag容量，返回最大价值
# w数组，v数组，bag容量，返回最大价值
def maxValue(index,bag):
if bag<0:
return -1
if index==len(w):
return 0
p1=maxValue(index+1,bag)
p2=0
next=maxValue(index+1,bag-w[index])
if next!=-1:
p2=v[index]+next
return max(p1,p2)
w=[1,2,3,4,5]
v=[1,2,3,4,50]
bag=10
print(maxValue(0,bag))1对应A，2对应B，26对应Z 如111对应AAA，KA，AK 返回转化数
# 1对应A，2对应B，26对应Z
# 如111对应AAA，KA，AK
# 返回转化数
def change(s,i):
if i==len(s):
return 1
if s[i]=='0':
return 0
ways=change(s,i+1)
if i+1<len(s) and (ord(s[i])-ord('0'))*10+(ord(s[i+1])-ord('0'))<27:
ways+=change(s,i+2)
return ways
print(change('111',0))
print(change('305',0))def LCSLength(X, Y):
# 初始化二维数组 C
m = len(X)
n = len(Y)
C = [[0] * (n + 1) for _ in range(m + 1)]
# 填充数组 C
for i in range(1, m + 1):
for j in range(1, n + 1):
if X[i - 1] == Y[j - 1]:
C[i][j] = C[i - 1][j - 1] + 1
else:
C[i][j] = max(C[i - 1][j], C[i][j - 1])
# 返回最长公共子序列的长度
return C[m][n]
def LCS(X, Y):
# 获取二维数组 C
m = len(X)
n = len(Y)
C = LCSLength(X, Y)
# 初始化结果字符串
result = ""
# 回溯数组 C
i = m
j = n
while i > 0 and j > 0:
if X[i - 1] == Y[j - 1]:
result = X[i - 1] + result # 将匹配的元素加入结果中
i -= 1
j -= 1
else:
if C[i - 1][j] > C[i][j - 1]:
i -= 1
else:
j -= 1
# 返回最长公共子序列
return result
# 测试
X = "ABCBDAB"
Y = "BDCABA"
print(LCSLength(X, Y)) # 输出 4
print(LCS(X, Y)) # 输出 BCBA 或 BDAB# 返回最长公共子序列
def process(s1,s2,i,j):
if i==0 and j==0:
return 1 if s1[i]==s2[j] else 0
if i==0:
if s2[j]==s1[i]:
return 1
else:
return process(s1,s2,i,j-1)
if j==0:
if s1[i]==s2[j]:
return 1
else:
return process(s1,s2,i-1,j)
p1=process(s1,s2,i-1,j)
p2=process(s1,s2,i,j-1)
p3=process(s1,s2,i-1,j-1)+1 if s1[i]==s2[j] else 0
return max(p1,p2,p3)
def longestCommen(s1,s2):
if s1==None or s2==None or len(s1)==0 or len(s2)==0:
return 0
s1=list(s1)
s2=list(s2)
# 0到len-1最长公共子序列长度
return process(s1,s2,len(s1)-1,len(s2)-1)
s1='abcdefghijklmn'
s2='abcdln'
print(longestCommen(s1,s2))def LPSLength(S):
# 初始化二维数组 L
n = len(S)
L = [[0] * (n + 1) for _ in range(n + 1)]
# 填充数组 L
for i in range(1, n + 1):
for j in range(1, n + 1):
if i > j:
L[i][j] = 0
elif i == j:
L[i][j] = 1
else:
if S[i - 1] == S[j - 1]:
L[i][j] = L[i + 1][j - 1] + 2
else:
L[i][j] = max(L[i + 1][j], L[i][j - 1])
# 返回最长回文子序列的长度
return L[1][n]
def LPS(S):
# 获取二维数组 L
n = len(S)
L = LPSLength(S)
# 初始化结果字符串
result = ""
# 回溯数组 L
i = 1
j = n
while i <= j:
if S[i - 1] == S[j - 1]:
result = S[i - 1] + result # 将匹配的元素加入结果中
i += 1
j -= 1
else:
if L[i + 1][j] > L[i][j - 1]:
i += 1
else:
j -= 1
# 返回最长回文子序列
return result
# 测试
S = "abcbda"
print(LPSLength(S)) # 输出 4
print(LPS(S)) # 输出 abba# 原字符串与其逆字符串的最长公共子序列既是最长回文子序列
# 在l与r范围内最长回文子序列长度
def process(l,r):
if l==r:
return 1
if l==r-1:
return 2 if s[l]==s[r] else 1
p1=process(l,r-1)
p2=process(l+1,r)
p3=process(l+1,r-1)+2 if s[l+1]==s[r-1] else process(l+1,r-1)
return max(p1,p2,p3)
def longestHuiwen(s):
if len(s)==0 and s==None:
return 0
if len(s)==1:
return 1
if len(s)==2:
return 2 if s[0]==s[1] else 1
return process(0,len(s)-1)
s='12a33211'
print(longestHuiwen(s))# 10行9列的棋盘，左下角在0，0，从0，0，到x，y位置，蹦k步，有多少种方法
def jump(a,b,rest,x,y):
if a<0 or a>9 or b<0 or b>8:
return 0
if rest==0:
return 1 if x==a and y==b else 0
ways=jump(a+2,b+1,rest-1,x,y)
ways+=jump(a+1,b+2,rest-1,x,y)
ways+=jump(a-1,b+2,rest-1,x,y)
ways+=jump(a-2,b+1,rest-1,x,y)
ways+=jump(a-2,b-1,rest-1,x,y)
ways+=jump(a-1,b-2,rest-1,x,y)
ways+=jump(a+1,b-2,rest-1,x,y)
ways+=jump(a+2,b-1,rest-1,x,y)
return ways
print(jump(0,0,10,7,7))
# 515813从start到end，
花费a，cur+2
花费b，cur*2
花费c，cur-2
两个瓶颈：以i结尾最长字串位置，上一个i-1(退到哪里)答案是什么
z,,,i(7)z
z为7+1
给定两个字符串s1与s2，
再给定三个整数a，b，c，分别代表插入，删除和替换一个字符的代价，求将s1变为s2的最小代价
def minCost(s1,s2,a,b,c):
if s1==None or s2==None:
return 0
s1=list(s1)
s2=list(s2)
row=len(s1)+1
col=len(s2)+1
dp=[[0]*col for i in range(row)]
for i in range(1,row):
dp[i][0]=b*i
for j in range(1,col):
dp[0][j]=a*j
for i in range(1,row):
for j in range(1,col):
if s1[i-1]==s2[j-1]:
dp[i][j]=dp[i-1][j-1]
else:
dp[i][j]=dp[i-1][j-1]+c
dp[i][j]=min(dp[i][j],dp[i][j-1]+a)
dp[i][j]=min(dp[i][j],dp[i-1][j]+b)
return dp[row-1][col-1]
# 给定两个字符串s1与s2，
# 再给定三个整数a，b，c，分别代表插入，删除和替换一个字符的代价，求将s1变为s2的最小代价
s1='abc'
s2='abd'
print(minCost(s1,s2,1,2,5))数组最大连续子串和
def maxSum(l):
if l==None or len(l)==0:
return 0
max_=-10**8
cur=0
for i in l:
cur+=i
max_=max(max_,cur)
cur=0 if cur<0 else cur
return max_
# 数组最大连续子串和
l=[1,2,3,-2,2,4,-5,6,7,-3]
l1=[-1,-2,-8-3]
print(maxSum(l))
print(maxSum(l1))子矩阵最大累加和
压缩矩阵技巧 假如是三行矩阵，各个区间行值，就转化为了一维数组子数组最大值 1 12 123 2 23 3
英文，三个数一股
中文，四个数一股
从简单到复杂
挨个数向前找小于自己的最大长度，n2
dp[i]：长度为i的序列最后一位的值，配合二分查找，nlogn
[1，12，123，1234，，，12345678910,,, 输入l，r，输出区间内可以被3整除的数字个数
1+2+,,,+10 等差数列和公式
给定一个字符串，删除掉里面字符，使字符串中没有重复字符，并且字典序最小
def bin_(m:int,n:int=2)->int:
'''
将m转换为n进制,默认2进制，2<=n<=9
'''
if m<n:
return m
return bin_(m//n)*10+m%ndef f64(n, x):
'''输入任意十进制数n要转换的进制x，
返回对应转换后的数。注意进制范围仅限2到64,
并且进制的值必须小于待转换的十进制数'''
# 1、判断是否超出范围，是则返回ERROR
if x < 2 or x > 64: # 进制超出范围
return 'ERROR'
# 2、拼接出64进制下，1-64的数值表示符号
li1 = [i for i in range(10)] # 拼接出0到9的列表
li2 = list('abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ')
li3 = ['@', '_']
li = li1 + li2 + li3
# li = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z', 'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z', '@', '_']
if x>n: # 进制x大于要转换的十进制数
return li[n]
# 3、进制转换
result = ''
while True:
m = n // x # 商
r = n % x # 余数
if n < x:
result = str(li[n]) + result # 跳出循环前，把最后的商，拼接在最前
break
result = str(li[r]) + result # 把每次的余数拼接到前面
n = m
return resultdef merge_sort(l):
if len(l)<=1:return
mid=len(l)>>1
L,R=l[:mid],l[mid:]
merge_sort(L)
merge_sort(R)
i,j,k=0,0,0
while i<len(L) and j<len(R):
if L[i]<R[j]:
l[k]=L[i]
i+=1
else:
l[k]=R[j]
j+=1
k += 1
while i<len(L):
l[k] = L[i]
i += 1
k+=1
while j<len(R):
l[k] = R[j]
j += 1
k+=1
n=int(input())
x=list(map(int,input().split()))
merge_sort(x)
print(' '.join(map(str,x)))长度为n的数组，q次查询，每次查出k的起始索引与终止索引
不存在
#某元素的起始位置，不存在返回-1
def bin_q_left(x):
left,right=-1,n
while left+1!=right:
mid=left+right>>1
if l[mid]<x:
left=mid
else:
right=mid
if right==n or l[right]!=x:
return -1
return right
#某元素的结束位置，不存在返回-1
def bin_q_right(x):
left,right=-1,n
while left+1!=right:
mid=left+right>>1
if l[mid]<=x:
left=mid
else:
right=mid
if left==-1 or l[left]!=x:
return -1
return left
#按照升序排列的长度为 n 的整数数组l，以及 q 个查询
#每个查询输出k的起始和终止位置
n,q=map(int,input().split())
l=list(map(int,input().split()))
for i in range(q):
k=int(input())
print(f'{bin_q_left(k)} {bin_q_right(k)}')第一个错误的版本leetcode.278.
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n]，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
输入：n = 5, bad = 4 输出：4 解释： 调用 isBadVersion(3) -> false 调用 isBadVersion(5) -> true 调用 isBadVersion(4) -> true 所以，4 是第一个错误的版本。
# The isBadVersion API is already defined for you.
# def isBadVersion(version: int) -> bool:
class Solution:
def firstBadVersion(self, n: int) -> int:
l,r=0,n+1
while l+1!=r:
mid=l+r>>1
if isBadVersion(mid):
r=mid
else:
l=mid
if r==n+1:
return -1
return r数组下标，从一开始,可以少做判断
Acwing.795.
输入一个长度为 n 的整数序列。
接下来再输入 m 个询问，每个询问输入一对 l,r。
对于每个询问，输出原序列中从第 l 个数到第 r 个数的和。
输入格式
第一行包含两个整数 n 和 m。
第二行包含 n 个整数，表示整数数列。
接下来 m 行，每行包含两个整数 l 和 r，表示一个询问的区间范围。
输出格式
共 m 行，每行输出一个询问的结果。
数据范围
1≤l≤r≤n, 1≤n,m≤100000, −1000≤数列中元素的值≤1000
输入样例：
5 3 2 1 3 6 4 1 2 1 3 2 4输出样例：
3 6 10
N=100008
n,m=map(int,input().split())
l=list(map(int,input().split()))
s=[0]*N
for i in range(n):
s[i+1]=s[i]+l[i]
for i in range(m):
l,r=map(int,input().split())
print(s[r]-s[l-1])Acwing.796.
输入一个 nn 行 mm 列的整数矩阵，再输入 qq 个询问，每个询问包含四个整数 x1,y1,x2,y2x1,y1,x2,y2，表示一个子矩阵的左上角坐标和右下角坐标。
对于每个询问输出子矩阵中所有数的和。
输入格式
第一行包含三个整数 n，m，q。
接下来 n 行，每行包含 m 个整数，表示整数矩阵。
接下来 q 行，每行包含四个整数 x1,y1,x2,y2，表示一组询问。
输出格式
共 qq 行，每行输出一个询问的结果。
数据范围
1≤n,m≤1000, 1≤q≤200000, 1≤x1≤x2≤n, 1≤y1≤y2≤m, −1000≤矩阵内元素的值≤1000
输入样例：
3 4 3 1 7 2 4 3 6 2 8 2 1 2 3 1 1 2 2 2 1 3 4 1 3 3 4输出样例：
17 27 21
#python
n,m,q=map(int,input().split())
l=[]
for i in range(n):
l.append(list(map(int,input().split())))
s=[[0]*(m+1) for i in range(n+1)]
for i in range(n):
for j in range(m):
s[i+1][j+1]=s[i+1][j]+s[i][j+1]-s[i][j]+l[i][j]
for i in range(q):
x1,y1,x2,y2=map(int,input().split())
print(s[x2][y2]-s[x1][y1])//c++
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, m, q;
int a[N][N], s[N][N];
int main()
{
scanf("%d%d%d", &n, &m, &q);
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= m; j ++ )
{
scanf("%d", &a[i][j]);
s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
}
while (q -- )
{
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
printf("%d\n", s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]);
}
return 0;
}总结
一维前缀和
S[i] = a[1] + a[2] + ... a[i] a[l] + ... + a[r] = S[r] - S[l - 1]二维前缀和 S[i, j] = 第i行j列格子左上部分所有元素的和 以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵的和为：
S[x2, y2] - S[x1 - 1, y2] - S[x2, y1 - 1] + S[x1 - 1, y1 - 1]一维差分 给区间[l, r]中的每个数加上c：
B[l] += c, B[r + 1] -= c二维差分 给以(x1, y1)为左上角，(x2, y2)为右下角的子矩阵中的所有元素加上c：
S[x1, y1] += c, S[x2 + 1, y1] -= c, S[x1, y2 + 1] -= c, S[x2 + 1, y2 + 1] += c
详解
类似于数学中的求导和积分，差分可以看成前缀和的逆运算。
差分数组：
首先给定一个原数组a：a[1], a[2], a[3],…, a[n];
然后我们构造一个数组b ： b[1] ,b[2] , b[3],…, b[i];
使得 a[i] = b[1] + b[2 ]+ b[3] +,…, + b[i]
也就是说，a数组是b数组的前缀和数组，反过来我们把b数组叫做a数组的差分数组。换句话说，每一个a[i]都是b数组中从头开始的一段区间和。
考虑如何构造差分b数组？
最为直接的方法
如下：
a[0]= 0;
b[1] = a[1] - a[0];
b[2] = a[2] - a[1];
b[3] =a [3] - a[2];
........
b[n] = a[n] - a[n-1];
我们只要有b数组，通过前缀和运算，就可以在O(n) 的时间内得到a数组 。
给定区间[l ,r ]，让我们把a数组中的[ l, r]区间中的每一个数都加上c,即 a[l] + c , a[l+1] + c , a[l+2] + c ,…, a[r] + c;
暴力做法是for循环l到r区间，时间复杂度O(n)，如果我们需要对原数组执行m次这样的操作，时间复杂度就会变成O(n*m)。有没有更高效的做法吗? 考虑差分做法。
始终要记得，a数组是b数组的前缀和数组，比如对b数组的b[i]的修改，会影响到a数组中从a[i]及往后的每一个数。
首先让差分b数组中的 b[l] + c ,a数组变成 a[l] + c ,a[l+1] + c,…, a[n] + c;
然后我们打个补丁，b[r+1] - c, a数组变成 a[r+1] - c,a[r+2] - c,…,a[n] - c;
a[r+1]+c-c就相当于没变化，后面数字同理无变化，相当于两次加减法实现了区间同时加减一个数
因此我们得出一维差分结论：给a数组中的[ l, r]区间中的每一个数都加上c,只需对差分数组b做 b[l] + = c, b[r+1] - = c。时间复杂度为O(1), 大大提高了效率。
代码模板
void insert(int l, int r, int c) {
b[l] += c;
b[r + 1] -= c;
}
void insert(int x1,int y1,int x2,int y2,int c){
b[x1][y1]+=c;
b[x1][y2+1]-=c;
b[x2+1][y1]-=c;
b[x2+1][y1+1]+=c;
}
双指针算法 实用i,j两个变量，不会退的扫描一个数组 常规写法
for(int i=0,j=0,i<n;i++){ while(j<i&&check(i,j)) j++; }这是i,j从0开始扫，j<i的扫法
for(int i=0,j=n-1;i<j;i++){ while(check()) j--; }这是i,j分别两端的写法 或者也能这样写
int i=0,j=-1; while(i<j){ if(check(i,j)) i++; else j--; }
将n2优化到n
给定一个字符串，单词用空格分隔，输出字符串里的每个单词，每个单词占一行
a='i love you my friend hello world hhh'
i=0
while i<len(a):
j=i
while j<len(a) and a[j] !=' ':
j+=1
for _ in range(i,j):
print(f'{a[_]}',end='')
print('')
i=j
i+=1#include<iostream>
#include<string.h>
using namespace std;
int main()
{
char str[1000];
gets(str);
int n=strlen(str);
for (int i=0; i<n; i++)
{
int j=i;
while(j<n && str[j]!=' ')j++;
for (int k=i;k<j;k++)cout<<str[k];
cout<<endl;
i=j;
}
return 0;
}acwing.799.
给定一个长度为n的整数序列，请找出最长的不包含重复数字的连续子序列，输出它的长度。
n=int(input())
l=list(map(int,input().split()))
st=[0]*(100000+10)
j=0
res=1
for i in range(n):
st[l[i]]+=1
while st[l[i]]>1:
st[l[j]]-=1
j+=1
res=max(res,i-j+1)
print(res)#include<iostream>
using namespace std;
const int N=100010;
int n;
int l[N],state[N];
int main(){
cin>>n;
for(int i=0;i<n;i++)cin>>l[i];
int res=0;
for(int i=0,j=0;i<n;i++)
{
state[l[i]]++;
while(state[l[i]]>1)
{
state[l[j]]--;
j++;
}
res=max(res,i-j+1);
}
cout<<res<<endl;
return 0;
}a = a ^ b;
b = a ^ b;
a = a ^ b; 任何数异或0为任何数本身
一个数异或本身等于0
n>>k&1
x&-xx=1010,lowbit(x)=10 x=101000,lowbit(x)=1000
每次减去lowbit(x)
#include<iostream>
using namespace std;
int lowbit(int x)
{
return -x&x;
}
int main(){
int res=0;
int x;
cin>>x;
while(x)
{
x-=lowbit(x),res++;
cout<<x<<endl;
}
cout<<res<<endl;
return 0;
}数据范围在-109~1010之间但操作和查询合起来的范围在105左右，可以将数映射到105的数组
-
时间复杂度为O(2N)O(2N)，下面会有证明。
-
举一个简单的例子：用韦恩图来思考，求S1、S2、S3三个集合的原有元素的并集，那么结果为：
S1+S2+S3−S1∩S2−S1∩S3−S2∩S3+S1∩S2∩S3。 -
以此类推到NN个圆的交集：用容斥原理的方法答案为所有单个集合的元素个数-所有两个集合互相交集的元素个数+所有三个集合互相交集的元素个数…
-
我们知道容斥原理公式一共涉及到的元素个数为：C1N+C2N+C3N+…+CNN。因为C0N+C1N+C2N+C3N+…+CNN=2n，因此CN1+CN2+CN3+…+CNN=2n−1，因此容斥原理公式一共涉及到的元素个数为2n−1。关于此公式(CN0+CN1+CN2+CN3+…+CNN=2n)的证明，我们可以假设等号左边为对于N个物品所有选法的总个数，等号右边考虑每个物品选与不选两种情况，因此等式成立。
-
因此容斥原理的时间复杂度为O(2N)。
-
容斥原理的证明：对于容斥原理|S1∪S2∪…∪SN|=∑Ni=1Si−∑Ni,jSi∩Sj+∑Ni,j,kSi∩Sj∩Sk+… 对于一个元素x，它在k个集合中，1≤k≤N，它本身被选择的次数为Ck1−Ck2+Ck3−…+(−1)k−1Ckk。我们知道一个结论：Ck1−Ck2+Ck3−…+(−1)k−1Ckk=1，因此对于每一个元素xx，它只被计算了1次，证毕。
AcWing 890.
给定一个整数n和m个不同的质数p1,p2,…,pm。
请你求出1~n中能被p1,p2,…,pm中的至少一个数整除的整数有多少个。
输入格式 第一行包含整数n和m。
第二行包含m个质数。
输出格式 输出一个整数，表示满足条件的整数的个数。
数据范围 1≤m≤16, 1≤n,pi≤109
输入样例： 10 2 2 3 输出样例： 7
那我们就先来定义一下本题的集合：Sn表示被n整除的数的集合。 那求的东西应该就是那个求大图的东西了。 我们先得出结论：Sn=n/p下取整。 那怎么求交上的呢？ 一样的，因为给定的数都是两两互质的，所以也是一样的。 然后就可以使用二进制来枚举了。
#include<bits/stdc++.h>
using namespace std;
const int N = 20;
#define ll long long
int n, m, p[N];
int main()
{
cin >> n >> m;
for(int i = 0; i < m; i ++) cin >> p[i];
int res= 0;
for(int i = 1; i < 1 << m; i ++)
{
int t = 1, cnt = 0;
for(int j = 0; j < m; j ++)
{
if(i >> j & 1)
{
cnt ++;
if((ll)t * p[j] > n)
{
t = -1;
break;
}
t *= p[j];
}
}
if(t != -1)
{
if(cnt % 2) res += n / t;
else res -= n / t;
}
}
cout << res << endl;
return 0;
}def fun(n,m):
l=[[0]*m for i in range(n)]
dx,dy=[0,1,0,-1],[1,0,-1,0]
d=0
x=y=0
for i in range(m*n):
l[x][y]=i+1
a,b=x+dx[d],y+dy[d]
if a<0 or a>=n or b<0 or b>=m or l[a][b]>0:
d=(d+1)%4
a,b=x+dx[d],y+dy[d]
x,y=a,b
for i in range(n):
print(' '.join(map(str,l[i])))
n,m=map(int,input().split())
fun(n,m)在 ISO 国际标准中定义了 A0 纸张的大小为 1189mm×841mm，将 A0 纸沿长边对折后为 A1 纸，大小为 841mm×594mm，在对折的过程中长度直接取下整（实际裁剪时可能有损耗）。
将 A1 纸沿长边对折后为 A2 纸，依此类推。
输入纸张的名称，请输出纸张的大小。
l=[1189,841]
s=input()
n=int(s[1])
for i in range(n):
l[i&1]//=2
print(l[n&1])
print(l[n&1==0])def get_next(s2):
if len(s2)==1:
return [-1]
next=[0]*len(s2)
next[0],next[1]=-1,0
i=2 # 目前在哪个位置上求next数组的值
cn=0 # 当前是哪个位置的值再和i-1位置的字符比较
while i<len(s2):
if s2[i-1]==s2[cn]:
cn+=1
next[i]=cn
i+=1
elif cn>0:
cn=next[cn]
else:
next[i]=0
i+=1
return next
def kmp(s1,s2):
#s1,s2均不为空字符串，均不为空值，s1不短于s2
if s1==None or s2==None or len(s2)<1 or len(s1)<len(s2):
return -1
s1,s2=list(s1),list(s2)
x,y=0,0
next=get_next(s2)
while x<len(s1) and y<len(s2):
if s1[x]==s2[y]:
x+=1
y+=1
elif next[y]==-1:
x+=1
else:
y=next[y]
return x-y if y==len(s2) else -1
print(kmp('asdfghj','asd'))
print(kmp('asdfghj','asda'))
print(kmp('addasasdfghj','asd'))
print(kmp('asdfghjasdqq','asdqq'))
'''
0
-1
5
7
'''def dfs(x,y):
if x<0 or x>n-1 or y<0 or y>n-1 or l[x][y]=='0':
return
l[x][y]='0'
dfs(x-1,y)
dfs(x+1,y)
dfs(x,y+1)
dfs(x,y-1)
n,m=map(int,input().split())
l=[]
for i in range(n):
l.append(list(map(int,input().split())))
res=0
for i in rnage(n):
for j in range(m):
if l[i][j]=='1':
res+=1
dfs(i,j)
print(res)grid=[
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
def dfs(x,y):
grid[x][y]='0'
for i in range(4):
x,y=x+dx[i],y+dy[i]
if x>-1 and x<n and y>-1 and y<m and grid[x][y]=='1':
dfs(x,y)
res=0
n,m=len(grid),len(grid[0])
dx,dy=[0,1,0,-1],[1,0,-1,0]
for i in range(n):
for j in range(m):
if grid[i][j]=='1':
res+=1
dfs(i,j)
print(res)#偏移量也可以用元组表示
for x, y in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
if 0 <= x < nr and 0 <= y < nc and grid[x][y] == "1":
dfs(grid, x, y)s1='''
010000
000100
001001
110000'''
s1=[list(i) for i in s1.split('\n') if i]s='''
01010101001011001001010110010110100100001000101010
00001000100000101010010000100000001001100110100101
01111011010010001000001101001011100011000000010000
01000000001010100011010000101000001010101011001011
00011111000000101000010010100010100000101100000000
11001000110101000010101100011010011010101011110111
00011011010101001001001010000001000101001110000000
10100000101000100110101010111110011000010000111010
00111000001010100001100010000001000101001100001001
11000110100001110010001001010101010101010001101000
00010000100100000101001010101110100010101010000101
11100100101001001000010000010101010100100100010100
00000010000000101011001111010001100000101010100011
10101010011100001000011000010110011110110100001000
10101010100001101010100101000010100000111011101001
10000000101100010000101100101101001011100000000100
10101001000000010100100001000100000100011110101001
00101001010101101001010100011010101101110000110101
11001010000100001100000010100101000001000111000010
00001000110000110101101000000100101001001000011101
10100101000101000000001110110010110101101010100001
00101000010000110101010000100010001001000100010101
10100001000110010001000010101001010101011111010010
00000100101000000110010100101001000001000000000010
11010000001001110111001001000011101001011011101000
00000110100010001000100000001000011101000000110011
10101000101000100010001111100010101001010000001000
10000010100101001010110000000100101010001011101000
00111100001000010000000110111000000001000000001011
10000001100111010111010001000110111010101101111000
'''
s=[list(i) for i in s.split('\n') if i]
#print(len('RRDDDDDDRRRRRRRRRDDLDDDLDLLLDDLLDDDLDDRDDRRDDLLLDDRDRDRRRRDRDRRRURURRURRUULUUULLUUUULLLUURRRRUUUULLULUUUUUUURUURRRRDDDRRDRRURRRRRRDRDDDDRRUURRURRDRDRDDDDDDDDDDDDRDDLDDDRRRDRRRRRRRURRDDDD'))
#186s1='''
010000
000100
001001
110000'''
s1=[list(i) for i in s1.split('\n') if i]
import queue
def dfs(start,end):
q1 = queue.Queue()
q1.put(start)
s1[start[0]][start[1]]=0
while not q1.empty():
t=q1.get()
for dx,dy in [(0,1),(1,0),(0,-1),(-1,0)]:
x,y=t[0]+dx,t[1]+dy
if 0<=x<n and 0<=y<m and s1[x][y]=='0':
s1[x][y] =s1[t[0]][t[1]]+1
q1.put((x,y))
# d[(x,y)]=t
if x==end[0] and y==end[1]:
return True
return False
d={}
n,m=len(s1),len(s1[0])
print(dfs((0,0),(n-1,m-1)))
print(s1[n-1][m-1])
# print(s1)
flag=True
fa = (n-1,m-1)
# while flag:
# print(fa,end='\t')
# fa=d.get(fa)
# if d.get(fa,-1)==-1:
# flag=False
# print(fa)路径记忆原理
# 存储每个结点的父结点，可以顺着节点向上查找
d=dict()
d[(1,1)]=1
d[1]=2
d[2]=3
d[3]=4
flag=True
fa = (1, 1)
while flag:
print(fa,end='\t')
fa=d.get(fa)
if d.get(fa,-1)==-1:
flag=False
print(fa)在O(1)时间删除链表结点
class Solution {
public:
void deleteNode(ListNode* node) {
auto p = node->next;
node->val = p->val;
node->next = p->next;
// 这两步的作用就是将 *(node->next) 赋值给 *node，所以可以合并成一条语句：
// *node = *(node->next);
delete p;
}
};反转链表
递推写法
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre=null;
ListNode cur=head;
while(cur!=null){
ListNode next=cur.next;
cur.next=pre;
pre=cur;
cur=next;
}
return pre;
}
}递归写法
class Solution {
public ListNode reverseList(ListNode head) {
if(head==null || head.next==null)return head;
ListNode tail=reverseList(head.next);
head.next.next=head;
head.next=null;
return tail;
}
}python库
from queue import LifoQueue
stack=LifoQueue()
for i in range(5):
stack.put(i)
while not stack.empty():
print(stack.get(),end=' ')c++数组实现
// tt表示栈顶
int stk[N], tt = 0;
// 向栈顶插入一个数
stk[ ++ tt] = x;
// 从栈顶弹出一个数
tt -- ;
// 栈顶的值
stk[tt];
// 判断栈是否为空，如果 tt > 0，则表示不为空
if (tt > 0)
{}python实现栈：
//其实一行新建一个空数组就可以用append和pop实现
class Stack():
def __init__(self):
self.stk=[]
def put(self,x):
self.stk.append(x)
def get(self):
return self.stk.pop()
def empty(self):
return False if self.stk else True
class Stack1():
def __init__(self,N=10**5):
self.N=N
self.stk=[0]*N
self.cur=0
def put(self,x):
self.stk[self.cur]=x
self.cur+=1
def get(self):
self.cur-=1
return self.stk[self.cur]
def empty(self):
return False if self.cur else True
stack=Stack()
for i in range(5):
stack.put(i)
while not stack.empty():
print(stack.get(),end=' ')
stack1=Stack1()
for i in range(5):
stack1.put(i)
while not stack1.empty():
print(stack1.get(),end=' ')class UnionFindSet():
def __init__(self,nodes):
self.fatherMap={}
self.sizeMap={}
for node in nodes:
self.fatherMap[node]=node
self.sizeMap[node]=1
def findFather(self,node):
father =self.fatherMap[node]
if node!=father:
father=self.findFather(father)
self.fatherMap[node]=father
return father
def union(self,a,b):
if a is None or b is None:
return
aFather=self.findFather(a)
bFather=self.findFather(b)
if aFather!=bFather:
aSize=self.sizeMap[aFather]
bSize=self.sizeMap[bFather]
if aSize<=bSize:
self.fatherMap[aFather]=bFather
self.sizeMap[bFather]=aSize+bSize
self.sizeMap.pop(aFather)
else:
self.fatherMap[bFather] = aFather
self.sizeMap[aFather] = aSize + bSize
self.sizeMap.pop(bFather)
def isSameSet(self,a,b):
return self.findFather(a)==self.findFather(b)struct tree{
int l,r;
long long pre,add;
}t[4*maxn+2];
void bulid(int p,int l,int r){
t[p].l=l;t[p].r=r;
if(l==r){
t[p].pre=a[l];
return;
}
int mid=l+r>>1;
bulid(p*2,l,mid);
bulid(p*2+1,mid+1,r);
t[p].pre=t[p*2].pre+t[p*2+1].pre;
}
void spread(int p){
if(t[p].add){
t[p*2].pre+=t[p].add*(t[p*2].r-t[p*2].l+1);
t[p*2+1].pre+=t[p].add*(t[p*2+1].r-t[p*2+1].l+1);
t[p*2].add+=t[p].add;
t[p*2+1].add+=t[p].add;
t[p].add=0;
}
}
void change(int p,int x,int y,int z){
if(x<=t[p].l && y>=t[p].r){
t[p].pre+=(long long)z*(t[p].r-t[p].l+1);
t[p].add+=z;
return;
}
spread(p);
int mid=t[p].l+t[p].r>>1;
if(x<=mid) change(p*2,x,y,z);
if(y>mid) change(p*2+1,x,y,z);
t[p].pre=t[p*2].pre+t[p*2+1].pre;
}
long long ask(int p,int x,int y){
if(x<=t[p].l && y>=t[p].r) return t[p].pre;
spread(p);
int mid=t[p].l+t[p].r>>1;
long long ans=0;
if(x<=mid) ans+=ask(p*2,x,y);
if(y>mid) ans+=ask(p*2+1,x,y);
return ans;
}
#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
int a[maxn+2];
int main(){
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
bulid(1,1,n);
for(int i=1;i<=m;i++){
int q,x,y,z;
scanf("%d",&q);
if(q==1){
scanf("%d%d%d",&x,&y,&z);
change(1,x,y,z);
}
else {
scanf("%d%d",&x,&y);
cout<<ask(1,x,y)<<endl;
}
}
return 0;
}class Node():
def __init__(self,l,r):
self.l=l
self.r=r
self.sum=0
self.add=0
def pushUp(p):
tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum
def build(p,l,r):
tree[p]=Node(l,r)
if l==r:
tree[p].sum=a[l]
return
mid=l+r>>1
build(p<<1,l,mid)
build(p<<1|1,mid+1,r)
pushUp(p)
def query(p, x, y):
if x<=tree[p].l and tree[p].r<=y:
return tree[p].sum
spread(p)
ans=0
mid=tree[p].l+tree[p].r>>1
if x<=mid:ans+=query(p << 1, x, y)
if y>mid:ans+=query(p << 1 | 1, x, y)
return ans
def spread(p):
# 如果懒标记不为0，就将其下传，修改左右儿子维护的值
if tree[p].add:
tree[p<<1].sum+=(tree[p<<1].r-tree[p<<1].l+1)*tree[p].add
tree[p<<1|1].sum+=(tree[p<<1|1].r-tree[p<<1|1].l+1)*tree[p].add
# 为该节点的左右儿子打上标记
tree[p<<1].add+=tree[p].add
tree[p<<1|1].add+=tree[p].add
# 下传之后将该节点的懒标记清0
tree[p].add=0
def change(p,x,y,k):
# 被覆盖的话，就对其进行修改
if x<=tree[p].l and tree[p].r<=y:
tree[p].sum+=(tree[p].r-tree[p].l+1)*k
# 打上懒标记
tree[p].add+=k
return
# 如果发现没有被覆盖，那就需要继续向下找
# 考虑儿子所维护的区间可能因为懒标记的存在而没有修改，因此将懒标记下放
spread(p)
mid=tree[p].l+tree[p].r>>1
# 如果要修改的区间覆盖了左儿子，就修改左儿子
if x<=mid:
change(p<<1,x,y,k)
# 右儿子同理
if y>mid:
change(p<<1|1,x,y,k)
# 最终维护的值等于左儿子的值+右儿子的值
tree[p].sum=tree[p<<1].sum+tree[p<<1|1].sum
N=10**5+5
tree=[Node(0,0) for i in range(N<<2)]
n,m=map(int,input().split())
a=[0]+list(map(int,input().split()))
build(1,1,n)
#要进行的操作
for _ in range(m):
aaa=list(map(int,input().split()))
if aaa[0]==1:
change(1,aaa[1],aaa[2],aaa[3])
else:
print(query(1,aaa[1],aaa[2]))def mul(a,b):
n,x=len(a),len(a[0])
x,m=len(b),len(b[0])
c=[[0]*m for i in range(n)]
for i in range(n):
for j in range(m):
for k in range(x):
c[i][j]+=a[i][k]*b[k][j]
return c
a=[[1,2],[3,4]]
b=[[5,6],[7,8]]
print(mul(a,b))
# [[19, 22], [43, 50]]给定 n 个整数 a1,a2,⋅⋅⋅,ana1,a2,···,an，求它们两两相乘再相加的和
n=int(input())
l=list(map(int,input().split()))
s=sum(l)
fang=0
for i in l:
fang=fang+(i**2)
print((s**2-fang)//2)
a1*a2+a2*a3+…+a1*an={(a1+…+an)^2 - (a1^2+a2^2+…+an^2)}/2
从2到n枚举，依次把质数的倍数删掉，剩下的就是质数
for(int i=2;i<=n;i++){
if(!st(i)){
primes[cnt++]=n;
for(int j=i+i;j<=n;j+=i)st[j]=true;
}
}优化后叫线性筛指数
1—n中有n/logn个质数
只筛掉质数的倍数，不筛合数的倍数
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 ... i
i=2 primes=[2] 4
i=3 primes=[2,3] 6 9
i=4 [2,3]
i=5
i=6
i=7
没必要写j<cnt,j因为在到达一定会停下来
如果i为合数，则i % primes[j] == 0一定会成立，跳出循环
如果i为质数，则i刚添加进质数表，在i % primes[j] == 0处跳出循环
//c++版本
int primes[N], cnt; //primes[]存储所有素数
bool st[N]; //st[x]存储x是否被筛掉
void get_primes(int n){
for (int i = 2; i <= n; i ++ ){
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] <= n / i; j ++ ){
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}//bing版本
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1000000; // 假设我们要找出100以内的素数
bool isprime[MAXN + 1]; // 用来标记每个数是否是素数，初始为false
vector<int> primes; // 用来存储素数表
void linear_sieve(int n) { // 线性筛素数的函数，参数n表示要筛到多少
for (int i = 2; i <= n; i++) { // 从2开始遍历每个数
if (!isprime[i]) { // 如果当前数没有被划掉，说明它是素数
primes.push_back(i); // 把它加入素数表
}
for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) { // 遍历素数表中的每个素数
isprime[i * primes[j]] = true; // 用当前数乘以素数来划掉合数
if (i % primes[j] == 0) break; // 如果当前数能被素数整除，就停止遍历，保证每个合数只被其最小质因数筛掉
}
}
}
int main() {
linear_sieve(MAXN); // 调用线性筛素数的函数，筛出100以内的素数
cout << primes.size() <<' ';
// cout << "The primes within " << MAXN << " are:" << endl;
// for (int p : primes) { // 输出素数表中的每个素数
// cout << p << " ";
// }
// cout << endl;
return 0;
}def getPrimes(x):
for i in range(2,x+1):
if not st[i]:primes.append(i)
for j in range(len(primes)):
if i*primes[j]>x:break
st[i*primes[j]]=True
if i%primes[j]==0:break
N=11
st=[False]*(N+1)
primes=[]
getPrimes(N)
print(primes)因式分解n的阶乘2<=n<=10**6
for(int i=0;i<cnt;i++){
int p=primes[i];
int s=0;
for(int j=n;j;j/=p)s+=j/p;
printf("%d %d\n",p,s);
}def get_primes(x):
for i in range(2,x):
if st[i]:
primes.append(i)
for j in range(len(primes)):
if primes[j]*i>x:
break
st[primes[j]*i]=False
if i%primes[j]==0:
break
N=10**6
st=[True]*(N+1)
primes=[]
get_primes(N)
n=5
for i in primes:
if i>n:
break
cnt=0
j=n
while j:
cnt+=j//i
j//=i
print(f'{i} {cnt}')在[L,R]区间中筛出质数 找到小于math.sqrt(R)+1的质数primes1，用primes1乘一个数得到[L,R]区间内的合数并且筛去，剩下的数就是质数。 时间复杂度:
O((R-L+1)*((R-L+1)/2+(R-L+1)/3+(R-L+1)/4+...+(R-L+1)/n)
=>
O((R-L+1)*loglogn得到[L,R]范围内p的最小倍数p0:
p0=math.ceil(l/p)*p
p0=max(2p,math.ceil(l/p)*p)math.floor(l/p)==math.ceil((l+p-1)/p)int gcd(int a, int b){
return b ? gcd(b, a % b) : a;
}def gcd(a,b):
return gcd(b,a%b) if b else adef lcm(a,b):
return a*b//gcd(a,b)// 求x, y，使得ax + by = gcd(a, b)
int exgcd(int a, int b, int &x, int &y){
if (!b){
x = 1; y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= (a/b) * x;
return d;
}
两个同等长度的数组，若两个数组同为降序或升序，对位相乘的值最大，若为降序乘升序，则值最小
N=P1a1+P2a2+...+pkak
(a1+1)(a2+1)...(ak+1)
(1+p1+p12+...+p1a1)(1+p2+p22+...+p2a2)...(1+pk+pk2+...+pka2)
输入n
42
输出
3
20 26 41
def fast_power(a,b,c):
ans=1
a%=c
while b:
if b&1:
ans=(a*ans)%c
a=(a*a)%c
b>>=1
return ans异或为0必败
不为零必胜
编程思想
第一二项为1，后面每项等于前两项和，求第n项
dp[i]=dp[i-1]+dp[i-2]
边界条件是
dp[0]=1,dp[1]=1
def fib(n):
dp=[0]*n
dp[0],dp[1]=1,1
for i in range(2,n):
dp[i]=dp[i-1]+dp[i-2]
return dp[n-1]
print(fib(50))爬楼梯：给定一个整数 n ，表示楼梯的阶数，每次可以爬 1 或 2 阶，求有多少种不同的方法可以爬到楼顶。
def climbStairs( n: int) -> int:
# 初始化数组
d = [0] * (n + 1)
# 边界条件
d[0] = 1
d[1] = 1
# 状态转移方程
for i in range(2, n + 1):
d[i] = d[i - 1] + d[i - 2]
# 返回结果
return d[n]
print(climbStairs(6))
print(climbStairs(7))给定一个 m x n 的网格，从左上角开始，每次只能向右或者向下移动一步，到达右下角有多少种不同的路径。
def uniquePaths(m: int, n: int) -> int:
# 初始化二维数组
dp = [[0 for _ in range(n)] for _ in range(m)]
# 边界条件
for i in range(m):
dp[i][0] = 1
for j in range(n):
dp[0][j] = 1
# 状态转移方程
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
# 返回结果
return dp[m-1][n-1]
print(uniquePaths(2,2))
print(uniquePaths(3,20))最小路径和：给定一个 m x n 的网格，其中每个格子填写了非负整数，从左上角开始，每次只能向右或者向下移动一步，找到一条到达右下角的路径，使得路径上经过的数字之和最小。
dp [i] [j] = min (dp [i-1][j],dp[i][j-1]) + grid[i][j]
边界条件是第一行和第一列需要累加前面的数字之和。
def minPathSum(grid) -> int:
# 初始化二维数组
m = len(grid)
n = len(grid[0])
dp = [[0 for _ in range(n)] for _ in range(m)]
# 边界条件
dp[0][0]=grid[0][0]
for i in range(1,m):
dp[i][0]=dp[i-1][0]+grid[i][0]
for j in range(1,n):
dp[0][j]=dp[0][j-1]+grid[0][j]
# 状态转移方程
for i in range(1,m):
for j in range(1,n):
dp[i][j] = min(dp[i-1][j],dp[i][j-1]) + grid[i][j]
# 返回结果
return dp[m-1][n-1]
l=[
[1,2,3,4,5,6,7],
[1,2,3,4,5,6,7],
[1,2,3,4,5,6,7],
[1,2,3,4,5,6,7],
[1,2,3,4,5,6,7],
]
print(minPathSum(l))f[i][j] = f[i][j-1] + f[i-j][j];
int m, n;
cin >> m >> n;
memset(f, 0, sizeof f);
f[0][0] = 1;
for(int i = 0; i <= m; i ++ ){
for(int j = 1; j <= n; j ++ ){
f[i][j] = f[i][j-1];
if(i >= j){
f[i][j] = f[i][j-1] + f[i-j][j];
}
}
}
cout << f[m][n] << endl;def lengthOfLIS(nums:list) -> int:
# 初始化数组
dp = [1] * len(nums)
# 状态转移方程
for i in range(1, len(nums)):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j]+1)
# 返回结果
return max(dp)
l=[1,2,3,4,6,5,8,7,8]
print(lengthOfLIS(l))六个苹果一袋或八个苹果一袋子，某个数量是否可以实现
用最大数量的8个一袋，剩下的用6个装，当剩下的剩下24以上时，返回不可能，因为24个可以用8来装
给定一个字符串由L和R组成，每次操作可以将L变为R，或将R变为L，令L均在R左侧，求最少操作次数。
暴力枚举每个分界点，左侧操作为L，右侧操作为R
优化：
前缀和数组记录L及R个数
查询很麻烦时要用优化，前缀或者差分
给定一个矩阵，找出其中边都为1的最大正方形
n2子矩阵规模n4
n*n矩阵，有n*n个点，随机找两个点作为矩形对角点坐标，n2*n2n2子矩阵正方形规模n3
随便点一个点n2,边长从1到遇到边界，n2*n
用二进制凑
先凑出01发生器
-
给定一个随机返回1-5整数的函数r1_5，完成一个函数等概率返回r0_1
-
给定一个随机返回1-5整数的函数r1_5，完成一个函数等概率返回r1_7
-
给定一个随机返回a-b整数的函数fa_b，完成一个函数等概率返回fc_d
-
给定一个返回0概率为p，返回1概率为1-p的函数，完成一个函数等概率返回f0_1
给定一个非负整数n，生成二叉树结构的数目
括号是否完整合法
count=0从左到右扫描，遇到左括号count++，遇到右括号count–,count小于0的时候，不合法，最后count=0
至少添加多少个括号
count
给定一个数组，求差值为2的数字对
遍历到一个数，找它的配对
两个数组移动元素，平均值均增加
只能由平均值大的数组取小于平均值的数移向另一个元素，每次取最小，这样大数组平均值变大最大，小数组平均值提升最小
给定两个数组，
无序元素的栈借助一个栈变为有序的，栈顶元素最大
返回方法数
-
给定一个非负矩阵，行列均按从小到大排列，返回是否存在某个值
-
返回某个元素数量最多的行，
1000000*4
4*1000000
两个辅助数列分别记录左右最大值
优化后双指针，移动小的指针
一个数组分为左右两部分，令每部分最大值之差绝对值最大
最大值减左右两个小的
字符串从前移到后形成旋转词，判断是否为互为旋转词
制造咖啡机数组
n个人
a分钟洗杯子
挥发时间
求最短时间
矩阵快速幂