yinsist

笔者上手一些大型项目时，常常会看不懂Makefile而造成一些困难，因此参考资料形成了一篇文章，从完全零基础过来的，用时也不多。文末附上一个笔者最近学习的rCore的Makefile，看完全篇文章后一定可以看懂的，本文也可用于一个简单的中文手册查询。 一些好的学习资料： Makefile Tutorial By Example 【从零开始学Makefile】 从零开始学Makefile_哔哩哔哩_bilibili Make/make.md · 岩木/CPP - Gitee.com 跟我一起写Makefile — 跟我一起写Makefile 1.0 文档 (seisman.github.io) makefile有点像跟手动编译过程反着来，一步步去找依赖项 规则的构成1234targets: prerequisites command command command targets（目标）：是文件名，通常一个规则只有一个targets command（命令/方法）：创建目标的一系列步骤，需要用tab开头， prerequisites（依赖）：也是文件名，可以有多个，用空格...

2023 秋 rCore 训练营个人存档：二三阶段优秀 二阶段实验总结lab1目的就是实现三个信息的统计 status: TaskStatus 按照提示直接设置为running [syscall_times: [u32; MAX_SYSCALL_NUM] 第一次尝试直接在sys_task_info来加载，发现好像不行，因为不知道传入的ti: *mut TaskInfo，这个参数到底在哪里被初始化的，而且每个任务都需要有一个syscall_times数组 由此我在TaskControBlock中维护一个pub task_syscall_times: [u32; MAX_SYSCALL_NUM]数组，这样通过全局遍历TASK_MANAGER可以很好的在每次系统调用时更新 更新位置在trap_handler进入syscall之前，读取x17寄存器为syscall id time: usize 需要得到的是从第一次运行到现在的时间，现在的时间可以通过get_time_ms直接获得 第一次运行开始的时间，需要在应用第一次变成Running态的时候记载，因此我们为每个 1TaskC...

欧几里得算法 筛法求素数（埃氏筛、欧拉筛） 裴蜀定理板子 欧几里得(辗转相除法)求a，b的最大公因数 gcd(a,b) = gcd(b,a%b) = ….. 直到(a,b)中b为0，那么结果就为a 123int gcd(int a, int b){ return b?gcd(a,b):a ;} 筛法求素数埃氏筛从2开始的 x ，划掉每个x的倍数，优化一下可以从x^2^开始划 12345678int primes[N],cnt;bool st[N];//初始为false，true表示被筛掉了，最后为false的都是质数for(int i=2; i<=n ;i++){ if(!st[i]){ primes[cnt++] = i; for(int j=i*i; j<=n; j++) st[i]=true; }} 欧拉筛 每个合数只被划掉一次，而且是被它的最小质因子划掉的 (原理是：每个合数都有一个<= sqrt(x) 的质因子 ) 由于被它的最小质因子划...

树状数组和线段树的实现 如何推导？查看本人的知乎这篇文章：前缀和改进之树状数组 - 知乎 (zhihu.com) 树状数组功能 单点修改，区间求和 O(logN) 可以在，O(logN)的时间内，动态求前缀和 ( 对比前缀和，修改的话需要O(N) ) 注意：树状数组下标一定要从1开始 树状数组初始化1for(int i=1 ; i<=n ; i++) add(i,a[i]); 小小地解释一下原理： 树状数组中奇数下标和原数组相等 c[x] = 原数组中下标从(x-lowbit(x)，x]的和 左开右闭 三个基本操作：1234567891011121314151617int a[N],c[N];//a[N]为原数组，c[N]为树状数组int lowbit(int x){ return x & -x;}//一般情况下只支持add，如果要实现修改某一个数，可以add他们的差值void add(int x , int v ){ for(int i=x;i<=n;i+=lowbit(i)) c[i] += ...

介绍简单dp： 01 背包一维二维实现 DP(动态规划)-背包01背包 题目 有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。第 i 件物品的体积是 vi，价值是 wi。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。 为什么称作01背包，因为对于每个物品，只对应选或者不选两种状态，因此称为01背包 主要思想： 状态表示: 我们用f[i][j]来表示，前i个物品，最大容量是j，可以得到的最大价值 状态计算: 对于f[i][j]，第 i 个物品，我们有两种选择 不选他: f[i][j]=f[i-1][j]，将第 i 个物品剔除然后选最大 选他: f[i][j]=f[i-1][j-v[i]]+w[i]，先将第 i 个物品放入背包，然后在前 i-1 个物品，容量为 j -v[i]的状态下找最大 因此得出状态方程: f[i][j] = max(f[i-1][j],f[i-1][j-v[i]]+w[i]) 二维朴素版1234567891011121314151617181920212223#include&...

quadTree，kdTree Lecture 19: Multi-Dimensional DataRange-Finding and Nearest (1D Data)BST中可添加的operation： select(int i): Returns the ith smallest item in the set. rank(T x): Returns the “rank” of x in the set (opposite of select). subSet(T from, T to): Returns all items between from and to. nearest(T x): Returns the value closest to x. 实现：Just search for N and record closest item seen 直到现在，我们总是在一维数据中比较，但是不是所有的item都能只在一个维度中完成比较的 Multi-dimensional Data我们想在二维空间中实现 2D Range Searching: How ma...

CS61B排序：选择排序，堆排序，归并排序，插入排序，希尔排序，快排 Sortinversion(逆序对) An inversion is a pair of elements that are out of order with respect to <. 一种看待sort的方法： Given a sequence of elements with Z inversions. Perform a sequence of operations that reduces inversions to 0. Sort中，我们关注两种复杂度 time complexity space complexity (extra memory usage) Selection Sortθ(N^2^) Find smallest item. Swap this item to the front and ‘fix’ it. Repeat for unfixed items until all items are fixed. Heap Sort 基于Selection S...

CS61B的BST，B树，23树，红黑树，LLRB 原理 Chapt10 ADTs, Sets, Maps, BSTs加快链表的查找也可以使用跳表来优化 θ(logN) BST(Binary Search Tree)一篇好文It’s Triangles All the Way Down (Part 1) | by Amy Liu | Medium 二分查找树 提出BST的原因 对于LinkedList来说，我们search时最坏情况需要遍历整个list，尽管list是有序的，对于ordered array来说，我们可以通过二分查找来加快查找速度 受array的启发，我们可以在LinkedList的middle node设置一个引用，然后将middle node左边的List的指向翻转，这样我们就可以从middle位置根据大小向两边查找了 我们可以做得更好，在左右部分，递归地，我们继续添加他们各自middle node的使用，直到每个部分只剩1个，这就会形成BST Binary Search Trees: Every key in the left subtree ...

CS61B 的并查集，从原理到实现，WQU，路径压缩 chapt9 Disjoint Sets(并查集)不同并查集的元素也不能相同，而且为正数 支持两个操作的数据结构 connect(x, y): connect x and y. Also known as union isConnected(x, y): returns true if x and y are connected (i.e. part of the same set). 1234567public interface DisjointSets { /** connects two items P and Q */ void connect(int p, int q); /** checks to see if two items are connected */ boolean isConnected(int p, int q); } ListOfSets最朴素的做法，List存set，List<Set<Integer>> 缺点：...