之前的模板在我考研时脑子一热删掉了QAQ，现在重新写了点，Python和C++都有。
dijkstra
\(O(n^2)\)
import os
import sys
import math
import copy
from collections import deque
from heapq import *
sys.setrecursionlimit(30000)
MAXN = 1 << 32
n, m, st = map(int, input().split())
mp = [[] for _ in range(n + 1)]
for i in range(m):
u, v, w = map(int, input().split())
mp[u].append([v, w])
## mp[v].append([u, w])
dis, vis = [MAXN] * (n + 1), [0] * (n + 1)
dis[st] = 0
for i in range(n):
t, minn = 0, MAXN
for j in range(1, n + 1):
if vis[j] == 0 and dis[j] < minn:
t, minn = j, dis[j]
vis[t] = 1
for v, w in mp[t]:
if vis[v] == 0 and dis[v] > dis[t] + w:
dis[v] = dis[t] + w
for i in range(1, n + 1):
if i < n:
print(dis[i], end = " ")
else:
print(dis[i])
\(O(nlogm)\)
import os
import sys
import math
import copy
from collections import deque
from heapq import *
sys.setrecursionlimit(30000)
MAXN = 1 << 32
class edge():
def __init__(self, v, w):
self.v = v
self.w = w
def __lt__(self, t):
if self.w < t.w:
return True
else:
return False
n, m, st = map(int, input().split())
mp = [[] for _ in range(n + 1)]
for i in range(m):
u, v, w = map(int, input().split())
mp[u].append([v, w])
## mp[v].append([u, w])
dis, vis = [MAXN] * (n + 1), [0] * (n + 1)
q = []
dis[st] = 0
heappush(q, edge(st, 0))
while len(q):
t = heappop(q)
u = t.v
if vis[u]:
continue
vis[u] = 1
for v, w in mp[u]:
if dis[v] > dis[u] + w:
dis[v] = dis[u] + w
heappush(q, edge(v, dis[v]))
for i in range(1, n + 1):
if i < n:
print(dis[i], end = " ")
else:
print(dis[i])
dfs序和树状数组
import os
import sys
import math
import copy
from collections import deque
from heapq import *
sys.setrecursionlimit(30000)
n, m = map(int, input().split())
a = list(map(int, input().split()))
a.insert(0, 0)
mp = [[] for _ in range(n + 1)]
in1, out1, sum = [0] * (n + 1), [0] * (n + 1), [0] * (n + 1)
for i in range(n - 1):
u, v = map(int, input().split())
mp[u].append(v)
mp[v].append(u)
cnt = 0
def dfs(u, fa):
global cnt
cnt += 1
in1[u] = cnt
for v in mp[u]:
if v == fa:
continue
dfs(v, u)
out1[u] = cnt
dfs(1, 0)
def lowbit(x):
return x & (-x)
def upd(x, d):
while x <= n:
sum[x] ^= d
x += lowbit(x)
def query(x):
ans = 0
while x:
ans ^= sum[x]
x -= lowbit(x)
return ans
for i in range(1, n + 1):
upd(in1[i], a[i])
while m:
m -= 1
ls = list(map(int, input().split()))
if ls[0] == 1:
x, y = ls[1], ls[2]
upd(in1[x], a[x] ^ y)
a[x] = y
else:
x = ls[1]
print(query(out1[x]) ^ query(in1[x] - 1))
线段树
import os
import sys
import copy
from math import gcd
sys.setrecursionlimit(300000)
a = [0 for _ in range(100005)]
val = [0 for _ in range(100005 << 2)]
def push_up(root):
val[root] = gcd(val[root << 1], val[root << 1 | 1])
def build(root, l, r):
if l == r:
val[root] = a[l]
return
mid = l + r >> 1
build(root << 1, l, mid)
build(root << 1 | 1, mid + 1, r)
push_up(root)
def query(root, l, r, ql, qr):
if qr < l or ql > r:
return 0
if ql <= l and r <= qr:
return val[root]
mid = l + r >> 1
return gcd(query(root << 1, l, mid, ql, qr), query(root << 1 | 1, mid + 1, r, ql, qr))
def solve():
n = int(input())
v = list(map(int, input().split()))
g = 0
for i in range(n):
g = gcd(g, v[i])
a[i + 1] = v[i]
if g > 1:
print(-1)
return
if v.count(1):
print(n - v.count(1))
return
build(1, 1, n)
len, l = n, 1
for i in range(1, n + 1):
while query(1, 1, n, l, i) == 1:
len = min(len, i - l + 1)
l += 1
print(len - 1 + n - 1)
T = 1
#T = int(input())
for _ in range(T):
solve()
倍增求lca
import os
import sys
import math
import copy
import collections
sys.setrecursionlimit(30000)
n, m, rt = map(int, input().split())
mp = [[] for _ in range(n + 1)]
for i in range(n - 1):
u, v = map(int, input().split())
mp[u].append(v)
mp[v].append(u)
lg, dep, fn = [0] * (n + 1), [0] * (n + 1), [[0 for _ in range(25)] for _ in range(n + 1)]
lg[0] = -1
for i in range(1, n + 1):
lg[i] = lg[i // 2] + 1
def lca_init(u, fa):
dep[u] = dep[fa] + 1
fn[u][0] = fa
for i in range(1, lg[dep[u]] + 1):
fn[u][i] = fn[fn[u][i - 1]][i - 1]
for v in mp[u]:
if v == fa:
continue
lca_init(v, u)
def lca(x, y):
if dep[x] < dep[y]:
x, y = y, x
while dep[x] > dep[y]:
x = fn[x][lg[dep[x] - dep[y]]]
if x == y:
return x
for i in range(lg[dep[x]], -1, -1):
if fn[x][i] != fn[y][i]:
x = fn[x][i]
y = fn[y][i]
return fn[x][0]
lca_init(rt, 0)
while m:
m -= 1
x, y = map(int, input().split())
print(lca(x, y))
字符串hash
import os
import sys
import copy
mod = int(1e9 + 7)
base = 131
def solve():
global mod
global base
s = list(input())
n = len(s)
s.insert(0, ' ')
hl, hr, p, sum = [0 for _ in range(n + 1)], [0 for _ in range(n + 1)], [0 for _ in range(n + 1)], [0 for _ in range(n + 1)]
p[0] = 1
for i in range(1, n + 1):
hl[i] = (hl[i - 1] * base % mod + int(s[i])) % mod
hr[i] = (hr[i - 1] * base % mod + int(s[n - i + 1])) % mod
p[i] = p[i - 1] * base % mod
sum[i] = sum[i - 1] + int(s[i])
def hash(h, l, r):
return (h[r] - h[l - 1] * p[r - l + 1] % mod + mod) % mod
ans = sum[n]
for i in range(1, n + 1):
if s[i] == '0':
l, r, maxn = 0, min(i - 1, n - i), 0
while l <= r:
mid = (l + r) >> 1
if hash(hl, i - mid, i) == hash(hr, n - i - mid + 1, n - i + 1):
l = mid + 1
maxn = mid
else:
r = mid - 1
ans = min(ans, sum[n] - (sum[i + maxn] - sum[i - maxn - 1]) // 2)
#print(maxn)
for i in range(1, n):
l, r, maxn = 0, min(i, n - i), 0
while l <= r:
mid = (l + r) >> 1
if hash(hl, i - mid + 1, i) == hash(hr, n - i - mid + 1, n - i):
l = mid + 1
maxn = mid
else:
r = mid - 1
#print(maxn)
ans = min(ans, sum[n] - (sum[i + maxn] - sum[i - maxn]) // 2)
print(ans)
T = 1
#T = int(input())
for _ in range(T):
solve()
Exgcd
\(O(logn)\)
int Exgcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1;
y = 0;
return a;
}
int d = Exgcd(b, a % b, x, y);
int t = x;
x = y;
y = t - (a / b) * y;
return d;
}