Hexo
0%

算法模板

Posted on Edited on In
算法模板

算法模板(肌肉记忆熟练度)

排列组合枚举

next_permutation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#next_permutation
def nextP(index):
    for t in range(index):
        if n <= 1:
            return
        for i in range(n - 2,-1,-1):
            if s[i] < s[i + 1]:
                for j in range(n - 1, i ,-1):
                    if s[j] > s[i]:
                        s[i],s[j] = s[j],s[i]
                        s[i+1:] = sorted(s[i + 1:])
                        break
                break
            else:
                if i == 0:
                    s.sort()


n = int(input())
index = int(input())
s = [int(i) for i in input().split()]

nextP(index)
print(' '.join(map(str,s)))

pre_permutation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#pre_permutation
def preP(index):
    global s 
    for t in range(index):
        if n <= 1:
            return
        for i in range(n - 2,-1,-1):
            if s[i] > s[i + 1]:
                for j in range(n - 1, i ,-1):
                    if s[j] < s[i]:
                        s[i],s[j] = s[j],s[i]
                        s[i+1:] = sorted(s[i + 1:],reverse = True)
                        break
                break
            else:
                if i == 0:
                    s = sorted(s,reverse = True)


n = int(input())
index = int(input())
s = [int(i) for i in input().split()]
preP(index)
print(' '.join(map(str,s)))

递归实现排列型枚举

1
2
3
4
5
6
#递归实现排列型枚举
from itertools import permutations
n = int(input())
s = [i for i in range(1,n+1)]
for var in permutations(s):
    print(' '.join(map(str,var)))

递归实现指数型枚举

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#92. 递归实现指数型枚举
n = int(input())
vis = [False]*n
def dfs(index):
    if index == n:
        res = []
        for i in range(n):
            if vis[i]:
                res.append(str(i + 1))
        print(' '.join(res))
        return
    #两种情况
    vis[index] = True
    dfs(index + 1)
    vis[index] = False
    dfs(index + 1)

dfs(0)

递归实现组合型枚举

1
2
3
4
5
6
#递归实现组合型枚举
from itertools import combinations
n,m = map(int,input().split())
arr = [i for i in range(1,n+1)]
for var in combinations(arr,m):
    print(' '.join(map(str,var)))

RMQ算法(ST表)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#ST算法(索引版)
#返回最大值索引版
from math import log as log
def ST_prework(n):
    for i in range(n):
        f[i][0] = i  #初始区间长度为2^0的阶段
    t = int(log(n,2)) + 1
    for j in range(1,t):
        for i in range(n - (1<<j) + 1):
            a = f[i][j-1]
            b = f[i + (1<<(j-1))][j-1]
            if arr[a] >= arr[b]: #这里一定要注意，一定是大于等于，因为如果两个数相等，我们要选前面一个，这样保证后面那个一样大小的数在需要时也能被选到
                f[i][j] = a
            else:
                f[i][j] = b


def ST_query(L,R):
    k = int(log(R - L + 1,2))
    a = f[L][k]
    b = f[R - (1<<k) + 1][k]
    if arr[a] >= arr[b]:
        return a
    else:
        return b
    


n,m = [int(i) for i in input().split()]
arr = [int(i) for i in input().split()]
f = [[0]*(n+1) for i in range(n+1)]

data = []
for i in range(m):
    temp = input().split()
    data.append((int(temp[0]),int(temp[1])))
    
ST_prework(n) #预处理

for i in range(m):
    print(arr[ST_query(data[i][0]-1,data[i][1]-1)])

并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#基于字典构建的一个链式树结构
class UFS(object):
    """并查集"""
    def __init__(self, n):
        """初始化两个字典，一个保存节点的父节点，另外一个保存父节点的大小
        初始化的时候，将节点的父节点设为自身，size设为1"""
        self.father = {}                                  #初始父节点可以设置为-1或它自己，这里设置为它自己
        self.size = {}                                    #记录根的规模
        self.twigs = set()                                     #记录连枝
        self.root_num = n                                #设置初始根数                    

        for node in range(1,n+1):
            self.father[node] = node                      #初始父节点可以设置为-1或它自己，这里设置为它自己
            self.size[node] = 1

    def findRoot(self, node):                                #查找根节点
        """使用递归的方式来查找父节点         ##查找根节点

        在查找父节点的时候，顺便把当前节点移动到父节点上面  
        这个操作算是一个优化
        """
        father = self.father[node]
        if(node != father):
            father = self.findRoot(father)
        self.father[node] = father                     #优化，把经过的点都直接连接根节点
        return father

    def is_same_set(self, node_a, node_b):
        """查看两个节点是不是在一个集合里面"""
        return self.findRoot(node_a) == self.findRoot(node_b)

    def union(self, node_a, node_b):
        """将两个集合合并在一起"""
        root_a = self.findRoot(node_a)
        root_b = self.findRoot(node_b)

        if(root_a != root_b):                               #如果根节点相同则(已经合并在一起)
            if(self.size[root_a] >= self.size[root_b]):                   #如果根节点，判断所连接节点的根节点规模哪一个更大，用更大规模的根节点作为连接节点
                self.father[root_b] = root_a                 #连接节点
                self.size[root_a] += self.size[root_b]  #更新深度
            else:
                self.father[root_a] = root_b                #连接节点
                self.size[root_b] += self.size[root_a]   #更新深度
            self.root_num -= 1                                    #若合并成功，总根数减一
        
        else:                                               #如果根节点相同则(已经合并在一起)
            """如果根节点相同则说明此时的两个节点已经
            接入一个集合，并且，由于这两个节点之间相连
            说明由这两节点形成了一个闭合的环，同时这两节点成为环的  连枝
            """
            self.twigs.add((node_a,node_b))                       #将连枝加入到集合中
            
        
        
    def countint_of_root(self):                                   #记录合并后的根数
        return self.root_num

    def is_cirle_exist(self):
        if len(self.twigs)!=0:
            return True
        else:
            return False
    def print_twigs(self):
        print(self.twigs)
    
    def twigs_num(self):
        return len(self.twigs)

    
n = int(input())	
ufs = UFS(n)
    
k = int(input())
for i in range(k):
    a,b = map(int,input().split())
    ufs.union(a,b)
		
print(ufs.root_num)  # True 根数

单源最短路径

SPFA算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#SPFA算法
def SPFA(start):
    queue = [start]
    inq = [False]*(n+1)  #判断是否在队列中
    dis = [float('inf')]*(n+1)
    dis[start] = 0
    inq[start] = True     #这是优化点，避免重复入队
    while queue:
        
        sam = queue.pop(0)
        inq[sam] = False

        if sam not in link.keys(): #防止节点孤立
            continue
        
        for node in link[sam]:
            if dis[node] > dis[sam] + link[sam][node]:
                dis[node] = dis[sam] + link[sam][node]
                if inq[node] == True:  #如果在队列中则不管他
                    continue
                inq[node] = True
                queue.append(node)

    return dis


