文章列表

15k字14 分钟

# 动态规划 动态规划（英语：Dynamic programming，简称 DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。 动态规划常常适用于有重叠子问题 [1] 和最优子结构性质的问题，动态规划方法所耗时间往往远少于朴素解法。 动态规划背后的基本思想非常简单。大致上，若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。 通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题
14k字13 分钟

# 普通莫队 # 简介 莫队算法 —— 优雅而不失复杂度的暴力 像暴力一样好写，又有分块一样时间复杂度，常数还小（不过要离线 莫队算法是由莫涛提出的算法。在莫涛提出莫队算法之前，莫队算法已经在 Codeforces 的高手圈里小范围流传，但是莫涛是第一个对莫队算法进行详细归纳总结的人。莫涛提出莫队算法时，只分析了普通莫队算法，但是经过 OIer 和 ACMer 的集体智慧改造，莫队有了多种扩展版本。 莫队算法可以解决一类离线区间询问问题，适用性极为广泛。同时将其加以扩展，便能轻松处理树上路径询问以及支持修改操作。 # 形式 假设n=mn=mn=m，那么对于序列上的
5.9k字5 分钟

# 分块 # 介绍 分块是一种思想，把一个整体划分为若干个小块，对整块整体处理，零散块单独处理。 块状数组把一个长度为nnn 的数组划分为aaa 块，每块长度为na\frac{n}{a}an​ 。对于一次区间操作，对区间內部的整块进行整体的操作，对区间边缘的零散块单独暴力处理。（所以分块被称为 “优雅的暴力”） # 暴力 + 暴力 = 分块 这里，块数既不能太少也不能太多。如果太少，区间中整块的数量会很少，我们要花费大量时间处理零散块；如果太多，又会让块的长度太短，失去整体处理的意义。一般来说，我们取块数为 n\sqrt{n}n​ ，这样在最坏情况下，我们要处理接近n\sqrt nn
3.1k字3 分钟

# 对拍是什么 对拍，是一个比较实用的工具。它能够非常方便地对于两个程序的输出文件进行比较，可以帮助我们实现一些自动化的比较输出结果的问题。 众所周知，几乎每一道编程题目，都会有某种正解能拿到满分；当我们想不出正解时，我们往往可以打暴力代码来获取部分分数。 但是，当我们觉得有思路写正解，但又担心自己正解写的不对，而恰好，我们又有一个能够暴力骗分的代码。这个时候就可以用到对拍。 暴力骗分代码必须保证正确性，只是超出时间限制，不能出现答案错误的情况。 这样，我们可以造多组数据，让暴力骗分的程序跑一遍，再让我们自己写的正解跑一遍，二者进行多次对比。如果多组数据都显示二者的输出结果一样，那么这个正解大
4.5k字4 分钟

# 贪心 贪心算法（英语：greedy algorithm），是用计算机来模拟一个「贪心」的人做出决策的过程。这个人十分贪婪，每一步行动总是按某种指标选取最优的操作。而且他目光短浅，总是只看眼前，并不考虑以后可能造成的影响。 可想而知，并不是所有的时候贪心法都能获得最优解，所以一般使用贪心法的时候，都要确保自己能证明其正确性。 简单来说，就是当前状态下只取当前状态的最优解 # 适用范围 贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。 # 贪心常见题型 # 排序解法 用排序法常见的情况是输入一个包含几个（一般一到两个