remi-riyaの博客

主要记录一些注意事项 关于第一次运行项目的一些坑 本地测试都使用了DISABLE标记，需要加上参数--gtest_also_run_disabled_tests才能运行测试用例，一种方便的解决方法是这样配置launch.json文件 123456789101112131415161718192021222324252627{ "version": "0.2.0", "configurations": [ { "name": "Debug disabled test", "type": "cppdbg", "request": "launch", "program": "${command:cmake.launchTargetPath
...

暂时只是零散的记录一些东西，等有了整体的认知之后再整理 数据库领域最重要的一句话： 天下没有免费的午餐，各种设计都有其优缺点。 数据库系统结构，从上往下 Query Plan 查询计划 Operator Execution 执行操作 Access Methods 访问方法（向上提供访问方法） Buffer Pool Manager 缓冲区管理器（将磁盘内容载入内存） Disk Manager 磁盘管理器 Page 硬件Page，通常大小为4kb，操作是原子的 操作系统Page，通常大小为4kb，有巨页 数据库系统Page，数据库系统自己定义的Page 面向元组存储 行存储常使用槽页，槽数组从前往后扩展，元组从后往前扩展。槽数组存储偏移值。 日志结构存储 内存中有一个mem表，用于快速更新，如果mem表满了就写入disk中的SSTable，在disk中有层级，每当一层满了后就合并SSTable并将新的SSTable放入下一层级。 缺点：元组生命周期伴随整个数据库， 索引组织存储

不知不觉好久没有写博客，自从开始考虑工作之后就日渐焦虑，打了一年铁开始准备找工作才发现自己只会C++，再加上可能是生涯最后一场XCPC的CCPC东北邀请赛因为不会看钟喜提铜牌，一直都感觉干什么都提不起劲， 直到昨天看到C++群群主的回答想走数据库内核方向，该怎么办？ - soulmate的回答 - 知乎，才又明确了方向。我一直都希望以后的工作能够是偏向计算机底层的基础设施，比如系统、引擎、框架，但又担心找不到工作，毕竟计算机大部分都是前端后端，很少看到招这些的厂商。也因此学了Go，准备走后端路线。但是现在既然看到了一条理想中的全新道路，并且有一点希望，我还是决定拼一把，遵从内心的选择，选择一条虽然难度可能很大但是喜欢的道路，就像当年选择打ACM一样。

由于大部分情况下只有在项目创建时才会写一下CMake，甚至在用了项目模板之后连创建的时候也不需要写，因此老是忘记一些东西要怎么写，故写个笔记方便以后查看。目前只记录一些最常用的函数，后续再逐渐补充，并添加一些教程。 特性 在CMake中不论Linux还是Windows都使用/作为路径分割符 常用函数 通用函数 cmake_minimum_required 这个函数用来指定脚本所需的CMake最低版本，比如你用到了一些高版本CMake的语法，就可以用这个函数来指定最低版本，一般放在CMakeLists.txt的第一行，比如cmake_minimum_required(VERSION 3.13)。 project 指定项目名称，LANGUAGES字段可以指定项目使用的语言，目前支持以下语言： C，C语言 CXX，C++ ASM，汇编 Fortran，Fortran语言 CUDA，英伟达的CUDA OBJC，苹果的Objective-C OBJCXX，苹果的Objective-C++ ISPC，一种英特尔的自动SIMD编程语言 VERSION字段可以指定项目版本，CMake使用 ...

花了我将近两天时间Debug的阴间题，写完感觉人生都空虚了（；´д｀）ゞ 题意还是很简单的，思路也很明显，就是记忆化搜索，或者像题解一样直接都预处理出来。 这题的图跟一般的图主要的区别在于图中的环是无法从外部进入的，因为光路是可逆的，所以光路只有两种可能，要么在一个环中死循环，要么形成一条链最后射出边界，虽然听起来很简单，但是我写了整整三个版本的代码，前两个版本都是没有考虑全面导致实现有问题，都是过60%，其中一个在我找出一个错误样例并改对后信心满满的交了一发之后从过60变成了过30…… 下面是翻车经历： 最开始的时候我只开了两个数组，一个记录是否被访问，一个记录答案，然后发现一面镜子可能在一条路径中被访问多次，于是又开了一个数组记录路径编号，交一发喜提wa（以下代码都经过多次修改，我也不确定是不是当初交的那一版_(:з)∠)_） 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686 ...

可持久化数据结构是指在每次修改后都保存了修改前版本的数据结构。在可持久化数据结构中，我们可以很方便的追溯到某次修改前的版本，以此来完成某些操作。简单来说，对于nnn次插入操作，我们就存储nnn个版本，第iii个版本对应了前iii次操作后的数据结构。当然，不可能真的存nnn个完全独立的版本，空间会直接爆炸(～￣▽￣)～。可以注意到，对于Trie和线段树等数据结构来说，每次插入只改变了一条链上的节点，因此对于每次插入操作，我们只需要新建这条链上的节点，而其他的节点可以直接白嫖上一个版本的。 常用的可持久化数据结构主要有可持久化的Trie和可持久化线段树。 可持久化Trie 首先，既然有nnn个版本，当然就对应了nnn个根节点，从不同的根节点开始遍历就可以得到不同版本的数据结构。下面简单演示一下可持久化Trie的插入过程。 最开始是一个空的Trie，插入一个字符串no（黑色节点表示根节点） 然后插入一个字符串game，由于这整个字符串都属于要改变的节点，所以都要新建，同时，为了从新建的根节点能够访问到以前插入的字符串，新的根节点也要有边连向n 继续再插入一个字符串no，但是no之前已经插 ...

（本文章主要涉及Nim博弈及相关变种，二分图博弈以后再补_(:з)∠)_） Nim博弈是最经典的博弈论问题之一，一般可以描述为如下：两个人轮流从若干堆石子中取石子，每次只能取一堆石子中的任意个，最后无法取（即所有石子都被取完）的玩家判负。Nim游戏拥有简洁的规则和优雅的结论，也是SG函数的基础。 基本概念 首先明确一些概念，Nim博弈是公平组合游戏（Impartial Combinatorial Games, ICG）的一种，所谓公平组合游戏，需要满足以下几个条件 有两个玩家 两个玩家轮流操作，在一个有限集合内任选一个进行操作，改变游戏当前局面 一个局面的合法操作只与游戏当前局面有关，与当前玩家和次序等其他因素无关（公平） 无法操作者判负 为什么要提这个呢？因为从这些条件里，我们可以得出一个最基本的定理：一局游戏的胜负只与当前的局面有关，与当前是哪个玩家在操作无关，因为当局面确定，由于合法操作不受其他因素影响，那么其所有可以进行的操作与操作后的局面都是确定的，在两个玩家都绝对理性的情况下（这是大前提，否则就没有意义了），其胜负自然也是确定的。 那么，我们就可以把所有局面分成两种：必 ...

BSGS算法（baby step giant step，大步小步算法），又叫北上广深算法（不是），是一种基于中间相遇思想求解离散对数的算法，即求解类似于ax≡b(modm)a^x\equiv b\pmod max≡b(modm)的方程。 BSGS算法 首先介绍最普通的BSGS算法。普通的BSGS算法要求mmm和aaa要互质，既然互质，那么根据欧拉定理 aφ(m)≡1(modm)a^{\varphi(m)} \equiv 1\pmod m aφ(m)≡1(modm) 也就是说，ax(modm)a^x \pmod max(modm)以φ(m)\varphi(m)φ(m)为周期循环，那么如果方程有解，解一定在000到φ(m)\varphi(m)φ(m)之间，如果暴力枚举，当mmm为质数时φ(m)\varphi(m)φ(m)最大为m−1m-1m−1，最坏复杂度为O(m)O(m)O(m)。 普通的BSGS算法就是对上述暴力算法的一个优化，我们可以把xxx改成At−BAt - BAt−B，那么原式变成aAt−B≡b(modm)a^{At - B} \equiv b \pmod maAt−B≡b(m ...

相信被头歌的禁止复制粘贴恶心到了的人肯定不止我一个，这次写一个链表的题，每一关都要用到上一关的代码，每一关都要重新把4种构造函数和4个功能函数重新打一遍，只能说很符合我对头歌的印象😅😅😅。 于是本着偷懒顺便造福大众的想法，我开始寻找解决的办法。经过一天一夜的尝试与搜索，终于找到了一种解决办法：调用系统API模拟键盘输入。 UPD：添加了一种新的方法，使用SendInput函数，可以输入中文。 正文 如何调用系统API呢？如果是大佬当然有无数的方法，但我们作为小白，选择最简单的方法就好了，那就是我们无敌的Python（撒花） 首先，安装PyWinHook和PyUserInput PyWinHook是Python的一个第三方库，可以对键盘、鼠标进行监听，PyUserInput可以模拟键盘鼠标输入。 https://www.lfd.uci.edu/~gohlke/pythonlibs/#pywinhook 在网址中找到对应的版本下载，如我的Python版本是3.10.10 64bit，那么就下载pyWinhook‑1.6.2‑cp310‑cp310‑win_amd64.whl，cp31 ...

Splay树，即二叉伸展树，是一种非严格平衡的二叉搜索树，由丹尼尔·斯立特Daniel Sleator 和 罗伯特·恩卓·塔扬Robert Endre Tarjan 在1985年发明（摘自百度百科）。相比与AVL、红黑树而言，Splay树不需要额外地存储平衡信息，因此显得更为简洁，代码实现也较为简单（指150行代码），同时具有很强的扩展性，常用于算法竞赛中。 至于我为什么突然想要学Splay树，因为这是Tarjan发明的……没错，就是求强连通分量、割点、桥的Tarjan算法的那个Tarjan。事情的起因是我最近刚学完强连通分量，然后查了一下Tarjan的资料，发现原来是祖师爷级别的大佬，拿过图灵奖，发明了很多图论的重要算法和数据结构。于是就对Splay树产生了兴趣，虽然这玩意已经明显超过了我的算法水平（刚学完强连通的蒟蒻），但我还是自不量力毅然决然地花了两天手搓了Splay，然后又花了一天的时间调试。 那么废话了那么多，接下来正式介绍Splay树 （以下内容和代码部分抄袭参考自oiwiki和其他人的博客、文章等） （图片均使用开源网站ioDraw绘制，感谢开源者的贡献） 基本成员 S ...