平凡人Kalzn的博客

原创 面试-数据库基础以及MySql、ClickHost、Redis简介

0.数据完整性1.数据库并发控制1.1事物1.2 并发读写错误1.3 锁1.3.1 乐观锁与悲观锁1.3.2 共享锁和排他锁1.3.3 行锁与表锁1.3.4 意向锁1.4 封锁协议与隔离级别1.5 MVCC1.5.1 概念1.5.2 当前读与快照读2. 数据库范式3.分布式系统CAP定理4.灾备5.Mysql数据库框架与引擎5.1.1 框架5.3 数据库索引5.3.1 聚簇索引（InnoDB）和非聚簇索引（MyISAM）5.3.2 索引数据结构5.3.3 索引分类总结5.3.4 索引可用性5.4 主从复制。

原创 博客迁移说明

说明

原创 SMO算法流程

机器学习

原创 基于C++的朴素贝叶斯分类器

机器学习

原创 基于C++的简单深度学习ANN（人工神经网络）模型

机器学习

原创 AOP（面向切面编程）的简单理解笔记

AOP（Aspect Oriented Programming 面向切面编程）是从OOP（面向对象编程）衍生出来的，我查阅了各种书籍、网课，上面的都比较说法晦涩难懂，有甚者连基本概念都没讲就直接领着啃源码，个人太笨了，不太适应这种学习方式。还是没能正确的理解AOP的本质，最后终于在知乎的这篇提问下找到了相对简单的引例。回忆一下，OOP的三个要素，“封装”、“继承”、“多态”。其中封装要求我们将各种方法封装到一个类里面，这样做分散了代码和功能，无疑提高了代码的可维护性和可重用性，但是也产生了一些弊端。如果有

