扶明の小站

前言 这个实验应该是对应着课程视频中的 CSAPP 深入理解计算机系统 Lecture 10 Program Optimization 说实话这样的一个重要的话题用一堂课的时间讲解未免有些许捉襟见肘 在这堂课上老爷子主要讲解了程序的常数级优化（即写出更适合计算机运行的程序）中的两个点： 访问数据应该要尽量满足程序的局部性原理，也就是需要根据计算机金字塔式的存储模型去设计程序； 举例：二维数组的行列访问书序颠倒后其性能差距主要是因为程序没有很好的空间局部性 减少每次循环的计算量，把循环中的常用值作为常数保存 举例：遍历字符串的时候使用for(i = 0; i < strlen(s); i++)这样的方式将程序的复杂度从线性降低到平方复杂度 这两个优化可以算是最为基础且最为重要的两点优化原则，但是面对Perllab实验想要达到的极致的优化，这样的优化方案还略显幼稚 实验文档：简书 PerfLab 文档中文翻译 参考资料：CSAPP：PerfLab实验 实验准备 这个实验的背景和要求都相对简单，阅读过实验文档后就能大致明白本次实验的目标是：通过所学到的底层知识对kern ...

前言 经过datalab的洗礼后，然后就迫不及待地开始上手bomblab啦，但是我万万没想到啊，这一个实验居然需要用到汇编的知识还要求学会调试器gdb的使用 可是这么点困难这么能湮灭心中的的热情呢，于是我打开 国内著名大学 B站 找了一个又一个的gdb教程，然而这些教程还！不！够！😭 无奈只能在积灰已久的收藏夹中翻出了那个陪伴我失眠的夜老爷子亲传 （助眠） 课程，于是翻到了以前很难理解的部分，发现有了一定的计算机基础知识作铺垫在加上刚学的gdb入门知识再去理解课程就会逐渐顺畅起来😆 于是，肝过视频后就迫不及待地开始实验啦 ~ 实验准备 这次的实验几乎不需要环境搭建（可能是我的Linux主机已经安装好了gdb的原因吧）需要用到的前置知识则要比datelab还是更专精些的，下面给刚刚新手推荐的一些前置知识讲解的视频供大家参考： Linux 使用gdb调试入门 【精校中英字幕】2015 CMU 15-213 CSAPP 深入理解计算机系统 Lecture5~6 还有就是后知后觉发现真的非常不错的gdb学习文档 Beej’s Quick Guide to GDB 然后阅读一下bomb.c文 ...

前言 面对有着计算机神书之称的《深入理解计算机系统》的第一个开篇实验Datelib，身为小白的我肯定是即惶恐又期待的，其实第一次了解这本书是在大一下临近期末的时候在知乎博主的推荐下去网路上找了这本书的电子版看的，但由于基础知识的缺乏抱着这本书啃的过程其实是举步维艰的甚至于跟着听CMU的课程也只是一知半解，后来就放弃挣扎了🤣 然后，现在过去一学期补充了相关的前置背景知识（计算机组成原理、linux系统入门），然后借着镜像计划这个契机正好算是挽回一下先前的遗憾吧~ 实验准备 下载必要文件并解压 测试编译文件时发生了这样的错误提示： 123/usr/include/gnu/stubs.h:7:27: 致命错误：gnu/stubs-32.h：没有那个文件或目录 # include <gnu/stubs-32.h> ^ 搜索后发现是由于64位机上未安装32位的glibc库文件，于是安装了相应的库文件 1sudo yum install glibc-devel.i686 由于编译的过程会经常用到make和make cle ...

区间贪心 区间选点 原题链接：AcWing 905. 区间选点 描述：给定 N 个闭区间 [ai,bia_i,b_iai​,bi​] [ai,bia_i,b_iai​,bi​]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。 输出选择的点的最小数量。 位于区间端点上的点也算作区间内。 实现： 将每个区间按照右端点从小到大排序 从前往后依次枚举每个区间，如果当前区间已经包含了点直接continue，否则选择当前区间的右端点 证明： 证明ans<=cnt ：cnt 是一种可行方案， ans是可行方案的最优解，也就是最小值。 证明ans>=cnt ： cnt可行方案是一个区间集合，区间从小到大排序，两两之间不相交。 所以覆盖每一个区间至少需要cnt个点。 核心代码： 12345678910111213for(int i = 0; i < n; i++){ int a, b; scanf("%d%d", &a, &b); r[i] = {b, a}; ...

背景 作者和大家一样都深受校园网设备限制之苦，一直在找寻机会突破校园网所有看过很多教程去试图冲破牢笼； 目前了解到的方式有： MAC地址复制 主要是找到一个同样在线的主机的MAC地址，然后冒充复制MAC地址后就相当于冒充这个设备上网；这样最大的好处在于不花钱😂，但是对被冒充的设备是会哦导致其暂时无法上网的，然后设备重新联网后你这边就会掉线，显然这不是长久的办法 路由器刷固件 这个在恩山无线论坛有很多教程，通过刷第三方固件可以获得原路由器没有的功能（例如连接校园网）还可以将路由器的功能发挥地更加激进。 最早我尝试过这个方案突破但是革命尚未成功，还把个路由器给刷坏了😅。还好是在某东买的当天坏隔天就退了（点名表扬某东）😉 买已经刷好固件的路由器 某宝上就有，但是一般来说路由器本身可能不会太好性价比要低很多，但是重在不需要自己刷不怕刷坏 适用对象 拥有一台Linux主机 非主要联网设备对网速要求不高 主要设备 一台Linux主机 无线网卡 前言 这个教程前半部分讲如何把Linux主机当路由器用（显然有点大材小用😂），我曾经尝试过用linux主机实现WIFI共享 ...

前言：本题来着[字节校园] 双月模拟笔试 3-4月场，个人感觉这是一个质量很高的题所以想要记录并分享一下自己当时的解法 Flowers 题面描述：给定 NNN 个数 h1, h2, ... hnh_1,\ h_2,\ ...\ h_nh1​, h2​, ... hn​ 表示高度，和 NNN 个数 a1, a2 .. ana_1,\ a_2\ ..\ a_na1​, a2​ .. an​ 表示高度对应的价值，求在高度序列中找到一串高度上升子序列使得价值最大，并输出最大价值 题目链接：Flowers 方法1： O(nlog⁡n)O_{(n\log{n})}O(nlogn)​ 思路： 本题很容易让人联想到最长不上升子序列问题，结合数据范围应该是 贪心+二分 优化版最长上升子序列问题（详细参考：动态规划习题集)）。但是具体细节还没想地太明白这里就不讲解（欢迎大大们教教你们的做法） 但是，本题其实还可以用树状数组解决： 首先分析题干得到本题的重要信息：序列具有最优子结构的特性即子问题的最优解可以推导得到更大规模问题的解，这是使用动态规划解题的很重要的条件之一，而本题虽然不是使用动态规划解 ...

