tzyt的博客

C. Train and Queries 题意： 题目链接（CF，洛谷） 给你一个长度为 n(1≤n≤2⋅105)n (1\le n \le 2 \cdot 10 ^ 5)n(1≤n≤2⋅105) 的数组 uuu。代表所有的火车站。火车只能从左边的站台开到右边的站台。也就是从 u1u_1u1​ 开始，再到 u2, u3u_2, \ u_3u2​, u3​，最后到 unu_nun​。 现在给你 k(1≤k≤2⋅105)k (1\le k \le 2 \cdot 10 ^ 5)k(1≤k≤2⋅105) 个询问，每个包含两个整数 aia_iai​ 和 bib_ibi​，问你是否可以从 aia_iai​ 这个站台开始，坐火车到 bib_ibi​。 比如：uuu 数组为 [3,7,1,5,1,4][3,7,1,5,1,4][3,7,1,5,1,4]，有以下三个询问： a1=3,b1=5a_1 = 3, b_1 = 5a1​=3,b1​=5。 从 333 号站台坐车到 555 号站台是可能的，有以下路径：[3,7,1,5][3,7,1,5][3,7,1,5]。 a2=1,b2=7a_2 = 1, ...

upd@2022/9/14：最近把实验的代码放到 github 上了，如果需要参考可以查看这里： https://github.com/ttzytt/xv6-riscv 里面不同的分支就是不同的实验。 开始之前先吐槽一句，为什么 xv6 源码的码风这么怪啊？？？函数的返回类型居然跟函数名不在同一行？？ int main(int argc, char* argv[]){ } 像这样…… 然后就是建议阅读时关闭暗黑模式（右下角齿轮标），因为有些图片上的字是黑的，开了暗黑模式就看不清了。 Lab 1: utils 实验说明地址：https://pdos.csail.mit.edu/6.828/2020/labs/util.html sleep 实现一个 sleep 命令，唯一的参数是休眠的时间。 因为有系统调用，所以实现起来还是比较简单的，可以直接调用提供的 sleep 系统调用。 唯一需要注意的是要在 #include user/user.h 之前先 #include kernel/types.h。这个文件里面包含了一些类型的定义，而 user.h 需要用到这些 ...

书的链接（中文翻译版）：https://github.com/duguosheng/6.S081-All-in-one 第零章 这章大部分的内容还是能够看懂的，但是在管道的示例程序上卡了很久。最后终于搞懂了，这里把我的理解写一下： int p[2];//p[0] 储存管道接收端的文件描述符，p[1] 为管道发送端的描述符 char *argv[2]; argv[0] = "wc"; //第一个参数是命令的名字 argv[1] = 0; //stdin pipe(p); //子 p[0] <--------- p[1] 父 if(fork() == 0) { close(0); dup(p[0]); close(p[0]); close(p[1]); exec("/bin/wc", argv); } else { write(p[1], "hello world\n", 12); close(p[0]); close(p[1]); } 首先需要注意的是父子进程的文件描述符是共享的，比如这里的 pipe() 函数，看似是运行子进 ...

题目链接（CF，洛谷） | 强烈推荐博客中观看。 这题是真的难想，我 cf 的题解看了好久才搞明白（我太菜了）。 题意 给你一个长度为 nnn 的排列 aaa，请你找出有多少个相同长度的排列 bbb 和 aaa 相似。 如果对于所有区间 [l,r](1≤l≤r≤n)[l, r] (1 \le l \le r \le n)[l,r](1≤l≤r≤n)，下面的条件满足： MEX⁡(al,al+1,…,ar)=MEX⁡(bl,bl+1,…,br)\operatorname{MEX}(a_l, a_{l + 1}, \ldots , a_r) = \operatorname{MEX}(b_l, b_{l + 1}, \ldots , b_r) MEX(al​,al+1​,…,ar​)=MEX(bl​,bl+1​,…,br​) 我们就称排列 aaa 和 bbb 是相似的。 其中 MEX⁡\operatorname{MEX}MEX 对于数组 ccc 的定义是：最小的，没有出现在 ccc 中的非负整数 xxx。 例如 MEX⁡([1,2,3,4,5])=0 MEX⁡([0,1,2,4,5])=3\o ...

