tzyt的博客

upd@2022/7/14：添加了 sysinfo 这个 lab，至此为止，lab2 已经全部写完。 upd@2022/9/14：最近把实验的代码放到 github 上了，如果需要参考可以查看这里： https://github.com/ttzytt/xv6-riscv 里面不同的分支就是不同的实验。 Lab2: system calls 系统调用过程 跟名字一样，这个 lab 需要我们往内核里增加两个系统调用。而要增加这些系统调用，我们首先需要了解系统调用的过程。 首先，用户态的系统调用函数被声明（没有实现）在 user/user.h 中。 12345678910111213141516171819202122// system callsint fork(void);int exit(int) __attribute__((noreturn));int wait(int*);int pipe(int*);int write(int, const void*, int);int read(int, void*, int);int close(int);int kill(int);i ...

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 源码的码风这么怪啊？？？函数的返回类型居然跟函数名不在同一行？？ 123intmain(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 第零章 这章大部分的内容还是能够看懂的，但是在管道的示例程序上卡了很久。最后终于搞懂了，这里把我的理解写一下： 1234567891011121314151617int p[2];//p[0] 储存管道接收端的文件描述符，p[1] 为管道发送端的描述符char *argv[2];argv[0] = "wc"; //第一个参数是命令的名字argv[1] = 0; //stdinpipe(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]);} 首先需要注意的 ...

题目链接（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 文件变成了这样： 123456789<link rel="stylesheet" type="text/css" href="https://cdn.jsdeli ...

一些废话 最近发现以前学过的算法都非常容易忘，像什么后缀自动机，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）比父节点大 ...