Hi! 👋

日知录 日日有所知即可 这是一本记录笔者学习历程中的体验的书。 QQ群：970200550 个人QQ: 1912309537 Github本项目 随笔 关于获取知识 现在的知识真的是太多了，难的不是找不到答案，难的是没办法准确的表述自己的问题。如果能够把问题表述得规范，常见，把这个问题投给搜索引擎或者大模型，可能很快问题的本质就能解决。不能把问题表述得清楚的原因很大程度上是我们对这个事物的认知还不够深刻。就像在摆弄一个黑盒子，我们如果直接提问“这里怎么这样，怎么办”，如果没有一个专业的指导者，自己是很难通过互联网找到答案的。通过“曲线救国”，我们搞清楚了专业的表达，比如“这里”是A,“这样”是B，我们就能提问出“A怎么会出现B的情况”，这样就很可能找到答案了。 很难提出有效关键的问题是阻碍学习进步的最大障碍之一。 大模型 AI大模型是一个好东西。可以说大模型是“汇集天地之精华”，庞大的语料库，巨量的参数，谁也不知道能算出个什么东西。对于计算机科学领域的问题，以ChatGPT3.5为例(学校的Wifi能直连，不用白不用啊)，随便问一些计算机领域的问题，基本上都能答上80%-90%，不过一些比较冷门的知识点比较弱，会搪塞一下你。它会很多编程语言，不过感觉它最擅长Python，这可能是因为Python用的人比较多吧。

闲言碎语：最近对引体向上着迷，虽然拉不了几个，身体上的健身还是太困难了，毕竟不是所有人都擅长运动。偶然间在网上冲浪看到一位82年的大叔把健身和编程结合起来了(B站，CF)，生活哪来那么多为什么，做点想做的就是了。决定，像健身一样coding，写点题解。今天听到一首歌很好听，推荐一下《有没有人曾告诉你》by陈楚生。 这次练的题目还是非常经典的，先看看题。 题目连接 题目大意：有$n$个目标排成一排，标记为$1$到$n$。射击选手可以射击一个目标$i$，然后获得$a_i$的积分，之后目标$i$损坏，无法再次被射击。这场游戏有两个选手R和S，R先射击，然后S射击，依次轮替，直到所有目标均被摧毁。获得最多累计积分的选手获胜。但是这样太简单了。所以，要求有$q$次询问，每次选取$l$到$r$区间内的目标进行比赛，问这个区间内S选手是否能够不输。 输入格式：第一行包含一个整数$t(1\le t \le 10^4)$，表示测试样例数。每个测试，第一行有两个整数$n,q(1\le n, q \le 2\cdot 10^5)$，表示总的目标数和询问次数。然后第二行是$n$个整数$a_1,a_2,\dots,a_n(1\le a_i\le 10^6)$表示每个目标的积分数。接下来$q$行，每行两个整数$l$和$r(1\le l \le r \le n)$表示每次询问的区间。保证$n$和$q$的分别在多组测试中和不超过$2\cdot 10^5$。 输出格式：对于每次询问，如果S选手不会输，就输出YES。反之输出NO。 这道题可以用哈希(hash)解决。 楔子：先手的人不会输，每次都取最大的值，后手的积分和不会大于先手的。如果每个积分大小的目标数量都是偶数，先手不管怎么取，后手只要取一样的就行了(首先有不输的策略，然后都是偶数又赢不了，两人均是选取最优的方案博弈，那就只能平局了)。如果存在奇数数量的积分，先手存在必胜的策略，只要每次取最大的，必然有次后手取不到一样的(取到不等号)。 问题就转化为在区间$l$到$r$之间是否有奇数数量的积分值，如果没有则S选手能够不输，否则就会输。 一个简单的事实。假设我们有两个随机变量$X,Y$，它们均有50%的概率是0，50%的概率是1。用数学表达式表示一下。 $$P(X=x)=0.5,x∈\{0,1\}$$$$P(Y=y)=0.5,y∈\{0,1\}$$令随机变量$Z=X\bigoplus Y$。那么$P(Z=0)=0.5\times 0.5+0.5\times 0.5=0.5$，也就是$X$和$Y$，同取$0$或者$1$的时候。同理求出$P(Z=1)=0.5$，和$X$和$Y$的分布相同。 hash是非常好用的东西，使用概率学打破常规。这里给每个不同的积分分配一个随机的64位无符号数。异或运算具有非常好的性质，比如两个相同的值异或起来就是0，我们通过前缀异或和可以很容易地求出某个区间内的异或值。那么有什么用呢？如果区间异或值为0，我们认为，这个区间内不存在奇数出现次数的值，错判概率是$2^{-64}$，也就是几乎等于正确。 首先，如果区间内每种数的出现次数均为偶数，给每个数分配了一个随机值之后仍然保持偶数，根据异或的性质，区间异或和100%为0。我们错判的概率情况是，区间内存在奇数次出现的值，但是随机分配后的随机数的异或和恰好是0。我们可以把所有奇数出现的值取出一个，运行交换律和结合律，得到全部的偶数出现次数的数异或上某些奇数出现次数的数的异或和。前者是0，而后者几乎不可能是0。因为，给每个不同的数分配的不同的64位随机数，一个随机数每个bit位上是0或1的概率均为50%，根据上面的那个简单的事实，这些数的异或和结果中每个bit位0或1的概率也均为50%，所以要想令后者为0造成误判，总共有64位，要求全零，概率就是$(0.5)^{64}=2^{-64}$。 Codeforces上的随机数也是要小心使用。如果这样写。 uint64_t generateRandom64() { auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count(); std::mt19937_64 generator(seed); std::uniform_int_distribution<uint64_t> distribution(0, UINT64_MAX); return distribution(generator); } 在CF平台上，每次生成的数都是一样的，因为每次获取的时间都是一样的。可能是代码优化，或者CF机子特别快的缘故。 #include <bits/stdc++.h> uint64_t generateRandom64(std::mt19937_64& generator) { std::uniform_int_distribution<uint64_t> distribution(0, UINT64_MAX); return distribution(generator); } void solve() { int n, q; std::cin >> n >> q; std::vector<uint64_t> a(n); std::map<int, uint64_t> mp; auto seed = std::chrono::high_resolution_clock::now().time_since_epoch().count(); std::mt19937_64 generator(seed); for (int i = 0; i < n; i++) { int x; std::cin >> x; if (!mp.count(x)) { mp[x] = generateRandom64(generator); } a[i] = mp[x]; if (i) a[i] ^= a[i - 1]; } for (int i = 0; i < q; i++) { int l, r; std::cin >> l >> r; l--; r--; if (!l && a[r] == 0 || (a[r] ^ a[l - 1]) == 0) { std::cout << "YES\n"; } else { std::cout << "NO\n"; } } } int main() { std::ios::sync_with_stdio(false); std::cin.tie(0); int T = 1; std::cin >> T; while (T--) { solve(); } return 0; } 稍微修改一下G神(GPT)的代码，下面是python版本(已测试)。 ...