n,m,s,t = map(int,input().split())

link = {}
for i in range(m):
    a,b,c = map(int,input().split())
    if a not in link.keys():
        link[a] = {b:c}
    else:
        if b not in link[a].keys():
            link[a].update({b:c})
        else:
            if c < link[a][b]:
                link[a][b] = c
    
    if b not in link.keys():
        link[b] = {a:c}
    else:
        if a not in link[b].keys():
            link[b].update({a:c})
        else:
            if c < link[b][a]:
                link[b][a] = c


dis = SPFA(s)
#print(parent)
print(dis[t])

dijkstra算法(优先队列实现)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#迪科斯彻算法(优先队列)
import heapq #注意，优先队列是传入的一个元组，而元组的第一个值决定了该元组的优先值
def dijkstra(start):
    pqueue = []
    heapq.heappush(pqueue,(0,start))     #使用heapq中的heappush方法来读入一个元组
    vis = [False]*(n+1)                  #(距离,节点)的形式
    dis = [float('inf')]*(n+1)
    dis[start] = 0
    parent = [0]*(n+1)


    while pqueue:
        sam = heapq.heappop(pqueue)  #取出队头
        curNode = sam[1]  
        curDis = sam[0]   #取出的就是当前最短路径
        vis[curNode] = True  #取出队列后才算使用过

        if curNode not in link.keys(): #防止节点孤立状态
            continue
        for node in link[curNode]:
            if vis[node] == False:
                if curDis + link[curNode][node] < dis[node]:
                    heapq.heappush(pqueue,(curDis + link[curNode][node],node))
                    parent[node] = curNode
                    dis[node] = curDis + link[curNode][node]

    return parent,dis

n,m,s,t = map(int,input().split())

link = {}
for i in range(m):
    a,b,c = map(int,input().split())
    if a not in link.keys():
        link[a] = {b:c}
    else:
        if b not in link[a].keys():
            link[a].update({b:c})
        else:
            if c < link[a][b]:
                link[a][b] = c
    
    if b not in link.keys():
        link[b] = {a:c}
    else:
        if a not in link[b].keys():
            link[b].update({a:c})
        else:
            if c < link[b][a]:
                link[b][a] = c


parent,dis = dijkstra(s)
#print(parent)
print(dis[t])

二分算法

二分法求最大满足（最小值最大）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#二分求最大满足
def isok(index):
    if s[index] <= goal:
        return True
    return False
    

def bin_search():
    left = 0
    right = len(s) - 1
    while left < right:
        mid = left + right + 1 >> 1
        if isok(mid):
            left = mid
        else:
            right = mid - 1

    # if s[left] != goal return -1 查不到
    
    return left


s = [int(i) for i in input().split()]
goal = int(input())
print(bin_search())

二分法求最小满足（最大值最小）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#二分求最小满足
def isok(index):
    if s[index] >= goal:
        return True
    return False
    

def bin_search():
    left = 0
    right = len(s) - 1
    while left < right:
        mid = left + right >> 1
        if isok(mid):
            right = mid
        else:
            left = mid + 1

    # if s[left] != goal return -1 查不到
    
    return left


s = [int(i) for i in input().split()]
goal = int(input())
print(bin_search())

矩阵快速幂(斐波那契前n项和为例)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#矩阵快速幂
#斐波那契前n项和
def mul_1(a,b):  #一维与二维
    temp = [0]*N
    for i in range(3):
        for j in range(3):
            temp[i] = (temp[i] + a[j]*b[j][i])%m
    return temp
    
def mul_2(a,b):  #二维与二维
    temp = [[0]*(N) for i in range(N)]
    for i in range(N):
        for j in range(N):
            for k in range(N):
                temp[i][j] = (temp[i][j] + a[i][k]*b[k][j])%m;
    return temp

n,m = map(int,input().split())
N = 3 #矩阵的大小
f = [1,1,1]
       
A = [[0,1,0],
     [1,1,1],
     [0,0,1]]
     
p = n - 1
while p:
    if p & 1 == 1:
        f = mul_1(f,A)
    A = mul_2(A,A)
    p >>= 1

print(f[2])

状态压缩DP

旅行商问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#最短Hamilton路径
#二进制状态压缩
n = int(input())
cost = []
for i in range(n):
    cost.append([int(i) for i in input().split()])

f = [[float('inf')]*(n + 1) for i in range(1 << n)]

f[1][0] = 0
for i in range(1,1 << n):
    for j in range(n):
        if (i >> j) & 1 == 1:
            for k in range(n):
                if (i >> k) & 1 == 1:
                    f[i][j] = min(f[i][j],f[ i ^ (1 << j)][k] + cost[k][j])

print(f[(1 << n) - 1][n - 1])

逆序对

归并排序版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#归并排序版
#小朋友排队
import copy
#利用归并计算  逆序数
def merge(s):
    n = len(s)
    if n <= 1 :
        return s
    mid = n//2
    s_left = merge(s[:mid])
    s_right = merge(s[mid:])

    i,j = 0,0

    result = []
    while i<len(s_left) and j < len(s_right):
        if s_left[i].high > s_right[j].high:
            result.append(s_right[j])
            s_right[i].hate += (len(s_left)-i)
            j += 1
        else:
            result.append(s_left[i])
            i += 1

    
    result += s_right[j:]
    result += s_left[i:]
    
    '''
    if i < len(s_left):
        result += s_left[i:]
        inNum += len(s_right)*(len(s_left)-i)+len(s_left)-1-i

    else:
        result += s_right[j:]
        inNum += len(s_left)*(len(s_right)-j)+len(s_right)-1-j
    '''
    return result

def baoli(s):
    global inNum
    for i in range(len(s)-1):
        for j in range(i+1,len(s)):
            if s[i] > s[j]:
                inNum += 1


def merge_sort1(s):
    global inNum
    n = len(s)
    if n <= 1:
        return s
    mid = n//2
    s_left = merge_sort1(s[:mid]) 
    s_right = merge_sort1(s[mid:])


    result = []
    while s_left and s_right:
        if s_left[0].high > s_right[0].high:#左侧部分都是排好序的,如果左侧出现一个数
            s_right[0].hate += len(s_left)   #比右侧的那个数大，则左侧这个数以后都比右侧这个数大
            for i in range(len(s_left)):     
                s_left[i].hate += 1          #此时左边这些数与右边这一个数都有对应关系
            result.append(s_right.pop(0))    #因此和这个数存在逆序关系
        else:
            result.append(s_left.pop(0))

    return result+s_left+s_right            #剩下的数字对不上说明原来就排好有序的


def merge_sort2(s):
    global inNum
    n = len(s)
    if n <= 1:
        return s
    mid = n//2
    s_left = merge_sort2(s[:mid]) 
    s_right = merge_sort2(s[mid:])


    result = []
    while s_left and s_right:
        if s_left[0].high <= s_right[0].high:
            s_right[0].hate += len(s_left)
            result.append(s_right.pop(0))
        else:
            result.append(s_left.pop(0))

    return result+s_left+s_right

