关于博客的一些事
这是我一次建立自己的博客，希望在博客上分享自己的生活学习。得益于Sanstale的帮助，使我能够顺利地把博客部署到网站。特此表达感谢之情，也希望大家能去看看他的博客，以下是链接。https://www.cybereal.one/
哈希表
...
并查集，优先队列，双端队列
并查集当我们碰到堆的划分问题时候我们可以用到并查集，其实就是每个节点通过一个父节点来存储信息，然后通过递归的方法将一个堆中所有子节点或叶子节点的父节点全部指向根节点，而根节点的父节点指向自己。本来我没有了解到这一层的时候认为堆的合并将会是很困难的事，因为每个父节点是不一样的，但现在就好办了，我们只要把两个根节点给合并，最后再递归一下就算成功了。它的时间复杂度比o（log n）很快，是反阿克曼函数，接近于o（1）。 12345678910int find_set(int i) { if (fa[i] == i) return i; return fa[i] = find_set(fa[i]);}void union_set(int a, int b) { a = find_set(a); b = find_set(b); if (a != b) fa[b] =...
博弈论的一些很基础知识
公平组合游戏公平组合游戏是两个人进行的游戏，回合制并且每个人操作的对象是同一个，换言之每一步状态，怎么操作都与操作者无关，两人都是全知全能，进行每一步操作时都了解后面操作的所有状态，去选择对自己最有利的解，这就叫做公平组合游戏，而基础的博弈论就是探讨这种情况的。 博弈论中最基本的知识在进行公平组合游戏时，每一步的状态可以概括为两种。p态：后手必胜，即这个回合开始时操作者的对手一定会赢。n态：先手必胜，即这个回合开始时操作者一定会赢。知道这两个概念之后不难推出两个结论。 能变成p态的状态一定是n态。因为每个人都想要最优解，如果前面已经先手必胜，那么等于可以选择下一回合自己变成后手必胜。当然也可以不选，那么就会输。 p态只能变成n态。这个回合我是后手必胜的状态，无法操作，但由于是必胜的状态，下一回合我操作一定是先手必胜。 sg函数sg函数是决定谁胜谁败的关键。我们规定sg函数的公式为 g(x)=mex{g(y)}...
欧几里得的游戏
本来我是完全没有接触过博弈论的，但是今天看到了这道题，用到了Euclidean Game 定理。搜了一下，发现这玩意好像有点意思，就写一下。 题干欧几里德的两个后代 Stan 和 Ollie 正在玩一种数字游戏，这个游戏是他们的祖先欧几里德发明的。给定两个正整数 M 和 N，从 Stan 开始，从其中较大的一个数，减去较小的数的正整数倍，当然，得到的数不能小于 0 。然后是 Ollie，对刚才得到的数，和 M , N 中较小的那个数，再进行同样的操作……直到一个人得到了0，他就取得了胜利。下面是他们用(25,7) 两个数游戏的过程： 初始：(25,7)；Stan：(11,7)；Ollie：(4,7)；Stan：(4,3)；Ollie：(1,3)；Stan：(1,0)。Stan 赢得了游戏的胜利。 现在，假设他们完美地操作，谁会取得胜利呢？ Input本题有多组测试数据。第一行为测试数据的组数 C 。 下面 C 行，每行为一组数据，包含两个正整数 M , N(M , N<2^31)M,N(M,N<2^31)。 Output对每组输入数据输出一行，如果 Stan...
高斯消元，快速幂和一些拓展
标准快速幂平时计算幂次时计算机的一般方法其实就是累乘，比如2^8就是222*2一直乘下去，这带来了极高的时间复杂度，大概是o（n），那么快速幂就是对于这种计算方法的优化，继续拿2的8次方举例，他会判断幂次是奇数还是偶数，发现是偶数，先对底数进行平方，变成4^4，然后继续操作，时间复杂度大概是o（logn）。这为什么能加快速度，其实是因为这样计算减少了计算规模。当然使用这种方法必须让你手写一个函数。 123456789long long qpow(long long a, long long n, long long mod) { long long res = 1; while (n > 0) { if (n & 1) res = res * a % mod; // 当前位是1 a = a * a % mod; // a翻倍 n >>= 1; // 指数右移，相当于除以2 } return...
线段树
线段树的设计是一颗二叉树，用来维护一个序列中各个区间的信息，像什么最大值，最小值，最大公因数等等，因为设计是二叉树，所以时间复杂度大约是（o logn），线段树的精髓是懒标记，懒标记是存储操作的方法，比如我们要在单点修改一个节点，不过操作不会马上进行，会存储在懒标记当中，然后在下次查询的时候执行操作，就可以压缩时间。以下是基本的模板。首先是建立线段树，通过递归建立左树和右数无限二分来实现的，先对叶子节点进行单独处理，然后就是对一般情况递归建立左右树直到遍历到叶子节点。 12345678910111213void build(int i, int l, int r) { tree[i].l = l; tree[i].r = r; if (l == r) { tree[i].val = arr[l]; // 叶子节点 return; } int mid = (l + r) / 2; build(i*2, l, mid); //关键递归 build(i*2+1, mid+1, r);...
kmp字符匹配算法，字典树，以及ac自动机
kmp字符匹配算法，字典树，以及ac自动机最近一直在写匹配问题，其实也没办法，难的自己也不会，只能写点简单的。但有一说一ac自动机是一个很有意思的算法。 kmp字符匹配算法先说kmp的时间复杂度，在给定两个字符串进行匹配的情况下，假设是最坏的情况一位位比较，那么正常两层循环算法的时间复杂度是o（n*m），而kmp算法能讲时间复杂度下降为o（n+m）。这是怎么做到的呢，kmp的原理是什么？比如给定两个字符串，主串是ababcababcac，要匹配的模式串是ababcac。kmp算法要做的就是适当的跳过，前面几位肯定是能吻合的，当匹配到第七位时候不适配了，这时候模式串第二位和主串第七位开始比较，最后得出结论。实现就是通过一个next数组来记录模式串的最大前缀和最大后缀相等的个数，比如对于ababcac，他的next数组是[0, 0, 1, 2, 0, 1,...
双指针单调栈一些写法
双指针单调栈一些写法双指针双指针本质其实是对两层for循环的一些优化，我们知道两层循环的时间复杂度大概是在o（n^2），而双指针往往只用了一层遍历就达到了目的，时间复杂度在o（n）。双指针的写法主要依据题目而定，但往往题目对于答案有多个限制要求，标准写法往往是通过for循环或者while循环使右指针有一个从左到右的遍历，然后左指针在满足条件的情况下缩短与右指针的距离。举一个例子。给定一个正整数数组 nums 和一个目标值 s，找到 和 ≥ s 的 最短连续子数组的长度，如果不存在这样的子数组，返回 0。输入：s = 7nums = [2,3,1,2,4,3] 输出：2 解释：子数组 [4,3] 的和是 7，长度为 2，是满足条件的最短子数组。我们不难发现这道题有几个限制要求，一个是 ≥ s 另外一个是最短连续子序列，那么内层循环要做的就是在 ≥ s的情况下缩短子序列长度，下面是示例代码。 12345678910111213141516int minSubArrayLen(int s, vector<int>& nums) { ...
二分三分以及01分数规划
二分三分以及01分数规划二分算法二分算法的本质是求严格增或严格减函数，数列，数组中的某一特值，通过将整个区间无限对半开，找到答案所在的区间，经过多次迭代后区间左边界等于区间右边界，或两者无限逼近，那么这个答案就是解。既然知道二分就是对于n个数对半开，那么如果将查询每一个数的时间复杂度视作为单位时间复杂度o（1），二分的时间复杂度就为o（log n），这比在数组中遍历每个元素o（n），快上很多。在一般算法竞赛中或者实际生活中，有时会需要我们去用到二分算法，那么他的标准模板是什么呢？我们如何在c++中运用它呢？ 12345678910int binarySearch(vector<int>& a, int target) { int l = 0, r = a.size() - 1; while (l <= r) { int mid = (l + r) / 2; if (a[mid] == target) return mid; else if (a[mid] < target)...
