头像

生日快乐

$\href{https://blog.csdn.net/eveee1123}{\sf\color{magenta}{My}\;\color{blue}{CS}\color{red}{DN}}$




离线:23小时前



t = int(input())

def LIS(arr, n):
    f = [1] * n
    for i in range(1, n):
        for j in range(i):
            if arr[i] > arr[j]: f[i] = max(f[i], f[j] + 1)
    return max(f)
while t:
    t -= 1
    n = int(input())
    num = list(map(int, input().split()))
    ans = LIS(num, n)
    ans = max(ans, LIS(num[::-1], n))
    print(ans)


新鲜事 原文

请问个人空间里视频一栏是什么意思呀



n = int(input())

rec = []
for i in range(n):
    l, r = map(int, input().split())
    rec.append((l, r))

rec.sort(key = lambda x: x[1])

cnt = 1
now = rec[0][1]
for i in rec:
    l, r = i[0], i[1]
    if l > now:
        cnt += 1
        now = r
print(cnt)


活动打卡代码 AcWing 905. 区间选点

n = int(input())

rec = []
for i in range(n):
    l, r = map(int, input().split())
    rec.append((l, r))

rec.sort(key = lambda x: x[1])

cnt = 1
now = rec[0][1]
for i in rec:
    l, r = i[0], i[1]
    if l <= now <= r: continue
    else:
        cnt += 1
        now = r
print(cnt)



生日快乐
1个月前

树状数组

维护序列前缀和

复杂度 O(logN)

小心不要用到下标[0]

C = [0] * (n + 1)
def lowbit(x):
    return x & (-x)

def add(x, i):
    while x <= n:
        C[x] += i
        x += lowbit(x)
def query(x):
    ans = 0
    while x:
        ans += C[x]
        x -= lowbit(x)
    return ans

线段树

维护区间和

class Node():
    l = 0
    r = 0
    su = 0 #sum
    def __init__(self, l = 0, r = 0, su = 0):
        self.l = l
        self.r = r
        self.su = su

def pushup(u):
    global t
    t[u].su = t[u << 1].su + t[u << 1 | 1].su
def build(u, l, r):
    global t
    if l == r:
        t[u] = Node(l, r, num[r - 1])
        return
    else:
        t[u] = Node(l, r)
        mid = l + r >> 1
        build(u << 1, l, mid)
        build(u << 1 | 1, mid + 1, r)
        pushup(u)
def query(u, l, r):
    if t[u].l >= l and t[u].r <= r: return t[u].su
    mid = t[u].l + t[u]. r >> 1
    ans = 0
    if l <= mid: ans = query(u << 1, l, r)
    if r > mid: ans += query(u << 1 | 1, l, r)
    return ans
def modify(u, x, v):
    if t[u].l == t[u].r: 
        t[u].su +=v
        return
    mid = t[u].l + t[u].r >> 1
    if x <= mid: modify(u << 1, x, v)
    else: modify(u << 1 | 1, x, v)
    pushup(u)

KMP

next数组表示模版串中以i结尾的后缀子串和前缀最大匹配长度

def KMP():
    global s, p
    s = ' ' + s
    p = ' ' + p
    ne = [0] * (n + 2)
    #求next
    j = 0
    for i in range(2, n + 1):
        while j and p[i] != p[j + 1]: j = ne[j]
        if p[i] == p[j + 1]: j += 1
        ne[i] = j
    #匹配
    j = 0
    for i in range(1, m + 1):
        while j and  s[i] != p[j + 1]: j = ne[j]
        if s[i] == p[j + 1]: j += 1
        if j == n:
            print(i - n, end = ' ')
            j = ne[j]



生日快乐
1个月前

平面图欧拉公式

$V - E + F = 2$

其实中V是顶点数,E是边数,F是面数


堆优化版本dijkstra

import heapq
INF = 0x3f3f3f3f
N = 1000000

e = [0] * N
idx = 0
ne = [0] * N
w = [0] * N
h = [-1] * N
n, m = map(int, input().split())

def add(a, b, c):
    global e, w, ne ,h, idx
    e[idx] = b
    w[idx] = c
    ne[idx] = h[a]
    h[a]= idx
    idx += 1

while m:
     m -= 1
     a, b, c = map(int, input().split())
     add(a, b, c)

def dijkstra():
    st = [False] * N
    dist = [INF] * N
    dist[1] = 0
    hp = []
    heapq.heappush(hp, (0, 1))

    while len(hp):
        t = heapq.heappop(hp)
        cur = t[1]; dis = t[0]

        if st[cur]: continue
        st[cur] = True

        i = h[cur]
        while ~i:
            j = e[i]
            if dist[j] > dist[cur] + w[i]: 
                dist[j] = dist[cur] + w[i]
                heapq.heappush(hp, (dist[j], j))
            i = ne[i]

    return -1 if dist[n] == INF else dist[n]

print(dijkstra())

Dijkstra

n , m = map(int , input().split())
N = n + 1000
g = [[0x3f3f3f3f]*N for i in range(N)]
while m:
    m -= 1
    x , y , z = map(int , input().split())
    g[x][y] = z
for  i in range(n):
    g[i][i] = 0
def dijkstra():
    st = [False] * N
    dist = [0x3f3f3f3f] * N
    dist[1] = 0
    for i in range(n-1):
        t = -1
        for j in range(1,n+1):
            if not st[j] and (t == -1 or dist[j] < dist[t]): t = j
        for j in range(1,n+1):
            dist[j] = min(dist[j] , dist[t] + g[t][j])

        st[t] = True
    return -1 if dist[n] == 0x3f3f3f3f else dist[n]

print(dijkstra())

Bellman_ford

两层循环,复杂度O(nm)

最外层循环意味着当前最短路包含几条边

'''
用来求单源最短路
算法思想:
扫描每一条边(x, y, z),若dist[y] > dist[x] + z,则用dist[x] + z 更新dist[y]
'''
import copy
class edge(): # a, b, w分别表示起点和终点以及权值
    a = 0
    b = 0
    w = 0
    def __init__(self, a, b, w):
        self.a = a
        self.b = b
        self.w = w

n, m, k = map(int, input().split())
g = [None] * m

for i in range(m):
    a, b, w = map(int, input().split())
    g[i] = edge(a, b, w)

def bellman_ford():
    dis = [0x3f3f3f3f3f] * (n + 1)
    dis[1] = 0 
    for i in range(k):
        backup = copy.deepcopy(dis)#backup是dis列表的拷贝,防止下面那层循环在更新dis数组时用到本层循环中刚更新过的dis
        for j in range(m):
            dis[g[j].b] = min(dis[g[j].b], backup[g[j].a] + g[j].w)
    return dis[n]

ans = bellman_ford()

if ans > 0x3f3f3f3f: print('impossible')
else: print(ans)

SPFA

from collections import deque
def spfa():
    dist = [0x3f3f3f3f] * (n + 1)
    v = [0] * (n + 1)
    q = deque()
    q.append(1)
    dist[1] = 0
    while len(q):
        pos = q.popleft()
        v[pos] = 0
        i = head[pos]
        while ~i:
            j = e[i]
            if dist[j] > dist[pos] + w[i]:
                dist[j] = dist[pos] + w[i]
                if not v[j]: q.append(j); v[j] = 1
            i = ne[i]
    return 'impossible' if dist[n] == 0x3f3f3f3f else dist[n]

Kruskal

'''
将边排序,每次选取边权最小的边,利用并查集判断该边两端点是否在同一个集合即可
'''
'''
e 用来存储边
n 点数
m 边数
ans 最小生成树代价
cnt 选取得总边数
'''
n, m = map(int, input().split())

class edge():
    a = 0
    b = 0
    w = 0
    def __init__(self, a = 0, b = 0, c = 0):
        self.a = a
        self.b = b
        self.w = c

e = [edge() for i in range(m)]
fa = [i for i in range(n + 1)]
for i in range(m):
    a, b, c = map(int, input().split())
    e[i].a = a
    e[i].b = b
    e[i].w = c

e.sort(key = lambda x: x.w)

def find(x):
    if x == fa[x]:
        return fa[x]
    else:
        fa[x] = find(fa[x])
        return fa[x]
ans = 0
cnt = 0
for i in e:
    x = i.a
    y = i.b
    x = find(x)
    y = find(y)
    if x != y:
        fa[x] = y
        ans += i.w
        cnt += 1
if cnt < n - 1:
    print('impossible')
else:
    print(ans)



生日快乐
1个月前

如有错误,烦请各位指出🙂🙂🙂

Lucas 组合数取模

b存在乘法逆元的充要条件是b与模数m互质

def exgcd(a, b): #扩展欧几里得
    if b == 0:
        x = 1
        y = 0
        return x, y
    x1, y1 = exgcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return x, y
'''
费马小定理,若p为素数
a ^ p % p = 1
所以当p为素数时
b的逆元为 b ^ (p - 2)
b存在乘法逆元的充要条件是b与模数m互质
'''
def quick_mod(a, b, p): #快速幂
    # return a^b%p
    ans = 1
    a %= p
    while b:
        if b & 1:
            ans = ans * a % p
            b -= 1
        b >>= 1
        a = a * a % p
    return ans
def Inv(b, p): #求逆元
    x, y = exgcd(b, p)
    return (x + p) % p
def C(n, m, p):
    if m > n: return 0
    a = 1; b = 1
    while m:
        a = a * n % p
        n -= 1
        b = b * m % p
        m -= 1
    return a * Inv(b, p) % p
def Lucas(n, m, p):
    if m == 0:
        return 1
    return C(n % p, m % p, p) * Lucas(n // p, m // p, p) % p

素数判定

def judge(x):
    if x < 2: return False
    sqx = int(math.sqrt(x)) + 1
    for i in range(2, sqx):
        if x % i == 0: return False
    return True

质因数分解

def prime_fac(x):
    p = []
    c = []
    for i in range(2, int(sqrt(x)) + 1):
        if x % i == 0:
            p.append(i)
        cnt = 0
        while x % i == 0:
            x //= i
            cnt += 1
        if cnt: c.append(cnt)
    if x > 1:
        p.append(x)
        c.append(1)
    return p, c

最大公约数

python自带gcd函数哦

import math
print(math.gcd(4, 6))

快速幂

def quick_mod(a, b, p):
    '''
    return a ^ b mod p
    '''
    ans = 1
    while b:
        if b & 1: ans *= a
        a = a * a % p 
        b >>= 1
    return ans % p
pow(a, b, c)
#这个是内置函数,直接就是快速幂,比我上面手写那个要快一些

扩展欧几里得

通解:

$a’ = a // gcd(a, b)$

$b’ = b // gcd(a, b)$

$x = x’ + k * b’$

$y = y’ - k * a’$

最小正整数解

$x = x’ mod b’$

def ex_gcd(a, b):
    '''
    return ax + by = gcd(a, b)
    '''
    if b == 0:
        x = 1
        y = 0
        return x, y
    x1, y1 = ex_gcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return x, y

质数筛

#线性筛
'''
if i % primes[j] == 0: break
我们希望每个合数被最小质因子筛除
break的原因是此时pj是i的最小质因子,那么下一个pj*i筛的合数的最小质因子一定不是pj
'''
cnt = 0 #cnt表示质数总个数
for i in range(2, n+1):
    if not vis[i]: #vis这个列表用来标记一个数是否被筛选过
        cnt += 1
        primes[cnt] = i #primes列表用来记录每一个质数
    for j in range(1, cnt+1):
        if primes[j] > n//i: break # 原因请见最上方注释
        vis[primes[j] * i] = 1
        if i % primes[j] == 0: break

质因数分解

'''
可能存在大于sqrt(x)的质因子
最后x如果不为1就说明此时的x为大于sqrt(x)的质因子
'''
import math
def get_prime_fac(x):
    sqr_x = int(math.sqrt(x))+ 1
    for i in range(2, sqr_x):
        cnt = 0
        if x % i == 0:
            while x % i == 0: x //= i; cnt +=1
            print(i, cnt) #i是当前质因数,cnt是指数
    if x != 1:
        print(x, 1) #x表示质因数,1表示指数是1
    print() # 输出一个回车,无实际意义


活动打卡代码 AcWing 1055. 股票买卖 II

生日快乐
1个月前
n = int(input())
nums = list(map(int, input().split()))
nums.append(-0x3f3f)
now = -1
cnt = 0
for i in range(n):
    if nums[i] <= nums[i + 1] and now == -1:
        now = nums[i]
    if nums[i] <= nums[i + 1] and now != -1:
        continue
    if nums[i] > nums[i + 1] and now != -1:
        cnt += nums[i] - now
        now = -1

print(cnt)



活动打卡代码 AcWing 1207. 大臣的旅费

生日快乐
1个月前
n = int(input())
N = 2 * n + 100
idx = 0
e = [0] * N
head = [-1] * N
nx = [-1] * N
w = [-1] * N
def add(a, b, c):
    global idx
    e[idx] = b
    w[idx] = c
    nx[idx] = head[a]
    head[a] = idx
    idx += 1

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

mxdeep = -1
node = -1
def dfs(x, fa, deep):
    global mxdeep, node
    if deep > mxdeep:
        mxdeep = deep
        node = x
    i = head[x]
    while ~i:
        j = e[i]
        if j == fa: i = nx[i]; continue
        dfs(j, x, deep + w[i])
        i = nx[i]
    return 

dfs(1, 1, 0)
dfs(node, node, 0)
print((11 + 10 + mxdeep) * mxdeep // 2)


活动打卡代码 AcWing 1233. 全球变暖

生日快乐
1个月前
from collections import deque
n = int(input())

g = [[] for i in range(n)]
vis = [[0] * n for i in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
for i in range(n):
    tmp = input()
    for j in tmp:
        g[i].append(j)

def bfs(i, j):
    total = 0
    warn = 0
    q = deque()
    q.append((i, j))
    vis[i][j] = True
    while q:
        x, y = q.popleft()
        total += 1
        sea = False
        for d in range(4):
            nx, ny = x + dx[d], y + dy[d]
            if nx < 0 or ny < 0 or nx >= n or ny >= n: continue
            if vis[nx][ny]: continue
            if g[nx][ny] == '#': q.append((nx, ny)); vis[nx][ny] = True
            if g[nx][ny] == '.': sea = True
        if sea: warn += 1
    return warn == total

cnt = 0
for i in range(n):
    for j in range(n):
        if g[i][j] == '#' and not vis[i][j]:
            if bfs(i, j): cnt += 1
print(cnt)