『算法-ACM 竞赛-算法-二分法』在单调递增序列 a 中查找小于等于 x 的数中最大的一个（即 x 或 x 的前驱）写在前面：我们主要还是分享算法的模板，而不是去刨析算法的原理！ 定义： 二分答案是指在答案具有单调性的前提下，利用二分的思想枚举答案，将求解问题转化为验证结果。 流程：首先需要估计答案的上下界，然后不断取区间中点进行验证（这就要求答案的验证应当简单可行），并通过验证结果不断更新答

『算法-ACM 竞赛-算法-二分法』信息竞赛进阶指南-二分法写在前面：我们主要还是分享算法的模板，而不是去刨析算法的原理！ 定义： 二分答案是指在答案具有单调性的前提下，利用二分的思想枚举答案，将求解问题转化为验证结果。 流程：首先需要估计答案的上下界，然后不断取区间中点进行验证（这就要求答案的验证应当简单可行），并通过验证结果不断更新答案区间，最终得到答案。不难看出，朴素的枚举验证时间复杂度是

『算法-ACM 竞赛-算法-ST 算法』信息竞赛进阶指南-区间最值问题的 ST 算法借助倍增和动态规划可以实现 O（1）的时间复杂度的查询 预处理：① 区间 DP 转移方程 f[i][j] = min(MAX 同理)(f[i][j - 1],f[i + ][j - 1]) f[i][j]表示从 i 位置开始的后 2^j 个数中的最大值 用 f[i][j]表示从 j 到 j+2^i-1 的

『算法-ACM 竞赛-算法-lowbit』算法竞赛进阶指南-lowbit 运算，找到二进制下所有是 1 的位写在前面：我们主要还是分享算法的模板，而不是去刨析算法的原理！ 主要思想是，对于非负整数 n，输出 n 最低位的 1 所在位，并不断把 n 赋值成 n-(n&-n)，直至 n=0。为了提高效率，我们使用 Hash 代替取 log，并且利用一个数学技巧：对于任意在[0,35

『算法-ACM 竞赛-算法-KMP』信息竞赛进阶指南–KMP 算法（模板）简介：KMP 算法是一种改进的字符串匹配算法，由 D.E.Knuth，J.H.Morris 和 V.R.Pratt 提出的，因此人们称它为克努特—莫里斯—普拉特操作（简称 KMP 算法）。KMP 算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个 next()函数实现，

『算法-ACM 竞赛-算法-Hash 算法』信息竞赛进阶指南-字符串哈希字符串 hash 主要应用在：寻找长度为 n 的主串 S 中的匹配串 T（长度为 m）出现的位置或次数的问题属于字符串匹配问题。类似的还有 KMP，我也有讲解。 原理： 将字符串中的每一个字母都看做是一个数字（例：从 a-z，视为 1-26）； 选取两个合适的互质常数 b 和 h，其中 h 要尽可能的大一点，为了降低冲突的概

『算法-ACM 竞赛-真题』第十届山东省赛 L 题 Median（floyd 传递闭包）+ poj1975Median Time Limit: 1 Second Memory Limit: 65536 KB Recall the definition of the median of elements where is odd: sort these elements and the median

『算法-ACM 竞赛-真题』ThePreliminaryContestforICPCAsiaXuzhou2019 徐州网络赛 XKC’sbasketballteaThe Preliminary Contest for ICPC Asia Xuzhou 2019 徐州网络赛 XKC’s basketball teamXKC , the captain of the basketball team ,

『算法-ACM 竞赛-真题』ThePreliminaryContestforICPCAsiaXuzhou2019 徐州网络赛 K 题 centerThe Preliminary Contest for ICPC Asia Xuzhou 2019 徐州网络赛 K 题 centerYou are given a point set with nn points on the 2D-plane, you

『算法-ACM 竞赛-真题』ThePreliminaryContestforICPCAsiaXuzhou2019 徐州网络赛 DCarneginonThe Preliminary Contest for ICPC Asia Xuzhou 2019 徐州网络赛 D CarneginonCarneginon was a chic bard. But when he was young, he was