线段树的基本操作 pushup() 通过子节点更新父节点 pushdown() build()将区间初始化为线段树 modify() 单点修改 & 区间修改 query() 线段树的存储结构 使用类似完全二叉树逻辑结构，故我们可以采取一维数组的存储结构存储线段树 编号（类比堆结构） 父节点：x/2（整除） 或者 x>>1 左子节点：2*x 或者 x<<1 右子节点：2*x+1 或者 x<<1|1 存储线段树总节点个数（需要开的空间大小）：4*x 我们以一个线段树的具体应用来讲解一下集体操作的实现： 最大数 题面描述：给定一个正整数数列 a[1]~a[n]，每一个数都在 0∼p−1 之间。 可以对这列数进行两种操作： 添加操作：向序列后添加一个数，序列长度变成 n+1； 询问操作：询问这个序列中最后 L 个数中最大的数是多少。 程序运行的最开始，整数序列为空。 一共要对整数序列进行 m 次操作。 写一个程序，读入操作的序列，并输出询问操作的答案。 原题链接：AcWing 1275. 最大数 线段树的节点结构 ...

多重背包问题 III 前言：本文是收录在动态规划习题集中的一个小part，但是思来想去认为这个的难度足够作为一个独立的文章，故此有了本文。 题面描述 有 NNN 种物品和一个容量是 VVV 的背包。第 iii 种物品最多有 sis_isi​ 件，每件体积是 viv_ivi​ ，价值是 wiw_iwi​ 。 求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。 原题链接：AcWing 6. 多重背包问题 III 方法：单调队列优化 复杂度：O(NV)O_{(NV)}O(NV)​ 考虑最原始的多重背包的求解方案： 可以看到 f[i,j]f[i,j]f[i,j]​ 与 f[i,j+v]f[i, j+v]f[i,j+v]​ 它们在计算推导的过程中重复计算了大量相同的项，而 f[i,j+1]f[i, j+1]f[i,j+1]​ 与 f[i,j+1+v]f[i, j+1+v]f[i,j+1+v]​ 也在推导的过程中计算了大量相同的项，据此我们可以根据这个特性减少计算量。 我们可以发现所有背包容量（j）对于当前物品体积（v）同余的项都在计算的过程中重复计算了大量相 ...

树状数组简介 以下讲解主要参考： AcWing 241. 楼兰图腾 题解 bilibili 完全理解并深入应用树状数组 OI Wiki 树状数组 树状数组可以用于解决部分单点修改 区间查询的问题 树状数组实现了：单点修改： Olog⁡nO_{\log{n}}Ologn​ 区间查询： Olog⁡nO_{\log{n}}Ologn​ 树状数组是将区间和划分为一种特殊的树状结构，通过对树的叶节点的查找而确定单点的值 树状结构的建立： 构建一个数组tr[x]保存以x结尾长度为x的lowbit值，这样就可以由特殊的区间和定义通过数组构建一个树状结构 我们无法简单地通过父节点的得到子节点（其直接子节点的数量都不是定值），单数对于tr[x]其父节点就是tr[x+lowbit(x)]（x+lowbit(x)是其lowbit值正好是比lowbit(x)大的最小值） 树的深度就是最大的lowbit值所在的位数也就是 log⁡2n + 1\log_2{n}\ +\ 1log2​n + 1 基本操作：单点修改 & 区间查询 lowbit(int x)操作 123int low ...

题目1 格子游戏 题面描述：Alice和Bob玩了一个古老的游戏：首先画一个 n×n 的点阵（下图 n=3 ）。接着，他们两个轮流在相邻的点之间画上红边和蓝边： 直到围成一个封闭的圈（面积不必为 1）为止，“封圈”的那个人就是赢家。因为棋盘实在是太大了，他们的游戏实在是太长了！他们甚至在游戏中都不知道谁赢得了游戏。于是请你写一个程序，帮助他们计算他们是否结束了游戏？ 原题链接：AcWing 1250. 格子游戏 解题思路： 问题转换，当要连接的两个点的本身就是一个是连接的状态那么就会得到一个环，我们用集合的形式维护已经连接的点根节点就当作链接状态的起始点，于是这样的判环问题就转化成了集合合并与查找的问题了 完整代码： 12345678910111213141516171819202122232425262728293031323334353637383940414243#include<iostream>#include<cstdio>using namespace std;const int N = 40010;int n, m;int p[N];int ...