前言 会尽量避免图片的使用，方便代码仓库的更新。 一些名词会进行解释，在编号较小的文章里面解释过的会减少解释，或者不解释。 如果有纰漏还请指正，笔者还是个newbie。 梦的开始 本章可以随便看看。 在《太空漫游2001》中，古猿将骨头抛向空中欢呼的瞬间，骨头变成了遨游太空的空间站。古猿用骨头来制作工具，捕获猎物，人类使用空间站去探索外界，在宇宙的终极智慧面前，人类和古猿都沉浸在使用自己微薄智慧所创造的工具的喜悦中，又何尝有不同呢？ 计算机学习很多时候是在学习使用新的工具，工具种类繁多，有成套成套的工具链，深入理解所有工具的底层不太现实，大多都是边学边用，像把玩一个黑盒子一样，在使用的过程中逐渐理解本质。国外的教科书开篇一般喜欢讲一些历史之类的放松一下心情，这里也先来了解一下什么是Vim。正所谓格物致知。笔者以前听电台讲格物致知，讲的是王阳明格竹子，就是干瞪眼看着竹子看了七天，然后大病一场，不仅知识没有学到，还把身体搞坏了。不过现在格物致知的意思已经不是那种“格”，而是了解事物本身，然后得到知识。 首先，Vim是编辑器，和Vscode，Sublime甚至是Windows记事本是同一类型的（替身使者），当然Vim具备的功能比记事本多多了，有很多方便程序员开发的功能。IDE(Integrated Development Environment，集成开发环境)，比上面这种强化版本的记事本更进一步，集成了各种调试工具，运行环境，比如Microsoft的Visual Stduio，JetBrains的IDEA，Xilinx的Vivado，还有最近鸿蒙开发的DevEco。集成开发环境主打一个即开即用，像一个精装房，直接就能拎包入住。Vim之类的编辑器主要就是实现了编辑功能，其他功能，比如Debugger(野路子编程，笔者用得也比较少，printf大法爱好者)没有，类似一个毛坯房，需要自己折腾。其实功能强到一定程度也能叫做IDE了，Vscode通过安装插件可以变得非常强大，可以称为一个轻量级的IDE，不过Vscode面对大型项目的时候可能会性能不足，有些IDE也需要简单配置一番，并不能直接使用。Vscode既可以说是功能强大的编辑器，也可以说是轻量级的IDE。事实上，2024年了，IDE和编辑器的界限也没有那么突出。 回到Vim，这里指原汁原味的Vim，不添加任何的插件，也不编写复杂的vimscript脚本(Vim的配置脚本语言，笔者不会，除了简单的set)，本文也主要讲原味Vim的使用。原版的美学就像玩Minecraft原版单机生存一样。原味Vim的功能已经有很多了，原生支持多种语言高亮。不过也会拓展一些其他玩法。 一些建议: 现在已经是2024年了，大模型有这么多为何不去问问大模型呢？大模型汇集天地之精华，问问没准就能得到答案(不过现在(2024.8.7)个人感觉还是问ChatGPT比较有用，毕竟人家英语语料练得多，计算机领域的项目的文档很多都是英文)。 可以去互联网上碰碰运气，虽然Vim现在是比较小众，不过Vim历史比较悠久，各位远古大神的文章可以博观而约取之。想办法把问题表述得更加清楚，找到合适的搜索关键词。 回到Vim，Vim是一个免费的开源的文本编辑器，改进自Bill Joy的Vi。Vim的作者是Bram Moolenaar（他的事迹可以去了解一下，2023年去世了，Vim打开会有“帮帮乌干达的可怜儿童”也是因为他）。Vim第一次发布于1991年，现在已经33年了。Vim原本是配备在Linux系统上的，开源软件一般在开源系统上会好用一些，在闭源系统上更新会慢一些，Windows上也有一款gVim可以使用，用起来差点意思而且相关的一些资料也会少很多，不过基本操作差不多，一般都是在Linux上用Vim，不过也有人在Windows上用gVim编写Verilog。Vim是Vi improved(改进的Vi)的缩写。Vi是Visual的缩写。 从说明书开始 一个好的开源项目需要有一个好的文档，其实任何软件都应是如此，说明文档需要把软件的功能讲清楚。不过手机app之类的从来没有啥教程，可能都是基于常识，所见即所得吧。实际上，Linux环境下基本上每个软件都有文档。使用man或者help就能查看软件的使用说明了，在《鸟哥的Linux私房菜》里面经常强调。 Take a bite! Linux下我都用下面的形式，读者可以使用man或help试试。man的全称应是manual，使用手册。 $ man vim 或 $ vim --help 读者可以浏览一下，help得到的说明比较简短，man得到的说明比较长。文档这么长，详细阅读实在是为难人。 比如gcc的文档 $ man gcc 按G跳到末尾(注意是大写的G)，发现有1.8w多行(gcc version 9.4.0 Ubuntu 9.4.0-1ubuntu1~20.04.2)。其实man也有很多指令，查看文档经常都是搜索关键词。在输入man vim之后，可以再输入/xxx在文档中查询字符串xxx，再输入n可以查找下一处，或者输入shift+n查找上一处。shift+n其实就是N，输入单个大写字符的时候可以使用shift。简单用Python写一个HelloWorld。 $ vim hello.py 在Linux的终端窗口或者通过SSH连接到Linux服务器上的终端上键入上述命令，之后会形成一个名字叫.hello.py.swp的文件.swp是swap的意思，交换文件。在Windows当中，使用word编辑文件的时候也会生成一个临时文件，比如在某个文件夹里创建一个test.docx，然后右键打开Command Prompt终端，再用Word打开test.docx，在CMD终端里面键入dir /a可以看到 2024/08/15 14:20 <DIR> . 2024/08/15 14:20 <DIR> .. 2024/08/15 14:20 0 test.docx 2024/08/15 14:20 162 ~$test.docx 2 个文件 162 字节 2 个目录 82,243,371,008 可用字节 有个~$test.docx的不可见文件。同样的vim也有一个这样的交换文件，里面维护着你对这个文档的操作，当你进行保存的时候，才会把这些操作更新到文件当中。如果没有保存就会丢失这些更新。回到Vim，如果此时你再打开一个终端窗口试图再向hello.py写入 ...

