算法日记（基础算法篇）

Competitive Programming
Word count: 1.8k   |   Reading time≈ 8 min

2023.1.9
2023.1.10 太痛苦了，一道题写了一天还不会写，艹……
y总写leetcode题是爽题，我写是送命题，%%%……

算法复杂度

衡量算法性能得主要对象是时间复杂度，一般不讨论空间复杂度。

由数据范围反推算法复杂度以及算法内容

**尺取法(双指针)**优化序列区间问题

O(n2)O(n^2)->O(n)O(n)
指针i,ji,j方向相反：左右指针；方向相同：快慢指针(产生一个大小可变的滑动窗口)。

1
2
3
4
5
6
朴素算法
for(i=0;i<n;i++)
{
    for(j=0;j<n;j++)
    //O(n^2)
}//双指针算法：将上述朴素算法优化到O(n)
1
2
3
4
5
6
7
双指针算法
for(i=0,j=0;i<n;i++)
{
    while(j<i&&check(i,j))j++;
    
    //每道题目的具体逻辑
}

反向扫描

数组元素的目标和
回文字符串
有效回文串
有效回文 II

同向扫描

Subsequence
Bound Found
最长连续不重复子序列

数组去重

1)哈希(利用哈希函数有冲突的特点去重，哈希表需要空间较大)
2)尺取法

1
2
3
4
5
6
7
8
9
10
11
12
#数组去重
a=list(map(int,input().split()))
n=len(a)
a.sort()#排序后重复元素会挤到一起
i=0#快指针
j=0#慢指针，指向不重复的最后一个元素
while i<n-1:
    i+=1
    if a[i]!=a[j]:#若a[i]!=a[j],则将a[i]放到a[j]后面
        j+=1
        a[j]=a[i]
print(a[:j+1])

删除有序数组中的重复项
移除元素

多指针

A-B 数对
三数之和
尺取法在链表中的应用：常用的双指针技巧
双指针知识点题库

2023.1.11

二分法

整数二分

找x的后继

1
2
3
4
5
6
7
8
9
10
def bisearch(a,x):
    l=0
    r=len(a)-1
    while l<r:
        mid=l+r>>1
        if a[mid]>=x:
            r=mid
        else:
            l=mid+1
    return l

找x的前驱

1
2
3
4
5
6
7
8
9
10
def bisearch(a,x):
    l=0
    r=len(a)-1
    while l<r:
        mid=l+r+1>>1
        if a[mid]<=x:
            l=mid
        else:
            r=mid-1
    return l

二分STL(bisect)

1
2
3
4
from bisect import bisect_left,bisect#二分库
a=[1,2,3,3,4,5,6,7,7,7,8,8]
print(bisect_left(a,3))#若x已存在，则返回能插入的最左边的位置->升序序列中，返回>=x的第一个数的下标->bisect_left(a,x)-1即返回最后一个<x的数下标
print(bisect(a,3))#若x已存在，则返回能插入的最右边的位置->升序序列中，返回>x的第一个数的下标->bisect(a,x)-1即返回最后一个<=x的数下标

整数二分建模

1
2
3
4
5
6
while l<r:
    mid=l+r>>1
    if check(mid):
        ans=mid
    else:
        pass

进击的奶牛
跳石头
聪明的质监员
Monthly Expense S
实数二分

1
2
3
4
5
6
7
eps=1e-7 #精度，需要仔细设计
while r-l>eps:
    mid=(l+r)/2
    if check(mid):
        r=mid
    else:
        l=mid

Pie
Expanding Rods
2023.1.12 被迫打了一天工，啥也没学，中午拿办公室电脑A了一题……
2023.1.13

三分法

注意：单峰（单谷）函数两边要严格单调，否则可能在一边f(mid1)==f(mid2)f(mid1)==f(mid2)，无法缩小区间。
实数三分
【模板】三分法
函数
UmBasketella
整数三分

1
2
3
4
5
6
7
while l<r:
    mid1=(2*l+r)//3
    mid2=(l+2*r+2)//3
    if check(mid1)>check(mid2):
        l=mid1+1
    else:
        r=mid2-1

2023.1.14

倍增法与ST算法

