视频讲解：https://www.bilibili.com/video/BV1db411f7M7 最近在leetcode遇到一道非常经典的题目：239. 滑动窗口最大值 - 力扣（LeetCode） 以前只会看题解用单调队列做，最近研究一下发现是一道很好的题，可以帮助我们提升“维护区间最值”的算法思维。 先介绍一下我解决这题所用的算法及其复杂度： 单调队列 O(n) st表 O(nlogn) 树状 […]

题目链接：D-排名估算_牛客挑战赛36 (nowcoder.com) 分析 / Analyse 看完题意有点懵，我们来分析一下，一共有n个人，已知抽了m次都没有比排名比自己高的，不妨将“已知事件”的设为事件A：“抽了m次都没抽中比自己高的”。 而抽人的前提是自己有一个排名，所以我们可以设事件Xi为“当前排名为i“，而在没有事件A的前提下，排名是均匀随机的，所以P(Xi) = 1 / n。 我们要求 […]

题目链接：Palindrome - HDU 6230 - Virtual Judge (vjudge.net) 从这里进也可以：Problem - 6230 (hdu.edu.cn) 题目大意 / Problem 有多组样例。 每组样例给一个字符串，问有多少个“一个半回文串”，一个半回文串的定义是，第一个回文串的右端点是第二个回文串的中心，第一个回文串的中心是第二个回文串的端点。 比如abcbab […]

题目传送门：第 46 届 ICPC 国际大学生程序设计竞赛亚洲区域赛（上海） D Strange_Fractions（解方程，数论） 解方程，设\(t = \frac{b}{a}\)，将方程两边同时乘\(t\)可以得到\(qt^2 - pt + q = 0\)，通过小学二年级学的一元二次方程求根公式可知：当\(p^2 - 4q^2 \ge 0\)时方程有解。由求根公式可以得到\(t = \frac […]

使用试除法得到质因数的复杂度是\(O(\sqrt{n})\)，如果数字较大比如\(10^{18}\)就束手无策了。 在上一篇文章有写到Miller Rabin可以在\(O(klog^{2}{n})\)的复杂度下判断一个数字是不是素数，这次要介绍的Pollard Rho（普拉德柔）算法就是结合Miller Rabin的快速素性检验来进行的一个复杂度大约为\(O(n^{\frac{1}{4}})\)来 […]

我们知道一般的素数判断是\(O(\sqrt{n})\)的复杂度的，当\(n \le 10^{14}\)且仅判断个数较少的情况下尚且能用，如果需要判断k个较大的数字（\(n \le 10^{18}\)）的数字，估计一下要运算\(k * 10^8\)之多，显然无法接受。 介绍 / Introduction 这里介绍的MillerRabin算法是一种可以在\(O(k*log^{2}{2})\)的复杂度内 […]

题目传送门：P4245 【模板】任意模数多项式乘法 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题目 / Problem NTT模板题，任意模数。 思路 / Thought 中国剩余定理。 代码 / Code

题目传送门：Problem - 7191 (hdu.edu.cn) 题目 / Problem 给定一个[1, n]的排列p和一个数字K，求[1, n]的子集T的个数。 子集T的大小为K，对于集合T中的任意一个元素x，p[x]不在该集合中。 思路 / Thought 排列的题很容易想到将i与p[i]连接起来，一定能组成若干个环，这里要求对于T中任意一个元素x，p[x]不能在T中，也就是说在若干个环中 […]

题目传送门：Problem - 7216 (hdu.edu.cn) 题意 / Problem 两个人玩游戏，给定3个数字，分别表示一个三角形的三条边，双方轮流进行一次操作，将三条边的其中一条减去一个正整数的长度，且使得新的三个数依然可以组成三角形。当无法操作时就输了。 思路 / Thought 先将结论，当(a - 1) ^ (b - 1) ^ (c - 1)不为0时必胜，否则必败。 典型的Nim […]

题目链接：Problem - 7152 (hdu.edu.cn) 题目 / Problem 有T个测试用例。 给定一个长度为N的数组，进行Q次操作。 每次操作有两种模式，模式1：选择一个区间[l, r]，将其复制一份并插入到这个区间右端点的后面，大于N的部分自动剔除。模式2：查询当前数组第x位的元素。 求所有操作模式2的查询结果的异或和。 思路 / Thought 我直呼牛逼！ 首先不难想到，当进 […]