Batch 云云：batch脚本已经死了 怎么说呢，batch脚本确实比较难用，教程残缺不全，毕竟是这是上古时代的遗物，和DOS系统有着非常密切的关系。众所周知，windows有着其他系统不具备的强大兼容性，同时这也让windows系统背上了沉重的历史包袱。（windows是不是读该成win DOS \[doge\]） 因此，batch有着DOS时代的眼泪（悲），不过我们就像一个优雅的爵士一样，我们可以把他装裱起来放在柜台上，时时把玩欣赏，同时我们可以感受到最质朴的脚本语言之一的样子。 给想学习bat脚本的人推荐一个网站： bat脚本之家 （链接以php结尾，php也可能是时代的眼泪吧） 一点点的罗列知识点是过于乏味的，我想通过一个个的尝试来加深对这个事物的认知。所有看到本文的人都能够一起动手尝试。 环境和工具：Windows操作系统。 官方资料: CMD文档 Try1 Hello, World! 梦开始的地方 首先，创建一个txt文件(最好用英文路径，不过windows中文支持挺好的?)，在里面复制如下代码。 @echo off echo Hello, world! pause 然后，将txt的后缀改成bat，鼠标双击运行可以看到 Hello, world! 请按任意键继续. . . 查阅资料思考问题： @echo off删去后会怎样？ windows和Linux的echo有什么区别？ pause有什么作用？ Try2 一个编译运行脚本 在windows系统中，有很多的IDE(Integrated Development Environment，集成开发环境)。比如我们在编写C++程序的时候，集成开发环境比如说Jetbrains家的Clion，微软的Visual Studio，或者简陋一点的Dev C++，它们都提供了一键编译的GUI。另外，虽然Vscode并不是IDE，不过内置的插件可以帮你完成这些步骤。但是如果我们回归到最朴素的样子，这里有一个编辑工具(比方说，gVim，Vscode，甚至是记事本，这里笔者用的Vscode)，并且有某种语言的编译器，或者说解释器，我们要在这个基础上编写一个功能脚本，实现一系列的操作帮我们减少重复劳动，提高工作效率。 查阅资料思考问题： “环境变量”是什么意思，它的本质是什么？ 如何添加环境变量？（Linux添加环境变量和Windows添加环境变量） 当前工作目录是什么？ C程序和Python中的相对路径是以什么为基准？ 假设文件目录是这样的 ./ ../ run.bat C++/ a.exe in.txt ok.cpp out.txt std_out.txt 笔者喜欢打codeforces所以编写了下面的脚本。 下面是一段脚本，它首先切换到源代码所在目录C++/编译运行filename中设置的源代码文件，编译运行得到从in.txt中读入数据，运行输出到out.txt，并且和答案的std_out.txt进行比较，如果编译失败或者是答案错误会输出FAIL，否则输出OK。这个脚本还支持两个选项，-i忽略和答案的比较，-n取消编译，只运行。 运行这个脚本需要将编译设置到环境变量，Windows一般是MinGW。 说教是无力的，自主查阅资料的过程收获颇丰 一些需要的知识: bat脚本中，cd，set等命令的含义和用法。 如何获取传给脚本的参数？ 如何获取上一条命令的返回值？ 标准输入输出重定向为文件 bat脚本字符的处理。 @echo off cd C++ set filename=ok.cpp set date=%DATE:~0,10% set time=%TIME:~0,8% echo System time %date% at %time% for /f "tokens=1-3 delims=/- " %%i in ("%date%")do set/a y=%%i,m=%%j,d=%%k set date=%y%/%m%/%d% if "%1" neq "-n" ( echo ***start to complile*** g++ -Wall %filename% -o a.exe -O2 for /f "tokens=1,2 delims= " %%a in ('forfiles /m a.exe /c "cmd /c echo @fdate @ftime"') do ( if "%%a" neq "%date%" ( echo ***fail to complie*** goto ERROR ) if "%%b" lss "%time%" ( echo ***fail to complie*** goto ERROR ) ) echo ***complied successfully*** ) echo ***begin to run*** a <in.txt> out.txt echo ***finsih running*** if "%1" == "-i" ( goto YES ) fc /w out.txt std_out.txt if %Errorlevel% == 0 ( :YES echo ___ _ __ echo / _ \^| ^| / / echo ^| ^| ^| ^| ^|/ / echo ^| ^| ^| ^| ^< echo ^| ^|_^| ^| ^|\ \ echo \___/^|_^| \_\ if "%1" == "-i" ( goto EOF ) ) else ( :ERROR echo ______ _____ _ echo ^| ____/\ ^|_ _^| ^| echo ^| ^|__ / \ ^| ^| ^| ^| echo ^| __/ /\ \ ^| ^| ^| ^| echo ^| ^| / ____ \ _^| ^|_^| ^|____ echo ^|_^|/_/ \_\_____^|______^| ) :EOF 运行的效果类似 ...