class Struct():
    def __init__(self):
        self.high = 0
        self.hate = 0

aHate = 0
num = int(input())
s = []
for i in input().split():
    temp = Struct()
    temp.high = int(i)
    s.append(temp)
merge_sort1(s)

for i in range(num):
    aHate += (1+s[i].hate)*s[i].hate // 2
print(aHate)

树状数组版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#树状数组求逆序对
#小朋友排队
def lowbit(x):
    return x & -x
def trAdd(x,v):
    i = x
    while i <= N:
        tr[i] += v
        i += lowbit(i)

def query(x):
    i = x
    res = 0
    while i > 0:
        res += tr[i]
        i -= lowbit(i)
    return res

N = 100010
tr = [0]*(N+1)
ans = 0

n = int(input())
nums = [0]*(n + 1)
data = [0] + [int(i) for i in input().split()]


for i in range(1,n+1):
    nums[i] += query(N) - query(data[i])
    trAdd(data[i],1)

tr = [0]*(N+1)
for i in range(n,0,-1):
    nums[i] += query(data[i] - 1)
    trAdd(data[i],1)

    ans += (1 + nums[i])*nums[i] // 2

print(ans)

扩展欧几里得算法

1
2
3
4
5
6
7
8
9
10
#ax+by = gcd(a,b)    
def exGcd(a, b):
    """
    a: 模的取值
    b: 想求逆的值
    """
    if (b == 0):
        return 1, 0, a
    x, y, gcd = exGcd(b, a % b)
    return y, x-a//b*y, gcd

排序算法

归并排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#归并排序
def merge_sort(s):
    n =len(s)
    if n<=1:
        return s
    mid = n//2
    s_left = merge_sort(s[:mid])
    s_right = merge_sort(s[mid:])


    result = []
    i,j = 0,0
    while i<len(s_left) and j<len(s_right):
        if s_left[i]<s_right[j]:
            result.append(s_left[i])
            i+=1
        else:
            result.append(s_right[j])
            j+=1
    result+=s_left[i:]    #python不怕此处越界报错
    result+=s_right[j:]   #python，越界为空,不怕此处越界报错
    return result





if __name__ == "__main__":
    s = [1,2,34,25,44,3254,34,56,46,54,7,56,67,342,56,42,3]
    print(s)
    s_n = merge_sort(s)
    print(s_n)

计数排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#计数排序
def counting_sort(s):
    a = [0]*10000
    n = len(s)
    result = [0]*n
    for i in s:
        a[i]+=1
    for i in range(1,10000):
        a[i] += a[i-1]                      #此操作使得a值为对应s 结果顺序值

    for i in range(n):                      #键值对套键值对
        result[a[s[i]]-1] = s[i]
        a[s[i]]-=1                          #由于重复数的结果位经上一部变成最高位
                                            #此步骤使重复相后置一位
    return result






if __name__ == "__main__":
    s = [34,32,1,2,7,3,34,34,5,43,56,45]
    s_n = counting_sort(s)
    print(s_n)

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#快速排序双全等定位
def quick_sort(s,first,last):
    if first >= last:
        return
    i = first
    j = last
    base = s[first]
    #两全等状态时,快速排序起始项一定要从非基数base侧开始,不然基数无法调换
    while i < j:            #快速排序起始项一定要从非基数base侧开始,不然基数无法调换
        while i < j and s[j] >= base: #注意一定要加'='号，不然会进左右呼唤的死循环
            j -= 1
        s[i],s[j] = s[j],s[i]  


        while i < j and s[i] <= base: #注意一定要加'='号，不然会进左右呼唤的死循环
            i += 1
        s[i],s[j] = s[j],s[i]
        

    quick_sort(s,first,i-1)
    quick_sort(s,j+1,last)



if __name__ == "__main__":
    s = [12,312,432,5,4,6,546,76,23,567,67,8,5,64]
    print(s)
    quick_sort(s,0,len(s)-1)
    print(s)

冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#冒泡排序
def maopao(s):
    n = len(s)
    for i in range(0,n-1):
        for j in range(0,n-i-1):
            if s[j]>s[j+1]:
                s[j],s[j+1] = s[j+1],s[j]






if __name__ == "__main__":
    s = [12,234,2133,34,5456,6]
    maopao(s)
    print(s)

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#希尔排序
#有违次次间隔排列，且反正排序版本
def shell_sort(s):
    n = len(s)
    gap = n//2
    while gap>=1:
        for i in range(gap,n):       #此处为每次取后1位往前插，并非取后间隔位往前插，但是每次间隔为的数都能被取到
            j = i
            while j>0:
                if s[j]<s[j-gap]:
                    s[j],s[j-gap] = s[j-gap],s[j]
                    j -= gap
                else:
                    break
        gap//=2




if __name__ == "__main__":
    s = [12,332,45,34,123,13,487,34,546,234,34,54,36]
    print(s)
    shell_sort(s)
    print(s)

选择算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#选择排序
def choose_sort(s):
    n = len(s)
    for i in range(0,n-1):
        min_index = i
        for j in range(i+1,n):
            if s[j]<s[min_index]:
                min_index = j
        s[i],s[min_index] = s[min_index],s[i]
    





if __name__ == "__main__":
    s = [12,233,4,45,546,67,45,24]
    print(s)
    choose_sort(s)
    print(s)

直接插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#直接插入排序,希尔排序的简单版本，对一定有序的数据较快
def insert_sort(s):
    n = len(s)
    for i in range(1,n):
        j = i
        while j>0:
            if s[j]<s[j-1]:
                s[j],s[j-1] = s[j-1],s[j]
                j-=1
            else:
                break








if __name__ == "__main__":
    s = [1,23,432,13,45,768,45,78,89,546,7,34,7,5,3]
    print(s)
    insert_sort(s)
    print(s)

树状数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#树状数组
#动态求连续区间和(树状数组)
def lowbit(x):
    return x & -x

def trAdd(x,v):
    i = x
    while i <= n:
        tr[i] += v
        i += lowbit(i)
        
def query(x):
    res = 0
    i = x
    while i > 0:
        res += tr[i]
        i -= lowbit(i)
    return res



n,m = map(int,input().split())
data = [0] + [int(i) for i in input().split()]

tr = [0]*(n + 1)
for i in  range(1,n + 1):
    trAdd(i,data[i])

for i in range(m):
    k,a,b = map(int,input().split())
    if k == 1:
        trAdd(a,b)
    else:
        print(query(b) - query(a - 1))

凸包

凸包的周长

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#凸包周长
class Struct():
    def __init__(self):
        self.x = 0
        self.y = 0

def slope(a,b):
    if a.x == b.x:
        return float('inf')
    return (a.y - b.y) / (a.x - b.x)