背景 大概一年多之前看了《复杂》这本书，最近因为一个比赛又想起了书里面介绍过的遗传算法，书里提供了详细的思路，所以想自己实现以下。 关于《复杂》这本书：不过多介绍内容，看完了只感觉非常牛逼，下面的介绍摘自豆瓣，自己加了一些标点符号： 蚂蚁在组成群体时为何会表现出如此的精密性和具有目的性？数以亿计的神经元是如何产生出像意识这样极度复杂的事物？是什么在引导免疫系统、互联网、全球经济和人类基因组等自组织结构？这些都是复杂系统科学尝试回答的迷人而令人费解的问题的一部分。 理解复杂系统需要有全新的方法。需要超越传统的科学还原论，并重新划定学科的疆域。借助于圣塔菲研究所的工作经历和交叉学科方法，复杂系统的前沿科学家米歇尔以清晰的思路介绍了复杂系统的研究，横跨生物、技术和社会学等领域，并探寻复杂系统的普遍规律，与此同时，她还探讨了复杂性与进化、人工智能、计算、遗传、信息处理等领域的关系。 书中讲的问题大概是这样的： 有一个机器人罗比，它生活在一个 10×1010\times 1010×10 的网格中。这个网格中散落着许多易拉罐，罗比需要在有限的动作中收集尽可能多的易拉罐。罗比的初始位置在 ( ...

题目链接（CF，洛谷） | 强烈推荐博客中观看。 题意 给你一个 n×mn \times mn×m (1≤n,m≤10001 \le n, m \le 10001≤n,m≤1000) 的格点图，每个格子的值要么是 −1-1−1，要么是 111，现在问你，是否有一条从 (1,1)(1, 1)(1,1) 到 (n,m)(n, m)(n,m) 的路径，使得路径上经过的格点的值的和为 000。在路径中，只能从 ai,ja_{i, j}ai,j​ 移动到 ai+1,ja_{i + 1, j}ai+1,j​ 或是 ai,j+1a_{i, j + 1}ai,j+1​（向右或是向下走）。 思路 看到这个 (1≤n,m≤10001 \le n, m \le 10001≤n,m≤1000) 的数据范围就知道暴搜肯定要寄了（别学我），所以得想一些别的办法。 首先，如果经过奇数个格子，或者说 n+m−1n + m - 1n+m−1 为奇数，那么肯定没有这样的一条路径（经过的 −1-1−1 和 111 点没有办法相等）。 直接判断某个格子图是否符合要求太麻烦，我们可以思考，如果有任意一条路径，我们是否能根据这条 ...

题目链接（CF，洛谷） | 强烈推荐博客中观看。 打的第一场 CF div.4 这个题就是那种想到点了就很很简单，没想到的话就……寄了的题（我就属于是寄了）。 1. 题意： 给你一个长度为 n (∑n<2⋅105)n \ (\sum n < 2\cdot 10^5)n (∑n<2⋅105) 的数组 aaa，问你在这个数组中，有多少个长度为 k+1 (1≤k<n)k + 1 \ (1\le k < n)k+1 (1≤k<n) 的区间，符合以下的条件： 20⋅ai<21⋅ai+1<22⋅ai+2< ⁣⋯<2k⋅ai+k注：i为这个区间开始的位置2^0 \cdot a_i < 2^1 \cdot a_{i + 1} < 2^2 \cdot a_{i + 2} < \dotsi < 2^k \cdot a_{i + k}\\ \footnotesize{注：i 为这个区间开始的位置} 20⋅ai​<21⋅ai+1​<22⋅ai+2​<⋯<2k⋅ai+k​注：i为这个区间开始的位置 2. ...

今天发完 Treap 的博客之后自己看了一遍，突然感觉很不爽。Treap 的这篇博客大量的用到了指针和箭头运算符，因为博客的字体没有连字（ligature）的功能，所以看着特别傻。于是我决定把博客的字体换成 Iosevka。 以下是一些我参考的网站 https://imbhj.com/25c13146/ https://zhuanlan.zhihu.com/p/361392320 基本的思路还是写一个 css 文件，然后在 html 的 head 部分注入进去。最后再在 hexo 的设置中把字体改成你想用的字体。 我改完写完 css 然后上传了字体文件之后 hexo s 了一下，发现没问题。不过很奇怪的是部署到 github 之后如果开 linux 的虚拟机访问，或是用手机访问，都不能正确的加载字体。 于是我就尝试 f12 了一下，打开 css 文件之后发现 css 文件变成了这样： <link rel="stylesheet" type="text/css" href="https://cdn.jsdelivr.net/hint.css/2.4.1/hint.min.css ...

一些废话 最近发现以前学过的算法都非常容易忘，像什么后缀自动机，AC 自动机，插头 dp，都基本全忘了（甚至 KMP 和网络流这种太久没写也有点忘了，我太菜了）。所以在想，可以在学的时候就做笔记，以后忘了直接看笔记就行。 然后就有了这篇博客，不过学习笔记类的文章不会跟题解一样详细，主要还是给自己看的，之后有时间的话可能会写教程类的文章。 upd 2022/6/19：把给 OI-wiki 写的文章搞过来了，感觉现在已经可以作为一个教程类文章了。不过还需要添加无旋 treap 的内容。 upd 2020/7/1：把给 OI-wiki 写的无旋 treap 和无旋 treap 的区间操作部分复制了过来、本文中的无旋操作几乎都是我写的，如果你想了解具体的贡献者可以看 OI-wiki 的 GitHub 页面。 因为图片的颜色问题，建议关闭黑暗模式观看。 简介 Treap（树堆） 是一种 弱平衡 的 二叉搜索树。它同时符合二叉搜索树和堆的性质，名字也因此为 tree （树） 和 heap （堆） 的组合。 其中，二叉搜索树的性质是： 左子节点的值（val\textit{val}val）比父节点大 ...

题目链接 博客中观看体验更佳 1.题意： 给你一个有 nnn 个节点的树，一开始，每个节点都是健康的。每秒钟你可以进行下面两种操作： 传播：对于一个节点，如果它的至少一个子节点被感染了，那么可以感染它的另一个子节点。（如果有多个节点符合条件，那一秒钟就可以传播多个节点） 注射：你可以任选树中的一个节点进行感染。（一秒钟只能多感染一个节点） 现在问你最少需要多少秒才能感染整个树。 2.思路： 看完题我们要注意到，这个题说的是节点可以把病毒传播给他们的兄弟节点，而不是传播给他们的子节点，所以这个树的每一层之间是完全独立的，不可能把病毒从一层传播给另一层。 所以我们肯定需要在一开始的时候就给每个节点的至少一个子节点注射病毒（具体哪个不重要），这样每秒钟能感染的节点更多（根据操作 1）。 那先给谁的子节点注射呢？考虑先被注射的子节点会有更多的时间把病毒传播给更多的子节点。所以我们应该先给子节点更多的节点注射病毒。 （如果先给子节点少的节点注射，那在给所有节点注射完之前，这个节点的所有子节点可能都被感染了，也就是有很多时间被浪费了）。 在确保每个节点都有至少一个子节点被注射后，我们还可以给子 ...