OS 操作系统学习心路历程。笔者学习了一下MIT6.1810。 XV6源码研读——从启动开始 导引文件 在内核当中，有一个entry.S文件，目的是用汇编跳转运行start()函数。为了能够让entry.S放在最开始执行，这里有一个kernel.ld的连接脚本（loader?），通过连接脚本的编排，使得entry.S的位置在RAM开始的位置，也就是0x80000000。 在汇编程序段当中有一些指令并不是真正的汇编指令，而是伪指令，这些指令会交给汇编器来处理，转换成真正的汇编指令。主要是为了方便程序段的书写。 在entry.S文件当中，有两个标签_entry和spin，其中spin标签是一个死循环。在_entry当中，使用了CSR寄存器之一的mhartid获取了运行当前代码段的硬件线程id。然后给这个对应的hart(硬件线程)开辟了对应的栈空间。接着调用call命令，跳转到start()函数所在的地址，此处的call应当是汇编伪指令，RISC-V下应该使用jal/jalr等指令。 使用过编译器的同学都知道，汇编是可以调用其他文件包括C文件的函数接口的。这里就是从entry.S跳转到start.c里面的start()函数的入口。 接下来我们来看start.c文件。这里涉及到一个汇编伪指令mret，这个指令的作用如下。 An MRET or SRET instruction is used to return from a trap in M-mode or S-mode respectively.（risc-v特权指令手册） mret指令的作用是从M特权陷阱当中返回。具体来讲，这个伪指令的具体动作包括： 特权模式修改为xPP位段所装载的特权模式。 xIE位段的值修改为xPIE。 xIE位段的值设置位1。 xPP位段设置位最低支持的特权模式，如果xPP不是M，xRET会设置MPRV=0。 从这一系列动作可以看出。M的特权>S的特权>U的特权。调用RET会降低特权模式，因为xPP段会被硬件清零。这体现了硬件上的权限管理。 回到start()函数中，我们可以看到首先设置了m_status寄存器当中的xPP位段，把其中特权模式设置为S。然后，它往mepc（Machine exception program counter register.）寄存器里写入内核的main函数的地址。其余动作。 关闭虚拟地址寻址。satp寄存器设置寻址模式，设置为0，其mod字段也为0，表示直接的物理地址寻址。 设置medeleg和mideleg寄存器，授予S模式全部的陷阱和异常异常。 设置sie寄存器，使能S模式外设，时钟，软件中断。 设置pmpaddr0和pmpcfg寄存器，使得S模式能够访问所有的地址空间 如下 调用了timerinit函数。在timerinit函数当中设置一些关于时钟中断的寄存器。 首先计算当前硬件线程的CLINT中断地址，然后将配置时钟的数据，写到某个数据区域当中，再把数据区域的指针记录到特权模式的临时寄存器mscratch当中，方便后续再timervec程序段当中使用。 设置mtvec寄存器，配置陷阱中断基地址。指向timervec程序段。在这个程序段当中，使用mscratch寄存器当中的数据，根据设置的时间间隔，设置下一个时钟中断的时机，安排S模式的软件中断，在时钟中断服务函数之后，这里使用了sip寄存器( Supervisor interrupt-pending register)。返回。 然后使能当前硬件线程全局中断，使能机器中断。 最后把硬件线程id保存在这个cpu的tp寄存器当中。 接下来就是最上面提到的mret了，从当前特权陷阱中返回，硬件自动切换特权模式从M到S，而且触发硬件自动恢复现场的特性，把先前写在mepc寄存器中main函数的地址，赋值给pc寄存器。 至此，程序以特权模式S，或者说内核态，运行kernel。 页表与虚拟地址 MIT6.1810的Lab3是关于页表和虚拟地址的。有一个困惑，比如这样一个简单的C语言程序，它是如何从虚拟地址0x0001处找到数的呢？ int main() { int p = *((int *)0x0001); return 0; } 课程手册book-riscv-rev3中说明 As a reminder, RISC-V instructions (both user and kernel) manipulate virtual addresses. ...