1.倍增法O(2n)O(2^n)从小区间到大区间；从小数值到大数值
把一个数二进制展开：N=a020+a121+a222+a323+a424+……N=a_02^0+a_12^1+a_22^2+a_32^3+a_42^4+……
二进制划分反映了一种快速增长的特性：2i=2i−1+2i−2+……+21+20+12^i=2^{i-1}+2^{i-2}+……+2^1+2^0+1
局限性：需要提前计算1,2,4,……,2k1,2,4,……,2^k个跳板，数据必须是静态的，如果变化，那么所有跳板必须重新计算。
国旗计划
2.ST算法适用于静态空间的RMQ
天才的记忆
Balanced Lineup G

2023.1.15

前缀和与差分

前缀和是差分的逆运算；差分数组对“区间修改”高效，但对“单点查询”不高效。
一维：
前缀和
Subsequences Summing to Sevens S
激光炸弹
差分
最高的牛
二维：
子矩阵的和
差分矩阵
地毯
Monitor
三维：压维
三维前缀和与三维差分
三体攻击

离散化 用相对值代替绝对值

步骤：1.排序；2离散化；3.归位
离散化手工编码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
n=int(input())
a=[0]+list(map(int,input().split()))
old=[(0,0)]*(n+1)
new=[(0,0)]*(n+1)
for i in range(1,n+1):
    old[i]=(a[i],i)
old.sort(key=lambda x:x[0])
for i in range(1,n+1):
    new[old[i][1]]=i
    # 若两个元素值相同，赋成同样的值
    # if old[i][0]==old[i-1][0]:
    #     new[old[i][1]]=new[old[i-1][1]]
for i in range(1,n+1):
    print(new[i],end=' ')

STL实现离散化 不去重

1
2
3
4
5
6
7
8
9
from bisect import bisect_left
n=int(input())
old=[0]+list(map(int,input().split()))
new=old.copy()
old.sort()
for i in range(1,n+1):
    new[i]=bisect_left(old,new[i])
for i in range(1,n+1):
    print(new[i],end=' ')

区间和

排序与排列

排序函数
sort()
sorted()
奖学金

排列
全排列的算法复杂度为O(n!)O(n!)
1.Python的排列组合函数
2.自写排列函数
AnnA_n^n

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def dfs(s,t):
    if s==t:
        for i in range(t):
            print(b[i],end=' ')
        print()
        return 
    for i in range(t):
        if not vis[i]:
            b[s]=a[i]
            vis[i]=True
            dfs(s+1,t)
            vis[i]=False
    
a=[1,2,3,4,5,6,7,8,9,10,11,12,13]
vis=[False]*20
b=[0]*20

n=3
dfs(0,n)

AnmA_n^m

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def dfs(s,t,m):
    if s==m:
        for i in range(m):
            print(b[i],end=' ')
        print()
        return 
    for i in range(t):
        if not vis[i]:
            b[s]=a[i]
            vis[i]=True
            dfs(s+1,t,m)
            vis[i]=False
    
a=[1,2,3,4,5,6,7,8,9,10,11,12,13]
vis=[False]*20
b=[0]*20

n=4
m=3
dfs(0,n,m)

蓝桥杯2016省赛C++A组第6题.寒假作业

分治法
最大子段和
南蛮图腾
2的幂次方
分形
1.汉诺塔
汉诺塔
2.快速幂(标准写法不是分治，而是二进制倍增)

1
2
3
4
5
6
7
8
9
10
11
12
def fastpow(a,n,m):
    if n==0:
        return 1
    if n==1:
        return a
    temp=fastpow(a,n//2,m)
    if n%2:
        return temp*temp*a%m
    return temp*temp%m

a,n,m=map(int,input().split())
print(fastpow(a,n,m))

归并排序
归并排序
逆序对的数量
Inversion

快速排序
快速排序
第k个数

贪心法与拟阵

贪心法
特征：
1.最优子结构性质。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质，也称此问题满足最优性原理。局部最优扩展到全局最优。
2.贪心选择性质。问题的整体最优解可以通过一系列局部最优的选择得到。

拟阵
如果一个问题满足拟阵结构，那么贪心能得到最优解。

最大不相交区间数量
游戏预言
Hero
Aaronson
搭配牛奶
跳跳！
纪念品分组
三国游戏
推销员

2023.1.18 又一章结束了，真就差不多10天一章，而且还有好多题不会……

补充

区间合并

  • Copyright： Copyright is owned by the author. For commercial reprints, please contact the author for authorization. For non-commercial reprints, please indicate the source.

扫一扫，分享到微信

微信分享二维码
  • Copyrights © 2023-2025 Shiki
  • Visitors: | Views: