• 算法基础课

    • 算法基础课

    第一讲 基础算法

    包括排序、二分、高精度、前缀和与差分、双指针算法、位运算、离散化、区间合并等内容。

    快速排序

    AcWing 785. 快速排序 https://acwing.caiths.com/problem/787/ AcWing 786. 第k个数 https://acwing.caiths.com/problem/788/

    归并排序

    AcWing 787. 归并排序 https://acwing.caiths.com/problem/789/ AcWing 788. 逆序对的数量 https://acwing.caiths.com/problem/790/

    二分

    AcWing 789. 数的范围 https://acwing.caiths.com/problem/791/ AcWing 790. 数的三次方根 https://acwing.caiths.com/problem/792/

    高精度

    AcWing 791. 高精度加法 https://acwing.caiths.com/problem/793/ AcWing 792. 高精度减法 https://acwing.caiths.com/problem/794/ AcWing 793. 高精度乘法 https://acwing.caiths.com/problem/795/ AcWing 794. 高精度除法 https://acwing.caiths.com/problem/796/

    前缀和与差分

    AcWing 795. 前缀和 https://acwing.caiths.com/problem/797/ AcWing 796. 子矩阵的和 https://acwing.caiths.com/problem/797/ AcWing 797. 差分 https://acwing.caiths.com/problem/799/ AcWing 798. 差分矩阵 https://acwing.caiths.com/problem/800/

    双指针算法

    AcWing 799. 最长连续不重复子序列 https://acwing.caiths.com/problem/801/ AcWing 800. 数组元素的目标和 https://acwing.caiths.com/problem/802/ AcWing 2816. 判断子序列 https://acwing.caiths.com/problem/2818/

    位运算

    AcWing 801. 二进制中1的个数 https://acwing.caiths.com/problem/803/

    离散化

    AcWing 802. 区间和 https://acwing.caiths.com/problem/804/

    区间合并

    AcWing 803. 区间合并 https://acwing.caiths.com/problem/805/

     

    第二讲 数据结构

    包括单链表，双链表，栈，队列，单调栈，单调队列，KMP，Trie，并查集，堆，哈希表等内容。

    单链表

    AcWing 826. 单链表 https://acwing.caiths.com/problem/828/

    双链表

    AcWing 827. 双链表 https://acwing.caiths.com/problem/829/

    栈

    AcWing 828. 模拟栈 https://acwing.caiths.com/problem/830/ AcWing 3302. 表达式求值 https://acwing.caiths.com/problem/3304/

    队列

    AcWing 829. 模拟队列 https://acwing.caiths.com/problem/831/

    单调栈

    AcWing 830. 单调栈 https://acwing.caiths.com/problem/832/

    单调队列

    AcWing 154. 滑动窗口 https://acwing.caiths.com/problem/156/

    KMP

    AcWing 831. KMP字符串 https://acwing.caiths.com/problem/833/

    Trie

    AcWing 835. Trie字符串统计 https://acwing.caiths.com/problem/837/ AcWing 143. 最大异或对 https://acwing.caiths.com/problem/145/

    并查集

    AcWing 836. 合并集合 https://acwing.caiths.com/problem/838/ AcWing 837. 连通块中点的数量 https://acwing.caiths.com/problem/839/ AcWing 240. 食物链 https://acwing.caiths.com/problem/250/

    堆

    AcWing 838. 堆排序 https://acwing.caiths.com/problem/840/ AcWing 839. 模拟堆 https://acwing.caiths.com/problem/841/

    哈希表

    AcWing 840. 模拟散列表 https://acwing.caiths.com/problem/842/ AcWing 841. 字符串哈希 https://acwing.caiths.com/problem/843/

    第三讲 搜索与图论

    包括DFS，BFS，树与图的深度优先遍历，树与图的广度优先遍历，拓扑排序，Dijkstra，bellman-ford，spfa，Floyd，Prim，Kruskal，染色法判定二分图，匈牙利算法等内容。

    DFS

    AcWing 842. 排列数字 https://acwing.caiths.com/problem/844/ AcWing 843. n-皇后问题 https://acwing.caiths.com/problem/845/

    BFS

    AcWing 844. 走迷宫 https://acwing.caiths.com/problem/846/ AcWing 845. 八数码 https://acwing.caiths.com/problem/847/

    树与图的深度优先遍历

    AcWing 846. 树的重心 https://acwing.caiths.com/problem/848/ 树与图的广度优先遍历 AcWing 847. 图中点的层次 https://acwing.caiths.com/problem/849/

    拓扑排序

    AcWing 848. 有向图的拓扑序列 https://acwing.caiths.com/problem/850/

    Dijkstra

    AcWing 849. Dijkstra求最短路 I https://acwing.caiths.com/problem/851/ AcWing 850. Dijkstra求最短路 II https://acwing.caiths.com/problem/852/

    bellman-ford

    AcWing 853. 有边数限制的最短路 https://acwing.caiths.com/problem/855/

    spfa

    AcWing 851. spfa求最短路 https://acwing.caiths.com/problem/853/ AcWing 852. spfa判断负环 https://acwing.caiths.com/problem/854/

    Floyd

    AcWing 854. Floyd求最短路 https://acwing.caiths.com/problem/856/

    Prim

    AcWing 858. Prim算法求最小生成树 https://acwing.caiths.com/problem/860/

    Kruskal

    AcWing 859. Kruskal算法求最小生成树 https://acwing.caiths.com/problem/861/

    染色法判定二分图

    AcWing 860. 染色法判定二分图 https://acwing.caiths.com/problem/862/

    匈牙利算法

    AcWing 861. 二分图的最大匹配 https://acwing.caiths.com/problem/863/

     

    第四讲 数学知识

    包括质数，约数，欧拉函数，快速幂，扩展欧几里得算法，中国剩余定理，高斯消元，求组合数，容斥原理，博弈论等内容。

    质数

    AcWing 866. 试除法判定质数 https://acwing.caiths.com/problem/868/ AcWing 867. 分解质因数 https://acwing.caiths.com/problem/869/ AcWing 868. 筛质数 https://acwing.caiths.com/problem/870/

    约数

    AcWing 869. 试除法求约数 https://acwing.caiths.com/problem/871/ AcWing 870. 约数个数 https://acwing.caiths.com/problem/872/ AcWing 871. 约数之和 https://acwing.caiths.com/problem/873/ AcWing 872. 最大公约数 https://acwing.caiths.com/problem/874/

    欧拉函数

    AcWing 873. 欧拉函数 https://acwing.caiths.com/problem/875/ AcWing 874. 筛法求欧拉函数 https://acwing.caiths.com/problem/876/

    快速幂

    AcWing 875. 快速幂 https://acwing.caiths.com/problem/877/ AcWing 876. 快速幂求逆元 https://acwing.caiths.com/problem/878/

    扩展欧几里得算法

    AcWing 877. 扩展欧几里得算法 https://acwing.caiths.com/problem/879/ AcWing 878. 线性同余方程 https://acwing.caiths.com/problem/880/

    中国剩余定理

    AcWing 204. 表达整数的奇怪方式 https://acwing.caiths.com/problem/206/

    高斯消元

    AcWing 883. 高斯消元解线性方程组 https://acwing.caiths.com/problem/885/ AcWing 884. 高斯消元解异或线性方程组 https://acwing.caiths.com/problem/886/

    求组合数

    AcWing 885. 求组合数 I https://acwing.caiths.com/problem/887/ AcWing 886. 求组合数 II https://acwing.caiths.com/problem/888/ AcWing 887. 求组合数 III https://acwing.caiths.com/problem/889/ AcWing 888. 求组合数 IV https://acwing.caiths.com/problem/890/ AcWing 889. 满足条件的01序列 https://acwing.caiths.com/problem/891/

    容斥原理

    AcWing 890. 能被整除的数 https://acwing.caiths.com/problem/892/

    博弈论

    AcWing 891. Nim游戏 https://acwing.caiths.com/problem/893/ AcWing 892. 台阶-Nim游戏 https://acwing.caiths.com/problem/894/ AcWing 893. 集合-Nim游戏 https://acwing.caiths.com/problem/895/ AcWing 894. 拆分-Nim游戏 https://acwing.caiths.com/problem/896/

     

    第五讲 动态规划

    包括背包问题，线性DP，区间DP，计数类DP，数位统计DP，状态压缩DP，树形DP，记忆化搜索等内容。

    背包问题

    AcWing 2. 01背包问题 https://acwing.caiths.com/problem/2/ AcWing 3. 完全背包问题 https://acwing.caiths.com/problem/3/ AcWing 4. 多重背包问题 https://acwing.caiths.com/problem/4/ AcWing 5. 多重背包问题 II https://acwing.caiths.com/problem/5/ AcWing 9. 分组背包问题 https://acwing.caiths.com/problem/9/

    线性DP

    AcWing 898. 数字三角形 https://acwing.caiths.com/problem/900/ AcWing 895. 最长上升子序列 https://acwing.caiths.com/problem/897/ AcWing 896. 最长上升子序列 II https://acwing.caiths.com/problem/898/ AcWing 897. 最长公共子序列 https://acwing.caiths.com/problem/899/ AcWing 902. 最短编辑距离 https://acwing.caiths.com/problem/904/ AcWing 899. 编辑距离 https://acwing.caiths.com/problem/901/

    区间DP

    AcWing 282. 石子合并 https://acwing.caiths.com/problem/284/

    计数类DP

    AcWing 900. 整数划分 https://acwing.caiths.com/problem/902/

    数位统计DP

    AcWing 338. 计数问题 https://acwing.caiths.com/problem/340/

    状态压缩DP

    AcWing 291. 蒙德里安的梦想 https://acwing.caiths.com/problem/293/ AcWing 91. 最短Hamilton路径 https://acwing.caiths.com/problem/93/

    树形DP

    AcWing 285. 没有上司的舞会 https://acwing.caiths.com/problem/287/

    记忆化搜索

    AcWing 901. 滑雪 https://acwing.caiths.com/problem/903/

     

    第六讲 贪心

    包括区间问题，Huffman树，排序不等式，绝对值不等式，推公式等内容。

    区间问题

    AcWing 905. 区间选点 https://acwing.caiths.com/problem/907/ AcWing 908. 最大不相交区间数量 https://acwing.caiths.com/problem/910/ AcWing 906. 区间分组 https://acwing.caiths.com/problem/908/ AcWing 907. 区间覆盖 https://acwing.caiths.com/problem/909/

    Huffman树

    AcWing 148. 合并果子 https://acwing.caiths.com/problem/150/

    排序不等式

    AcWing 913. 排队打水 https://acwing.caiths.com/problem/915/

    绝对值不等式

    AcWing 104. 货仓选址 https://acwing.caiths.com/problem/106/

    推公式

    AcWing 125. 耍杂技的牛 https://acwing.caiths.com/problem/127/