def dotLen(s):
    ans = 0
    for i in range(1,len(s)):
        ans += pow(pow((s[i].y - s[i-1].y),2) + pow((s[i].x - s[i-1].x),2),0.5)
    return ans

def solve():
    #下半部分
    baos1 = []
    baos1.append(datas[0])
    baos1.append(datas[1])
    for i in range(2,n):
        while len(baos1) > 1 and slope(datas[i],baos1[-2]) <= slope(baos1[-1],baos1[-2]):
            del baos1[-1]
        baos1.append(datas[i])


    #上半部分
    baos2 = []
    baos2.append(datas[0])
    baos2.append(datas[1])
    for i in range(2,n):
        while len(baos2) > 1 and slope(datas[i],baos2[-2]) >= slope(baos2[-1],baos2[-2]):
            del baos2[-1]

        baos2.append(datas[i])


    del baos2[-1] #去除上半部分凸包的尾部

    baos2.reverse()
    res = baos1 + baos2
    return res



n = int(input())
datas = []
for i in range(n):
    temp = Struct()
    temp.x,temp.y = map(float,input().split())
    datas.append(temp)

def cmp(x): #先按x后按y进行比较
    return 100000000*x.x + x.y
datas = sorted(datas,key = cmp)

res = solve()
#print(res)
print('%.2f'%dotLen(res))

旋转卡尺

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#凸包
#旋转卡壳
class Struct():
    def __init__(self):
        self.x = 0
        self.y = 0
        
def slope(a,b):
    if a.x == b.x:  #这里a与b的连线垂直坐标轴，斜率为无穷
        return float('inf')
    return (a.y - b.y)/(a.x - b.x)

def merge_sort(datas): #按x为第一，y为第二排序
    n = len(datas)
    if n <= 1:
        return datas
    mid = n // 2
    left = merge_sort(datas[:mid])
    right = merge_sort(datas[mid:])
    result = []
    i,j = 0,0
    while i < len(left) and j < len(right):
        if left[i].x < right[j].x:
            result.append(left[i])
            i += 1
        elif left[i].x > right[j].x:
            result.append(right[j])
            j += 1
        elif left[i].y < right[j].y:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result += left[i:] + right[j:]
    return result

def Cross(u,a,b): #叉积 
    return (a.x - u.x)*(b.y - u.y) - (a.y-u.y)*(b.x - u.x)



 
def solve():
    #下半部分
    baos1 = []
    baos1.append(datas[0])
    baos1.append(datas[1])
    for i in range(2,n):
        while len(baos1)>1 and slope(datas[i],baos1[-2]) <= slope(baos1[-1],baos1[-2]):
            del baos1[-1]
        baos1.append(datas[i])
    '''
    for i in range(len(baos1)):
        print(baos1[i].x,baos1[i].y)
    print('-------------')
    '''
    #上半部分
    baos2 = []
    baos2.append(datas[0])
    baos2.append(datas[1])
    for i in range(2,n):
        while len(baos2)>1 and slope(datas[i],baos2[-2]) >= slope(baos2[-1],baos2[-2]):
            del baos2[-1]
        baos2.append(datas[i])
    ''' 
    for i in range(len(baos2)):
        print(baos2[i].x,baos2[i].y)
    print('-------------')
    '''
    del baos2[-1]#去掉上半部分凸包的尾部(因为尾部已经在下半部分储存,不去头是为了使得能够闭环)
    baos2.reverse()  #为了能够有方向的形成环
    res = baos1 + baos2
    '''
    for var in res:
        print(var.x,var.y)
    '''
    return res

def dotLen(s):
    ans = 0
    for i in range(1,len(s)):
        ans += ((s[i].y - s[i-1].y)**2 + (s[i].x - s[i-1].x)**2)**0.5
        #print(((s[i].y - s[i-1].y)**2 + (s[i].x - s[i-1].x)**2)**0.5)
    return ans

def dotlen(a,b):
    return ((a.y - b.y)**2 + (a.x - b.x)**2)


def kq(s):
    ans = 0
    ps = 2  #设置对踵点
    for i in range(len(s)-1):       #通过叉积求面积以此寻找对踵点
        while Cross(s[i],s[i+1],s[ps]) < Cross(s[i],s[i+1],s[ps+1]):
            ps = (ps+1)%(len(s)-1)  #绕一圈可归零
            #print(i+1,i+2,ps,'=',len(s))
        ans = max(ans,max(dotlen(s[i],s[ps]),dotlen(s[i+1],s[ps])))
    return ans

if __name__ == "__main__":
    n = int(input())
    datas = []
    for i in range(n):
        temp = Struct()
        temp.x,temp.y = [eval(i) for i in input().split()]
        datas.append(temp)

    datas = merge_sort(datas)
    
    '''
    for i in range(n):
        print(datas[i].x,datas[i].y)
    '''
    
    res = solve()
    #print('allLen:',dotLen(res))
    '''
    for i in range(len(res)):
        print(res[i].x,res[i].y)
    '''
    print(kq(res))

线段树

线段树求区间和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#线段树求区间和
带通求连续区间和
class Struct():
    def __init__(self):
        self.left = 0
        self.right = 0
        self.sum = 0

def pushup(curNode):
    tr[curNode].sum = tr[curNode << 1].sum + tr[curNode << 1 | 1].sum

def build(curNode,L,R):
    if L == R:
        tr[curNode].left = L
        tr[curNode].right = R
        tr[curNode].sum = data[R]
        return
    tr[curNode].left = L
    tr[curNode].right = R

    mid = L + R >> 1
    build(curNode << 1,L,mid)
    build(curNode << 1 | 1,mid + 1,R)
    pushup(curNode)

def query(curNode,L,R):
    if tr[curNode].left >= L and tr[curNode].right <= R:
        return tr[curNode].sum
    mid = tr[curNode].left + tr[curNode].right >> 1

    res = 0
    if L <= mid:
        res += query(curNode << 1,L,R)
    if R > mid:
        res += query(curNode << 1 | 1,L,R)
    return res

def modify(curNode,x,v):
    if tr[curNode].left == tr[curNode].right:
        tr[curNode].sum += v
        return
    mid = tr[curNode].left + tr[curNode].right >> 1
    if x <= mid:
        modify(curNode << 1,x,v)
    if x > mid:
        modify(curNode << 1 | 1,x,v)

    pushup(curNode)




n,m = map(int,input().split())
data = [0] + [int(i) for i in input().split()]


tr = [Struct() for i in range(4 * n + 1)]
build(1,1,n)

for i in range(m):
    k,a,b = map(int,input().split())
    if k == 1:
        modify(1,a,b)
    else:
        print(query(1,a,b))

DP子序列

最长公共子序列(朴素)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#最长公共子序列
#朴素
n = int(input())
s1 = [0]+[int(i) for i in input().split()]
s2 = [0]+[int(i) for i in input().split()]

f = [[0]*(n+1) for i in range(n+1)]
for i in range(1,n+1):
    for j in range(1,n+1):
        if s1[i] == s2[j]:
            f[i][j] = max(f[i-1][j-1] + 1,f[i][j])
        else:
            f[i][j] = max(f[i-1][j],f[i][j-1])

print(f[n][n])

最长公共子序列(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#最长公共子序列
#对于互异的两组排列
n = int(input())
s1 = [0]+[int(i) for i in input().split()]
s2 = [0]+[int(i) for i in input().split()]
pos = {} #s2在s1中的位置
for i in range(1,n+1):
    pos[s1[i]] = i

f = [float('inf')]*(n+1)
f[0] = 0
Len = 0
for i in range(1,n+1):
    left = 0
    right = Len

    if pos[s2[i]] > f[Len]:
        Len += 1
        f[Len] = pos[s2[i]]
    else:
        while left < right:
            mid = left + right >> 1
            if f[mid] > pos[s2[i]]:
                right = mid
            else:
                left = mid + 1
        f[left] = min(pos[s2[i]],f[left])

print(Len)

最大子序和(单调队列)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#最大字串和
#单调队列
n,m = map(int,input().split())
arr = [0] + [int(i) for i in input().split()]
preSum = [0]*(n+1)
for i in range(1,n+1):
    preSum[i] = preSum[i-1] + arr[i]
queue = [0]*(n+1)
head = 0
reap = 0
res = -float('inf')
for i in range(1,n+1):
    if i - queue[head] > m: #超过范围（m+1(前缀和要多一位)）的队头弹出(永远用不到的)
        head += 1
    res = max(res,preSum[i] - preSum[queue[head]])
    #队非空
    while head <= reap and preSum[queue[reap]] >= preSum[i]: #弹出无用元素，形成单调队列
        reap -= 1
    reap += 1
    queue[reap] = i #添加

print(res)

最大子序和(DP)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#最大子序列
def mlenSequence(s):
    dp = [0]*len(s)
    dp[0] = s[0]
    mlen = dp[0]
    for i in range(1,len(s)):
        if dp[i-1] < 0:
            dp[i] = s[i]
        else:
            dp[i] = dp[i-1] + s[i]

        if mlen < dp[i]:
            mlen = dp[i]
    return mlen




s = [int(i) for i in input().split()]
mlen = mlenSequence(s)
print(mlen)

最长上升子序列

最长上升子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#最长升降子序列
t = int(input())
for i in range(t):
    n = int(input())
    data = [int(i) for i in input().split()]
        
    res = 1
     
    f = [0]*(n)  
    for i in range(n):
        f[i] = 1
        for j in range(i):
            if data[i] > data[j]:
                f[i] = max(f[i],f[j] + 1)
                    
        res = max(res,f[i])
    
    f = [0]*(n)
    for i in range(n):
        f[i] = 1
        for j in range(i):
            if data[i] < data[j]:
                f[i] = max(f[i],f[j] + 1)
                    
        res = max(res,f[i])
                    
                    
    print(res)

升降子序列铺满问题(贪心与dfs)

为了对抗附近恶意国家的威胁，R国更新了他们的导弹防御系统。

一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单调 下降。

例如，一套系统先后拦截了高度为3和高度为4的两发导弹，那么接下来该系统就只能拦截高度大于4的导弹。

给定即将袭来的一系列导弹的高度，请你求出至少需要多少套防御系统，就可以将它们全部击落。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
def dfs(index,numUp): #当前位置当前上升子序列个数与当前下降子序列个数
    global res
    if numUp > res:
        return 
    
    if index == n:
        res = numUp
        return
    

    #上升子序列中 (用于处理(严格)下降子序列铺满情况(不严格情况不加等号))
    k = 0
    while k < numUp and rearUp[k] < arr[index]:
        k += 1
    temp = rearUp[k]
    rearUp[k] = arr[index]
    if k < numUp:
        dfs(index + 1, numUp)
    else:
        dfs(index + 1, numUp + 1)
    rearUp[k] = temp
    
def solve():
    res = 0
    f = [0]*(n)
    for i in range(n - 1,-1,-1):
        f[i] = 1
        for j in range(n - 1,i,-1):
            if arr[j] <= arr[i]:
                f[i] = max(f[j]+1,f[i])
        res = max(res,f[i])
        
    return res

arr = [int(i) for i in input().split()]
n = len(arr)
rearUp = [0]*(n)

print(solve())

res = float('inf')
dfs(0,0)

print(res)

纯降子序列铺满问题(最长上升子序)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
data = [int(i) for i in input().split()]

n = len(data)

# 求最长下降子序列
res = 0
f = [0]*(n)
for i in range(n - 1,-1,-1):
    f[i] = 1
    for j in range(n - 1,i ,-1):
        if data[j] <= data[i]:
            f[i] = max(f[i],f[j] + 1)

    res = max(res,f[i])

print(res)

# 求用多少各最长下降子序列铺满
res = 0
f = [0]*(n)
for i in range(n):
    f[i] = 1
    for j in range(i):
        if data[j] < data[i]:
            f[i] = max(f[i],f[j] + 1)

    res = max(res,f[i])

print(res)

最小生成树(Kruskal)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#最小生成树
class Struct():
    def __init__(self):
        self.f = 0
        self.t = 0
        self.w = 0

class UFS():
    def __init__(self,n):
        self.father = {}
        self.size = {}
        for i in range(1,n+1):
            self.father[i] = i
            self.size[i] = 1

    def findRoot(self,node):
        father = self.father[node]
        if father != node:
            father = self.findRoot(father)
        self.father[node] = father
        return father

    def union(self,node_a,node_b):
        root_a = self.findRoot(node_a)
        root_b = self.findRoot(node_b)

        if root_a != root_b:
            if self.size[root_a] > self.size[root_b]:
                self.father[root_b] = root_a
                self.size[root_a] += seelf.size[root_b]
            else:
                self.father[root_a] = root_b
                self.size[root_b] = self.size[root_a]
            return True
        else:
            return False


n,m = map(int,input().split())
data = []
for i in range(m):
    a,b,w = map(int,input().split())
    temp = Struct()
    temp.f = a
    temp.t = b
    temp.w = w
    data.append(temp)

data = sorted(data,key = lambda x : x.w)

ufs = UFS(n)
res = 0
for i in range(m):
    if ufs.union(data[i].f,data[i].t):
        n -= 1
        res += data[i].w

if n == 1:
    print(res)
else:
    print('orz')

博弈论(sg函数)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
# 多人sg函数
from collections import deque
def Lin(a,b):
    if a not in link.keys():
        link[a] = {b}
        ind[b] += 1
    else:
        if b not in link[a]:
            ind[b] += 1
            link[a].add(b)

def topSort():
    queue = deque()
    for i in range(1,n+1):
        if ind[i] == 0:
            queue.append(i)
    while queue:
        curNode = queue.popleft()
        
        if curNode not in link.keys():
            continue
        for node in link[curNode]:
            ind[node] -= 1
            sto[node] |= 1 << sg[curNode]
            if ind[node] == 0:
                sg[node] = 0
                while sto[node] & 1:
                    sg[node] += 1
                    sto[node] >>= 1
                queue.append(node)

n,m,k = map(int,input().split())
link = {}
ind = [0]*(n + 1)
for i in range(m):
    a,b = map(int,input().split())
    Lin(b,a)

startNodes = [int(i) for i in input().split()]

sg = [0]*(n + 1)
sto = [0]*(n + 1)
topSort()

res = 0
for i in range(k):
    res ^= sg[startNodes[i]]
    
if res:
    print('win')
else:
    print('lose')

差分约束

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#糖果 差分约束
def SPFA(start):
    queue = [start]
    inq = [False]*(n+1)  #判断是否在队列中
    
    dis[start] = 0
    inq[start] = True     #这是优化点，避免重复入队

    cnt = [0]*(n + 1) #判断负环
    while queue:
        
        sam = queue.pop()
        inq[sam] = False

        if sam not in link.keys():
            continue
        
        for node in link[sam]:
            if dis[node] < dis[sam] + link[sam][node]: #最长路
                dis[node] = dis[sam] + link[sam][node]
                cnt[node] = cnt[sam] + 1

                if cnt[node] >= n + 1:
                    return False
                
                if inq[node] == True:  #如果在队列中则不管他
                    continue
                inq[node] = True
                queue.append(node)

    return True




def add(a,b,t):
    if a not in link.keys():
        link[a] = {b:t}
    else:
        if b not in link[a].keys():
            link[a].update({b:t})
        else:
            link[a][b] = max(link[a][b],t)


n,k = map(int,input().split())
dis = [-float('inf')]*(n+1)

link = {}
for i in range(k):
    x,a,b = map(int,input().split())
    if x == 1:
        add(a,b,0)
        add(b,a,0)
    elif x == 2:
        add(a,b,1)
    elif x == 3:
        add(b,a,0)
    elif x == 4:
        add(b,a,1)
    elif x == 5:
        add(a,b,0)

#超级源点
for i in range(1,n+1):
    add(0,i,1)

res = 0
if SPFA(0):
    for i in range(1,n+1):
        res += dis[i]
    print(res)
else:
    print(-1)

AC自动机

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
# 搜索关键词
from collections import deque
def insert(x):
    global idx
    p = 0
    for var in string:
        t = ord(var) - ord('a')
        if tr[p][t] == 0:
            idx += 1
            tr[p][t] = idx
        p = tr[p][t]

    cnt[p] += 1

def build():
    global num
    queue = deque()
    for i in range(26):
        if tr[0][i] != 0:
            queue.append(tr[0][i])

    while queue:
        sam = queue.popleft()
        nodes_in.append(sam)
        for i in range(26):
            if tr[sam][i] == 0:
                tr[sam][i] = tr[ne[sam]][i]
            else:
                ne[tr[sam][i]] = tr[ne[sam]][i]
                queue.append(tr[sam][i])


N = 10010
S = 55
t = int(input())
for _ in range(t):
    
    
    tr = [[0]*(26) for i in range(N*S)] #26个字母
    cnt = [0]*(N*S)
    ne = [0]*(N*S)
    idx = 0
    
    n = int(input())
    
    for i in range(n):
        string = input()
        insert(i)
    
    nodes_in = deque() #存下每一个入队节点
    build()
    
    goal = input()
    
  
    res = 0
    j = 0
    for var in goal:
        t = ord(var) - ord('a')
        j = tr[j][t]
        p = j
        while p:
            res += cnt[p]
            cnt[p] = 0
            p = ne[p]
    
    print(res)

IDA*

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
from copy import deepcopy
def f():   #每一次
    global s
    res = 0
    for i in range(n - 1):
        if s[i + 1] - s[i] != 1:
            res += 1
    return (res + 2) // 3  #对res向上取整 res + (n - 1)) // n
    
    
def dfs(depth):
    global s,max_depth
    if depth + f() > max_depth:
        return False
    if f() == 0:
        return True
    
    #区间插空
    #不对Len迭代而直接迭代右端点可以减少迭代层数
    for left in range(n):
        for right in range(left,n):
            for end in range(right + 1,n):
                sc[depth] = deepcopy(s)  #该层原本的样子(s用来传递给下一层)
                d2 = end - right
                #进行插空操作（前后换位）
                for i in range(left,left + d2):
                    s[i] = sc[depth][right + 1 + (i - left)]
                for i in range(left + d2,end + 1):
                    s[i] = sc[depth][i - d2]
                        
                if dfs(depth + 1):
                    s = deepcopy(sc[depth])  #回溯
                    return True
                s = deepcopy(sc[depth])  #回溯
                
                
    return False
                



t = int(input())
for i in range(t):
    n = int(input())
    s = [int(i) for i in input().split()]
    sc = [[0] for i in range(5)]
    max_depth = 0
    while max_depth < 5 and dfs(0) == False:
        max_depth += 1
    if max_depth < 5:
        print(max_depth)
    else:
        print("5 or more")

等比数列求和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
def getPrimes(n):
    vis = [False]*(n+1)
    for i in range(2,n + 1):
        if vis[i] == False:
            primes.append(i)
            minp[i] = i
            
        j = 0
        while primes[j]*i <= n:
            vis[primes[j]*i] = True
            minp[primes[j]*i] = primes[j]
            if i % primes[j] == 0:
                break
            j += 1

def power(x,p): 
    res = 1
    while p > 0:
        if p & 1:
            res = res * x % mod
        x = x*x % mod
        p >>= 1
    return res
    
def getSum(p,k): #从1开始的等比数列
    if k==1:
        return 1
    if k & 1 == 0: #偶数情况
        return (1 + power(p,k >> 1)) * getSum(p, k >> 1) % mod
    else:          #奇数情况
        return getSum(p, k - 1) + power(p, k - 1) %mod



a,b = map(int,input().split())
mod = 9901
n = a
minp = [0]*(n + 1)
primes = []
getPrimes(n)

fact = [] #存放质因子
countPrime = [0]*(n + 1) #统计各个质因子个数
while n > 1:
    curPrime = minp[n]
    fact.append(curPrime)
    while n % curPrime == 0:
        countPrime[curPrime] += 1
        n //= curPrime

ans = 1

for var in fact:
    ans = ans * getSum(var,b*countPrime[var] + 1) % mod
    
print(ans)

二次筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
# 二次筛法 
## (写法与y总一致，素数只初始化一次)
### 1. 筛选区间上限为N 则首先需要筛选2~log2N的素数，再通过区间左端点作为偏移量，映射到需要筛选的区间
### 2. 映射初始条件 max(2*p,(left + p - 1)// p * p)，每次+p即可完成对合数的剔除
### 3. 注意，存储时为了不爆空间，需要对映射区间取一个左端点的偏移量，以区间长度为上限进行存储

### python版本
def getPrimes(n):
    vis = [False]*(n + 1)
    for i in range(2,n+1):
        if vis[i] == False:
            primes.append(i)
        j = 0
        while primes[j]*i <= n:
            vis[primes[j]*i] = True
            if i % primes[j] == 0:
                break
            j += 1


primes = []
getPrimes(50000)
while True:   #无定行输入
    try:
        left,right = map(int,input().split())
        vis = [False]*(1000010) #二次筛
        for p in primes:
            j = max(2*p,(left + p - 1)// p * p)
            while j <= right:
                vis[j - left] = True   #为了节省空间需要加入left偏移量
                j += p
                
        realPrimes = []
        for i in range(right - left + 1):  #遍历原区间（带有left的偏移量）
            if vis[i] == False and i + left >= 2:
                realPrimes.append(i + left)
                
        if len(realPrimes) < 2:
            print("There are no adjacent primes.")
        else:
            maxPi = 0
            minPi = 0 
            for i in range(len(realPrimes) - 1):
                d =  realPrimes[i + 1] - realPrimes[i]
                if d < realPrimes[minPi + 1] - realPrimes[minPi]:
                    minPi = i
                if d > realPrimes[maxPi + 1] - realPrimes[maxPi]:
                    maxPi = i
            
            print("%d,%d are closest, %d,%d are most distant." %(realPrimes[minPi],realPrimes[minPi + 1],
                                                                         realPrimes[maxPi],realPrimes[maxPi + 1]))
    except:
        break

隔板法求方程解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#方程的解(隔板法)
def power(x,p):
    res = 1
    while p:
        if p & 1:
            res = res * x % mod
        x = x * x % mod
        p >>= 1
    return res

def combination(n,k):
    jie = [1]*(n + 1)
    for i in range(1,n+1):
        jie[i] = jie[i - 1]*(i)
    return jie[n] // jie[k] // jie[n - k]


mod = 1000
k , x = map(int,input().split())
n = power(x,x)


print(combination(n - 1,k - 1))

卡特兰数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#求卡特兰数 n个数组成的二叉搜索树的个数就是一个卡特兰数，知道这个结论于是就很好办了：

n = int(input())
N = 3*n + 1

c = [[0]*(N) for i in range(N)]

for i in range(N):
    for j in range(i + 1):
        if j == 0:
            c[i][j] = 1
        else:
            c[i][j] = c[i - 1][j - 1] + c[i - 1][j]
            
print(c[n*2][n] // (n + 1))

求互质数个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def getPrimes(n):
    phi[1] = 1 #默认0与1互质
    vis = [False]*(N + 1)
    for i in range(2,n+1):
        if vis[i] == False:
            primes.append(i)
            phi[i] = i - 1
        j = 0
        while primes[j]*i <= n:
            vis[primes[j]*i] = True
            phi[primes[j]*i] = (primes[j] - 1)*phi[i]
            if i % primes[j] == 0:
                phi[primes[j]*i] = primes[j]*phi[i]
                break
            j += 1

树的中心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
# 树的中心
def Lin(a,b,c):
    if a not in link.keys():
        link[a] = {b:c}
    else:
        if b not in link[a].keys():
            link[a].update({b:c})
        else:
            link[a][b] = max(link[a][b],c)
def dfs_down(curNode,lastNode): #子节点推父节点(先到最底层再向上)
    if curNode not in link.keys():
        return 0
    for node in link[curNode].keys():
        if node == lastNode:
            continue
        temp = dfs_down(node,curNode) + link[curNode][node]
        if temp >= d1[curNode]:
            d2[curNode] = d1[curNode]
            d1[curNode] = temp
            son1[curNode] = node
        elif temp > d2[curNode]:
            d2[curNode] = temp
            
    return d1[curNode]
            

def dfs_up(curNode,lastNode): #父节点推子节点(从上到下)
    if curNode not in link.keys():
        return
    for node in link[curNode].keys():
        if node == lastNode:
            continue

        if son1[curNode] == node:
            up[node] = max(up[curNode],d2[curNode]) + link[curNode][node]
        else:
            up[node] = max(up[curNode],d1[curNode]) + link[curNode][node]
        
        dfs_up(node,curNode)
            

n = int(input())
link = {}

d1 = [0]*(n + 1)
d2 = [0]*(n + 1)
son1 = [0]*(n + 1) #从哪个节点走上来的最长路
up = [0]*(n + 1)

for i in range(n - 1):
    a,b,c = map(int,input().split())
    Lin(a,b,c)
    Lin(b,a,c)

dfs_down(1,-1)
dfs_up(1,-1)

res = float('inf')
for node in range(1,n+1):
    res = min(max(d1[node],up[node]),res)
print(res)

双向广搜

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#双向广搜一般用在最小步数模型中，在搜索空间空间很大的情况下可以提升根号倍速度
from collections import deque
def extend(queue,bian,vis,visO):
    sam = queue.popleft()
    cnt = vis[sam]
    for i in range(len(sam)):
        for var in  bian.keys():
            if i + len(var) > len(sam): #无法变换
                continue
            if sam[i:i + len(var)] == var: #如果可以变换
                for yinShe in bian[var]:
                    new = sam[:i] + yinShe + sam[i + len(var):]
            
                    if new in vis.keys():
                        continue
                    if new in visO.keys():
                        return cnt + 1 + visO[new]
                    vis.update({new : cnt + 1})
                    queue.append(new)
    return 11

def bfs():
    queue1 = deque()
    queue2 = deque()
    queue1.append(start) #存内容与步数
    queue2.append(end)
    

    while queue1 and queue2:
        if len(queue1) < len(queue2):
            res = extend(queue1,bianS,visS,visE)
        else:
            res = extend(queue2,bianE,visE,visS)
        if res <= 10:
            return res
    return 11

start,end = input().split()
bianS = {}
bianE = {}

visS = {start:0}
visE = {end:0}

while True:
    try:
        a,b = input().split()
        if a not in bianS:
            bianS[a] = {b}
        else:
            bianS[a].add(b)
        if b not in bianE:
            bianE[b] = {a}
        else:
            bianE[b].add(a)
    except:
        break

ans = bfs()
if ans <= 10:
    print(ans)
else:
    print("NO ANSWER!")

阶乘的质数分解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#阶乘的质数分解
def getPrimes(N):
    for i in range(2,N+1):
        if vis[i] == False:
            primes.append(i)
            minp[i] = i
        j = 0
        while primes[j]*i <= N:
            vis[primes[j]*i] = True
            minp[primes[j]*i] = primes[j]
            if i % primes[j] == 0:
                break
            j += 1
            

N = 1000100
vis = [0]*(N + 1)
minp = [0]*(N + 1)
primes = []
getPrimes(N)

n = int(input())

fact = []
countPrimes = [0]*(N + 1)

for x in range(2,n+1):
    while x > 1:
        curPrime = minp[x]
        fact.append(curPrime)
        while x % curPrime == 0:
            countPrimes[curPrime] += 1
            x //= curPrime
    
for i in range(2,len(countPrimes)):
    if countPrimes[i]:
        print(i,countPrimes[i])

EK算法最大流

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#最小割问题 EK算法(BFS)
from collections import deque

def Lin(a,b,c):
    if a not in link.keys():
        link[a] = {b:c}
    else:
        if b not in link[a].keys():
            link[a].update({b:c})
        else:
            link[a][b] += c


def ek(s,t):
    global pre
    vis = [False]*(n+1)
    pre = [-1]*(n+1)
    queue = deque()
    queue.append(s)
    vis[s] = True
    flow = float('inf')
    while queue:
        curNode = queue.popleft()
        if curNode == t:
            return flow
        if curNode not in link.keys():
            continue
        for node in link[curNode].keys():
            if link[curNode][node] <= 0 or vis[node] == True and pre[node] != -1:
                continue
            flow = min(flow,link[curNode][node])
            pre[node] = curNode
            vis[node] = True
            queue.append(node)
    return -1



n,m,s,t = map(int,input().split())
link = {}
for i in range(m):
    a,b,w = map(int,input().split())
    Lin(a,b,w)
    Lin(b,a,0)
    
        
maxFlow = 0

while True:
    pre = []
    flow = ek(s,t)
    if flow == -1:
        break
    
    #print(flow)
    p = t
    while p != s:
        link[pre[p]][p] -= flow #更新残余网络
        link[p][pre[p]] += flow #更新后悔网络
        p = pre[p]
        
    maxFlow += flow
print(maxFlow)

最近公共祖先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#祖孙询问
def bfs(root):
    depth[0] = 0 #哨兵，防跳过根节点
    depth[root] = 1

    queue = []
    queue.append(root) #从根节点开始维护节点深度与倍增数组

    while queue:
        sam = queue.pop(0)

        if sam not in link.keys():
            continue
        
        for node in link[sam]:
            if depth[node] > depth[sam] + 1: #该点尚未被搜索过
                depth[node] = depth[sam] + 1
                fa[node][0] = sam
                for k in range(1,16): #向上跳2^(k-1)的点再向上跳2^(k-1)则是向上跳2^k的点
                    fa[node][k] = fa[fa[node][k - 1]][k - 1]

                queue.append(node)

def lca(a,b):
    if depth[a] < depth[b]:
        a,b = b,a

    for k in range(15,-1,-1):
        if depth[fa[a][k]] >= depth[b]:
            a = fa[a][k]
    
    if a == b: #如果跳到和b同层，则找到最近公共祖先
        return a
    for k in range(15,-1,-1):
        if fa[a][k] != fa[b][k]:
            a = fa[a][k]
            b = fa[b][k]

    return fa[a][0]

N = 40010
n = int(input())
depth = [float('inf')]*(N)
fa = [[0]*(16) for i in range(N)]

link = {}
for i in range(n):
    a,b = map(int,input().split())
    if b == -1:
        root = a
    if a not in link.keys():
        link[a] = {b}
    else:
        link[a].add(b)
    if b not in link.keys():
        link[b] = {a}
    else:
        link[b].add(a)

bfs(root)

m = int(input())
for i in range(m):
    a,b = map(int,input().split())
    p = lca(a,b)
    if p == a:
        print(1)
    elif p == b:
        print(2)
    else:
        print(0)

最近公共祖先与书上差分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
# LCA与树上差分
# 树上差分目的：快速给每一条路径加上一个数，并可以快速求每一条边的边权
### python版本
#暗之连锁
#LCA与树上差分
def bfs(root):
    queue = [root]
    depth[0] = 0
    depth[root] = 1

    while queue:
        sam = queue.pop(0)

        if sam not in link.keys():
            continue

        for node in link[sam]:
            if depth[node] > depth[sam] + 1:
                depth[node] = depth[sam] + 1
                fa[node][0] = sam
                for i in range(1,17):
                    fa[node][i] = fa[fa[node][i - 1]][i - 1]
                queue.append(node)

def lca(a,b):
    if depth[a] < depth[b]:
        a,b = b,a
    for i in range(16,-1,-1):
        if depth[fa[a][i]] >= depth[b]:
            a = fa[a][i]

    if a == b:
        return a
    for i in range(16,-1,-1):
        if fa[a][i] != fa[b][i]:
            a = fa[a][i]
            b = fa[b][i]

    return fa[a][0]

def dfs(curNode,lastNode):
    global ans
    res = d[curNode]
    for node in link[curNode]:
        if node == lastNode:
            continue
        temp = dfs(node,curNode)
        
        if temp == 0:
            ans += m
        elif temp == 1:
            ans += 1  
        res += temp

    return res




n,m = map(int,input().split())
depth = [float('inf')]*(n + 1)
fa = [[0]*(17) for i in range(n+1)]

link = {}
for i in range(n-1):
    a,b = map(int,input().split())
    if a not in link.keys():
        link[a] = {b}
    else:
        link[a].add(b)

    if b not in link.keys():
        link[b] = {a}
    else:
        link[b].add(a)

bfs(1)

d = [0]*(n + 1)
for i in range(m): #做树上差分
    a,b = map(int,input().split())
    p = lca(a,b)
    d[a] += 1
    d[b] += 1
    d[p] -= 2

ans = 0

dfs(1,-1)

print(ans)

高斯消元

球形产生器问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
def gauss():
    c = 1
    r = 1
    while c <= n:
        #找主元
        t = r
        for i in range(r + 1,n+1):
            if abs(b[i][c]) > abs(b[t][c]):
                t = i
        #交换
        for i in range(c,n + 2):
            b[t][i],b[r][i] = b[r][i],b[t][i]
        
        # 归一化
        for i in range(n+1,c - 1,-1):
            b[r][i] /= b[r][c]
        # 消
        for i in range(r + 1 , n + 1):
            for j in range( n + 1,c - 1,-1):
                b[i][j] -= b[i][c] * b[r][j]
        
        c += 1
        r += 1
        
    
    # 化成对角矩阵
    for i in range(n,1,-1):
        for j in range(i - 1,0,-1):
            b[j][n + 1] -= b[i][n + 1] * b[j][i]
            b[j][i] = 0
    

n = int(input())
a = []
b = [[0]*(15) for i in range(15)]

for i in range(n + 1):
    a.append([0] + [float(i) for i in input().split()])
    
for i in range(1,n+1):
    for j in range(1,n+1):
        b[i][j] += 2*(a[i][j] - a[0][j])
        b[i][n + 1] += a[i][j] * a[i][j] - a[0][j] * a[0][j]



gauss()

for i in range(1,n+1):
    print("%.3lf"%(b[i][n + 1]),end = ' ')