tzyt的博客

书的链接（中文翻译版）：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）。 那先给谁的子节点注射呢？考虑先被注射的子节点会有更多的时间把病毒传播给更多的子节点。所以我们应该先给子节点更多的节点注射病毒。 （如果先给子节点少的节点注射，那在给所有节点注射完之前，这个节点的所有子节点可能都被感染了，也就是有很多时间被浪费了）。 在确保每个节点都有至少一个子节点被注射后，我们还可以给子 ...

upd@2022/12/18：感谢@adpitacor和@iterator_traits在评论区中指出的几个错别字，现在已经修正 upd@2022/11/24：这篇文章能入选洛谷日报我也是很惊喜。同时深感以前写的东西水平不太行，不过既然入选了日报，还是希望尽量能把文章的水平提高一点的。显然我不可能把整个文章重写一遍，但是可以加入一些自己这段时间新学到的东西，比如栈溢出攻击和 backtrace 的实现，所以赶在发表之前把他们添加了进来。 除了内容上的变化，这次更新还修复了一些错别字，这主要需要感谢 @cancan123456 在洛谷评论区的提醒。文章发出后有很多洛谷的朋友在评论区提醒和提出建议。比如 @szTom指出了 __fastcall 的影子空间。@LiuTianyou 介绍了强制内联的方法（这次新加的内容就使用了强制内联，以前属实是太菜了不知道有这个东西），以及调用约定中的 thiscall。@小菜鸟 提到了 longjump 函数（和本文中的一次返回多个函数有关）。 非常感谢这些网友，在学会了这些东西后我会考虑把它们陆续加进来，如果你有别的任何建议也欢迎像他们一样在评论区提 ...

题目连接 博客中观看体验更佳 1：题意 给你两个字符串，sss 和 ttt （ sss 和 ttt 的长度都不超过 10510^5105 ）。再给你一些询问 （ 询问数量不超过 10510^5105 ），每个询问为小写字母 'a' 到 'r' 的子集，对于每个询问，请你回答在 sss 串和 ttt 串只包含询问中给定的字母时是否相等。 2：分析 2.1：暴力 很容易想到暴力的方法，对于每个询问，我们可以只考虑包含在集合中的字符，然后对比两个字符串。当然，这样我们就会需要对于每个询问重新遍历一遍字符串，复杂度也会到达 n2n^2n2 （ nnn 为询问的数量和字符串的长度）。通过这个方法，我们可以拿到这道题的部分分。 不过如何才能拿到其他分数呢？ 2.2：简化问题 直接解决这个问题可能太复杂了，我们可以试试看化简一下这个问题，再把化简过的解法推广到原问题。 我们首先考虑询问中只包含两个字母的情况。设这两个字母为 a 和 b。那么我们如何判断两个只包含 a 和 b 的字符串是否相等呢？ 首先需要考虑的肯定是两个串中 a 和 b 的数量是否相等，如果 a 和 b 的数量不等，那这两个串一定不 ...