快速排序——分治

快速排序

1、确定分界点 $q[l]$, $q[(l + r) / 2]$, $q[r]$ 随机 2、调整区间：使得左边的数小于等于 $x$，右边的数大于等于 $x$。 3、递归处理左、右两段。

代码模板：

def quick_sort(arr, left, right):
    if left >= right: return

    i = left - 1
    j = right + 1
    x = arr[(i + j) // 2]
    while left < right:
        while True:
            i += 1
            if arr[i] >= x: break
        while True:
            j -= 1
            if arr[j] <= x: break

        if i < j:
            arr[i], arr[j] = arr[j], arr[i]
        else:
            break
    quick_sort(arr, left, j)
    quick_sort(arr, j + 1, right)

n = int(input())
a = list(map(int, input().split()))
quick_sort(a, 0, n-1)
print(' '.join(map(str, a)))

快速选择算法

找到分界点 $x$, $q[L], q[(L + R) / 2], q[R]$
左边所有数 $Left <= x$，右边所有数 $Right >= x$
递归排序 Left, 递归排序 Right

\[\begin{cases} k \leq S_L & 递归 Left \\ k \geq S_L & 递归 Right, k - S_L \end{cases}\]

归并排序——分治

归并排序

确定分界点 $\text{mid} = (l + r) / 2$
递归排序 left， right
归并——合二为一

def merge_sort(arr, l, r, tmp):
    if l >= r: return
    mid = (l + r) // 2
    merge_sort(arr, l, mid, tmp)
    merge_sort(arr, mid + 1, r, tmp)
    i = l
    j = mid + 1
    k = 0
    while (i <= mid and j <= r):
        if arr[i] <= arr[j]:
            tmp[k] = arr[i]
            i += 1
        else:
            tmp[k] = arr[j]
            j += 1
        k += 1
    while i <= mid:
        tmp[k] = arr[i]
        i += 1
        k += 1
    while j <= r:
        tmp[k] = arr[j]
        j += 1
        k += 1
    i, j = l, 0
    while i <= r:
        arr[i] = tmp[j]
        i += 1
        j += 1

n = int(input())
arr = list(map(int, input().split()))
tmp = [0] * n
merge_sort(arr, 0, n - 1, tmp)
print(' '.join(map(str, arr)))

逆序对的数量

归并排序：

[L， R] => [L, mid], [mid + 1, R]
递归排序 [L, mid] 和 [mid + 1, R]
归并，将左右两个有序序列合并成一个有序序列

左半边内部的逆序对数量： merge_sort(L, mid)
右半边内部的逆序对数量： merge_sort(mid + 1, R)

def merge_sort(arr, l, r, tmp):
    if l >= r: return 0
    mid = (l + r) // 2
    res = merge_sort(arr, l, mid, tmp) + merge_sort(arr, mid + 1, r, tmp)

    k = 0
    i = l
    j = mid + 1
    while i <= mid and j <= r:
        if (arr[i] <= arr[j]): 
            tmp[k] = arr[i]
            k += 1
            i += 1
        else:
            res += mid - i + 1
            tmp[k] = arr[j]
            k += 1
            j += 1
    while i <= mid:
        tmp[k] = arr[i]
        k += 1
        i += 1
    while j <= r:
        tmp[k] = arr[j]
        k += 1
        j += 1
    
    i = l
    j = 0
    while i <= r:
        arr[i] = tmp[j]
        i += 1
        j += 1
    
    return res


n = int(input())
arr = list(map(int, input().split()))
tmp = [0] * n
print(merge_sort(arr, 0, n - 1, tmp))

二分

当找红色分界点时， $\text{mid} = \frac{l + r + 1}{2}$

\[\text{if} (\text{checkmid}) \begin{cases} true & [mid, r] : l = mid \\ fasle & [l, mid - 1] : r = mid - 1 \end{cases}\]

当找绿色分界点时， $\text{mid} = \frac{l + r}{2}$

\[\text{if} (\text{checkmid}) \begin{cases} true & [1, mid] : r = mid \\ fasle & [mid + 1, r] : l = mid + 1 \end{cases}\]

如何选择模板？

根据 checkmid 函数检查如何更新 mid

如果是 $l = mid$，那么就要补上 +1

如果是 $r = mid$，那么就不用补上 +1

为什么要补上 +1 ?

因为 C++ 默认是下取整，当 $l = r -1$ 时，那么 $mid = \frac{l + r}{2} = \frac{l + l + 1}{2} = l$ , $l$ 和 $r$ 没变，陷入死循环。

数的范围

 def binary_search(arr, k):
    l = 0
    r = len(arr) - 1

    while l < r:
        mid = (l + r) // 2
        if arr[mid] >= k:
            r = mid
        else:
            l = mid + 1
    if arr[l] != k:
        return [-1, -1]

    left = l

    l = 0
    r = len(arr) - 1
    while l < r:
        mid = (l + r + 1) // 2
        if arr[mid] <= k:
            l = mid
        else:
            r = mid - 1

    return [left, l]

n, q = map(int, input().split())
arr = list(map(int, input().split()))
for i in range(q):
    k = int(input())
    res = binary_search(arr, k)
    print(' '.join(map(str, res)))

## 数的三次方根

 def binary_search(l, r, k):
    while (r - l) > 1e-8:
        mid = (l + r) / 2
        if mid ** 3 >= k:
            r = mid
        else:
            l = mid

    return l

l = -10000
r = 10000
k = float(input())
print(binary_search(l, r, k))

# 高精度

大整数存储

## 高精度加法

 def add(A, B):
    if len(A) < len(B): return add(B, A)
    
    C = []
    t = 0
    for i in range(len(A)):
        t += A[i]
        if i < len(B):
            t += B[i]
        C.append(t % 10)
        t //= 10

    if t: C.append(t)
    return C

a = str(input())
b = str(input())
A, B = [], []
for i in range(len(a)-1, -1, -1): A.append(int(a[i]))
for i in range(len(b)-1, -1, -1): B.append(int(b[i]))

C = add(A, B)
for i in range(len(C)-1, -1, -1):
    print(C[i], end='')

## 高精度减法

def cmp(A, B):
    if (len(A) != len(B)): return len(A) > len(B)

    for i in range(len(A) - 1, -1, -1):
        if A[i] != B[i]: return A[i] > B[i]

    return True

def sub(A, B):
    C = []
    t = 0 
    for i in range(len(A)):
        t = A[i] - t
        if (i < len(B)): t -= B[i]
        C.append((t + 10) % 10)
        if (t < 0): t = 1
        else: t = 0
    
    while(len(C) > 1 and C[-1] == 0): C.pop()
    return C

a = str(input())
b = str(input())
A, B  = [], []
for i in range(len(a) - 1, -1, -1): A.append(int(a[i]))
for i in range(len(b) - 1, -1, -1): B.append(int(b[i]))

if cmp(A, B): 
    C = sub(A, B)
else: 
    C = sub(B, A) 
    print('-', end='')

for i in range(len(C) - 1, -1, -1):
    print(C[i], end='')

## 高精度乘法

 def multiply(A, b):
    C = []
    t = 0
    i = 0
    while t != 0 or i < len(A):
        if i < len(A): 
            t += A[i] * b
            i += 1
        C.append(t % 10)
        t //= 10
    
    while(len(C) > 1 and C[-1] == 0): C.pop()
    return C


a = str(input())
b = int(input())

A = []

for i in range(len(a)-1, -1, -1): A.append(int(a[i]))

C = multiply(A, b)

for i in range(len(C)-1, -1, -1): print(C[i], end='')

## 高精度除法

 def div(A, b):
    C = []
    r = 0
    for i in range(len(A)-1, -1, -1): 
        r = r * 10 + A[i]
        print(r)
        C.append(r // b)
        r %= b

    C = C[::-1]

    while(len(C) > 1 and C[-1] == 0): C.pop()
    return C, r

a = input()
b = int(input())

A  = []

for i in range(len(a)-1, -1, -1): A.append(int(a[i]))

C, r = div(A, b)


for i in range(len(C)-1, -1, -1): print(C[i], end='')

print(r)

# 前缀与差分

## 前缀和

 n, m = map(int, input().split())
arr = [0] + list(map(int, input().split()))
pre_sum = [0] * len(arr)

for i in range(1, n+1):
    pre_sum[i] = pre_sum[i-1] + arr[i]

for _ in range(m):
    l, r = map(int, input().split())
    print(pre_sum[r] - pre_sum[l-1])

## 子矩阵的和

 n, m, q = map(int, input().split())
matrix = [[0] * (m + 1)]
for i in range(n):
    arr = [0] + list(map(int, input().split()))
    matrix.append(arr)


S = matrix
for i in range(1, n + 1):
    for j in range(1, m + 1):
        S[i][j] += S[i-1][j] + S[i][j-1] - S[i-1][j-1]


for i in range(q):
    x1, y1, x2, y2 = map(int, input().split())
    print(S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1 - 1][y1 - 1])

## 差分

 def insert(b, l, r, c):
    b[l] += c
    b[r+1] -= c


n, m = map(int, input().split())
nums = [0] + list(map(int, input().split()))
queries = [tuple(map(int, input().split())) for _ in range(m)]

b = [0 for _ in range(n + 2)]

for i in range(1, n+1):
    insert(b, i, i, nums[i])
for query in queries:
    insert(b, *query)

res = [0] * (n+1)
for i in range(1, n+1):
    res[i] = res[i-1] + b[i]

print(' '.join(map(str, res[1:])))

## 差分矩阵

 def insert(b, x1, y1, x2, y2, c):
    b[x1][y1] += c
    b[x2+1][y1] -= c
    b[x1][y2+1] -= c
    b[x2+1][y2+1] += c

n, m, q = map(int, input().split())

a = [[ 0 for i in range(m+2)] for i in range(n+2)]
b = [[0 for i in range(m+2)] for i in range(n+2)]

for i in range(1, n+1):
    row = list(map(int, input().split()))
    for j in range(1, m + 1):
        a[i][j] = row[j-1]
        insert(b, i, j, i, j, a[i][j])


while q:
    q -= 1
    x1, y1, x2, y2, c = map(int, input().split())
    insert(b, x1, y1, x2, y2, c)

for i in range(1, n+1):
    for j in range(1, m+1):
        b[i][j] += b[i-1][j] + b[i][j-1] - b[i-1][j-1]
        print(b[i][j], end=' ')
    print()

# 双指针算法

## 最长连续不重复子序列

 n = int(input())
q = list(map(int, input().split()))
s = [0] * 100010
res = 0
i = j = 0

while i < n:
    s[q[i]] += 1
    while j < i and s[q[i]] > 1:
        s[q[j]] -= 1
        j += 1
    res = max(res, i - j + 1)
    i += 1

print(res)

## 数组元素的目标和

n, m, x = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

i = 0
j = m -1
while i< n:
    while j >= 0 and A[i] + B[j] > x:
        j -= 1
    if j >= 0 and A[i] + B[j] == x:
        print(f'{i} {j}')
        break
    i += 1

## 判断子序列

 n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

i = j = 0
while i < n and j < m:
    if a[i] == b[j]: i += 1
    j += 1

if (i == n): print("Yes")
else: print("No")

# 位运算

## » k & 1

求 n 的二进制表示中第 k 位是几。

先把第 k 位一道最后一位 $n » k$
看个位是几 $x & 1$

因此方法就是: $n » k & 1$

lowbit

返回 x 的最后一位 1

\[x = 1010 \qquad lowbit(x) = 10\] \[x = 101000 \qquad lowbit(x) = 1000\]

如何实现lowbit:

\[x & -x = x & (~x + 1)\] \[x = 1010 ... 10 ... 0\] \[~x = 0101 ... 01 ... 1\] \[~x + 1 = 0101 ... 10 ... 0\]

 n = int(input())
arr = map(int, input().split())
for x in arr:
    s = 0

    i = x
    while i:
        s += 1
        i -= i & -i
    print(s, end=' ')

# 单链表

 def add_to_head(x):
    global idx, head
    e[idx] = x
    ne[idx] = head
    head = idx
    idx += 1

def add(k, x):
    global idx
    e[idx] = x
    ne[idx] = ne[k]
    ne[k] = idx
    idx += 1

def remove(k):
    ne[k] = ne[ne[k]]


N = 100010
n = int(input())

e = [0] * N
ne = [0] * N
idx = 0
head = -1

for i in range(n):
    op = input().split()
    if op[0] == 'H':
        add_to_head(int(op[1]))
    elif op[0] == 'I':
        add(int(op[1]) - 1, int(op[2]))
    else:
        k = int(op[1])
        if k:
            remove(k - 1)
        else:
            head = ne[head]
            
i = head
res = []
while i != -1:
    res.append(e[i])
    i = ne[i]

print(' '.join(map(str, res)))

# 双链表

 # 在节点 k 的右边插入一个数 x
def insert(k, x):
    global idx
    e[idx] = x
    l[idx] = k
    r[idx] = r[i]
    r[k] = idx
    idx += 1

def remove(k):
    l[r[k]] = l[k]
    r[l[k]] = r[k]


N = 100010
e = [0] * N
l = [0] * N
r = [0] * N
idx = 2
m = int(input())

r[0] = 1
l[1] = 0
idx = 2

for i in range(m):
    inp = input().split()
    if inp[0] == 'L':
        x = int(inp[1])
        insert(0, x)
    if inp[0] == 'R':
        x = int(inp[1])
        insert(l[1], x)
    if inp[0] == 'D':
        k = int(inp[1])
        remove(k + 1)
    if inp[0] == 'IL':
        k, x = int(inp[1]), int(inp[2])
        insert(l[k + 1], x)
    if inp[0] == 'IR':
        k, x = int(inp[1]), int(inp[2])
        insert(k + 1, x)

i = r[0]
while i != 1:
    print(e[i], end=' ')
    i = r[i]

栈

模拟栈

 class Stack():
    def __init__(self):
        self.items = []
    def push(self, item):
        self.items.append(item)
    def pop(self):
        return self.items.pop()
    def empty(self):
        if len(self.items) == 0:
            return 'YES'
        else:
            return 'NO'
    def query(self):
        return self.items[-1]

m = int(input())
S = Stack()
for i in range(m):
    inp = input().split()
    if inp[0] == 'push':
        S.push(int(inp[1]))
    if inp[0] == 'pop':
        S.pop()
    if inp[0] == 'empty':
        print(S.empty())
    if inp[0] == 'query':
        print(S.query())

表达式求值

def eval():
    b = num.pop()
    a = num.pop()
    c = op.pop()
    if c == '+':
        x = a + b
    elif c == '-':
        x = a - b
    elif c == '*':
        x = a * b
    elif c == '/':
        x = int(a / b)
    num.append(x)

pr = {
    '+': 1,
    '-': 1,
    '*': 2,
    '/': 2,
}

digits = ('0', '1', '2', '3', '4', '5', '6', '7', '8', '9')

num = []
op = []
strs = input().strip()

i = 0
while i < len(strs):
    c = strs[i]
    if c in digits:
        x = 0
        j = i
        while j < len(strs) and strs[j] in digits:
            x = x * 10 + int(strs[j])
            j += 1
        i = j - 1
        num.append(x)
    elif c == '(': op.append(c)
    elif c == ')':
        while op[-1] != '(': eval()
        op.pop()
    else:
        while (len(op) > 0 and op[-1] != '(' and pr[op[-1]] >= pr[c]):
            eval()
        op.append(c)
    i += 1
while len(op): eval()
print(num[-1])

模拟队列

单调栈

N = 100010
stk = [0] * N
tt = 0
arr = list(map(int, input().split()))

n = int(input())
for x in arr:
    while tt and stk[tt] >= x: tt -= 1
    if not tt: print("-1 ")
    else: print(stk[tt])
    tt += 1
    stk[tt] = x

On this page