原创 我仍为一届平凡人(以此纪念我这差不多的本科三年、算竞生涯、失败的感情经历以及作为保研边缘人的历程）

也许还是我想多了，从大学入学一开始直至被国科大录取，我还是没能跳脱出自己的小圈子，我的大学三年至此，已经告一段落了。在此我记录一下我的大学三年。This is over, my university life.记录一些重要的时间节点时间事件2015年9月进入菏泽一中开始我的高中生活2016年4月和她在一起了2016年8月高二分班，我差一点去优等班，而她去了优等班2017年8月高三开始，我终于被分到了优等班，但是和她不是一班2018年6月-8月高考.

原创 KalznOJ评测机，有待完善的一个OnlineJudge评测机

暂时搞完了，准备考研了。考完研在搞。github项目地址Kalzn_Code_Judger简介这是一个使用c编写的online judge的评测机，将在完善优化后作为KalznOJ的评测沙盒。Judger每次从一个json文件中读入任务的配置信息。然后生成评测结果，在测试例中，结果将写入工作区目录下的result.txt文本文件中。在正式使用时可以将结果写入json。准备目前Judger仅在centOS7以及ubnutu20.04中测试过，理论上适用于所有支持seccomp沙盒机制的linux版

原创 2021年-蓝桥c/c++ b组国赛回忆题解

A这个题有点坑人，因为他不是一个算法题，而是一个计算机知识题，不知道出题人出这个题的意图。。刚拿到蒙了，但是回忆了一下，有次我手机限速，百度了一下1Mbps是多少。隐隐约约记得公式是1Mbps=0.125MB/s， 所以。。B利用素数筛达标，打到20210605，然后依次判定数字，以及每个数位是不是质数即可。注意这里不认为1是质数。C日期题，从2001.1.1枚举到2021.12.31，依次判断即可。Ddp可解。dp[i]dp[i]dp[i]为有iii个节点的二叉数的最小权值。则：dp[i

原创 我的明天

先报一下自己的成果吧，挺丢人的。2019 ACM山东省省赛 银奖2019 ICPC区域赛 银川 铜2019 ICPC区域赛 EC-Final 银2020 蓝桥杯 B组 国二（丢人）2020 CCPC 长春 银奖2020 天梯赛 个人国一2020 ICPC区域赛 上海 银奖（第38名）接触算比赛已经两年半了，算是我这篇博客的续集了，这半年里经历了很多事情。理论上也该退役了，但是因为疫情的影响，ICPC部分场次被推到了年后。不过年后真的就有点紧张了（要考研了嘛）。我是不太想找工作，毕竟顶着一个双

原创 状压dp （CCPC-长春 J - Abstract Painting）

题意：给你一个区间[0,n]，和k个圆，圆满足以下几点限制：1、圆上的任意一点的x坐标都在[0,n]之间。2、圆心是位于x轴上的整数。3、半径是1到5的整数。4、圆与圆之间最多1个交点。问：你再往上添加圆，同样满足上述限制，有多少种添法。题解：先说比赛情况，72名银，卧槽，还被73名的铜首老大哥挂知乎了，色色发抖QAQ。老大哥只比我们慢1min。比赛是推出了转移方程，但是没有写写出来，最后20分钟，在我和队友枪键盘中度过，他手里是K题，我手里是这个题。。。最后一个没过。dp[i][j]，

原创 强连通缩点/最长路 （石油大学组队赛 K: Birdwatching）

题意：给你一个有向图GGG，和其中的一个点TTT，你需要找到所有的满足以下条件的点T′T'T′。1、<T′,T>∈G<T',T>\in G<T′,T>∈G2、简单路径<T′,T><T',T><T′,T>只有一条题解：这个题起初大家交的很多，因为这个题看起来非常的简单，我也是，然后就直接建反图跑最短路上了。然后就wa了，一看大家都是73point。后来仔细想想，好像这个题没有这么的简单。我一开始的思路是：直接建反图，然后跑可达点。.

原创 线段树 （ICPC小米预赛第二场 C Data Structure Problem）

题目链接题意：给你一个两个序列bbb和aaa,序列ccc由其生成，生产方式为：c0=0,ci=max{ci−1+bi,ai}c_0=0,c_i=max\{c_{i-1}+b_i,a_i\}c0​=0,ci​=max{ci−1​+bi​,ai​}每次会对a、b进行单点修改，对c进行单点询问。题解：首先如果不考虑a序列的影响。那么ci=∑j=1ibic_i=\sum_{j=1}^ib_ici​=∑j=1i​bi​此时我们考虑因为有些位置，ai>bia_i>b_iai​>bi​所以，我们必

原创 二分/贪心（ICPC小米预赛第一场 A 2020）

题目链接题意：给你一个只包含0，1，2的序列，问你最多可以同时取出多少个“2020”子序列。题解：比赛时是队友写出的，赞叹队友的思维能力，真的强。二分答案，然后贪心取即可。检查时传入需要组成x个，遍历数组，每次遇到2，即优先让没有开始组成的序列获取，然后由已经组成到“20”的序列获取。每次遇到0，每次优先由已经组成“2”的序列获取，然后由已经组成“202”的序列获取。最后查看是否组成了x个“2020”下面是ac代码：// % everyone#include <cstdio>#inc

原创 题目图片

原创 hash (codeforces 1394B Boboniu Walks on Graph )

题目链接题意：给你一个k长度序列c，和一个有向图，对于任意一个出度为s的点，下一步都会沿着权值第c[s]小的边走到下一节点。问：有多少符合要求的序列c，使得按照这个序列走，对于所有的点，都可以走回自己。题解：真的不会。一看题解，好家伙，hash（bitset也可）。因为如果想要每个点都会走回自己。那生成图就要满足是几个环的集合。满足此情况的充分必要条件是每个点的出度和入度都是1。题目保证了权值两两不同，所有每个点的出度一定为1。所以我们建立一个入度序列d。如果一个终点为v的边呗被选择了，则有：d[v]

原创 线段树 （ICPC小米预赛第一场 E Phone Network ）

题目链接题意：给你一个1到n的数组。元素取值是[1, m]。对于1到m的每一个i。你要回答出至少包含[1,i]的所有元素各一次的最小区间长度。题解：距离出线只差一题。队友在搞G题构造，我在搞这个。最后没出。没办法。一看题解，发现真的只差一步就搞出来了：vector存入1到m的每个数字的位置序列。想到了。线段数维护每个点作为左端点时的最近右端点。想到了。从[1,i]递推[1,i+1]，因为这个数值单调可以二分寻找赋值。也想到了。最后一步通过最近右端点怎么维护最小区间长度，愣是没想到。很骚的是，题解也一笔带

原创 线段树/树状数组(codeforces 1404C Fixed Point Removal)

题目链接题意:给你一个长度为n的数组。我们定义一种操作，如果数组中有某个数满足ai=ia_i=iai​=i，即值等于它的下标，你就可以删去它，它后面的元素将全部往前移动一格。现在有m次查询，每次查询给你一对x，y。你要回答出，在不删除前x个和后y个元素的情况下，你最多可以进行多少次上述操作。题解：挺有意思的一道线段树。我们考虑离线，先把查询按照x排序。我们先考虑：对于一个元素而言，如果它的值大于了它的下标，那么这个元素就肯定不可能被删除。那么我们现在设：g=i−aig=i-a_ig=i−ai​。

原创 网络流/最大权闭合子图(石油大学组队赛 G: Trading Cards)

题意：给你n种物品和他们的价格，其中有一些是你拥有的，一些是你没有的，你可以自由买卖（价格一样）。最后有m种集合，如果你最后拥有的物品构成了某个集合，你就可以得到这个集合的价值。问：最后你最大可以拿到多少钱？题解：最大权闭合子图的模板题，不知道为啥没人过？QAQ。建模很简洁，1到m号点是集合，m+1到n+m是纸牌点，按照应用最小权闭合子图模型建图。这里有一点变形就是纸牌可以卖，我们不妨一开始全卖了，然后跑最小割。最后答案是 ： 所有集合价值+所有已拥有牌的价值-网络流最小割。下面是ac代码：//.

原创 Purfer序列

Purfer序列是一个元素值域均为[1,n]的，n-1个整数构成的序列。其可以与一个n阶完全图的生成树一一对应，形成双射。凯莱定理即由此而来。构造方法，树构造purfer每次选择编号最小的叶子节点，删去，然后把它的父节点的编号加入到序列后面，最后只剩下两个节点时算法停止。从上述构造 Prufer 序列的过程可以看出 Prufer 序列具有以下两个性质：1、在构造完 Prufer 序列后原树中会剩下两个节点，其中一个一定是编号最大的点 n。2、每个节点在序列中出现的次数是其度数减 1，因此没有出现

原创 支配树学习思路/模板

首先解释什么是支配树。首先我们先看一下DAG，我们现在有一个DAG：如果我们从1出发，对于图中的一个点ppp,在从1到ppp的不同路径中，总有一些点是必经的，例如图中的8号点，我们发现在从1到8的不管是那一条路径上，5都是必须经过的。（当然1号点和8号点用可以理解为必经的）。对于每一个点，如果把该点向上最近的一个必经点和该点连有向边。我们就得到了这个图的支配树。还是那这个DAG举例，我们按...

原创 字典树(codeforces1416C XOR Inverse)

题目链接题解:我们建立01字典树，将每一个数依次插入，在途径的点记录该位的0/1。我们思考，对于一个数的每一位（字典树的每一层）都有可能形成逆序对。对于p节点。我们查看途径他的0，1序列。可以O(n)O(n)O(n)记录其中<0,1>对和<1, 0>对的数量。我们把每一层的01和10对的数量记录下来。如果该位10对数量大于01对，即将这一位异或1反转。否则该位就是0。由此题启发，又找到一种O(nlogn)O(nlogn)O(nlogn)的统计逆序对的，使用01字典树方法。代码很短

原创 Tarjan点双连通分量(石油大学组队赛 K: Plan B)

题意, 给你一个无向图，给几个点染色。求这样的点的点集：删去这个点后，图剩余的联通块中，有至少一个不含有染色点。题解：首先知道，符合要求的点一定是割点，我们在原图上跑点双联通分量，然后进行缩点，缩点方式：每个双连通分量缩为一个点、然后新建虚拟节点作为割点，然后链接成为树。 形成树后，在树上统计信息。如果一个虚拟节点（割点）的某孩子中或者父节点方向没有染色点。则该割点为所求点。下面是ac代码：// % everyone#include<cstdio>#include<iostre.

原创 点分树(动态点分治)

前置知识点分治吐槽不知道为什么，网上有关点分树的讲解不多。而且都写的很简单（快哭了）。憨批实在是不懂。于是只能按照他们所给的思想手撸代码了。讲解我们在点分治中，使用了分治的思想，对于每个子树求解，我们都不会直接递归，而是找到重心后，从重心开始递归。这样在一些极端样例（一条链）的情况，仍能保证O(nlogn)O(nlogn)O(nlogn)不会退化为O(n2)O(n^2)O(n2)。这是一个很神奇的分治方式。这时我们试想这么一道题目：给你一颗n个节点树（n<1e5），给你m次询问（m&lt

原创 三分(石油大学组队赛 H: Mountain View UCF)

题意：给你几个点组成山脉的纵切面，一个横坐标对应一个y坐标，而且x递增给出。求一个长度为W的区间，让区间中的山的评价高度最大（即总高度最大）题解：这个题写崩了，虽然用了线段树，但是预处理前缀和就可以了。主要是比赛时候有点懵了。我们考虑：如果区间的两个端点都在山坡上（不跨越任何顶点），那么随着区间的滑动，总面积大小是一个单峰的，或者单调的函数。所有我们可以枚举每个不跨越节点区间段，然后执行三分。具体操作： int l = lisan[1]; int r = l - m; while(.

原创 dfs/思维(石油大学组队赛 E: Flow Finder)

题意: 给你一个树形河流(叶子节点是源头，往父节点流水)流量值会累加。现在给你一些节点的流量，问：能否唯一确定其他节点的流量。题解：我们思考，先从叶子节点往根节点dfs一下，如果一个点的孩子的流量都确定了，我们的父节点也可以确定了。然后我们在从根节点往叶子节点dfs一下，查看能否唯一确定一个节点的孩子。无非这样集中情况：(1) 父节点的值没有确定：此时不可能有唯一解，因为如果根节点可以确定的话，我们一定在第一遍dfs或者父节点的父节点处把它确定了。(2) 父节点确定，子节点有一个没有确定：此时.

原创 记忆化搜索（ 石油大学组队赛A: Rush Hour Puzzle）

题意：如图，把一号车从出口（3，6）弄出去，最少多少步，（10步以上输出-1）题解：没啥知识含量，就硬模拟，记录压缩状态dp[sta]，因为每个车都只会在自己所在的列、行移动，所以压缩是只记录一维就行。每个坐标最多6种情况（其实可以在针对车进行压缩，每个车都是4、5个情况。但是空间已经够了）。所以状态为6n6^n6n种，n为车的数量。然后就是模拟转移+记忆化搜索。下面是ac代码：#include<iostream>#include<cstdlib>#include<.

原创 状压dp（石油大学组队赛 J: Watch Later）

题意：给你一个字串，你每次可以选择一段连续的相同的字符删去，但是你以但选择了一种类型，你就必须把这个类型的所有区间段都删去，才可以考虑选下一种类型。为最少几步可以清空字串。题解：一直在考虑区间dp，后来经队友提醒才知道是状压（快哭了）。然而我不会（快哭了）。然后他们就过了（快哭了）。我们思考状压，二进制该位是1，即为选过这个字符了。然后状压dp模板，这里要知道的是状压dp的主过程就已经是O(2kk)O(2^kk)O(2kk)的了，所以只能O(1)O(1)O(1)转移状态，这里考虑预处理一个表sum[s.

原创 思维/构造(石油大学组队赛 E: The League of Sequence Designers)

应该不算太难的一道构造题,但是就没有想到，直接上代码吧，代码很容易就看懂了。#include<cstdio>#include<iostream>#include<cstring>#include <map>#include <queue>#include <set>#include <cstdlib>#include <cmath>#include <algorithm>#inc.

原创 双联通缩点/树上差分(石油大学组队赛I: One-Way Conveyors)

题意:给你一个n点m边无向图。你需要给每一个边定向，然后必须让所给的k对点是可达的。题解：首先明确一点，我们通过边定向，是可以将一个无向图边双连通块构成一个强连通块的。构造方法也很简单，直接在块内dfs，形成dfs树，将父节点指向孩子节点。因为是块是双连通，所有一定有另一个路径使该点走回根节点。所以，形成的图一定是强联通的。所以我们在原图上跑tarjan，跑出边双连通分量，分量内部定向构建强连通。然后分量一定形成一棵树。如果一对点在一个分量内部。肯定可达。而如果在两个分量之间，我们就进行树上差分。维护.

原创 数位dp/二分/思维（石油大学G: A-Number and B-Number）

题意：有两种序列A-Number和B-Number。A-Number是所有数位中有7的和被7整除的数。B-Number是A-Number序列除去下标是数位中有7的和被7整除的数。问：第N个B-Number是。题解：这个题只要想明白了，就特别水。我们可以考虑二分结果。然后计算他前面有多少个B-BNumber。如果比N大则缩小，否则增大。那怎么找他是前面有多少个B-Number呢。很简单，我们设F(x)为[0, x]之间A-Number的数量。那么数x之前有ans个B-Number：ans=F(x)−F(.

原创 Trajan/强连通（石油大学组队赛 B: Thrall’s Dream）

题意：给你一个有向图，和两个点x，y。你要判断一个点能不能到达另一个点。题解：用tarjan跑强连通然后缩点建图，然后在新图上dfs出一个点能到达和被到达的点。跑出一个邻接矩阵来，如果矩阵全1则可以，否则不可以。比赛时是Case后面加了个#号，是很悲伤的。下面是ac代码：#include<cstdio>#include<iostream>#include<cstring>#include <map>#include <queue>.

原创 dp/模拟(石油大学组队赛 A Famous Equation / HDU-4249)

题目链接题意：给你一个等式，里面只有一个+号和一个=号，有些数位被隐藏为？号，不允许前导零。问：有有多少种方案让等式成立。题解：一个模拟加+dp，我们记dp[i][2]为三个数考虑到第i位，这一位有没有进1的方案数。按照三个数的情况分类讨论。我们可以对每一位？的最小取值打个标记，即如果？号在一个数的开头，那么它只能最小取1，而不可以取0，否则就可以取到0。因为时间充足，我们可以枚举三个数每一位的取值情况（其实可以O(1)O(1)O(1)进行状态转移）。最后时间复杂度为O(d∗93)O(d*9^3)O

原创 计数dp（石油大学组队赛 HDU-4248 A Famous Stone Collector）

题目链接题意：有n中石头，第i种有ai个，随意取石头排成一个序列，问：有多少种非空排列方式。题解：首先一个队都在想生成函数：显然是生成函数的模板题，但是一看模数是1e9+7懵了。队友的MTT当场tle。然后陷入了沉思到比赛结束。比赛后一看题解，很好，dp。然后一看HDU的时限是15s（中石油oj是1s）。队友当场口吐芬芳，在HDU交了一发MTT，遂过。本憨批不会MTT，只得用dp做，QAQ。首先考虑dp[i][j]为考虑前i种石头，序列长度为j的求法。显然是个很水dp，，（上了就想生成函数太伤了）

原创 最小生成树/二分/思维(石油大学组队赛 HDU-4253 Two Famous Companies)

题目链接题意，给你一个无向图，边分黑白，而且有权值。固定使用k个白边，n-1-k个黑边。问：最小生成树。题解：不看题解，再给本憨批800年也想不出这种解法。首先说做法：我们把所有白边都加上一个值C（可为负数），则此时显然在排序后白边的位置会整体往前/后”偏移“一段距离。我们二分C的值，然后求最小生成树，直到而分出一个刚好用k条白边的情况。这个最小生成树的值即为所求。粗略证明：此部分证明是我自己推定的，，，可能会有错误，酌情参考首先考虑最小生成树，但是这时白边的数量可能不符合要求。假定现在白边选多

原创 可并堆（左偏树）

如题意，即为可以合并的堆，在普通堆的基础上，我们在计入每个节点的父节点和该节点子树距离这个节点最近的叶子。我们在原堆的基础上追加一个性质：树的左孩子的距离不小于有孩子的距离（左偏），为什么要这么做呢，注意是建少合并时的数量。（启发式合并思想）。于是合并时，我们，针对堆的性质，对于两个节点，我们尝试把权值大的点挂在到小的点上（小根堆），然后进行递归处理。处理完成后，然后如果左孩子的距离小于右孩子的距离，即交换两个节点。另外有pop操作，我们取出首节点后，清除首节点，然后合并他的左右孩子即可。#inclu

原创 威佐夫博弈扩展（HDU-6869 Slime and Stones）

威佐夫博弈扩展第i个奇异局面为：a[i]=⌊1−k−k2+2k+52i⌋a[i]=\lfloor\frac{1-k-\sqrt{k^2+2k+5}}{2}i\rfloora[i]=⌊21−k−k2+2k+5​​i⌋b[i]=⌊3+k+k2+2k+52i⌋b[i]=\lfloor\frac{3+k+\sqrt{k^2+2k+5}}{2}i\rfloorb[i]=⌊23+k+k2+2k+5​​i⌋当k=0时，即为威佐夫博弈的结论。做差即可验证：b[i]−a[i]=⌊(k+1)i⌋b[i]-a[i]=

原创 LCT/尺取（HDU-6858 Discovery of Cycles）

题目连接题意：给你一个n点m边无向图。有q次查询，每次查询区间l， r。问：该区间中的边形成的子图能否构成至少一个简单环。查询必须在线。题解：对于每个边i，我们都可以找出从它开始最早的可以形成简单环的端点，即区间[ i, ans[i] ]，这里有结论，f(i)=ans[i]是单调递增的。所以可以尺取。对于所有i，求出最短区间，然后就可以O（1）查了。这里需要一个数据结构：可以动态断边、删边、并查看该图任意两点的联通性（又不需要真正的连接环，这点很重要）。显然是LCT了。在判定两点是否联通时，我们先

原创 结论/数学（HDU-6853 Jogging）

题目连接题意，给你一个坐标（x，y），在周围的8给方向里，如果gcd（x，y）！=1，则可以走过去，这是等概率的。为最后回到起点的概率。题解：结论：如果不可以经过对角线，ans=（起点的度数+1）/（图的总度数+联通块大小）。如果经过对角线即为0/1。因为联通快不会很大。所以可以直接搜索 。下面是ac代码：#include<cstdio>#include<iostream>#include<cstring>#include <map>#inc

原创 树形dp（HDU-6820 Tree）

题目连接题意：给一颗带边权的树，你要求一个最大权联通快，要求里面超过k度的节点只能有一个。题解：这个题解不是官方思路。而是一位大佬的思路。首先，我们dp[i][2]表示第i个节点为根的子树。有没有与fa向连的最大权值。我们不妨先考虑，没有大于k度的节点，然后再对于每一个节点，令它的度数大于k，从而求出最大权。显然对于dp[i][0]，他最多可以连接k个孩子，对于dp[i][1]，他最多可以连接k-1个孩子。我们首先要择优选取。我们首先递归孩子，得出孩子节点的最大权值，再以（孩子的最大权值+这条边的