SRTBOT框架 Subproblem definition 子问题定义 用清晰的语言去定义一个子问题是什么，并明确它所包含的参数。 子问题通常是原问题输入的一部分，有时候为了记录局部状态，我们还需要引入一些辅助变量。 Relate subproblem solutions recursively 写出递归关系式 找到当前子问题和更小子问题之间的数学或逻辑关系。 这是最难的一步，需要我们发挥归纳思维。我们可以尝试一个局部暴力破解。也就是问自己一个问题：“如果我知道了关于这个子问题的某个关键决策，它会缩减成哪个更小的子问题？”然后把所有可能的决策都试一遍，从中跳出最好的那个。 Topological order on subproblems 确定拓扑顺序 递归调用其实可以看做是一个有向图，如果算法能够正常结束，这个依赖图必然是一个有向无环图。 我们需要清晰的指出子问题的计算顺序，以确保当我们在计算当前子问题的时候，它所依赖的更小的子问题已经被计算出来了。 Base cases of relation 边界条件 当子问题足够小，不再依赖更小的子问题时，可以直接给出答案的情况。 ...

我们为什么需要锁？ 如果一个应用程序运行在多个 CPU 核上，并且执行了系统调用，那么内核需要能够处理这些并行的系统调用。 如果多个内核都在运行系统调用，那么它们可能访问内核中共享的数据结构。 当有对这些数据结构的并行访问时，我们需要锁来协调对共享数据的更新。更进一步的，我们需要锁来保证共享的数据是正确的。 从 kfree 考虑，我们假设有2个CPU在处理这个函数，这时候一个CPU执行 r->next = kmem.freelist; 另一个函CPU时也执行 r->next = kmem.freelist; 这样 r1 r2 都指向 freelist 然后到了下一句 kmem.freelist = r; 两个CPU执行完之后，我们会丢失先执行的那个CPU所指向的页表。 锁的抽象 123struct lock{} 锁有两个关键的方法，分别是 acquire() 和 release() ，它们都接受一个指向锁的指针作为参数， acquire() 确保了只能有一个进程能够成功的获取锁，任何在同一时间获取锁的进程必须等到第一个进程调用 release 。 锁的获 ...

BSGS 算法解决的是一类问题，即$$g^x\equiv h \pmod p$$ 已知 g,h,pg,h,pg,h,p 求 xxx 。这就是 DLP ，即离散对数问题。 BSGS 的想法是把指数 xxx 拆成两个部分 $$x=im+j$$ 这样原式变成$$g^{im+j}\equiv h \pmod p$$ 也就是$$(g^m)^i\equiv h\cdot g^{-j}\pmod p$$ 于是我们可以先把左边所有的 (gm)i(g^m)^i(gm)i 存起来 然后枚举右边所有的 hg−jhg^{-j}hg−j 两边一旦撞上，就得到解 算法步骤 要解$$g^x\equiv h \pmod p$$ 第一步，选取步长 取$$m=\lceil \sqrt n \rceil$$ 第二步，预处理 giant steps 计算并存表$$(g^m)^0, (g^m)^1, (g^m)^2, \dots, (g^m)^{m-1}$$ 把”值->指数 iii “存进哈希表 第三步，枚举 baby steps 依次计算$$h, hg^{-1}, hg^{-2}, \dots, hg^{-(m-1)} ...

CPU Intro：进程与程序 进程与程序 程序本身是 lifeless（无生命） 的，它只是静静地躺在磁盘上，是一堆等待被执行的指令和静态数据。 进程（Process） 是一个 “running program”。操作系统负责把那些静止的字节跑起来，让它们变成有用的东西。 在操作系统眼中，每个进程都有自己独立的 机器状态（machine state）： 内存：用于存储指令和数据。 寄存器：比如程序计数器（PC），记录当前运行到哪一条指令了。 但是我们知道，随便打开几个软件会有好几个进程，但是物理上的 CPU 是有限个。为了服务这些进程，我们需要一项被称为 CPU 虚拟化 (Virtualizing the CPU) 的技术。为了实现这样的目标，操作系统采用了一个非常经典的方法，叫做 “分时共享”。 这样的分时共享可以用下面的例子来理解： ♟️ 形象理解：分时共享与国际象棋大师 (点击展开) 我们可以想象一个超级快速的 国际象棋大师 同时在和 10 个人下棋： 大师走到第 1 个棋盘前，思考一下，走了一步。 然后他迅速跑到第 2 个棋盘前，走了一步。 接着是第 3 个 ...

Info: Def: a cipher defind over (K, M, C) a cipher is a pair of “efficient” algs (E, D) where E:K×M→CE:K\times M\to CE:K×M→C and D:K×C→MD:K\times C \to MD:K×C→M Consistency equation: ∀m∈M,k∈K,D(k,E(k,m))=m\forall m \in M,k\in K,D(k,E(k,m))=m∀m∈M,k∈K,D(k,E(k,m))=m every cipher has to satisfy it in order to be a cipher. Other wise, it would be unpossible to decrypt. E is often randomized. D is always deterministic. One time pad Warning: First example of a “secure” cipher. M=C=K={0,1}nM=C=K=\{0,1 ...

定义 给定一个由正整数列表(M1,M2,...,Mn)(M_1,M_2,...,M_n)(M1​,M2​,...,Mn​)和另一个整数SSS（目标和）。问题在于找到该列表的一个子集，使其元素之和恰好等于SSS。 这个问题也可以用二进制向量来描述：寻找一个二进制向量x=(x1,x2,...,xn)x = (x_1,x_2,...,x_n)x=(x1​,x2​,...,xn​)，使得S=∑i=1nxiMiS=\sum_{i=1}^{n} x_i M_iS=∑i=1n​xi​Mi​，向量xxx中的1小时对应位置的整数MiM_iMi​被选中加入子集。 问题的困难性 一般情况：子集和问题通常是一个NP-complete问题，这意味着在计算上通常被认为是困难的 暴力破解：通过检查所有可能的2n2^n2n个二进制向量可以找到解，但效率特别低。 碰撞算法：存在一种碰撞算法，可以将运行时间缩短到O(22/n)O(2^{2/n})O(22/n)，但需要巨大的存储空间。 “易解”的情况：超递增序列 如果整数列表r=(r1,r2,...,rn)r = (r_1,r_2,...,r_n)r=(r1​,r2​,. ...