# tk's blog Read Me *** 这里是tk\_sky的gitbook，和我的blog仓库同步。 一般我写的博客都会在这个仓库的分类下面，有时间就push一下。内容比较随缘，做算法的时候会整理些算法，学csapp的时候会整理一些笔记，学java的时候会记录一些技术，反正更新比较随缘，欢迎观看。 当然里面还有什么随笔什么的，那些是老博客上同步的，就憋看了（ # 算法相关 # 数据结构 # 【集训整理】 旋转treap模板 *** Treap是一种弱平衡的二叉搜索树，它同时符合二叉搜索树和堆的性质： > 二叉搜索树：右子节点值>父节点>左子节点 > > 堆：子节点的优先值比父节点值小 我们让每个节点的值符合二叉搜索树的性质，同时给每个节点赋一个随机的优先值，让优先值满足堆的性质。 由于优先值是随机的，一旦不满足堆性质就会产生旋转，所以就很难出现退化成链的情况，达到平衡的效果。 Treap分为旋转Treap和无旋treap两种，旋转treap的旋转操作分为右旋和左旋： !\[image-20220703180723552]\(【集训整理】 旋转treap模板.assets/image-20220703180723552.png) 写成代码如下： ``` void left_rotate(int& id) { //左旋 int tmp = rchild[id]; rchild[id] = lchild[tmp]; lchild[tmp] = id; id = tmp; push_up(lchild[id]); push_up(id); } void right_rotate(int& id) { //右旋 int tmp = lchild[id]; lchild[id] = rchild[tmp]; rchild[tmp] = id; id = tmp; push_up(rchild[id]); push_up(id); } ``` 旋转操作其实只涉及两个点，交换下孩子即可。 树的储存，使用数组模拟结构体： ``` int lchild[maxn]; int rchild[maxn]; int val[maxn],prio[maxn]; int siz[maxn], cnt[maxn]; int tot, root; ``` `val`存值，`prio`存节点的优先值，`siz`记录某节点的子节点的数量，`cnt`记录某节点的值出现的次数，用于处理重复元素的情况。 创建节点： ``` int create(int v) { //创建节点，并给予随机优先值 tot++; val[tot] = v; prio[tot] = rand(); siz[tot] = 1; cnt[tot] = 1; return tot; } ``` 用rand函数给prio赋随机值。 更新siz的push\_up操作： ``` void push_up(int id) { //用于旋转后重新计算size siz[id] = siz[lchild[id]] + siz[rchild[id]] + cnt[id]; } ``` 在旋转/插入后siz可能会变化，要push\_up从下到上更新。 初始化： ``` void build() { //初始化，插入一个正无穷和一个负无穷 root = create(-inf); rchild[root] = create(inf); push_up(root); } ``` 初始化要先往里边塞一个正无限和一个负无限节点。 插入： 在二叉查找树上找位置插入，找到树缺位或已有节点修改。每次插完都要检测符不符合堆的性质，如果不符合就用旋转的方式进行平衡。 注意，每层插入递归结束后都要进行一次push\_up重新计算size值。 ``` void insert(int& id, int v) { if (!id) { //找到树缺位（引用指向的变量（l/rchild）为0） id = create(v); return; } if (v == val[id]) cnt[id]++; else { //遍历查找树，知道找到他该在的位置 if (v < val[id]) { insert(lchild[id], v); //每次插完都要检测符不符合堆的性质，不符合就平衡 if (prio[id] < prio[lchild[id]]) right_rotate(id); } else { insert(rchild[id], v); if (prio[id] < prio[rchild[id]]) left_rotate(id); } } push_up(id); //插入后size会变，沿路更新 } ``` # 二叉树及相关数据结构的java语言实现 *** 二叉树是一种很直观的非线性数据结构。本篇主要记录与二叉树相关的数据结构的java语言实现方法。 ## 一、二叉树 ### 1. 节点 既然有java，就简简单单用类来实现节点。 ```java class TreeNode{ int value; TreeNode leftNode; TreeNode rightNode; //构造函数 TreeNode(int v){ this.value = v; } } ``` main函数手动建树： ```java public static void main(String[] args){ TreeNode node1 = new TreeNode(10); TreeNode node2 = new TreeNode(3); TreeNode node3 = new TreeNode(30); TreeNode node4 = new TreeNode(15); TreeNode node5 = new TreeNode(6); node1.leftNode = node2; node1.rightNode = node3; node3.leftNode = node4; node2.rightNode = node5; //结构：10 - 30 - 15 // - 3 - 6 ``` 这样就建好了一个无序的二叉树。 ### 2. 遍历 一般遍历有深度优先和广度优先两种，深度包括先序、后序、中序遍历。这三者区别主要是先序遍历优先访问中间节点，中序是在中间访问中间节点（先访问左节点，后中节点，后右节点），后序遍历是先左右节点最后中间节点。 ```java static void traversal(TreeNode node){ //先序遍历 if(node == null) return; System.out.println(node.value); traversal(node.leftNode); traversal(node.rightNode); } ``` 广度优先遍历即层次遍历，和`bfs`类似，将首节点入队，每次循环从队伍中取出一个点，输出中间节点，把左右子节点入队，从上到下按层访问。 ```java static void layerTraversal(TreeNode node){ //层次遍历（bfs） if(node == null) return; LinkedList list = new LinkedList(); list.add(node); while(!list.isEmpty()){ TreeNode node_now = list.removeFirst(); System.out.println(node_now.value); // 左右儿子通通入队 if(node_now.leftNode != null) list.add(node_now.leftNode); if(node_now.rightNode != null) list.add(node_now.rightNode); } } ``` # 快乐树0x01：AVL树的java实现 *** > 写几个码量比较大的数据结构试试看，不知道过几天还记不记的得 ## 1. AVL树 * 树的高度：根节点到叶子节点的最长距离 * AVL树是一种平衡二叉树，其任何一个节点的两个子树的高度最大差为1 ## 2. 节点 ### 节点定义 ```java public class AVLTree>{ //用java自带的泛型，实现Comparable接口做比较 Node root;//跟节点 class Node>{ T value; Node left; Node right; int height; //节点的高度 public Node(T key, Node left, Node right){ this.value = key; this.left = left; this.right = right; this.height = 0; } } } ``` 相比普通的二叉树，会记录多一个节点的高度。 ### 取height函数 ```java int height(Node node){ //获取树的高度 if(node!=null) return node.height; return 0; } ``` ## 3. 旋转 旋转操作是AVL树平衡的核心。旋转操作其实就是一种改变根节点，从而使得树平衡的方法。 如果在AVL树中进行插入或删除操作，可能会导致平衡被打破。 可以分为4种情况：LL、LR、RL和RR。 四种情况分别对应如图： ![img](https://images0.cnblogs.com/i/497634/201403/281624280475098.jpg) ### LL的旋转 LL情况下，可进行一次单旋转： ![img](https://images0.cnblogs.com/i/497634/201403/281626153129361.jpg) LL对应的旋转是左单旋转，把k1作为根节点，k2作为k1的又子树，同时将k1的右子树作为k2的左子树。 当然，旋转后要重新计算节点的高度。由于高度是自下而上的，只用取自己的子树最高高度+1即可。 代码中，以k1为最左节点，参数为最高节点（因为不能向上查，只能向下） ```java private Node LLRotation(Node k2){ //执行左单旋转，返回新的（子树）根节点。注意k1永远是原左节点。 Node k1 = k2.left; k2.left = k1.right; k1.right = k2; k2.height = Math.max(height(k2.left),height(k2.right))+1; //注意这里k1的高度是新树，所以用k2.height就可以了，不用重复求 k1.height = Math.max(height(k1.left),k2.height)+1; //重新计算节点的高度 return k1; } ``` ### RR的旋转 RR对应的是右单旋转，与LL的左单旋转对称。 ![img](https://images0.cnblogs.com/i/497634/201403/281626410316969.jpg) ```java private Node RRRotation(Node k1){ //执行右单旋转，返回新的（子树）根节点。注意k1永远是原左节点。 Node k2 = k1.right; k1.right = k2.left; k2.left = k1; k1.height = Math.max(height(k1.left),height(k1.right))+1; k2.height = Math.max(height(k2.left),k1.height)+1; return k2; } ``` 要注意的是k1永远指原左边的节点，k2是右边的节点。 ### LR的旋转 LR的情况通过一次旋转不能完全解决，需要两次单旋转才能恢复平衡。 ![img](https://images0.cnblogs.com/i/497634/201403/281627088127150.jpg) 对LR的双旋转其实就是 **围绕k1**进行一次右单旋转和 **围绕k3**进行一次左单旋转。 ```java private Node LRRotation(Node k3){ k3.left = RRRotation(k3.left); //围绕k1RR旋转 return LLRotation(k3); //围绕k3LL旋转 } ``` ### RL的旋转 RL的情况和LR是对称的。 ![img](https://images0.cnblogs.com/i/497634/201403/281628118447060.jpg) ```java private Node RLRotation(Node k1){ k1.right = LLRotation(k1.right); //k3在第二层 return RRRotation(k1); //k1在最上层 } ``` ## 4. 插入 根据二叉查找树性质插入节点。递归，边界条件是到达叶子的子树（当前节点==null） 由于插入操作是不稳定的，可能改变平衡状态，需要在每层递归（但根据AVL的性质，不会超过2层不平衡）检测平衡状态，如果不平衡则进行相应的旋转。 因为进行了旋转和插入，所以递归需要在返回时重新统计高度。 ```java private Node insert(Node tree,T value){ //tree：插入的位置 value：插入的值 if(tree == null){ //递归，边界条件，一定要写 tree = new Node(value,null,null); }else{ int cmp = value.compareTo(root.value); if(cmp<0){ //<，应该在左子树插入 tree.left = insert(tree.left,value); //插入后可能导致不平衡，需要判断状态并旋转恢复 if(height(tree.left)-height(tree.right)==2){ //因为是在左子树插入的，就有LL和RL两种非平衡情况 if(value.compareTo(tree.left.value)<0) //LL tree = LLRotation(tree); else //LR tree = LRRotation(tree); } }else if(cmp>0){ //>，在右子树插入 tree.right = insert(tree.right,value); if(height(tree.right)-height(tree.left)==2){ if(value.compareTo(tree.right.value)>0) tree = RRRotation(tree); else tree = RLRotation(tree); } }else{ //cmp == 0 System.out.println("不允许插入相同的节点！"); } } //经过了旋转，要重新计算节点的高度 tree.height = Math.max(height(tree.left),height(tree.right))+1; return tree; } ``` ## 5. 删除 删除相比插入更麻烦，因为删除要考虑其左右子树。简单的做法是另写两个函数（比较好写，就不写出来了）分别查找子树的最大和最小值，在左树高度更大时将左树最大值与要被删的节点互换，然后再删；在右树高度更大时将右树最小值与要被删的节点互换，直到要被删除节点的位置没有任何子树，然后再删除。这样可以保住左右子树的数据仍然符合规则的同时方便地删除节点。 ```java private Node remove(Node tree, Node target){ // tree: 当前节点 target：待删除节点 if(tree==null||target==null) return null; //递归，边界条件一定要写 int cmp = target.value.compareTo(tree.value); // 沿树查找，老套路 if(cmp<0){ tree.left = remove(tree.left, target); if(height(tree.right)-height(tree.left)==2){ Node l =tree.left; if(height(l.right)>height(l.left)) tree = LRRotation(tree); else tree = LLRotation(tree); } }else if(cmp>0) { tree.right = remove(tree.right, target); if(height(tree.left)-height(tree.right)==2){ Node l = tree.left; if(height(l.right)>height(l.left)) tree = LRRotation(tree); else tree = LLRotation(tree); } }else{ //tree就是要删除的节点 if(tree.left!=null && tree.right!=null){ //要删除的节点左右都非空 if(height(tree.left)>height(tree.right)){ //左子树比右子树高 Node max = findMax(tree.left); //这个findMax函数用来找出子树中的最大节点 tree.value = max.value; tree.left = remove(tree.left,max); //这里的做法是把要被删的节点的左子树中的最大节点和要被删节点交换 //然后在那个位置再删掉要被删节点，那个位置肯定没有子树，直接删掉 //这样删除很方便，也不影响左子树都比右子树小的性质 }else{ //左子树不比右子树高 Node min = findMin(tree.right); //这个findMin函数用来找子树的最小节点 tree.value = min.value; tree.right = remove(tree.right,min); //找出右子树的最小节点和被删节点互换再删除，和上面一样 } }else{ //被删节点已经没有左右子树了，直接删 Node tmp = tree; tree = (tree.left!=null)?tree.left:tree.right; tmp = null; } } return tree; } ``` 完整的AVL树要能维护一组数据，肯定还要提供相应的遍历/查找等等操作，但这些都比较好写，不单独列出。 > 这玩意是真的难写，这个未完全版本都要150行，考场要写出来真不容易，也许有其他替代方案？ # 快乐树0x02 线段树实现(c++) *** ## 一、线段树的基本思想 ### 线段树？ 线段树是一种用来维护\_**区间信息**\_ 的数据结构。比如需要对一段连续的区间进行修改、查询等大量操作，使用线段树来维护相比线性表能取得更大优势。 线段树的时间复杂度为 $$O(logN)$$级。 ### 基本思路 线段树的基本思想是将每一个区间长度>1的部分划分成左右两个区间进行递归求解，在一层层划分时将整个线段划分成一个树形结构。这样就可以合并欲求区间包含的子树的信息来求得所求区间包含的全部信息。 这个树形结构是一棵二叉树，因此可以用二叉树的性质，求得： 某区间 $$p$$ 的左子区间（左儿子）的节点号为 $$p\_2$$，右子区间（右儿子）节点号为 $$p\_2+1$$ ### Lazy tag 由于线段树要支持对维护数据中的任意一个区间进行修改，而线段树是一个树形结构，如果每次修改都要对涉及的所有节点都去修改，其修改效率反而不如线性表。实际上，对欲修改区间，如果线段树某节点的区间正好全部在欲修改区间中，那么只需要修改该节点的值就可以了，不需要再深入到子节点中进行修改，因为至少目前用不到。对该节点进行修改后，我们给该节点打上一个标记，表明我们这次修改的数量，如果以后需要获取其子节点中的值，我们再把之前这次修改进行落实。这样，如果以后不需要其子节点的值，我们就省下了修改其子节点 的时间。 这个lazy tag的方法有点像初学的时候做的一道铺地毯的题，相比去修改每个被地毯覆盖的点，记录每次铺地毯的范围并与欲求坐标进行比对效率更高。 ## 二、代码实现 ### 建立线段树 递归分割建树。树的节点总数大致是原数集大小的4倍，开4\*maxn。 ```c int d[maxn * 4];//存树 int b[maxn * 4];//lazytag标记 int a[maxn];//原数据集 void build(int s, int t, int p) { //建立线段树，对[s,t]建树，当前根节点编号为p if (s == t) { //找到单个数了 d[p] = a[s]; return; } int m = s + ((t - s) / 2); //求中间值，二分递归 build(s, m, p * 2);//p*2是左子节点 build(m + 1, t, p * 2+1);// 右子节点 d[p] = d[p * 2] + d[p * 2 + 1];//更新节点 } ``` ### getsum函数 写一个函数，取得区间和。依然是递归，递归边界是当前区间全部在所求区间内，就返回当前节点值。 对于遇见的lazy tag，将tag记录的修改作用到子节点上，然后把标记下放到子节点中。注意，所有被标记的节点是已经被作用了修改的，而其子节点还没有被作用修改。 ```c int getsum(int l, int r, int s, int t, int p) { //取得区间和，l、r是最终目标范围，s、t是当前递归范围，p是当前范围的节点编号 if (l <= s && t <= r) { //如果当前区间全部在目标范围内，直接返回 return d[p]; } int m = s + (t - s) / 2; //拆分，递归 if (b[p]) { //如果有标记，往子节点访问要更新 d[p * 2] += b[p] * (m - s + 1); d[p * 2 + 1] += b[p] * (t - m); b[p * 2] += b[p]; b[p * 2 + 1] += b[p]; b[p] = 0; } int sum = 0; if (l <= m) { //左半边有目标范围 sum += getsum(l, r, s, m, p * 2); } if (r > m) { //右半边（注意右半边不包括m）有目标范围 sum += getsum(l, r, m + 1, t, p * 2 + 1); } return sum; } ``` ### add函数 用于区间修改（加或减）。使用lazy tag：在发现当前节点完全包含在目标节点时，就没有必要再修改子节点了，直接给本节点的值修改 $$修改值×本节点表示的长度$$ 即可，同时在本节点打下标记。同样，在遇到标记的时候，要先更新子节点并下沉标记到子节点，然后再拆分递归。当然，没有必要处理叶子节点的标记，因为他们没有子节点。 ```c void add(int l, int r, int c, int s, int t, int p) { //区间加（减），l,r是最终目标区间，c是增加的值，可以为负。s,t是当前区间，p是当前区间节点编号 if (l <= s && t <= r) { //目标全包含当前区间，计算后返回 d[p] += (t - s + 1) * c; b[p] += c; //标记好 return; } //具体要往子节点访问，更新子节点并消除标记 int m = s + ((t - s) / 2); if (b[p] && s != t) { //非叶子带标记，更新子节点值并下沉标记 d[p * 2] += b[p] * (m - s + 1);//总和是修改了b[p]*num的 d[p * 2 + 1] += b[p] * (t - m); b[p * 2] += b[p]; //标记下沉 b[p * 2 + 1] += b[p]; b[p] = 0; } if (l <= m) add(l, r, c, s, m, p * 2); if (r > m) add(l, r, c, m + 1, t, p * 2 + 1); d[p] = d[p * 2] + d[p * 2 + 1]; } ``` ### 调用示例 注意，建树时节点编号必须>0，否则n\*0都是0，整个树都会发生错误。 ```c int main() { for (int i = 1; i <= 10; i++) { a[i] = 1;} build(1, 10, 1); add(1, 4, 0, 1, 10, 1); printf("%d", getsum(1, 10, 1, 10, 1)); } ``` *** 提供区间加减法、区间求和的完整代码模板： ```c #include using namespace std; #define maxn 10100 int d[maxn * 4];//存树 int b[maxn * 4];//lazytag标记 int a[maxn];//原数据集 void build(int s, int t, int p) { //建立线段树，对[s,t]建树，当前根节点编号为p if (s == t) { //找到单个数了 d[p] = a[s]; return; } int m = s + ((t - s) / 2); //求中间值，二分递归 build(s, m, p * 2);//p*2是左子节点 build(m + 1, t, p * 2+1);// 右子节点 d[p] = d[p * 2] + d[p * 2 + 1];//更新节点 } int getsum(int l, int r, int s, int t, int p) { //取得区间和，l、r是最终目标范围，s、t是当前递归范围，p是当前范围的节点编号 if (l <= s && t <= r) { //如果当前区间全部在目标范围内，直接返回 return d[p]; } int m = s + (t - s) / 2; //拆分，递归 if (b[p]) { //如果有标记，往子节点访问要更新 d[p * 2] += b[p] * (m - s + 1); d[p * 2 + 1] += b[p] * (t - m); b[p * 2] += b[p]; b[p * 2 + 1] += b[p]; b[p] = 0; } int sum = 0; if (l <= m) { //左半边有目标范围 sum += getsum(l, r, s, m, p * 2); } if (r > m) { //右半边（注意右半边不包括m）有目标范围 sum += getsum(l, r, m + 1, t, p * 2 + 1); } return sum; } void add(int l, int r, int c, int s, int t, int p) { //区间加（减），l,r是最终目标区间，c是增加的值，可以为负。s,t是当前区间，p是当前区间节点编号 if (l <= s && t <= r) { //目标全包含当前区间，计算后返回 d[p] += (t - s + 1) * c; b[p] += c; //标记好 return; } //具体要往子节点访问，更新子节点并消除标记 int m = s + ((t - s) / 2); if (b[p] && s != t) { //非叶子带标记，更新子节点值并下沉标记 d[p * 2] += b[p] * (m - s + 1);//总和是修改了b[p]*num的 d[p * 2 + 1] += b[p] * (t - m); b[p * 2] += b[p]; //标记下沉 b[p * 2 + 1] += b[p]; b[p] = 0; } if (l <= m) add(l, r, c, s, m, p * 2); if (r > m) add(l, r, c, m + 1, t, p * 2 + 1); d[p] = d[p * 2] + d[p * 2 + 1]; } int main() { for (int i = 1; i <= 10; i++) { a[i] = 1; b[i] = 0; } build(1, 10, 1); add(1, 4, 0, 1, 10, 1); printf("%d", getsum(1, 10, 1, 10, 1)); } ``` *** 提供区间加减、乘法、区间求和的代码模板： ```c #include using namespace std; #define maxn 10100 int d[maxn * 4];//存树 int b[maxn * 4];//lazytag标记 int b2[maxn * 4];//标记2 int a[maxn];//原数据集 void build(int s, int t, int p) { //建立线段树，对[s,t]建树，当前根节点编号为p if (s == t) { //找到单个数了 d[p] = a[s]; return; } int m = s + ((t - s) / 2); //求中间值，二分递归 build(s, m, p * 2);//p*2是左子节点 build(m + 1, t, p * 2+1);// 右子节点 d[p] = d[p * 2] + d[p * 2 + 1];//更新节点 d[p] %= 998244353; } int getsum(int l, int r, int s, int t, int p) { //取得区间和，l、r是最终目标范围，s、t是当前递归范围，p是当前范围的节点编号 if (l <= s && t <= r) { //如果当前区间全部在目标范围内，直接返回 return d[p]; } int m = s + (t - s) / 2; //拆分，递归 if (b[p]) { //如果有标记，往子节点访问要更新 d[p * 2] += b[p] * (m - s + 1); d[p*2] %= 998244353; d[p * 2 + 1] += b[p] * (t - m); d[p * 2+1] %= 998244353; b[p * 2] += b[p]; b[p * 2 + 1] += b[p]; b[p] = 1; } if (b2[p]>1) { //如果有标记2，往子节点访问要更新 d[p * 2] *= b2[p]; d[p * 2] %= 998244353; d[p * 2 + 1] *= b2[p]; d[p * 2 + 1] %= 998244353; b2[p * 2] *= b2[p]; b2[p * 2 + 1] *= b2[p]; b2[p] = 0; } int sum = 0; if (l <= m) { //左半边有目标范围 sum += getsum(l, r, s, m, p * 2); sum %=998244353; } if (r > m) { //右半边（注意右半边不包括m）有目标范围 sum += getsum(l, r, m + 1, t, p * 2 + 1); sum %= 998244353; } return sum; } void add(int l, int r, int c, int s, int t, int p) { //区间加（减），l,r是最终目标区间，c是增加的值，可以为负。s,t是当前区间，p是当前区间节点编号 if (l <= s && t <= r) { //目标全包含当前区间，计算后返回 d[p] += (t - s + 1) * c; d[p]%= 998244353; b[p] += c; //标记好 return; } //具体要往子节点访问，更新子节点并消除标记 int m = s + ((t - s) / 2); if (b[p] && s != t) { //非叶子带标记，更新子节点值并下沉标记 d[p * 2] += b[p] * (m - s + 1);//总和是修改了b[p]*num的 d[p * 2 + 1] += b[p] * (t - m); d[p * 2] %= 998244353; d[p * 2 + 1] %= 998244353; b[p * 2] += b[p]; //标记下沉 b[p * 2 + 1] += b[p]; b[p] = 0; } if (l <= m) add(l, r, c, s, m, p * 2); if (r > m) add(l, r, c, m + 1, t, p * 2 + 1); d[p] = (d[p * 2] + d[p * 2 + 1]) % 998244353; } void mul(int l, int r, int c, int s, int t, int p) { //区间乘法，l,r是最终目标区间，c是乘的值，可以为负。s,t是当前区间，p是当前区间节点编号 if (l <= s && t <= r) { //目标全包含当前区间，计算后返回 d[p] *= c; b2[p] *= c; //标记好 d[p] %= 998244353; return; } //具体要往子节点访问，更新子节点并消除标记 int m = s + ((t - s) / 2); if (b2[p]>1 && s != t) { //非叶子带标记，更新子节点值并下沉标记 d[p * 2] *= b2[p];//这里是乘积，直接乘就行了 d[p * 2 + 1] *= b2[p]; d[p * 2] %= 998244353; d[p * 2 + 1] %= 998244353; b2[p * 2] *= b2[p]; //标记下沉 b2[p * 2 + 1] *= b2[p]; b2[p] = 1; } if (l <= m) mul(l, r, c, s, m, p * 2); if (r > m) mul(l, r, c, m + 1, t, p * 2 + 1); d[p] = (d[p * 2] + d[p * 2 + 1]) % 998244353; } int main() { for (int i = 1; i <= 10; i++) { a[i] = 1; b[i] = 0; b2[i] = 1; } build(1, 10, 1); mul(2, 6, 2, 1, 10, 1); printf("%d", getsum(1, 10, 1, 10, 1)); } ``` # 链表的Java语言实现 *** > 这不是各种算法竞赛来了嘛，毕竟卷算法的大佬们走的都是C赛道，有言曰“人卷我逃，人逃我卷”，于是果断选择Java赛道。但是确实没打过Java赛道啊，赶紧用Java实现几个常用的算法和数据结构练练手。 在打C赛道的竞赛时，算法书都推荐使用结构体来实现链表，毕竟C语言还没有类，都是这么搞的。 但都1202年了，当然要用上~~现代化~~的面向对象了。毕竟古典的结构体实现方法和类很像，都有独立的多个对象和内置属性。而且java不需要指针了，好耶！ 所以，开始吧\~ ## 一、定义节点类 ```java class Node{ int v;//节点值 Node next;//下一个节点 } ``` 定义Node类，支持单向指向，包含一个携带的值和下一个节点的引用。 作为类，可以添加构造方法来初始化： ```java Node(int value){ v = value; } ``` 写完以后就可以实操了。 ## 二、创建链表 创建一个包含6个节点的链表： ```java class Node{ int v;//节点值 Node next;//下一个节点 Node(int value){ v = value; } } class node_in_java { public static void main(String[] args){ Node node_first = new Node(0); //新建起始点 Node node_now = node_first; // for(int i =1;i<=5;i++){ //新建几个node连在一起 Node new_node = new Node(i); //新建Node对象 node_now.next = new_node; //连接新节点 node_now = new_node; //重设下一个要连接的节点 } } } ``` 注意Node类要写在程序主类的外面，否则main函数是没法直接创建非静态子类的对象的。 另外还要注意起始点一定要存下来，用起点来代表整个列表，不然没有引用了整个列表就找不到了。 ## 三、链表的基本操作 创建完链表以后，下面对链表进行一些基本操作。 ### 1. 遍历 ```java node_now = node_first; System.out.println(node_now.v); //首节点单独输出 while(node_now.next != null){ node_now = node_now.next; //切目标节点为下一个 System.out.println(node_now.v); //输出当前节点值 } ``` 遍历结束的条件是当前Node的next为null，即没有被分配下一个的点，就是结尾了。 输出结果： > 0 1 2 3 4 5 ### 2. 插入节点 具体操作是先遍历到目标节点，然后新建节点使老节点指向它，然后再设置它的下一节点重新接回链表。 单独开个新方法实现比较好。 ```java static void insert(int v,int num,Node start){ //插入节点，在第n个节点（0开始）后插入值为v的点 int count = 0; Node now = start; while(count != num){ now = now.next; count++; //找到目标节点 } Node target_next = now.next; //存下目标节点的下一个节点等待接回 Node new_node = new Node(v); now.next = new_node; new_node.next = target_next; } ``` 然后在主程序里调用： ```java insert(233 ,2,node_first); ``` 输出效果： > 0 1 2 233 3 4 5 ### 3. 替换节点 把目标节点的下一个节点给它的前一个节点即可。 ```java static void replace(int v, int num, Node start){ //替换节点，把num号节点换成值为v的新节点 int count = 0; Node now = start; while(count != num-1){ //注意到目标前一个就可以停了 now = now.next; count++; } Node new_node = new Node(v); //建新节点 new_node.next = now.next.next; //先改被替换点前面那个点的指针 now.next = new_node; //再把目标节点换掉 new_node.v = v; //记得赋值 } ``` ### 4.删除节点 类似替换，只不过不建新节点了。 ```java static void delete(int num, Node start){ //删除节点 int count = 0; Node now = start; while(count != num-1){ //注意到目标前一个就可以停了 now = now.next; count++; } now.next = now.next.next; //优雅而简洁 } ``` ## 其他 链表的意义在于删除/替换/插入节点效率相较于普通数组更快。如果要遍历的话，效率反而更慢。 Java其实自带了`LinkedList`类，可以直接使用。~~那我为什么还要手写~~ 用法： `LinkedList sites = new LinkedList<>();` 声明链表 `sites.add("mcyou.cn");` 添加元素 `System.out.println(sites.get(1));` 根据索引获取元素 ...... # 算法 # DP的背包问题小结-java语言描述 *** > 依然是复习以前学过的内容hhh ## 一、01背包 ### 题目 一共有N件物品，第i（i从1开始）件物品的重量为w\[i]，价值为v\[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？ ### 分状态和转移方程 显然变量为装入的物品和背包的质量，所求的目标是最大的价值。 因此设`dp[i][j]`来表示将前i件物品在j的限重下的价值最大值。 对于每个状态`dp[i][j]`有两种情况： 1. 装入第i件物品（`dp[i-1][j-w[i]] + v[i]`） 2. 不装入 （`dp[i-1][j]`） 故转移方程为： `dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])` ## 二、完全背包 ### 题目 同01背包类似，但每种物品可以取无限个。 ### 分析 和01背包类似，我们设出同样的dp状态，`dp[i][j]`来表示将前i种物品在j的限重下的价值最大值。 还是分两种情况： 1. 装入第i种物品，但和01背包不一样，这里装入一次以后还可以继续装入，所以应该转移到`dp[i][j-w[i]] + v[i]`而不是`dp[i-1][j-w[i]] + v[i]`。 2. 不装入第i种物品（还是`dp[i-1][j]`） 所以转移方程为： `dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]] + v[i])` ### 优化 这里可以做一个优化，可以通过滚动数组的方式，省去\[i]，压缩空间复杂度。 转移方程可改写为：`dp[j] = max(dp[j], dp[j-w[i]] + v[i])` 这里注意时间复杂度是不能被压缩的，而且这样写的前提是循环时`j`必须正向枚举，确保此时访问的`dp[j-[i]]`已经在本次循环中被计算到。 > 01背包也可以类似优化，只不过要逆向枚举，确保此时访问的`dp[j-[i]]`是上一次循环计算到的结果。 ## 三、多重背包 ### 题目 和完全背包不一样在于每种物品的数量是指定好的。一共有N种物品，第i（i从1开始）种物品的数量为n\[i]，重量为w\[i]，价值为v\[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？ ### 分析 因为指定了特定种类的物品数就相当于指定了n个独立的物品，所以多重背包问题可以直接化为01背包问题解决，其时间复杂度也不高。 转移方程可参考01背包。具体就是把给定数量的物品都视为单独的01背包里的物品来处理。 > 参考 > > [动态规划之背包问题系列 - 知乎 (zhihu.com)](https://zhuanlan.zhihu.com/p/93857890) # 【集训整理】2-SAT问题 模板题 *** 题面： > *m* 个约束条件，第 *j* 个约束条件有四个整数 *u*,*x*,*v*,*y*，表示 $$a\_u=x$$与 $$a\_v=y$$两者至少有一个成立。请判断是否至少存在一组 *a* 的值满足上述条件。 2-SAT是2-Satisfiability的意思，给一堆布尔变量，每个只有两种选择（1或0），要求满足方程组。 2-SAT的解题方法和差分约束一样是转化为图，然后对图进行操作。 要转化成图，可以把原式化成蕴含式（或者理解成如果...则一定...），给a、非a，b、非b分别建一个点，然后根据蕴含式的箭头连接边，这样就可以转换成图了。 这里的边（箭头）表示逻辑蕴含关系，因此同一个强连同分量内的变量值一定是同时成立的。也就是说，如果出现了如非a和a在同一个强连通分量里，那么就出现了矛盾，这个方程组是无解的。 这样就把方程组转化成了图论的找强连通分量的问题。 转换的方法： | 原式 | 建图 | | ------------------------------- | ----------------------------------------------- | | $$eg a\vee b$$ | $$a\rightarrow b\wedge\neg b\rightarrow\neg a$$ | | $$a \vee b$$ | $$eg a\rightarrow b\wedge\neg b\rightarrow a$$ | | $$eg a\vee\neg b\space \space$$ | $$a\rightarrow\neg b\wedge b\rightarrow\neg a$$ | 然后用tarjan找强连通分量即可。 ``` #include #include #include using namespace std; int n, m; #define maxn 2000005 vector vec[maxn]; int low[maxn], dfn[maxn],color[maxn], cnt = 0,cnt2 = 0; bool vis[maxn]; stack sta; void tarjan(int u) { low[u] = dfn[u] = ++cnt; sta.push(u); vis[u] = true; for (int v : vec[u]) { if (!dfn[v]) { tarjan(v); low[u] = min(low[u], low[v]); } else if (vis[v]) { low[u] = min(low[u], dfn[v]); } } if (low[u] == dfn[u]) { cnt2++; while (sta.top() != u) { color[sta.top()] = cnt2; vis[sta.top()] = 0; sta.pop(); } color[sta.top()] = cnt2; vis[sta.top()] = 0; sta.pop(); } } int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= m; i++) { int u, x, v, y; scanf("%d %d %d %d", &u, &x, &v, &y); //建图 if (!x && !y) { vec[u + n].push_back(v); vec[v + n].push_back(u); } else if (!x && y) { vec[v].push_back(u); vec[u + n].push_back(v+n); } else if (x && !y) { vec[v + n].push_back(u+n); vec[u].push_back(v); } else if (x && y) { vec[u].push_back(v + n); vec[v].push_back(u + n); } } for (int i = 1; i <= n * 2; i++) { if (!dfn[i]) tarjan(i); } for (int i = 1; i <= n; i++) { if (color[i] == color[i + n]) { printf("NO"); return 0; } } printf("YES"); } ``` # 【集训整理】Tarjan算法 模板题 *** 题面： > 给你一个 *n* 个点，m\* 条边的无向图简单图。求割点数量，割边数量，极大点双连通分量数量，极大点双连通分量包含边数的最大值。 > > 割点：在图中移除这个点后，存在一个点对在原图中连通在新图中不连通。 > > 割边：在图中移除这条边后，存在一个点对在原图中连通在新图中不连通。 > > 点双连通分量：原图的一个点数大于 1 的连通子图，不存在对于这个子图的割点。 > > 极大点双连通分量：是点双连通分量，且任意新增一个点后不是点双连通分量。 Tarjan主要基于dfs的思想，用来求解图的连通性问题。算法思想： 1. 时间戳：记录在dfs时每个截点被访问的顺序，用dfn\[x]来表示。 2. 搜索树：从某个节点出发进行dfs，访问到的边和节点构成的树。 3. 追溯值：用low\[x]表示，表示满足下列条件的节点中dfn的最小值： * x为根的搜索树中的所有节点 * 通过一条不在搜索树上的边，能到达搜索树的节点 这样追溯值就表示x点属于包含low\[x]节点的环（如果有环的话）。 追溯值的计算方法（dfs回溯的时候算）： 先让$$low\[x] = dfn\[x]$$，然后对x的每条边能到达的点y： * 若y在x搜索树上（y>x)，则$$low\[x] = min(low\[x],low\[y])$$ * 若y不在x的搜索树上（y\ 如果$$low\[y]<=dfn\[x]$$，说明有另一条路可以连回x以上，说明该边不是桥。 ### 割点 点x是割点当且仅当$$dfn\[x]<=low\[y]$$ > 就算回路连回x点，删掉x点还是能把图拆断 参考代码： ``` void tarjan(int x){ dfn[x]=low[x]=++num; int flag=0; for(int i=head[x];i;i=edge[i].next){ int y=edge[i].to; if(!dfn[y]){ tarjan(y); low[x]=min(low[x],low[y]); if(low[y]>=dfn[x]){ flag++; if(x!=flag||flag>1){ cur[x]=1; } } } else low[x]=min(low[x],dfn[y]); } } ``` ### 边双连通分量 定义：没有割边的分量 去掉桥后dfs即可 ### 点双连通分量（vDCC） 在tarjan过程中维护一个栈: 当第一次访问一个节点时，将其入栈；当$$dfn\[x]<=low\[y]$$成立时（找到割点），一直弹栈直至y被弹出，x->y构成一个vDCC 参考代码： ``` void tarjan_dcc(int x){ dfn[x]=low[x]=++num; stac[++top]=x; if(x==root&&head[x]==0){ //孤立点 dcc[++cnt].push_back(x); return ; } int flag=0; for(int i=head[x];i;i=edge[i].next){ int y=edge[i].to; if(!dfn[y]){ tarjan_dcc(y); low[x]=minn(low[x],low[y]); if(low[y]>=dfn[x]){ flag++; if(x!=root||flag>1)cur[x]=1; cnt++; int z; do{ z=stac[top--]; dcc[cnt].push_back(z); }while(z!=y); dcc[cnt].push_back(x); } } else low[x]=minn(low[x],dfn[y]); } } ``` ### 强连通分量 注意点双是无向图的概念，强连通分量是有向图的概念。 与求点双的方法类似，但是强连通要求$$dfn\[x]==low\[y]$$时才能开始退栈。 > 参考 > > \[tarjan算法(新) | Liyue (theshineyue.github.io)]\( 算法总结/) > > [60 分钟搞定图论中的 Tarjan 算法（一） - 知乎 (zhihu.com)](https://zhuanlan.zhihu.com/p/101923309) # 【集训整理】差分约束 模板题 *** 题面： > *m* 个约束条件，第 *j* 个约束条件有三个整数\_u\_,*v*,*w*，表示$$a\_u-a\_v\le w$$ > > 请判断是否至少存在一组 \_a\_的值满足上述条件。 差分约束系统是一种特殊的n元一次不等式组，包含n个变量及m个约束条件。其中约束条件是由其中两个变量作差构成 ，如$$x\_i-x\_j<=c\_k$$ 这个$$x\_i-x\_j<=c\_k$$ 和最短路的三角不等式$$dist\[y]<=dist\[x]+z$$ 相似，所以可以把每个变量都看作一个点，每个约束条件相当于从节点$$i$$向节点i连一条长度为$$c\_k$$的有向边。判断无解只需要判断图中是否存在负环就可以了。 为了避免不联通的情况，设一个新点n+1，然后让他向每个点都连一条边权为0的边。 所以就把一个不等式组的问题变成了图的问题。对n+1号点跑一遍单源最短路，使用SPFA，判断是否存在负环即可。 SPFA的原版方法： > 将起点入队，每次从队列里取一个点，尝试更新（松弛）与这个点连接的所有点的最短路径长度。如果松弛成功，那么将这个点入队（当然，如果队列里已经有了，那就没必要再入队了。用一个数组记录这个数是否已经在队列里了）。 用SPFA求负环的方法： > 对于负环，SPFA会对他反复松弛，使最短路变小。所以我们只要记录一下每个节点松弛的次数，如果某个点的松弛次数>n了，那肯定是有负环了。 ``` #include #include #include #define N 51000 using namespace std; int v[N], w[N], nex[N]; int d[N], cnt[N], first[N]; bool vis[N]; int t; int n,m; void add(int x, int y, int z){ t++; nex[t] = first[x]; first[x] = t; v[t] = y; w[t] = z; } bool SPFA(int s){ int x, y, i, j; queueq; memset(d, 0x3f, sizeof(d)); memset(vis, false, sizeof(vis)); while (!q.empty()) q.pop(); d[s] = 0; cnt[s] = 1; q.push(s); vis[s] = true; while (!q.empty()){ x = q.front(); q.pop(); vis[x] = false; for (i = first[x]; i; i = nex[i]){ y = v[i]; if (d[y] > d[x] + w[i]){ d[y] = d[x] + w[i]; cnt[y] = cnt[x] + 1; if (cnt[y] > n) return false; if (!vis[y]){ q.push(y); vis[y] = true; } } } } return true; } int main() { cin >> n >> m; for (int i = 1; i <= m; i++) { int a, b, c; cin >> b >> a >> c; add(a, b, c); } d[n + 1] = 0; for (int i = 1; i <= n; i++) add(n + 1, i,0); if (SPFA(n+1)) cout << "YES"; else cout << "NO"; } ``` # 【集训整理】最近公共祖先LCA 模板题 *** > 最近公共祖先：在有根树中，两个节点的最近的公共祖先 > > 也就意味着，树上两个节点的最短距离就是他们的最近公共祖先到这两个节点距离之和 ### 朴素算法 我们可以通过一遍dfs记录下每个节点的深度信息。 在查询的时候，先让深度大的点往上跳，直到两点深度相等。两点深度相等以后就一起一步一步往上跳，直到跳到同一个点。 显然这样的做法过于暴力，会T。 ### 倍增算法 > 倍增：由于所有数都可以由 $$a\_12^n + a\_22^{n-1}+...+a\_{n-1}2^1+a\_n2^0$$表示，所以相比于从1跳到n，我们可以一次性跳$$2^k(k<=log\_2n)$$步，然后逐步缩小k直到跳到n。这样就可以将复杂度降至o(logn)。 > > 例：跳到14，14 = 8 + 4 + 2 朴素算法为什么会慢呢？ 朴素算法在往上跳的时候是一步一步跳的，这样跳万一两点都很深，那么就会很慢。我们可以利用倍增的思想，一次跳一大步，然后再逐渐缩小步长逼近目标。 为了实现快速的一次跳$$2^k$$步的目标，我们采用空间换时间——在dfs结束的时候算出所有节点的$$2^k$$级祖先（根据数据范围决定k的最大值，这里选20）。 设$$fa\[i]\[j]$$表示第i号节点的$$2^j$$级祖先，得到一开始的dfs如下： ``` void dfs(int now, int dep, int father) { // 预处理深度 if (vis[now]) return; vis[now] = true; depth[now] = dep; fa[now][0] = father; for (int v : vec[now]) { dfs(v, dep + 1, now); } } ``` 这样就用dfs先记录下自己的$$2^0$$级祖先（直系父亲）。 接下来通过两个循环，做一个类似于dp一样的转移来求fa： > 怎么求fa： > > 通过一个简单的原理： $$2^i = 2^{i-1} + 2^{i-1}$$ > > 可得到：$$fa\[now]\[i] = fa\[fa\[now]\[i-1]]\[i-1];$$ > > 意思是now的$$2^i$$祖先等于now的$$2^{i-1}$$祖先的$$2^{i-1}$$祖先 ``` for (int j = 1; j <= 20; j++) for (int i = 1; i <= n; i++) fa[i][j] = fa[fa[i][j - 1]][j - 1]; ``` 这里由于直接固定了遍历到2的20次方，有可能跳的太多，会超过树的根，也就是0，所以在lca的时候要把0的情况剔除。 接下来就是倍增跳LCA的过程了。 跳LCA有两个步骤：跳到同一深度，一起往上跳。 跳到同一深度后，如果两个节点相同，直接返回；否则两个点一起往上跳。 两个点一起跳，能跳的条件是：跳这个步长还在树上（$$fa\[i]\[j]!= 0$$） 一直跳到找到相同节点位置。跳的时候从20开始逐步缩小步长。 ``` int lca(int x, int y) { //用倍增法求lca if (depth[x] < depth[y]) swap(x, y); for (int i = 20; i >= 0; i--) { if (fa[x][i] != 0 && depth[fa[x][i]] >= depth[y]) x = fa[x][i]; } if (x == y) return x; for (int i = 20; i >= 0; i--) { if (fa[x][i] != 0 && fa[y][i] != 0 && fa[x][i] != fa[y][i]) { x = fa[x][i]; y = fa[y][i]; } } return fa[x][0]; } ``` 完整代码： ``` #include #include #include using namespace std; const int maxn = 6e5; int n, m; int depth[maxn], fa[maxn][21]; bool vis[maxn]; vector vec[maxn]; void dfs(int now, int dep, int father) { // 预处理深度 if (vis[now]) return; vis[now] = true; depth[now] = dep; fa[now][0] = father; for (int v : vec[now]) { dfs(v, dep + 1, now); } } int lca(int x, int y) { //用倍增法求lca if (depth[x] < depth[y]) swap(x, y); for (int i = 20; i >= 0; i--) { if (fa[x][i] != 0 && depth[fa[x][i]] >= depth[y]) x = fa[x][i]; } if (x == y) return x; for (int i = 20; i >= 0; i--) { if (fa[x][i] != 0 && fa[y][i] != 0 && fa[x][i] != fa[y][i]) { x = fa[x][i]; y = fa[y][i]; } } return fa[x][0]; } int main() { cin >> n >> m; for (int i = 1; i <= n-1; i++) { int a, b; scanf("%d %d", &a, &b); vec[a].push_back(b); vec[b].push_back(a); } dfs(1, 1, 0); for (int j = 1; j <= 20; j++) for (int i = 1; i <= n; i++) fa[i][j] = fa[fa[i][j - 1]][j - 1]; for (int i = 1; i <= m; i++) { int a, b; scanf("%d %d", &a, &b); printf("%d\n", lca(a, b); } } ``` # 二分查找与二分答案-java实现 *** > 翻洛谷的时候发现好多例题都做过，但谁让我过了两年啥都记不得了呢，只能复(预)习一下了（ 笑 ## 二分查找 二分查找是一种利用二分的思想快速在有序数列里查找指定数位置的方法。 模板题：[P2249 【深基13.例1】查找 - 洛谷 | 计算机科学教育新生态](https://www.luogu.com.cn/problem/P2249) 当然这个题要求用C的`unsigned int`而java没有这种东西，所以过不了。不过算法还是可以写一下的。 ```java public static void main(String[] args){ int n,m; Integer[] a = new Integer[1000005]; Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); for(int i = 1;i<=n;i++){ a[i]=sc.nextInt(); } for(int i = 1;i<=m;i++){ int target = sc.nextInt(); int l = 1;int r = n; while(r-l>1){ int mid = (l+r)/2; if(target <= a[mid]){ r = mid; }else{ l = mid; } } int ans; if(a[l]==target) ans = l; else if(a[r]==target) ans = r; else ans = -1; System.out.print(ans +" "); } } ``` 主要思路：因为本人比较笨，所以就用笨方法来判断，不取巧。每次查询时定义左边界、有边界和mid，反复利用二分的方法找到中间值和目标值进行对比。因为数列有序，如果mid大于目标值，则在mid左边寻找，即把右边界改为mid，反之亦然。直到左边界和右边界靠在一起或重合（r-l<=1）时停止。 这个时候由于缩小边界时我们包含了边界，所以答案一定在边界上，要么是左边界要么是右边界，简单判断输出答案即可。 要注意的是数列中可能有很多重复的目标元素，所以为了取第一次出现的那个，遇见 a\[mid] == target 时也要缩右边界，即把已经发现的这个target作为右边界。这样可以避免前面还有重复的元素，也不怕最后找不到答案，反正最后边界也是会被判断到的。 *** ## 二分答案 二分答案是二分查找的一种更广泛的推广。 应用场景：求使某条件最大的某变量的最小可能情况/使某条件最小的某变量的最大可能情况 一般来说，使用二分答案要满足下列前提： 1. 答案在固定区间内 2. 很难直接搜索或遍历得到，但给出一个值可以很快判定它是否符合要求 3. 查找区间具有有序性 ### 例题 \[P2678 [NOIP2015 提高组\] 跳石头 - 洛谷 | 计算机科学教育新生态](https://www.luogu.com.cn/problem/P2678) > 这项比赛将在一条笔直的河道中进行，河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间，有 N块岩石（不含起点和终点的岩石）。在比赛过程中，选手们将从起点出发，每一步跳向相邻的岩石，直至到达终点。 > > 为了提高比赛难度，组委会计划移走一些岩石，使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制，组委会至多从起点和终点之间移走 M 块岩石（不能移走起点和终点的岩石）。 > > 求最短跳跃距离的最大值。 和上面的三个前提对应： 1. 答案在1-赛道长度之间，是固定区间； 2. 可以使用较简单的方法判断某最短距离是否可行（下文说明）； 3. 我们的答案范围最短跳跃距离为1-赛道长度，自然是有序的。 综上，可以使用二分答案解这道题。 * **为什么采用二分的思想？** 设某种情况的最短跳跃距离为x、赛道长度为L，若最短跳跃距离为x可行，则\[1, x)上的结果一定可行，但一定不为最优，所以答案一定在\[x, L]上。反之，如果x不可行，则答案一定在\[1, x)上。 这个过程和之前的二分查找不能说长得很像，只能说完全一致。所以采用二分思想来处理这个问题。 * **为什么说判断某最短距离是否可行满足“比较简单”的要求？** 可以采用以下方法判断最短距离m是否可行： 按最短间隔m为标准移走石头，间隔\m) return false; else return true; } ``` 最后洛谷挂了7个点emmm 原因是为了满足m的最小间隙，不仅仅要移除一个石头。有可能要移除很多石头才能满足要求。用模拟的方法，模拟一个人慢慢跳，用while循环到结束为止。 新的judge方法： ```java static boolean judge(long m1){ int count = 0; int i = 1; int now = 0; while(im) return false; else return true; } ``` 至于主函数，把二分查找的代码简单拿出来做一个修改就好了。 成功AC\~ 完整代码： ```java import java.util.Scanner; class Main { static long[] a = new long[50005]; static int len,n,m; static boolean judge(long m1){ int count = 0; int i = 1; int now = 0; while(im) return false; else return true; } public static void main(String[] args){ Scanner sc = new Scanner(System.in); len = sc.nextInt(); n = sc.nextInt(); m = sc.nextInt(); for(int i = 1;i<=n;i++){ a[i]=sc.nextInt(); } long r = len, l = 1; while(r-l>1){ long mid = (l+r)/2; if(!judge(mid)){ r = mid; }else{ l = mid; } } long ans; if(judge(r)) ans = r; else if(judge(l)) ans = l; else ans = -1; System.out.print(ans); } } ``` 总结而言，二分答案其实就是用二分的方式猜答案的一个过程，只是说有序数列需要抽象出来比较困难，同时也需要想到一个简单可行的judge()方法判断猜测的数据是否满足题意。 # 动态规划-java语言练习一：暴力DP *** 重新进行算法的一个卷，主要复习高二学的动态规划知识（ 练习题目参考洛谷提单：[【动态规划】普及\~省选的DP题 - 题单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)](https://www.luogu.com.cn/training/1435#information) 练习暴力DP主要是先找回DP的感觉，练习推转移方程。 ## T1. 乌龟棋 线性DP \[P1541 [NOIP2010 提高组\] 乌龟棋 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)](https://www.luogu.com.cn/problem/P1541) 题目讲从起点到终点，每个点有不同的分数，有指定数量的1,2,3,4号牌，每张最多用一次，用几号牌乌龟就走几格。求能获得的最高分数。 设`num[i]`为i处的分数，`count[i]`为某号牌的张数。 ### 分状态 可以看出状态可以由使用不同种牌的次数来划分，因此设`s[a][b][c][d]`为使用了a张1号，b张2号...牌能取得的最高分数。 显然，`s[0][0][0][0]`=`num[1]`，我们要求的就是`s[num_a][num_b]...`的值。 ### 转移方程 对于某种牌，只有使用和不使用两种选择。因此，对于1号牌： $$s\[a]\[b]\[c]\[d] = max (s\[a-1]\[b]\[c]\[d]+num\[r],s\[a]\[b]\[c]\[d])$$ 其中，$$r=1+a+2\_b+3\_c+4\*d$$。（注意起点编号是1，所以r要先+1） 同理，可推得总的状态转移方程： $$s\[a]\[b]\[c]\[d]=max(s\[a-1]\[b]\[c]\[d],s\[a]\[b-1]\[c]\[d],s\[a]\[b]\[c-1]\[d],s\[a]\[b]\[c]\[d-1])+ num\[r]$$ 即某状态可以由少使用一张某种牌+这个状态对应的地图上的点的分数来得到。 当然，由于输入说可能没有某种牌(a=0,b=0,...)，代码实现的时候我们只能把这四种牌的转移方程拆开写。 ### 代码 ```java import java.util.Scanner; public class 乌龟棋1541 { public static void main(String[] args){ int n,m; int[] num = new int[400]; int[] count = {0,0,0,0,0}; Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); for(int i = 1;i<=n;i++) num[i] = sc.nextInt(); for(int i = 1;i<=m;i++) count[sc.nextInt()]++; int[][][][] s= new int[41][41][41][41]; s[0][0][0][0] = num[1]; for(int i = 0;i<=count[1];i++){ for(int j = 0;j<=count[2];j++){ for(int k = 0;k<=count[3];k++){ for(int l = 0;l<=count[4];l++){ int r = 1+i+j*2+k*3+l*4; if(i!=0) s[i][j][k][l] = Math.max(s[i][j][k][l],s[i-1][j][k][l]+num[r]); if(j!=0) s[i][j][k][l] = Math.max(s[i][j][k][l],s[i][j-1][k][l]+num[r]); if(k!=0) s[i][j][k][l] = Math.max(s[i][j][k][l],s[i][j][k-1][l]+num[r]); if(l!=0) s[i][j][k][l] = Math.max(s[i][j][k][l],s[i][j][k][l-1]+num[r]); } } } } System.out.println(s[count[1]][count[2]][count[3]][count[4]]); } } ``` ## T2. 樱花 多重背包 [P1833 樱花 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)](https://www.luogu.com.cn/problem/P1833) # 快速幂 *** 快速幂用于快速计算指数（$$2^n$$），主要思想是二分。 由于计算机计算单个乘法比多个乘法快得多，所以利用二分的思想来减少乘法运算次数可以提高速度。 例：$$7^{10} = 7*7*7\*...*7$$ 需要计算9次乘法，而先计算$$7^5$$再计算$$7^{10}$$，就只用计算$$7^5 = 7*7*7*7*7$$和$$7^{10}=7^5*7^5$$，只用5次乘法。 以此类推，得到一个递归二分的策略： $$ n是奇数：a^n = a^{n-1}\*a^n\ n是偶数：a^n = a^{n/2}\*a^{n/2}\ n=0：a^n = 1 $$ 写成代码： ``` typedef long long ll; ll qpow(ll a, ll n) { if (n == 0) return 1; else if (n % 2 == 1) return qpow(a, n - 1) * a; else { ll temp = qpow(a, n / 2); return temp * temp; } } ``` 这是递归版本的快速幂。 可以看到，这里二分的操作可以和二进制的右移对应，于是可以用二进制的方式理解： $$7^{10} =7^{\[1010]\_2}$$ ，于是$$7^{10}=7^{\[1000]\_2} \* 7^{\[0010]\_2}$$ 由于上面的递归形式递归会耗费时间，所以用二进制的思路将上面的递归改成循环形式会更好。 具体方法：由于每个二进制位表示一次平方，所以我们对n的每个二进制位，让底数进行一次自乘，如果对应的二进制位为1，则将此时的底数乘给ans，达到例如 $$7^{\[1010]\_2}=7^{\[1000]\_2} \* 7^{\[0010]\_2}$$的效果。 代码： ``` int qpow(int a, int n){ int ans = 1; while(n){ if(n&1) //如果n的当前末位为1 ans *= a; //ans乘上当前的a a *= a; //a自乘 n >>= 1; //n往右移一位 } return ans; } ``` # 状态压缩DP-java描述 *** ## 概念 > 状态压缩是一种利用二进制数来对状态进行压缩的方式。状态压缩之后，我们可以通过整数的加减来表示状态之间的转移。整数和状态一一对应。 一般而言，状态压缩用于解决非常多阶段的动态规划问题。 二进制状压的可以将状态数压至 $ 2^n \* n $ ，时间复杂度为状态数X决策数n，所以时间复杂度为 $2^n\*n^2 $。 虽然看着很大，但还是远小于爆搜的n!复杂度。但由于复杂度很大，这种题目的特征是n的值非常小，一般范围只有两三位数。 ## 位运算基础 状压使用位运算操作二进制数，从而检测或改变状态。常用的二进制位运算操作： 1. 判断一个数字x二进制下第i位是不是等于1。（最低第1位） 方法：`if((( 1<<(i−1) ) & x)>0)` 将1左移i-1位，相当于制造了一个只有第i位 上是1，其他位上都是0的二进制数。然后与x做与运算，如果结果>0， 说明x第i位上是1，反之则是0。 1. 将一个数字x二进制下第i位更改成1。 方法：`x=x|(1<<(i−1))`证明方法与1类似。 1. 将一个数字x二进制下第i位更改成0。 方法：`x=x&~(1<<(i−1))` 1. 把一个数字二进制下最靠右的第一个1去掉。 方法：`x=x&(x−1)` ## 例题 ![例题](https://img-blog.csdnimg.cn/20200223190918412.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjYyMTE1,size_16,color_FFFFFF,t_70) ![在这里插入图片描述](https://img-blog.csdnimg.cn/20200223190931850.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjYyMTE1,size_16,color_FFFFFF,t_70) ![在这里插入图片描述](https://img-blog.csdnimg.cn/20200223190941474.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNjYyMTE1,size_16,color_FFFFFF,t_70) ### 二进制状态表示 转换为二进制数为 \[111..11] 表示全部都选的状况 转换为二进制数为 \[000..00] 表示全都不选的状况 \[11001] 表示选第1,4,5个 ### 转移方程 首先考虑循环，我们依次考虑每个包裹 `i`，是第一层； 在考虑包裹 `i` 时，从下到上，从已存在推未存在的状态，对所有已存在的状态 `j` 做分析，看选这个包裹是否对这个状态有影响。 设读入的每个包裹包含的种类的数据为`data[]` 设`dp[l] = k`为想要获得`l`（二进制表示）状态对应的糖果种类，至少要选取`k`个包裹。 所以，得到转移方程为： ```java dp[j | data[i]] = dp[j] + 1; ``` 其中，`j|data[i]`的意义为取了这个包裹后小明手上有的糖果种类状态。（由原状态在`data[i]`不为0的位上置1） ### 完整代码 详细说明见注释。 ```java public static void main(String[] args) { int n,m,k; Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); k = sc.nextInt(); int[] data = new int[n]; int[] dp = new int[1< 例子： > > 2 3 5 7 11 13 17 19 > > 差分数列：2 1 2 2 4 2 4 2 ### 作用： 用于将区间操作转换成单点操作，原本对区间的操作在差分数列上体现的是对1-2个单点的操作。 例如，对数列的前k项同时-1，差分数列上表现为对第1项减1，对第n+1项加1，其余项不变。 ### 例题： [Problem - D - Codeforces](https://codeforces.com/contest/1443/problem/D) 题意：给定一串序列，可以进行无限次操作：对前任意k个数减1或对后任意k个数减1，求是否能将这个数组的元素全部置0. 发现是前k个和后k个的区间问题，考虑维护差分，把原数列置零等同于把差分数列置零（第一项是0，剩下的项和第一项的差都是0）。 对差分数列来说，对前k个数减1只意味着对第1项减1，对第n+1项加1，其余项不变；对后k个数减1对差分数列只意味着对第k项减1。 容易发现，我们可以对任意正数做任意次减1，直到减到0为止；唯一的变数在于负数，某负数要加到0，只能靠减第一项来实现。所以只用判断第一项减到0时负数能不能都加到0就行了。 代码： ``` const int maxn = 30005; int a[maxn],dif[maxn]; int main() { int t; cin >> t; while (t--) { int n; cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; dif[1] = a[1]; int tot = 0; for (int i = 2; i <= n; i++) { dif[i] = a[i] - a[i - 1]; if (dif[i] < 0) tot-=dif[i]; } if (a[1] >= tot) cout << "YES\n"; else cout << "NO\n"; } } ``` # 乘法逆元 *** 数学上乘法逆元的定义是 $$ax=1，则x是a的乘法逆元$$。 我们这里讨论关于取模运算的乘法逆元。 定义： 满足 $$ax\mod b = 1$$时，称 $$x为a关于模b的逆元$$。 所以逆元有什么用呢？ 题目中可能会出现操作中间树很大的情况，如求解： $$3 \* 6 / 3 \mod 7$$ 规定中间变量不能超过7，于是操作步骤为： $$原式 = ((3\*6)\mod 7)/3 \mod 7$$ $$= 4/3$$ 发现无法整除。 可以求出除数3关于模数7的逆元为5，根据定义，在7模数下，3 \* 5 = 1，所以1/3 = 5. 于是我们可以把$$/3$$替换成$$5$$，避免了无法整除的问题。 于是问题来到了如何求逆元。 费马小定理： $$a^{b-1} \mod b = 1$$ 改写一下： $$a^{b-2} \* a\mod b = 1$$ 所以 $$a^{b-2}$$ 就是a模b的逆元。一般这个数用快速幂来算。 # 题解 # CFRound-GoodBye2022题解 > 参加了孟爷爷的蓝桥杯训练营，奉旨写题解（ 本套题是CF的2022告别题，没有现场打，但既然要作为蓝桥杯的练习，那自然要用java多熟悉一下用java来写算法辣（~~u1s1 用Java写算法是真的蛋疼~~ 经过孟爷爷评测，本场的难度是div1+2，~~是打不过的难度~~，尽量看看能做几题 ## A. Koxia and Whiteboards > [Problem - A - Codeforces](https://codeforces.com/contest/1770/problem/A) **题目大意**： 有一串n个数字，要进行m次操作，每次操作有一个对应的替换数字，每次操作可以选择一个前者的数字替换为后者。求最后这n个数的总和最大是多少。 数据范围是 $$n,m≤100，a\_i,b\_i <10^9$$ **思路**： 那么一看这个题就是一个贪心，每次只要取原数最小的替换即可。正确性：替换没有后效性（就是说，不存在执行一个非贪心的操作能使得后期能取得比贪心更高的收益），对于每次替换，替换最小的收益一定比替换其他的收益大。 于是代码就出来了，用优先队列动态维护最小值，然后每次都替换最小值就好。复杂度O(NlogN)。 **坑**： 一看这个题目，就立马按签到题的思路写了，结果没好好读题直接吃亏。首先题目说`perform m operations`，这里隐含了两个意思：1. 这m个替换必须全部都执行，不能选择性执行；2. 后面说的是`the j-th operation`，意味着每次替换的顺序已经固定，所以必须按顺序进行替换，不能修改顺序。 > 与stl不同，java自带的优先队列默认是升序排列。使用`poll()`方法取出队首并出列，使用`peek()`方法取出队首而不出列，使用`add()`方法添加元素。 > > 可以使用自定义比较器的方法来自定义排序的方式： > > ```java > static Comparator cmp = new Comparator(){ > public int compare(Integer e1, Integer e2){ > return e2-e1; // 降序 > } > } > ... > Queue pq = new PriorityQueue<>(cmp); > ``` > > 当然用取负的方法也是可以的。 **代码**： ```java import java.util.PriorityQueue; import java.util.Scanner; public class Main { public static void main(String[] args) { int t; Scanner scanner = new Scanner(System.in); t = scanner.nextInt(); while(t>0){ long tot = 0; long add = 0; PriorityQueue pqa = new PriorityQueue<>(); int n = scanner.nextInt(); int m = scanner.nextInt(); for(int i =1;i<=n;i++){ long tmp = scanner.nextInt(); pqa.add(tmp); tot+=tmp; } for(int i =1;i<=m;i++){ long b = scanner.nextInt(); add += b-pqa.poll(); pqa.add(b); } System.out.println(add+tot); t--; } } } ``` ## B. Koxia and Permutation > [Problem - B - Codeforces](https://codeforces.com/contest/1770/problem/B) **题目大意：** 给出n和k，求一种\[1,n]的排列的构造，使得在宽度为k的窗口（\[1,k]，\[2,k+1]，...）内最大值和最小值的和最小。 数据范围：$$n,k<2^5$$ **思路：** 每次k是给定的，那么就是一个标准的滑动窗口。这题是一题构造题，那么我们就应该找到一种通用的规律设置排列。尤其观察样例，发现其实后两个case都是无效样例，说明规律应该是显而易见的。 下面考虑贪心。考虑n=5，k=2，为使min+max最小，我们应当尽量凑【max=一个大值，min=一个小值】这样的组合，例如【5, 1, 4, 3, 2】。最优解就是将最大值放在第一位（使得其只参与一次，当然解法不唯一），然后使得它所在窗口的范围（与k有关）内能包括进最小值（贪心，自然是放在最右边），再放置次大值并根据窗口范围放置次小值，以此类推直到放完。例如n=6，k=3，可构造【6, 5, 1, 4, 3, 2】。由于考虑到了各个窗口位置，容易证明这样一定是最优的。 总结下，我们依次从大到小放置数字，但每次到达窗口边界（i % k == 0）就放置一个小值（从小到大取），其他位置都从大到小放置大值。复杂度为O(n)。 **重要：针对Java的优化：** 我的解法复杂度为O(n)，面对2e5的数据绰绰有余，于是敲好java代码提交： ```java import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner scanner = new Scanner(System.in); int t = scanner.nextInt(); while(t>0){ int n = scanner.nextInt(); int k = scanner.nextInt(); int nows = 0, nowb = n+1; for(int i = 1;i<=n;i++){ if(i%k!=0){ nowb--; System.out.printf("%d ",nowb); }else{ nows++; System.out.printf("%d ",nows); } } System.out.print('\n'); t--; } } } ``` 然后愉快的TLE了... 重写了一份C版本的代码，顺利通过，而且在100ms以内。 按理来说Java虽然比C慢，但是计算不应该慢这么多才对。观察本题，发现本题输入输出较多，且输出远大于题目输入，猜测可能是Java的输入输出过于慢导致TLE。 #### 输入优化 要优化输入，可以简单的让Scanner采用`BufferedInputStream`来读取`System.in`，而不是直接让Scanner读取它： ```java Scanner scanner = new Scanner(new BufferedInputStream(System.in)); ``` 这样的优化书写简单，并且不用修改后面的Scanner用法。在本题大致可以加快50ms左右。 对于输入还有更深入的优化，也就是使用`BufferedReader`和`StringTokenizer`来替代Scanner： ```java static class FastReader{ BufferedReader br; StringTokenizer st; public FastReader(){ br = new BufferedReader(new InputStreamReader(System.in)); } String next(){ while (st == null || !st.hasMoreElements()){ try{ st = new StringTokenizer(br.readLine()); } catch (IOException e){ e.printStackTrace(); } } return st.nextToken(); } int nextInt(){ return Integer.parseInt(next()); } long nextLong(){ return Long.parseLong(next()); } double nextDouble(){ return Double.parseDouble(next()); } String nextLine(){ String str = ""; try{ str = br.readLine(); } catch (IOException e){ e.printStackTrace(); } return str; } } ``` 之后实例化并调用`reader.nextInt()`等方法即可。这种方法可以在无优化的基础上提高100ms左右。当然，理论上第一种优化方案已经足够。 #### 输出优化 输出可以使用`PrintWriter`配合`OutputStreamWriter`来替代`System.out`。这种方法很好写，而且printwriter实例的用法和System.out类似： ```java static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); ... out.printf("%d ",nowb); out.println("hello world"); ``` 在本题，简单的输出优化就可以使得TLE->AC(374ms)，可谓重大优化。 **AC代码：** ```java import java.io.BufferedInputStream; import java.io.OutputStreamWriter; import java.io.PrintWriter; import java.util.Scanner; public class Main { static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); public static void main(String[] args){ Scanner scanner = new Scanner(new BufferedInputStream(System.in)); int t = scanner.nextInt(); while(t>0){ int n = scanner.nextInt(); int k = scanner.nextInt(); int nows = 0, nowb = n+1; for(int i = 1;i<=n;i++){ if(i%k!=0){ nowb--; out.printf("%d ",nowb); }else{ nows++; out.printf("%d ",nows); } } out.print('\n'); out.flush(); t--; } } } ``` # java相关 # Java与算法竞赛——注意事项摘录 <<<<<<< HEAD ## Java与算法竞赛——语言相关事项摘录 上 *** > 此处摘录总结一些网上看到的用Java打算法竞赛的常用注意事项和语言相关代码优化。虽然记下来不一定考场上记得就是了。上篇记录一些基本输入输出相关内容，下篇主要介绍容器之类相关语言方向要适应的点。 ### 一、输入输出 #### 1. 输入 标准输入方法： `Scanner s = new Scanner (System.in);` 优化输入方法： `Scanner s = new Scanner (new BufferedInputStream(System.in));` 用流处理在数据量大的时候会快一点。 接下来用`Scanner`对象提供的方法来输入： * 整数：`int a = s.nextInt()` * 浮点数：`double t = nextDouble()` * 字符串：`String str = s.nextInt()` 特别地，可以使用`nextLine()`来读取一整行： `String str = s.nextLine()` 要判断输入是否结束，可以使用`s.hasNext()`： ```java while(s.hasNext()){ int a = s.nextInt(); ... } ``` #### 2. 输出 标准输出方法： `System.out.println(n);` 优化输出方法： `PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));` `out.println(n);` `out.printf("%.2f\n", ans);` (可用类似`printf`的方式输出) 如果要格式化输出，可以使用格式类，如`NumberFormat` 或 `DecimalFormat`类： ```java public static void main(String[] args) { NumberFormat formatter = new DecimalFormat( "000000"); String s = formatter.format(-1234.567); // -001235 formatter = new DecimalFormat( "##"); s = formatter.format(-1234.567); // -1235 s = formatter.format(0); // 0 formatter = new DecimalFormat( "##00"); s = formatter.format(0); // 00 formatter = new DecimalFormat( ".00"); s = formatter.format(-.567); // -.57 formatter = new DecimalFormat( "0.00"); s = formatter.format(-.567); // -0.57 formatter = new DecimalFormat( "#.#"); s = formatter.format(-1234.567); // -1234.6 formatter = new DecimalFormat( "#.######"); s = formatter.format(-1234.567); // -1234.567 formatter = new DecimalFormat( ".######"); s = formatter.format(-1234.567); // -1234.567 formatter = new DecimalFormat( "#.000000"); s = formatter.format(-1234.567); // -1234.567000 formatter = new DecimalFormat( "#,###,###"); s = formatter.format(-1234.567); // -1,235 s = formatter.format(-1234567.890); // -1,234,568 } ``` #### 3. 文件读写 输入 ```java FileInputStream fis = new FileInputStream("b.in"); System.setIn(fis); ``` 输出 ```java FileInputStream fis = new FileInputStream("b.in"); System.setIn(fis); ``` 这样就可以用重定向的方式在标准输出流读写文件了。 ### 二、高精相关 ~~y1s1 Java啥都可以用自带类来解决真的爽~~ 在Java中没有提供long long，最大提供到long，高于long数据范围的需使用高精度。不过好在Java中提供了简单的高精度方式，不用像某C语言一样要手写。 Java中主要通过调用`BigInteger`和`BigDecimal`来实现高精度。 ```java BigInteger a = new BigInteger("123456789"); BigDecimal b = new BigDecimal("233.333"); BigInteger c = new BigInteger("123"); System.out.println(c.add(a)); //加 System.out.println(a.subtract(c)); //减 System.out.println(a.multiply(c)); //乘 System.out.println(b.divide(b)); //除 System.out.println(a.remainder(c)); //取余数 System.out.println(a.mod(c)); //取余 System.out.println(c.pow(3)); //c的3次方 System.out.println(a.gcd(c)); //求最大公约数 System.out.println(a.compareTo(c)); //比大小，大于则>0，小于则<0，等于则=0 long d = a.longValue(); //转换为long System.out.println(d); ``` 输出 > 123456912 123456666 15185185047 1 90 90 1860867 3 1 123456789 注意：使用这两个类时只能使用其内部的方法来进行加减，不能直接使用运算符。 \#补充：关于取余（remainder)与取模（mod）的区别： > 例子： > > -14 取余 3 = -2 > > -14 mod 3 = 1 取余运算为数学意义上的取余，其结果可以为负，目的是使商尽可能大的情况下获得余数。 而取模运算返回值一定为正，且要求第二个参数（如本例的3）必须>0。目的是使商尽量小的情况下获得正余数。 > Java默认的%运算符是取余，而python是取模。 ### 三、常用容器 #### 1. Set 使用`java.util.Hashtag`来实现。 ```java Set s = new HashSet<>(); s.add(233); System.out.println(s.contains(233)); //true ``` #### 2. Map 使用`java.util.HashMap`来实现 ```java Map m = new HashMap<>(); m.put(1, 233); m.put(2, 666); m.remove(1); System.out.println(m.get(1)); ``` 因为map是无序的，所以需要使用迭代器来遍历map。 ```java Iterator> it = m.entrySet().iterator(); while(it.hasNext()){ Map.Entry e = it.next(); System.out.println(e.getKey() + " " + e.getValue()); } ``` #### 3. vector\&list c++的`vector`对应java中的容器为`Arraylist`。使用`Arraylist`可以用数组的数据结构实现元素的增删查找等等。`ArrayList`是通过**数组**的实现方式实现的，和数组类似，适合查改而不适合插入。 使用`Arraylist`下的方法对其进行增删查改： ```java ArrayList a = new ArrayList<>(); a.add(123); a.set(0,888); a.remove(0); a.clear(); a.add(999); ``` 其中需要注意，`set(int index, int value)`方法是用于修改`Arraylist`的现有元素的值，不能用于添加元素。如果搜索到的index没有值，会报错。 还可以通过其自带的方法对其进行排序、拷贝： ```java ArrayList b = (ArrayList) a.clone(); a.add(666); Collections.sort(a); ``` 至于输出，可以用get()方法来获取单个元素值，通过for循环遍历；也可以和普通数组一样用foreach方式输出： ```java System.out.println(a.get(1)); for(int i : a){ System.out.println(i); } ``` > 结果： > > 999 666 999 注意：`ArrayList`只能存放引用数据类型，不能存放基础数据类型。 > java还提供另外一种容器 `LinkedList`，与`ArrayList`不同，`LinkedList`是通过**链表**实现的，因此可以直接使用内置的方法执行插入元素操作。当然同列表一样，相对于数组它更适合插入/删除中间元素，而不适合查改。 #### 4. 优先队列 优先队列通过`PriorityQueue`类来实现。优先队列会自动将加入的元素排序，其默认顺序是升序（队首最小）。 定义与增删元素： ```java PriorityQueue pq = new PriorityQueue<>(); pq.add("mcyou"); pq.add("abc"); pq.add("233"); pq.remove("abc"); ``` > 可以使用offer()方法代替add()方法，区别是offer()不会产生报错。 读取队首： ```java System.out.println(pq.peek()); System.out.println(pq.poll()); System.out.println(pq.peek()); System.out.println(pq.size()); ``` peak()方法可取出队首元素但不删除它，poll()方法则会取出首元素的同时删除它。size()方法可以取出队中的元素数量。 > 输出效果： > > 233 233 mcyou 2 如果需要降序排序（队首最大），则需要在定义时声明： `PriorityQueue pq = new PriorityQueue<>(Collections.reverseOrder());` 修改后重新运行，输出如下： > qq qq mcyou 2 #### 5. 队列/双向队列 java提供了`queue`类和`deque`两种类，不过既然有deque那就直接用deque吧。 注意：对应的是`ArrayDeque`类。 ```java ArrayDeque queue = new ArrayDeque() queue.offer(1); //尽量还是用offer() queue.offer(2); queue.offer(3); System.out.println(queue.peek()); //返回第一个元素 while (!queue.isEmpty()) { System.out.println(queue.pop()); ``` 作为双向队列，相比于普通的queue： 还可以使用`offerFist()`或者`offerLast()` 来在队首或者队尾添加元素。 还可以使用`peekFirst()`或者`peekLast()` 获得队尾或者队首的元素。 还可以使用`pollFirst()`或者`pollLast()`移除并返回队尾或队首的元素。 其他容器的`pop()`、`push()`、`foreach遍历`等等方法这里也适用。 > 队列的意义在于新添加的数据置于队尾，先pop的数据位于队首。所以一般是用offer()来直接在队尾添加元素、用peek()或者poll()取元素，尽量不用push()之类本身与单向队列顺序相违背的方法，否则容易导致混乱。 #### 6. 栈 java也提供了`Stack`类，用以处理先进先出的数据结构。不过使用`deque`来代替也没什么毛病就是了。 栈内置方法介绍： | 序号 | 方法描述 | | -- | ----------------------------------------------- | | 1 | boolean empty() 测试堆栈是否为空。 | | 2 | Object peek( ) 查看堆栈顶部的对象，但不从堆栈中移除它。 | | 3 | Object pop( ) 移除堆栈顶部的对象，并作为此函数的值返回该对象。 | | 4 | Object push(Object element) 把项压入堆栈顶部。 | | 5 | int search(Object element) 返回对象在堆栈中的位置，以 1 为基数。 | 声明示例：`Stack st = new Stack();` > 参考 > > [【经验总结】Java在ACM算法竞赛编程中易错点 - Angel\_Kitty](https://www.cnblogs.com/ECJTUACM-873284962/p/7342030.html) \======= ## Java与算法竞赛——语言相关事项摘录 上 *** > 此处摘录总结一些网上看到的用Java打算法竞赛的常用注意事项和语言相关代码优化。虽然记下来不一定考场上记得就是了。上篇记录一些基本输入输出相关内容，下篇主要介绍容器之类相关语言方向要适应的点。 ### 一、输入输出 #### 1. 输入 标准输入方法： `Scanner s = new Scanner (System.in);` 优化输入方法： `Scanner s = new Scanner (new BufferedInputStream(System.in));` 用流处理在数据量大的时候会快一点。 接下来用`Scanner`对象提供的方法来输入： * 整数：`int a = s.nextInt()` * 浮点数：`double t = nextDouble()` * 字符串：`String str = s.nextInt()` 特别地，可以使用`nextLine()`来读取一整行： `String str = s.nextLine()` 要判断输入是否结束，可以使用`s.hasNext()`： ```java while(s.hasNext()){ int a = s.nextInt(); ... } ``` #### 2. 输出 标准输出方法： `System.out.println(n);` 优化输出方法： `PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));` `out.println(n);` `out.printf("%.2f\n", ans);` (可用类似`printf`的方式输出) 如果要格式化输出，可以使用格式类，如`NumberFormat` 或 `DecimalFormat`类： ```java public static void main(String[] args) { NumberFormat formatter = new DecimalFormat( "000000"); String s = formatter.format(-1234.567); // -001235 formatter = new DecimalFormat( "##"); s = formatter.format(-1234.567); // -1235 s = formatter.format(0); // 0 formatter = new DecimalFormat( "##00"); s = formatter.format(0); // 00 formatter = new DecimalFormat( ".00"); s = formatter.format(-.567); // -.57 formatter = new DecimalFormat( "0.00"); s = formatter.format(-.567); // -0.57 formatter = new DecimalFormat( "#.#"); s = formatter.format(-1234.567); // -1234.6 formatter = new DecimalFormat( "#.######"); s = formatter.format(-1234.567); // -1234.567 formatter = new DecimalFormat( ".######"); s = formatter.format(-1234.567); // -1234.567 formatter = new DecimalFormat( "#.000000"); s = formatter.format(-1234.567); // -1234.567000 formatter = new DecimalFormat( "#,###,###"); s = formatter.format(-1234.567); // -1,235 s = formatter.format(-1234567.890); // -1,234,568 } ``` #### 3. 文件读写 输入 ```java FileInputStream fis = new FileInputStream("b.in"); System.setIn(fis); ``` 输出 ```java FileInputStream fis = new FileInputStream("b.in"); System.setIn(fis); ``` 这样就可以用重定向的方式在标准输出流读写文件了。 ### 二、高精相关 ~~y1s1 Java啥都可以用自带类来解决真的爽~~ 在Java中没有提供long long，最大提供到long，高于long数据范围的需使用高精度。不过好在Java中提供了简单的高精度方式，不用像某C语言一样要手写。 Java中主要通过调用`BigInteger`和`BigDecimal`来实现高精度。 ```java BigInteger a = new BigInteger("123456789"); BigDecimal b = new BigDecimal("233.333"); BigInteger c = new BigInteger("123"); System.out.println(c.add(a)); //加 System.out.println(a.subtract(c)); //减 System.out.println(a.multiply(c)); //乘 System.out.println(b.divide(b)); //除 System.out.println(a.remainder(c)); //取余数 System.out.println(a.mod(c)); //取余 System.out.println(c.pow(3)); //c的3次方 System.out.println(a.gcd(c)); //求最大公约数 System.out.println(a.compareTo(c)); //比大小，大于则>0，小于则<0，等于则=0 long d = a.longValue(); //转换为long System.out.println(d); ``` 输出 > 123456912 123456666 15185185047 1 90 90 1860867 3 1 123456789 注意：使用这两个类时只能使用其内部的方法来进行加减，不能直接使用运算符。 \#补充：关于取余（remainder)与取模（mod）的区别： > 例子： > > -14 取余 3 = -2 > > -14 mod 3 = 1 取余运算为数学意义上的取余，其结果可以为负，目的是使商尽可能大的情况下获得余数。 而取模运算返回值一定为正，且要求第二个参数（如本例的3）必须>0。目的是使商尽量小的情况下获得正余数。 > Java默认的%运算符是取余，而python是取模。 ### 三、常用容器 #### 1. Set 使用`java.util.Hashtag`来实现。 ```java Set s = new HashSet<>(); s.add(233); System.out.println(s.contains(233)); //true ``` #### 2. Map 使用`java.util.HashMap`来实现 ```java Map m = new HashMap<>(); m.put(1, 233); m.put(2, 666); m.remove(1); System.out.println(m.get(1)); ``` 因为map是无序的，所以需要使用迭代器来遍历map。 ```java Iterator> it = m.entrySet().iterator(); while(it.hasNext()){ Map.Entry e = it.next(); System.out.println(e.getKey() + " " + e.getValue()); } ``` #### 3. vector\&list c++的`vector`对应java中的容器为`Arraylist`。使用`Arraylist`可以用数组的数据结构实现元素的增删查找等等。`ArrayList`是通过**数组**的实现方式实现的，和数组类似，适合查改而不适合插入。 使用`Arraylist`下的方法对其进行增删查改： ```java ArrayList a = new ArrayList<>(); a.add(123); a.set(0,888); a.remove(0); a.clear(); a.add(999); ``` 其中需要注意，`set(int index, int value)`方法是用于修改`Arraylist`的现有元素的值，不能用于添加元素。如果搜索到的index没有值，会报错。 还可以通过其自带的方法对其进行排序、拷贝： ```java ArrayList b = (ArrayList) a.clone(); a.add(666); Collections.sort(a); ``` 至于输出，可以用get()方法来获取单个元素值，通过for循环遍历；也可以和普通数组一样用foreach方式输出： ```java System.out.println(a.get(1)); for(int i : a){ System.out.println(i); } ``` > 结果： > > 999 666 999 注意：`ArrayList`只能存放引用数据类型，不能存放基础数据类型。 > java还提供另外一种容器 `LinkedList`，与`ArrayList`不同，`LinkedList`是通过**链表**实现的，因此可以直接使用内置的方法执行插入元素操作。当然同列表一样，相对于数组它更适合插入/删除中间元素，而不适合查改。 #### 4. 优先队列 优先队列通过`PriorityQueue`类来实现。优先队列会自动将加入的元素排序，其默认顺序是升序（队首最小）。 定义与增删元素： ```java PriorityQueue pq = new PriorityQueue<>(); pq.add("mcyou"); pq.add("abc"); pq.add("233"); pq.remove("abc"); ``` > 可以使用offer()方法代替add()方法，区别是offer()不会产生报错。 读取队首： ```java System.out.println(pq.peek()); System.out.println(pq.poll()); System.out.println(pq.peek()); System.out.println(pq.size()); ``` peak()方法可取出队首元素但不删除它，poll()方法则会取出首元素的同时删除它。size()方法可以取出队中的元素数量。 > 输出效果： > > 233 233 mcyou 2 如果需要降序排序（队首最大），则需要在定义时声明： `PriorityQueue pq = new PriorityQueue<>(Collections.reverseOrder());` 修改后重新运行，输出如下： > qq qq mcyou 2 #### 5. 队列/双向队列 java提供了`queue`类和`deque`两种类，不过既然有deque那就直接用deque吧。 注意：对应的是`ArrayDeque`类。 ```java ArrayDeque queue = new ArrayDeque() queue.offer(1); //尽量还是用offer() queue.offer(2); queue.offer(3); System.out.println(queue.peek()); //返回第一个元素 while (!queue.isEmpty()) { System.out.println(queue.pop()); ``` 作为双向队列，相比于普通的queue： 还可以使用`offerFist()`或者`offerLast()` 来在队首或者队尾添加元素。 还可以使用`peekFirst()`或者`peekLast()` 获得队尾或者队首的元素。 还可以使用`pollFirst()`或者`pollLast()`移除并返回队尾或队首的元素。 其他容器的`pop()`、`push()`、`foreach遍历`等等方法这里也适用。 > 队列的意义在于新添加的数据置于队尾，先pop的数据位于队首。所以一般是用offer()来直接在队尾添加元素、用peek()或者poll()取元素，尽量不用push()之类本身与单向队列顺序相违背的方法，否则容易导致混乱。 #### 6. 栈 java也提供了`Stack`类，用以处理先进先出的数据结构。不过使用`deque`来代替也没什么毛病就是了。 栈内置方法介绍： | 序号 | 方法描述 | | -- | ----------------------------------------------- | | 1 | boolean empty() 测试堆栈是否为空。 | | 2 | Object peek( ) 查看堆栈顶部的对象，但不从堆栈中移除它。 | | 3 | Object pop( ) 移除堆栈顶部的对象，并作为此函数的值返回该对象。 | | 4 | Object push(Object element) 把项压入堆栈顶部。 | | 5 | int search(Object element) 返回对象在堆栈中的位置，以 1 为基数。 | 声明示例：`Stack st = new Stack();` > 参考 > > [【经验总结】Java在ACM算法竞赛编程中易错点 - Angel\_Kitty](https://www.cnblogs.com/ECJTUACM-873284962/p/7342030.html) > > > > > > > > 2db037fcf6de5bcf588074205a43fc7a350195a0 [算法竞赛中的JAVA使用笔记](https://www.myblog.link/2016/11/14/Note-of-java/) # java面向对象简要总结 一 *** java作为一门面向对象语言，最重要的特性之一就是万物皆为对象。 ## 一、类 \[修饰符] class 类名{ ​ 属性.. ​ 方法.. ​ 构造器... } ​ 类可以被理解为数据类型，同int、char等数据类型类似。类的成员包含属性、方法、构造器。 ### 1.修饰符 java中常用的修饰符有： * private 只能在该类的内部被访问，其子类也不行 * protected 可以被同包的类访问，也可以被不同包中的子类访问 * 默认修饰符 只能被同一个包的类访问 * public 能被任意同或不同包的类访问 * 其他修饰符 * static 被修饰的类或变量为静态类/变量，静态类或变量属于类，不属于实例 * final 被final修饰的类或方法不能被继承，一般用于避免工程问题；修饰变量同static * transient * abstract * 其他高级修饰符 ### 2.属性 属性，或字段，是类或实例中储存的数据。 定义属性： \[修饰符] 属性类型 属性名 （赋值） ### 3.方法 方法是类中构成类的功能的部分，负责实现特定的工作，类似于结构化程序里的函数。 方法不能独立存在，必须依附于对象。 \[修饰符] 返回值类型 方法名 (形参) { 方法体 } ### 4.构造方法 构造方法用于在创建对象时执行操作，常用于对象的初始化等。 \[修饰符] 方法名（必须和类名相同）(参数) { 方法体 } ## 二、实例 实例就是对象，是属于某个类的对象，相对于类是切实存在、占用内存的实体。 一般通过new关键字来创建实例，在内存中为对象分配空间。 类名 实例名 = new 类名() 没有被static修饰的属性或方法属于对象本身，而不属于类，可以直接由对象调用。 属于对象的属性或方法都只针对对象本身，对象间的数据并不冲突。 ## 三、抽象类 ### 抽象类的声明和规则 抽象类是被abstract修饰的类。抽象类必须包含被abstract修饰的抽象方法。 格式： abstract class 类名 { 类体 } 抽象类不能被实例化，不能用new创造实例。 抽象方法没有方法体，没有{}。 ### 抽象类的作用 抽象类不能创建实例，只能被当成父类被新的类继承。 这个特性让抽象类很适合作为一个类的模板存在，让子类的设计能够遵循父类的特征，避免设计的随意性。 对相同特征提取出抽象类，然后再由子类对模板进行扩展和改造，是一种非常好用的设计模式。 ## 四、 包 软件包是java类的整合，具体到文件上就是不同的文件夹结构。 定义软件包：`package 包名` 导入软件包：`import 包名` 如 `import java.util.*` 、 `import java.util.Date` # java面向对象简要总结 三 *** ## 一、引用类型 针对java的对象，我们操作的标识符实际上是“引用”，通过引用指向一个对象的地址，类似于C中的指针。我们通过标识符来对对象进行操作。 ### 四种引用类型 java针对不同的引用类型有不同的垃圾回收方式。 ### 1、强引用 java默认的声明方式就是强引用。只要引用还指向某个对象，该对象就不会被回收。 ```java Object obj = new Object();//强引用 //如果需要让Object可以被回收，只需要： obj = null; ``` 手动将引用设置为“null”可以使对象能被回收。 ### 2、软引用 java的软引用可以将对象设为可被清理状态，当JVM内存不足时，系统将会清理被标识为软引用的对象。 ```java SoftReference ref = new SoftReference<>(obj); ``` 可用`ref.get()`来获取引用指向的对象。 ### 3、弱引用 设置弱引用，只要JVM进行垃圾回收，则弱引用指向的对象无论内存剩余情况如何，都会被系统清理。 ```java WeakReference ref = new WeakReference<>(obj); ``` ### 4、虚引用 虚引用是最弱的一种引用，即使有弱引用指向，没有其他引用指向的对象仍然会被回收。 ```java PhantomReference ref = new PhantomReference<>(obj); ``` ### instanceof 运算符 `instanceof`是java保留字，用于测试它左边的对象书否是它右边类的实例。返回值是逻辑型。 ```java String s = "String类是Object的子类"; boolean isObject = s instanceof Object; //返回值是true ``` ## 二、组合 组合是一种实现程序复用的手段，但不借助继承。相比继承，使用组合的方法进行代码复用能够保证更好的封装性。组合思想将要被复用的父类当做新类（子类）的组成部分，由新类直接调用父类的方法。 例子： ```java class father{ public void do(){ System.out.println("do sth.."); } } class child{ private father f; public child(father a){ f = a; //将父类的对象引入 } public void do(){ //重新定义一个do方法 f.do() //直接调用父类的方法 } } ``` 在上述例子中，新建child对象时需要传递一个father对象。 ```java father f1 = new father(); child c1 = new child(f1); ``` ## 三、初始化块 初始化与构造器类似，都在类中定义用于对对象进行初始化操作。 初始化块分为静态初始化块和非静态初始化块两种： * 静态初始化块： 在初始化块之前加上`static`修饰符，只会在类装载到系统时执行一次。 * 非静态初始化块： 不加任何修饰符，在该类的每个对象生成时都会执行一次，且执行顺序在构造方法之前。 初始化块语法格式： ```java class test{ [修饰符] { dosth(); } } ``` 初始化块没有命名，只有`{ }`。 可以定义多个初始化块，运行顺序仅依据定义的先后。 ## 四、包装类 java是面向对象的语言，但其包含的8种基本数据类型并不是标准的对象，不支持面向对象的编程机制。如果需要将基本数据类型转换为对应的按类编写的引用类型，从而可以像对象一样对其进行操作。 ```java int i = 1; Integer itObj = new Integer(i); int i2 = itObj.intValue(); //取出int变量 ``` # java面向对象简要总结 二 *** ## 一、类的继承 类可以继承，即基于原有的类派生出一个新类，子类继承父类的属性和方法。 继承表示方法： ```java <修饰符> class 子类名 extends 父类名{ 类体 } ``` 这样子类就可以调用父类的属性和方法。 例子： ```java class testclass { public int normal_int = 1; } class another_class extends testclass{ int another_int = 1; void a() { normal_int = 233; //调用父类中的属性 } } ``` 可以通过 `super.[属性或方法名]` 来访问父类的属性或方法。 继承可以是多重次的，访问多重继承不需要使用`super.super`，因为父类已经继承了其上的所有父类。 同其他方法一样，子类也可以直接调用父类的构造方法。示例如下： ```java class testclass2 extends testclass1{ testclass2(){ //testclass2的构造方法 super(); //调用父类的构造方法 } } ``` ## 二、重写 重写建立在继承关系上，能够让子类重新编写父类的某些方法，以使子类能够更加适应程序的需求。 例子： ```java class oneClass{ void print(){ System.out.println("属于父类"); } } class anotherClass{ void print(){ System.out.println("属于子类"); } } ``` 如果在子类中调用.print()，则实际会调用到被重写了的print方法，输出“属于子类”。 ## 三、重载 在java中，只要方法的参数不一样，就可以允许两个或多个方法同名。因此，可以基于提供参数的不同，分别执行不同的方法。 例子： ```java public class oneClass{ void print(){ System.out.println("打印了寂寞"); } void print(int a, int b){ System.out.println(a+"和"+b); } void print(int a, bool b){ System.out.println(a+"和"+b); } } ``` ## 四、隐藏和封装 java提供了3种访问控制符，与默认权限一起组成了4种访问控制级别，分别是： * private * default * protected * public 通过对类的属性和方法进行有效的权限控制，可以隐藏有必要隐藏的内容，只对外保留以需要的方法或属性的访问权限，以确保自己程序的运行不会因为外界访问而产生问题。 也可以通过访问权限控制，增加符合自身要求的供外界调用的方法，保证数据的产生或修改都符合自身程序要求，保证运行稳定，而不是让外界直接修改类内部的数据。 所谓“高内聚，低耦合”，就是让内部具体实现的方式封装在内部，而只提供少量必要方法供外部使用。 ## 五、接口 接口与类相似，接口也可以定义方法，作为系统与外界交互的窗口，规范实现者提供的服务，可以作为多个程序之间的通信标准。 申明方法： \[public] interface 接口名 { \[常量] 抽象方法 } 接口中为保证静态且final，只能定义常量，不能定义变量。 接口里的方法都是公共的且抽象的，默认强制设置，可以不用关键字修饰。 因为接口中的方法都是抽象的，要实现这些方法，必须要由其他类来进行实现。 实现接口的格式： class 类名 implements <接口名> { ... } 例子： ```java interface jiekou{ int add(int a,int b); } class classOne implements jiekou{ public int add(int a,int b){ return a+b; } } ``` 一个类可以实现多个接口，弥补了继承的不足。 `implements 接口1, 接口2` 通过面向接口编程，能够实现将具体实现和限制要求分离，从而减少程序间的耦合。 # 后端相关 # Linux-Crontab命令 *** ## 简介 crontab是用来设置定时执行语句或程序的指令。 直接使用crontab命令将读取一个文件（时程表），并将根据该文件的内容设置定时执行指令。 ## 使用命令 ``` crontab [ -u user ] file ``` > 指定时刻表 或 ``` crontab [ -u user ] { -l | -r | -e } ``` > -e 指定编辑器 -r 移除当前时刻表 -l 列出当前时刻表 ## 时间格式 时程表文件中设置定时执行任务的格式。 ``` f1 f2 f3 f4 f5 program ``` 解释： > ``` > * * * * * > - - - - - > | | | | | > | | | | +----- 星期中星期几 (0 - 6) (星期天 为0) > | | | +---------- 月份 (1 - 12) > | | +--------------- 一个月中的第几天 (1 - 31) > | +-------------------- 小时 (0 - 23) > +------------------------- 分钟 (0 - 59) > ``` * 中 f1 是表示分钟，f2 表示小时，f3 表示一个月份中的第几日，f4 表示月份，f5 表示一个星期中的第几天。program 表示要执行的程序。 * 当 f1 为 \* 时表示每分钟都要执行 program，f2 为 \* 时表示每小时都要执行程序，其馀类推 * 当 f1 为 a-b 时表示从第 a 分钟到第 b 分钟这段时间内要执行，f2 为 a-b 时表示从第 a 到第 b 小时都要执行，其馀类推 * 当 f1 为 \*/n 时表示每 n 分钟个时间间隔执行一次，f2 为 \*/n 表示每 n 小时个时间间隔执行一次，其馀类推 * 当 f1 为 a, b, c,... 时表示第 a, b, c,... 分钟要执行，f2 为 a, b, c,... 时表示第 a, b, c...个小时要执行，其馀类推 ## 例子 首先创建时程表文件 `vim timetable` 然后输入以下内容 ``` 0 */2 * * * touch /test/testfile 意思是每两个小时创建一个testfile 50 7 * * * /sbin/service sshd start 意思是每天7：50开启ssh服务 50 22 * * * /sbin/service sshd stop 意思是每天22：50关闭ssh服务 0 0 1,15 * * fsck /home 每月1号和15号检查/home 磁盘 1 * * * * /home/bruce/backup 每小时的第一分执行 /home/bruce/backup这个文件 00 03 * * 1-5 find /home "*.xxx" -mtime +4 -exec rm {} \; 每周一至周五3点钟，在目录/home中，查找文件名为*.xxx的文件，并删除4天前的文件。 30 6 */10 * * ls 意思是每月的1、11、21、31日是的6：30执行一次ls命令 ``` 保存，输入`crontab timetable` 即可开启定时任务 输入`crontab -l`查看开启的定时任务 ## 注意事项 * crontab 由 crond 服务调度，系统的 crond 服务每分钟会检查一次是否有需要执行的定时任务。因此任务执行的具体时间与添加 crontab 的时间无关。 * 由于定时任务是由系统服务执行的，所以不会弹出shell界面，因此在定时任务执行 echo 之类的命令没有意义。定时任务常用来设置简单的备份之类。 * 因为是系统服务执行，所以使用到的目录必须是绝对目录。 # Spring Data JPA 使用方法 *** JPA是Java官方定义的一套与数据库交互的接口标准。Spring Data JPA 实现了它，并且整合了多种数据库，使得与数据库的交互变得简单。 使用Spring Data JPA的逻辑： > 在springApplication设置里设置数据源（datasource）； > > 编写一个实体类，其中的属性对应数据库表单的列； > > 为这个实体类添加注解，使其能够与数据表衔接； > > 定义Dao（Repository），使用它来与数据库进行交互。 ## 一、导入包 首先用maven导入包： ```xml org.springframework.boot spring-boot-starter-data-jpa org.projectlombok lombok true mysql mysql-connector-java ``` 这里导入lombok，用于生成构造方法；导入mysql-connector，用于连接mysql数据库，与mysql交互这个是必须的。 ## 二、创建数据库 在外部（cmd）登录mysql并使用SQL语句创建数据库`jpatest`，新建一个表`users`用来储存用户数据。 ```sql mysql> create table users ( -> id int, -> name char(30), -> password char(30), -> userInfoId int); ``` 然后用ALTER指令设置id为主键，并设置其为自增。 创建完成后可以用IDEA自带的database工具登录数据库并查看： ![IDEA的database工具](https://s1.328888.xyz/2022/09/17/o9Gan.png) > 这里注意，IDEA的database窗口只是用于预览数据库和数据表，并不能让项目连上数据库。还需要手动设置datasource。 ## 三、配置数据源 在Spring设置（`application.properties`，一般在`resources`目录下，也有一种写为yml形式）中添加如下语句以添加数据源： ```properties spring.datasource.driver-class-name=com.mysql.cj.jdbc.Driver spring.datasource.url=jdbc:mysql://localhost:3306/jpatest?useUnicode=true&characterEncoding=utf8 spring.datasource.username=root spring.datasource.password=password ``` 这样就指定了一个数据源，其驱动为mysql驱动，数据库的url为`mysql://localhost:3306/jpatest`，也就是`jpatest`数据库。然后我们指定了用户名和密码。 ## 四、创建实体类 对应我们的需求和数据库的各列，我们新建下面的User类： ```java import lombok.*; import javax.persistence.*; @Data @RequiredArgsConstructor @NoArgsConstructor @Entity @Table(name="users") public class User { @Id @GeneratedValue(strategy = GenerationType.IDENTITY) private int id; @NonNull private String name; @NonNull private String password; @NonNull @Column(name="userinfoid") private int userInfoId; } ``` 下面对类上的注解进行说明。这些注解都是由`javax.persistence`定义的。 ### @Data、@RequiredArgsConstructor 和@NoArgsConstructor 都是lambok提供的。`@Data`提供getter和setter，`@NoArgsConstructor`提供`@Entity`要求的无参构造方法，而`@RequiredArgsConstructor`则提供仅包含必须的几个属性（这里是除了id以外的属性，因为id我们希望它自动生成）的构造方法。 `@RequiredArgsConstructor` 只会识别带有lombok的`@NonNull`注解或`final`修饰符的属性。所以在相关属性上加上`@NonNull`。 > p.s. 好像很多人用`@RequiredArgsConstructor`不需要使用@NonNull，但我本地没办法不用@NonNull实现。 ### @Entity、@Id 和 @Table `@Entity`注解会将这个类表示为准备映射数据库的实体类，必须结合@Id注解使用。 `@Id`所标注的属性会被识别为主键。一个表必须有主键，所以必须存在这个注解。 > `@GeneratedValue`用于给主键指定生成策略，一般用`GenerationType.IDENTITY`来指定主键为自增。这里的注解设置必须和数据库一致，否则会出错。 `@Table`用于标识需要对应的数据表名。如`@Table(name="users")`表示对应的是数据源下的`users`这个表。 ### @Column 这个注解用于属性上，可写可不写，用于指定这个属性所对应的列的名字。如果不写，那么指定的列默认是和这个属性名字相同的列。注意大小写是敏感的，要和数据库严格一致。 ## 五、创建UserRespository 这就是所谓的Dao层，由Spring提供具体实现。我们在这里需要定义一个接口`UserRespository`，继承Spring提供的接口`JpaRepository< >`以使用Spring提供的方法。 ```java @Repository public interface UserRepository extends JpaRepository { } ``` ### 说明： * `JpaRepository< >`需要提供实体类和ID（主键）的类； * 为了之后让Spring托管这个类，加上`@Repository`注解使之被定义为一个bean； * 只要留空这个接口就可以使用了。 在留空这个接口的情况下，就可以执行`save`，`saveall`，`delete`，`find`等等的CRUD（增删查改）操作了。但是由于`JpaRepository`实现的时候不知道你的类有哪些属性，所以要进行一些具体的操作，比如`findByPassword`（根据密码查找用户），就必须要在这个接口下自定义一些方法来完成。 Spring Data的一个强大的功能在于，你只需要在接口定义这个方法，而不需要实际写代码来实现它，Spring框架会自动理解你的方法的目的，并自动帮你实现想要的操作。 例如，上面提到的`findByPassword`可以直接用这样的方式实现： UserRepository： ```java @Repository public interface UserRepository extends JpaRepository { public User getByPassword(String passwd); } ``` test()： ```java user = userRepository.getByPassword("123"); ``` 虽然我们没有编写任何实现相关代码，但Spring仍通过解析方法名的意义帮你完成了你想要的操作。 除了匹配具体的数值，方法名的解析还支持值区间、包含、前缀等等非常丰富的匹配方法。这些方法在书写时IDEA都会提供补全的提示，非常方便。 当然，有时候我们还是会想用sql的方式进行操作，也可以使用`@Query`注解实现。 例子： ```java @Query(value = "select u from User u where u.password='123'") public User getByPassword2(); ``` 这个语法和原生的sql有所不同，需要单独查阅。 # Spring集成Artemis实现JSM的异步消息传递 *** JMS是一套Java定义的标准，用于在程序之间进行消息的流通。 ## 一、概念逻辑 JMS的逻辑如下： 发布信息的称为JMS生产者，生产者将信息发送给JMS服务器，同时说明发送到的目的地（Destination），JMS服务器将消息保存在对应目的地的一个队列（queue）中，等待JMS消费者领取。 JMS消费者有两种领取信息的方式，一种是拉（pull）模式，即发出收取消息的请求，等待直到队列中有消息到达为止；一种是推（push）模式，即由容器监听目标队列，消息到达时通知对应的消费者进行处理。 这样的模式意味着信息的传送可以不一定是一对一的。对发送到队列的信息，消费者提取后即pop掉。 JMS服务器（MQ，消息队列，在Artemis里称broker）常用apeche的ActiveMQ，以及其新版本Artemis。在本地或远程部署Artemis实例后即可使用。 Spring提供了一套JMS实现，即JMSTemplate，可用它写出消费者和生产者，与Artemis交互。 ## 二、引入依赖及配置 要在Spring项目中使用artemis，可在maven用springboot starter引入相应的框架： ```xml org.springframework.boot spring-boot-starter-artemis ``` 在application.yml中，可以对Artemis做一些配置。如果只是使用本地的Artemis broker实例，可以不做任何配置。 配置示例如下： ```yaml spring: artemis: broker-url: tcp://api.mcyou.cc user: admin password: passwd ``` 这里配置了broker的地址、用户名及密码。注意它是基于tcp的。 接下来要下载并创建artemis实例。首先在Apeche网站下载artemis，然后进入其lib，使用命令`artemis create 目标目录` 来在目标位置创建一个实例。创建时会要求输入想要的用户名及密码。 完成后来到实例的目录，进入/bin/，执行`artemis run`即可运行该实例。 ## 三、创建生产者 ```java import org.apache.activemq.artemis.jms.client.ActiveMQQueue; import org.springframework.beans.factory.annotation.Autowired; import org.springframework.jms.core.JmsTemplate; import org.springframework.stereotype.Service; import javax.jms.Destination; @Service public class JmsMessagingService { private JmsTemplate jms; private Destination messageQueue = new ActiveMQQueue("cc.mcyou.queue");; @Autowired public JmsMessagingService(JmsTemplate jms){ this.jms = jms; } public void sendUser(User user){ jms.send(messageQueue, session -> session.createObjectMessage(user)); } public void sendUser2(User user){ jms.convertAndSend("cc.mcyou.queue", user); } } ``` 导入一个JmsTemplate，然后使用jms实例即可完成发送操作。 这里sendUser方法和sendUser2方法展示了两种发送对象的方式。sendUser方法使用jms.send方法，需要使用MessageCreator来构造Message；sendUser2方法直接使用convertAndSend方法，发送对象更方便一些。 对于每个发送，都要指定一个`Destination`。这里既可以构造一个Destination对象，也可以直接用字符串表明destination的名字，传递给artemis处理。 ## 四、创建拉模式的消费者 ```java import org.springframework.beans.factory.annotation.Autowired; import org.springframework.jms.core.JmsTemplate; import org.springframework.stereotype.Component; @Component public class JmsMessageReceiver { private JmsTemplate jms; @Autowired public JmsMessageReceiver(JmsTemplate jms){ this.jms = jms; } public User receiveUser(){ return (User)jms.receiveAndConvert("cc.mcyou.queue"); } } ``` 还是通过Spring容器注入一个JmsTemplate的实例。在接收信息时，对应发送信息时的方法名，这里同样可以用`receive`方法或`receiveAndConvert`方法，且同样要指定一个接收的目的地。接收对象时直接用`receiveAndConvert`比较简单。如果用`receive`方法，需要手动注入一个`MessageConverter`对其进行转换。 注意对于拉模式的这种`receive`等方法，在调用时进程会被阻塞，等待信息到达。 ## 五、创建推模式的消费者 ```java import org.springframework.jms.annotation.JmsListener; import org.springframework.stereotype.Component; @Component public class UserListener { @JmsListener(destination = "cc.mcyou.queue") public void receiveUser(User user){ System.out.println("收到用户："+user.name); } } ``` 推模式是一个Listener的模式。使用注解`@JmsListener`注册监听器，同时指定destination。这样这个方法就交给Spring挂起，等待消息到达时由Spring调用这个方法，进行后续的处理。 推模式的最大好处在于不会阻塞进程，比较适合需要保证可用性的场景。 使用Spring提供的模板实现JMS，然后与Artemis通信，这样就使得限定于Java的JMS得以利用跨语言的Artemis进行通信。当然基于JMS的信息仍然必须由基于JMS的消费者接受才能利用。 # Spring使用自定义配置项 *** 在写Spring应用的时候，经常会用到Spring支持的application.yml 或 application.properties 来对Spring的一些属性进行设置。 实际上，Spring的这些配置项是与Spring内部的一些bean一一对应的。在配置文件修改这些属性时，就是在修改Spring运行时对应的一些bean的各种属性。 > application.yml 和 application.properties 的区别： > > 本质上他们的作用相同，仅仅是格式不同而已。.yml使用yaml格式，用冒号和缩进表示属性、参数以及层级关系；.properties格式用.来作为层级的区分。 基于这种配置项与bean的一一对应关系，我们可以通过Spring提供的注解来使得我们的bean与自定义的配置项挂钩。 为了使得一个模块专注于自己的事而不必兼顾配置项的读取，最好将一个模块需要用到的配置项抽取出来，集合到一个专用于储存配置的类中，比如下面的类`AppConfig`。 ```java package cc.mcyou.jmstest; import lombok.Data; import org.springframework.boot.context.properties.ConfigurationProperties; import org.springframework.stereotype.Component; @Component @ConfigurationProperties(prefix = "mcyou.config") @Data public class AppConfig { boolean config1 = true; //默认值 int config2 = 1; } ``` 注解说明： * 使用Spring提供的注解`@ConfigurationProperties` 即可告诉Spring应该将这个类纳入配置项管理。属性`prefix`表示在配置项里这个类的属性将在哪个层级下表示。 * 为了使其他类能够使用配置类读取配置项，用`@Component`将其注册为bean。在需要的类处使用`@autowired`引入即可。 * 由于Spring管理配置时都会使用set get等标准bean方法，所以这里必须提供get set方法，否则配置项不生效。这里用lombok的`@Data`。 接下来在对应的.yml或.properties文件里进行配置即可。 ```yaml mcyou: config: config1: false config2: 2 ``` 除了在这里配置，自定义配置同样可以通过部署环境的环境变量进行调整。 # MIT6.824分布式系统Lab1.MapReduce笔记 # MIT6.824分布式系统Lab2-Raft-A笔记 # MIT6.824分布式系统Lab2-Raft-B笔记 # 杂谈 # 杂谈-关于2021 *** ### 小小的引子 ​ 年度杂谈节目来了（ ​ 好久没更新了 上一个杂谈貌似还是高中毕业犯病罢（其实想想没必要的，没这么浓烈的感情，只是在地铁上没事干hh） ​ 以后可能会自己写一个网页，大概思路就是可以像说说一样发一些犯病内容，然后存起来，每天随机展示一篇这个样子。（因为犯病的时效性实在是太强了hhh） ​ 本来不是很想写的，但看到空间里好多人都在写总结，并且刚刚还在和游戏群里的群友写文来着，写上瘾了还是来凑个热闹吧（瞎写的，不要在意文笔就是了） ### 关于之前的犯病文 ​ 不知道出于什么目的啊，很无聊的就会去仿照佬佬的文案写一篇像模像样的犯病文。一开始感觉挺好的，既可以抒发感情又可以练习作文准备高考。（这就是为什么那段时间的犯病文都是高考作文风格的） ​ 但是很大的副作用就是现在看着好羞耻（ ​ 在随机跳犯病文系统做好之前还是先把之前的犯病文隐藏了？ ​ 不过博客嘛，还是要能够随手发一点自己想发的东西，记录当时的感想比较好，先留着吧\~ ### 正题-关于2021 ​ 现在写这篇文章是在成电的宿舍里，旁边有4个舍友（跑了一个，回家了）。想想去年今日还是在家里，应该是在电脑边玩吧。仅仅一年的时间，变化确实是挺大的。一年前大概是最最焦虑的时候，每天听点鸡汤歌曲（虽然现在也听），想着以后怎么怎么样该怎么这么办，如果什么什么那怎样怎样，应该是挺焦虑的。当时有一天考试考的不好，真的就是跟垮掉一样的emo， ​ 说实话，我现在对目前的这个境遇并不满意。那个时候偶然看到哈工大的分数是640，“哎呀好低啊，这学校感觉不太行”，结果现在高攀不起确实是事实hhh。当时想，只要把自己管好了，清华也不是不可能（笑）。但事实是，人是有天赋的，这个天赋就包括自律能力，以及对知识的接受程度，对情绪的处理能力，对压力的缓解能力，甚至包括看待世界的角度，有些时候说做不到，就真的做不到了。所以现在虽然不满意，但其实也不愿意再回去一次，谁知道会不会做的更烂呢（ 。当然我还是相信一切不是绝对的，至少要像理想的方向走几步试试嘛。 ​ 21年的开头两个月应该是整个人最颓丧、心理状态最差的两个月吧。首先是高考压力，那个不用说；最主要还是寒假来了。寒假我没选择留在学校那边补课做作业，而是选择自己去图书馆自习。大多数时候确实也做到了，每天最累的一件事就是盘算怎么买共享单车去图书馆最便宜。自己在图书馆最大的感觉就是孤独和迷茫。以前有老师每天布置任务的时候从来没有这样的感觉，那段时间高考的压力，成长的孤独感与漫长而又不知道如何利用的时间一起导致了我第一次感受什么叫emo。真正的无助和压抑，面对未来的无所适从，算是第一次真真切切的感受。当时的感觉就是，这个图书馆越坐越emo，有几天是直接不敢去图书馆了，怕心理出问题。 ​ 当然可能是受某原字开头游戏的影响，情绪慢慢随着剧情的推进有所缓和；看了大刘一篇《人生》，顿时就感觉到人生的沧桑和寂寞，也开始慢慢知道所谓信念的意义。也看了知乎上一篇关于病态的虚无感的文章，讲的是年轻人对目标和信念的缺乏。具体情形不太记得了，但当时我在床上想了很多，在图书馆的天台看着远处的大楼也想了很多。面对自己提出的疑问，我就是喜欢不停地想啊想，但幸运的是我还真想通了。想通了什么呢，不太好描述，结果就是我不再去想这些问题了。我要给自己树立一个很宏大的目标，仅此而已。至于怎么实现，不是我应该要管的，我也管不了。无论如何，自从那一天我给手机的开屏信息改成#include，壁纸改成灯塔之后，我就再也没有因为思考意义或者无故的虚无而浪费时间了。这段时间也算是一种蜕变吧。 ​ 之后就是高考了，没什么好说的，不能说非常努力，也不能说摆烂。总而言之，这段过程就是为高考做酝酿以及做几套卷子。只记得6月7号我生日那天，雨下的非常大，一进考场就停，一出考场就下，搁着故意捉弄人呢hhh。回忆起来的话，高考的压力确实是非同一般，就算嘴上不承认，但晚上也还是会失眠。这次高考题目和往年差距比较大，许多同学直接心态爆炸，而我提前做过期望预期所以还好心态没有非常炸，最后结果虽然不是那么满意但也没有低于期望。 ​ 印象比较深的是要准备报志愿的时候，拿着估分找可以去的学校，那是我第一次为分数感到无力。高考这种东西，似乎能改变很多，每个人都尝试去改变，但最终好像又回到命中注定的结局。既然是注定的结局，那就没什么后悔的必要，我就是这样想的。不过所幸的是志愿报的比较好，压线进这种事确实要攒不少人品hhh。 ​ 之后就是一个漫长的假期，好像什么事都没干成。最后几天收拾行李，坐车走的时候看着住的房子越来越远，又让我想起小学第一次坐电单车去上学的那种好像有什么东西在家没拿一样的奇怪感觉。到成电搬搬东西，布置宿舍，认识了舍友，平平常常，但偶尔看着成都灰蒙蒙的天，还是能想到家已在千里之外。 ​ 在成电的日子如今已经过去三个月了，有军训，有上课，有考试，但总结起来，我觉得还是平平常常。真的是平平常常，没什么波澜起伏，就好像在做一个每晚都连续的梦一样。不知不觉，上半年还在昆明，下半年已经身在成都，但生活的一切好像没什么变化，仍然是每天上课作业，只不过宿舍里多了电脑，课可以水调罢了。生活真的是太平常了，作为introvert 社交上其实也没有遇到特别大的挫折，无非是还未找到维持life-time的好友。其他活动非必须我去的也很少，也没有什么体验感可言，最主要的社交停留在线上，偶尔会感觉到孤独，但不至于emo。也不知道这是不是一种好的状态，但目前而言我就陷入这种状态之中，不知道会不会，或者说应不应该破局呢。 ​ 在学业上来说，和其他云南人一样，其实我也蛮力不从心的，主要是两科数学。在心理课做了一个心理剧，讲的是主角勤奋勤奋不过勤奋党，天赋比不过天赋党，感觉自己顿时已成戏中人啊。有的舍友天赋足够，不需要像我每天赶课、赶作业也可以学懂；有的人真的每节课第一排从不缺席，下课了一定不会走。有些时候只能感叹，确实没办法啊。 ​ 虽说大学生活平淡，但和中学比还是有不少不同点的。大多数事情可以DIY了，时间表可以DIY，宿舍可以DIY，衣服可以DIY，连个性也可以DIY，确实给我带来了新的体验。参加了工作室，也听了不少分享，对以后的选择路径也明确了不少。总之呢，大学相对中学多了不少机会，但机会永远只留给有准备的人。相对于卷，我还是倾向于取巧，同时在必要的时候给予最大程度的内卷值。怎么说来着？啊对，动态规划，DP\~ ​ 总之，2021确实是人生值得记一笔的一年（以至于我写博客写到了2点）。不过我觉得，有些事情，真的记一笔就好。 ### 关于2022+ ​ 现在想想啊，人的状态还是在一个正态分布里上下波动的。这种状态本身是很难被改变或者控制的，人并不能说想通了哪一点就能够让心态保持在什么样的水平，再说我也不是所谓内心强大的人。所以在未来，自然是要接受波动的——该怎么着就怎么着吧。 ​ 克制强迫症。有些时候，可能是因为算法学多了的原因，会很强迫症地对各种事情下意识做出评价，对这考虑对那考虑，但实际上这对大局，或者说自己的心态是没有任何意义的。强迫症地评价看法和观点，关心与自己无关的事，还是尽量减少吧，毕竟在杂事关心的越多，在正事关心的就越少。当然了，这种强迫症也体现在对各种事情量化效果的追求，提前评价半天不如直接去做，做事少考虑后果，这样也可以减少在图书馆做作业的时候摸鱼的次数hhhh ​ Do what you believe it's true.现在我的手机壁纸和开屏文字都没改，希望我的脑壳也能和手机的储存一样一直存着那座灯塔。活着很累，但总要活着；坚持很累，但总得have a start. ​ The less, the better. 和客服强迫症差不多，少一点感叹和空想的时间，少写点这种丢人现眼的杂谈，多搞点社交，看看闲书，反正有的是时间造作。 ### 尾声 别问尾声为什么这么短，问就是两点了写不动了。 升华主题？那是什么？ # 杂项 # c语言 scanf的返回值 *** 之前做学校的题，题目要求输入一串字符串，没有结尾标识，因此需要单独判断语句是否输入结束。除了正常的方法读`\0`、读或者使用`%s`之外，其实也可以利用scanf的返回值来完成。在用vs调代码之前都不知道scanf有返回值（说你呢不用`scanf_s`不给过的\*\*IDE） scanf的返回值： > scanf的返回值是所输入的数据与格式字符串中匹配的次数。 > > 如果输入出错，则返回EOF（常量，EOF==-1） 例子 ```c char a[1000]; char now; for(int i =1;scanf("%c",&now)==1;i++){ a[i]=now; } ``` 其中利用scanf的返回值做判断条件，只要输入完成，则scanf返回值为0，循环结束。 # 系统设计 ## 1. 总体设计 本工程采用前后端分离的设计模式，将后端与前端分离从而方便分工并保证程序的逻辑清晰。 ## 前后端约定 规定整个程序的全局变量如下： `char map[][]` 储存地图情况，用0表示空格 1表示蛇 2表示果子。 `int map_len` 表示地图的边长。 `int head_x` 表示蛇头x坐标。 `int head_y` 表示蛇头y坐标。 `int scoer` 表示玩家目前得分。 全局变量还包括一条链表，节点为node类，用来储存蛇身信息。 ## 前端 前端负责编写main函数，控制开始界面和地图的定时刷新，渲染地图的实时效果，处理用户的输入与后端的交互。 （1）游戏开始：开始界面的美化；用户输入地图大小，并用while+if判断用户输入的地图大小是否合理（限制在10\~100以内），并提示过大/过小； （2）主体：使用`Sleep`以及`system("cls")`达到不断刷新界面的目的，模拟蛇的移动；调用来自后端的move()，传入用户控制的方向，并将move返回值作为游戏是否继续的判断（move会返回0和1，while(1)则循环继续） （3）游戏结束：询问用户是否再玩一次，或者是否查看排行榜（调用跟排行榜相关的函数） ## 后端 后端负责编写游戏的运行逻辑，处理用户输入后的数据分析等等。 * `int move(char c)` 函数 由前端调用，每帧调用一次，是蛇移动的主要逻辑。 返回值含义： 0：游戏结束 1：正常进行 参数：经前端处理过的控制指令，为'w'/'a'/'s'/'d'。 * `int judge(int x, int y)` 函数 判断蛇是否咬到身体或者撞墙或吃到果子。 参数： x：欲判断格子的x坐标 y：欲判断格子的y坐标 返回值含义： 0：目标格子为空，可正常继续； 1：蛇撞墙或撞到自己，游戏结束； 2：蛇吃到果子。 * `void generate_fruit()` 函数 随机生成一个果子。 ## 2.模块设计 ### `move()` 函数 伪代码表示如下： ```c int move(char c){ int target_x = 计算目标x坐标(c,now_x) int target_y = 计算目标y坐标(c,now_y) int status = judge(target_x, target_y) if(status == 1){ return 0; } 链表.在首位置添加节点(target_x,target_y) if(status == 2){ score += 5 generate_fruit() }else{ int tmp_x = 链表.取末位置节点x int tmp_y = 链表.取末位置节点y 链表.删除末位置节点() map[tmp_x][tmp_y] = 0 } head_x = target_x head_y = target_y map[x][y] = 1; return 1; } ``` ### `judge()`函数 # 计科基础 # 编译原理 # 编译原理：词法分析笔记 *** ## 定义 词法分析是将源程序从左至右，逐个字符地扫描，然后产生一个个的单词符号，将源程序转换成单词符号。之后就可以根据单词符号做后续的分析。 ## 单词 单词符号分为5类： 1. 标识符，如变量、数组、函数等，如`length`，`nextch`等； 2. 基本字，也叫保留字，如`if`，`while`等等； 3. 常数，如`3.1415926`； 4. 运算符，如`+`，`-`，`*`, `/`, `>=`, `!`, `==`, `&&`等； 5. 界符，如`;`,`(`.`)`,`:`等。 表示方法： 识别出的单词应该用二元式来表示，以便后续处理：（单词类别，单词属性） > e.g.（标识符的编码，标识符的名称“i”） ## 正则表达式 设正则表达式`r`表示语言`L(r)`，则`L(r)`就是根据`r`的规则递归地定义的。 正则表达式简介书面地规定了一门语言。 归纳步骤： * `(r) | (s)`：可选 r 或 s； * `(r)(s)`：连接r和s； * `(r)*`：称为Kleene闭包，也就是将L连接0次或多次后得到的串集； * `(r)`：括号不影响其所表示的语言。 > e.g. > > `（a | b）*` == `(a*b*)*`，都表示由任意个a和b组成的串，如空串ε、a、ab、ba、baba等。 ## 有限状态自动机 有限状态自动机用具体程序的方式实现了正则表达式的匹配。 有限状态机有一系列有限状态的集合和一些从一个状态通往另一个状态的边，其中一个状态是初态，某些状态是终态。 有限状态自动机分为两类： 1. 不确定的有限状态自动机，英文简写NFA。其对边上的标号没有限制，可以以空串ε作为标号，一个符号也可以标记离开同一个状态的多条边（可以有多个同标号的出边，所谓不确定具体去哪个状态）。 2. 确定的有限状态自动机，DFA，有且仅有一条以某符号为标号的离开该状态的边。 DFA是NFA的一个特例，它没有对输入ε的转换动作，且对于状态s和输入符号a，有且只有一条标号为a的边离开s。 DFA的例子： ![](https://ask.qcloudimg.com/developer-images/article-audit/7175224/q9masxhpy3.png?imageView2/2/w/1620) NFA的例子：![](https://ask.qcloudimg.com/developer-images/article-audit/7175224/fqctwl82ab.png?imageView2/2/w/1620) ## NFA的确定化 由于NFA在转移时具有不同的可能性，所以在具体实现的运行时往往效率较低，因此需要一种方法将NFA转化为确定的DFA。 ### 三个重要的操作（概念）： * 状态集的空闭包集合（ε-闭包）： 若`I`是一个状态集合，其空闭包集合就是`I`中从任意元素出发经过**任意**条ε弧（标号为ε的边）能到达的状态的集合，记为`ε-closure(I)`； * 状态集的a弧转换： `I`中的任意状态经过**一条**a弧能到达的所有状态的集合，记为`move(I,a)`； * 状态集的a弧转换的闭包`Ia`： 就是状态集I的a弧转换的ε闭包，即 $$I\_a = ε-closure(move(I,a))$$ ### 确定化的步骤 #### 第一步：规则转换 将NFA转换成标准形式： ![](https://ask.qcloudimg.com/developer-images/article-audit/7175224/965r4x1qdv.png?imageView2/2/w/1620) #### 第二步：状态合并 为了确定化DFA，我们需要从初态开始，根据ε-闭包将闭包内的状态合并为一个新的状态，然后根据\*（输入的字符）弧转换引出新的状态，直到全部状态都已转换完成。 实例：原来的NFA： ![img](https://ask.qcloudimg.com/developer-images/article-audit/7175224/1iznu3hlfi.png?imageView2/2/w/1620) 首先求初状态的ε-闭包，即{i,1,2}，作为初始集合S； 求出S的a弧、b弧转换的ε-闭包，即Ia、Ib，得到新状态A、B： A = {1,2,3}，B={1,2,4} 以此类推，求出新状态的的a弧、b弧转换的ε-闭包，直至不再产生新状态（新集合）为止。一般做法是列出列为I、Ia、Ib的表格，每个新状态开一行；每个产生的新集合（状态）都要再去求Ia和Ib，直到不产生新状态（产生表的新行）为止。接下来只需要根据表合并新状态，然后构造DFA即可。 ![img](https://ask.qcloudimg.com/developer-images/article-audit/7175224/j2s4rgf6kb.png?imageView2/2/w/1620) 这样就完成了NFA到DFA的等价转化。其中产生新状态和求\*弧转换的表，称为Dtran表。 ### NFA确定化实例： NFA： ![](https://i.328888.xyz/2023/02/15/mXQmt.png) 列表： ![](https://i.328888.xyz/2023/02/15/mgCdk.png) 合并状态： ![](https://i.328888.xyz/2023/02/15/mg22p.png) 根据表构造DFA：[![mgcuH.png](https://i.328888.xyz/2023/02/15/mgcuH.png)](https://imgloc.com/i/mgcuH) > 参考：[编译原理学习笔记-3：词法分析(一)基本过程、正规式和有限自动机 - 腾讯云开发者社区-腾讯云 (tencent.com)](https://cloud.tencent.com/developer/article/1613187) # CSAPP 第二章笔记 *** ## 2. 信息表示法 位是信息储存的基本单位，特指二进制位，储存范围为0\~1。 一个字节固定由8位组成，表示范围是0\~255，与字长（多少位）无关。 ### 2.1.1 十六进制 用二进制表示大数过于漫长，所以使用16进制来表示位模式。 十进制： 1-9 10 11 12 13 14 15 十六进制：1-9 A B C D E F C语言中一般以`0x`或`0X`开头表示十六进制值。 ### 2.1.2 字数据大小 计算机系统储存/操作/传送时二进制码的单位称为字。字的长度为字长。 n位机器表示字长为n的机器。如32位和64位。 字长决定了虚拟地址空间的最大大小。32位机器的虚拟地址的范围为 $$0-2^{32}-1$$个字节。 32位和64位程序在编译时编译器分配的字节数是不同的： | | 字节数表 | | | | :------: | :------------: | :-: | :-: | | 有符号 | 无符号 | 32 | 64 | | char | unsigned char | 1 | 1 | | short | unsigned short | 2 | 2 | | int | unsigned int | 4 | 4 | | long | unsigned long | 4 | 8 | | int32\_t | uint32\_t | 4 | 4 | | int64\_t | uint64\_t | 8 | 8 | | float | | 4 | 4 | | double | | 8 | 8 | ### 2.1.3 寻址和字节顺序 不同机器对数据的储存方式不同。 * 小端法（大多数机器）： 最低有效字节储存在低地址，最高有效字节储存在高地址。 * 大端法： 最低有效字节储存在高地址，最高有效字节储存在低地址。 例子 0x012345 在地址0x100-0x102的储存： 小端法： 0x100 0x101 0x102 45 23 01 （其中45是最低有效字节） 大端法： 0x100 0x101 0x102 01 23 45 ### 2.1.6 布尔代数 主要是位运算的运算符 * NOT 表示为 \~ 否 * AND 表示为 & 与 * OR 表示为 | 或 * EXCLUSIVE-OR 表示为 ^ 异或 其中 0^1 = 1 而 1^1 != 1 注意位级运算与逻辑运算不同。 ### 2.1.9 位移运算 主要是逻辑位移与算数位移的区别。 \[01100011] >>4（逻辑右移）-> \[00000110] \[01100011] >>4（算数右移）->\[00000110] \[10010101] >>4（逻辑右移）->\[00001001] \[10010101] >>4（算数右移）->\[11111001] 第四个运算，因为数据最高位是1，所以用1填充。 ### 2.2.2 无符号数的编码 二进制位转无符号数用函数 $$B2U\_\omega$$ （Binary to Unsigned）来表示 无符号数编码的定义： $$B2U\_\omega(\vec x) = \sum\limits\_{i=0}^{\omega-1}x\_i2^i$$ 其实就是将无符号数用二进制位表示。 $$B2U\_\omega$$ 是反身的，即 $$B2U\_\omega$$ = $$U2B\_\omega$$ ，因为二进制位及其表示的数是一一对应的。 ### 2.2.3 补码编码 补码（Two's Complement）编码的定义： $$B2T\_\omega(\vec x) = -x\_{\omega-1}2^{\omega-1}+ \sum\limits\_{i=0}^{\omega-1}x\_i2^i$$ 主要逻辑是因为最高有效位为1的值大于其他所有没有该位的数，所以设它的权重为负（$$-2^{\omega-1}$$）。 因为其权重最高，所以当最高有效位为1时，整个数的值必<0；当最高有效位为0时，整个数的值必>0. 例子（$$\omega$$代表补码位数，这里是4位补码）： $$ B2T\_4(\[0101]) = -0*2^3 + 1*2^2 +0*2^1 + 1*2^0 = 0+4+0+1 = 5 $$ $$ B2T\_4(\[1011]) = -1*2^3 + 0*2^2 +1*2^1 + 1*2^0 = -8+0+2+1 = -5 $$ 可以看出，$$\omega$$位补码能表示的最大范围 $$TMax\_\omega = 2^{\omega-1}-1$$ ，其表示的最小范围为$$TMin\_\omega=-2^{\omega-1}$$ 以长度4为例，其表示的范围就为 -8\~7. 数字与补码间也是一一对应的，具有反身性。 > 个人补充 > > 由此可以看出，程序在被编译时需要确定相应类型的最大数据长度（位数），因此才有int\_32或者64之类的标准。此外，这里也说明int空间内所存储的数字大小并不影响其所占用的内存空间。 有符号数还有两种表示方法，即**原码**和**反码**。 从补码展开其实是英文和数学的逻辑（如`Two's Complement`指对非负数x的表示法为$$2^\omega-x$$）。中文的逻辑（如`原码` `补码`）是从原码出发，反码和补码是对原码的修改。 * 原码 原码是人脑比较容易理解的一种表示方法，即在原本数据上再加一个二进制位表示正负，0表示正，1表示负。 例：（8位） 1：\[0000 0001] -1：\[1000 0001] > 注： > > 正数的补码和原码相同，负数就是原码除符号位不变，其他全部与原码相反，最后+1 > > \[+1] = \[00000001]原 = \[00000001]反 = \[00000001]补 > > \[-1] = \[10000001]原 = \[11111110]反 = \[11111111]补 > > 可以理解补码是在反码的基础上补。 * 反码 反码与补码类似，只不过最高位有效权是$$- (2^{\omega-1}-1)$$ 而不是$$-2^{\omega}-1$$。 > 注： > > 正数的反码和原码相同，负数的反码除了符号位不变，其他全部与原码相反。 > > \[+1] = \[00000001]原 = \[00000001]反 > > \[-1] = \[10000001]原 = \[11111110]反 > > 可以理解反码是原码基础上的反位结果。 ### 2.2.4 有符号数与无符号数的转换 这样的转换在处理时，不改变原来的二进制位值，只是解释的方法改变。 * 补码->无符号数 $$ T2U\_{\omega}(x)=x+2^{\omega} \space\space(x<0) $$ 补码$$-2^{\omega-1}$$到0的部分平移到无符号数$$2^{\omega-1}$$到$$2^{\omega}$$之间，x>0的部分不变。 * 无符号数->补码 $$ U2T\_{\omega}(x)=x-2^{\omega} \space\space(x>TMax\_{\omega}) $$ 无符号数$$2^{\omega-1}$$到$$2^{\omega}$$之间的部分平移到补码$$-2^{\omega-1}$$到0之间，x<$$2^{\omega-1}$$的部分不变。 > 补：关于为什么C语言定义INT\_MIN要用-(INT\_MAX)-1而不用-2147483648： > > [c语言里面TMin不能写成-2147483648的原因\_zerods-seu的博客-CSDN博客](https://blog.csdn.net/zerodshei/article/details/51920425) ### 2.2.6 扩展一个数的位表示 1. 无符号数的扩展：零扩展（扩展位全部填零） 2. 补码数的扩展： $$B2T\_{\omega+k}(\[x\_{\omega-1},...,x\_{\omega-1},x\_{\omega-1},x\_{\omega-2},...,x\_0]) = B2T\_\omega(\[x\_{\omega-1},x\_{\omega-2},...,x\_0])$$ 即扩展位都用最高位填充 > 例：\[1011] = 3-8 = -5 > > \[11011] = 8+3-16 = -5 > > \[111011] = 16+8+3-32 = -5 ### 2.2.7 截断数字 1. 截断无符号数： 有可能不溢出，也可能出现溢出的情况（截断了有效位）。出现溢出时就和通过取余的方法来取减小位数类似： $$B2U\_k\[x\_{k-1},x\_{k-2},...,x\_0]= B2U\_\omega(\[x\_{\omega-1},x\_{\omega-2},...,x\_0])\space mod\space 2^k$$ 1. 截断补码数： 与截断无符号数类似： $$B2T\_k\[x\_{k-1},x\_{k-2},...,x\_0]= U2T\_k( B2U\_\omega(\[x\_{\omega-1},x\_{\omega-2},...,x\_0])\space mod\space 2^k )$$ 例子：将四位数值截断到三位数值： | 二进制 | 二进制 | 十六进制 | 十六进制 | 无符号 | 无符号 | 补码 | 补码 | | ---- | --- | ---- | ---- | --- | --- | --- | --- | | 原始值 | 截断值 | 原始值 | 截断值 | 原始值 | 截断值 | 原始值 | 截断值 | | 0000 | 000 | 0 | 0 | 0 | 0 | 0 | 0 | | 0010 | 010 | 2 | 2 | 2 | 2 | 2 | 2 | | 1001 | 001 | 9 | 1 | 9 | 1 | -7 | 1 | | 1011 | 011 | B | 3 | 11 | 3 | -5 | 3 | | 1111 | 111 | F | 7 | 15 | 7 | -1 | -1 | ### 2.3.1 无符号加法 无符号加法溢出：$$x+y=x+y-2^\omega$$（溢出时） ### 2.3.2 补码加法 补码加法溢出： $$x+y=x+y-2^\omega$$（正溢出） $$x+y=x+y+2^\omega$$（负溢出） ### 2.3.4 无符号和补码乘法 无符号和补码的乘法也类似，溢出时截断即可。 $$x\*y = (x ×y)mod\space2^\omega$$ ### 2.3.6 乘/除以常数 一个变量乘或除以常数时可以用位移的方法用更快的时间来达到同样的目的（编译器其实也会做类似优化） $$x\*2^k = x<<2$$ $$x/2^k = x>>2$$ ### 2.4.1 二进制小数 小数相对整数不同主要是因为有小数点的定义。但如果使用定点数，即小数点所在的位确定的表示方法来表示小数，其能表示的数将非常有限。 浮点数顾名思义就是小数点所在位不定的表示方法。 ### 2.4.2 IEEE浮点表示 IEEE浮点标准用类似科学计数法的方式来表示小数。 例如十进制数12.34可以表示为$$1×10^1+2×10^0+3×10^{-1}+4×10^{-2}$$ 同样二进制数10.11可以表示为$$1\times2^1+0\times2^0+1\times2^{-1}+1\times2^{-2}$$ 类似科学技术法有 符号S$$（+1/-1）\times 原数M（如1234）\times2^{指数E}$$ **IEEE浮点标准表示法定义：** $$V = (-1)^s\times M \times 2^E$$ 其中： > S：符号位 0/1 > > M：尾数 表示一个整数，相当于上述的原数 > > E：阶码 表示一个整数，作用是为尾数加权 类似于上述2的指数 在具体内存中，float和double数据类型的结构分布为： 符号数（s） 阶码（exp）尾数（frac） > s、exp、frac这里指符号数、阶码、尾数在浮点数数据类型中的位模式，不是它们的值 在float和double类型中阶码和尾数所占的位数不同。 ![位表示](https://img-blog.csdnimg.cn/20210206104342484.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0MDM3MzU4,size_16,color_FFFFFF,t_70) IEEE定义了三种情况的值： 1. ***规格化的值*** 阶码exp的位模式不全为0（exp!=0）且不全为1时，称这个浮点数为规格化的值。 **阶码的值E**: $$E = e - bias$$ > e指浮点数exp位的值，bias是偏置值，因为E需要能够表示负数，所以减去偏置值使得阶码的值的范围能够与0对称。 > > bias的值为$$2^{k-1}-1$$ （单精度为127，双精度为1023） **尾数的值M**：$$M=1+f$$ > f 指的是frac区域的位表示的整数值。在解析时给他+1，目的是为了和非规格化数平滑衔接。 1. ***非规格化的值*** 阶码exp的位模式全为0（exp=0）且不全为1时，称这个浮点数为非规格化的值。 非规格化的值用来密集且均匀地表示0和0周围的小数。 **阶码的值E**: $$E = 1 - bias$$ > 这里用1-bias 也是为了和规格化的值平滑连接 **尾数的值M**：$$M=f$$ > 因为本身就用于表示0周围很小的数，所以不需要+1. 1. ***特殊值*** 当阶码各位全为1时，这个浮点数表示特殊值。 * 小数域（frac）全为0时，表示无穷，正还是负无穷由符号位决定。 * 小数域为非0时，表示NAN，即Not A Number，用来表示结果不能是实数或者无穷的情况，如计算$$\sqrt{-1}$$、无穷大-无穷大时就会返回NAN。 浮点数具体到位上比较难以理解，但看图即可比较好的明白其构造： !\[aaaaa]\(CSAPP 第二章笔记.assets/aaaaa.png) !\[img]\(CSAPP 第二章笔记.assets/MCVX\`I%HS\@MY{BO$$J9D\_PI5.png) ### 2.4.4 舍入 对浮点数进行舍入是由于浮点数的精度是有限的，关于某个数（不一定是无理数或者10进制下小数位很长的数）只能由于其最相近的可表示的数来表示。 * 对于正好处于两个可表示小数值中间的数，IEEE标准采用**向偶数舍入**的方法，即向舍入后最末位为偶数的方向进行舍入。 !\[bbb]\(CSAPP 第二章笔记.assets/bbb.png) * 对于其他数，向更靠近的那个可表示的浮点数舍入。 ### 2.4.5 浮点运算 因为浮点数存在溢出和舍入的情况，所以在浮点运算时容易出现丢失精度的问题。 例如 (3.14+1e10)-1e10的值为0，因为在第一次运算的时候3.14因为精度问题被舍入了。 因此浮点运算往往不具有交换性和结合性，可能会导致一些问题。 > 哎哟终于结束了 挺枯燥的一章 但还是很有意思的（ # 计算机组成原理笔记 *** ## 第一章 1. 冯诺依曼体系： * 由五大部件（储存器，运算器，控制器，输入设备和输出设备）组成； * 采用二进制表示信息； * 采用存储程序的工作方式。 2. 所有计算机都是冯诺依曼体系？ × 3. 硬件系统基本组成： * CPU由运算部件、寄存器组和控制器组成，通过CPU内部总线相互交换信息；控制器提供整个系统工作所需的各种微命令，这些微命令可用组合逻辑电路或执行微程序产生。 * 储存器包括主存，外存和高速缓存等。 * 输入输出设备、总线和接口。 4. 北桥：内存控制，视频控制，与CPU的交互；南桥：控制外部设备和BIOS 5. 性能的评价指标： * 字长：定点运算的操作数的位数； * CPU主频`f`：CPU内核的工作频率，CPU时钟频率。时钟周期T = 1/f。 * 平均每条指令的时钟周期数CPI，每条指令的平均用时 = CPI / f ## 第二章 6. 十六进制的一种标注方法是以H为后缀，最大数码为F； 7. 原码：第一位符号位，0正1负；范围是 $$-(1-2^{n-1}) 到 1-2^{n-1}$$ 8. 补码：- (X) = (X变反 + 1)；范围是$$-1 到 1-2^{n-1}$$ 9. 浮点数： $$N = (-1)^s ×1.M × 2 ^{E-127}$$ 10. IEEE754：一位符号位，8位指数位，23位尾数位，共32位 11. 十进制转IEEE754：先转换成二进制，规格化二进制（1.xx \* 2^x），阶码真值+偏置值得阶码，再拼上尾数和符号位。 12. 大端法：高字节存放在低地址，就是人的阅读习惯；小端法：高字节放在高地址，使得数据位的权值和地址的高低联系起来。 13. 补码加法：符号位参与运算直接相加；补码减法：转换为与减数的负数（变反+1）相加； 14. 原码加减法：先对数值位进行加减，再处理符号位 ## 第三章 13. CPU硬件结构模型： * 运算部件：ALU，输入逻辑，输出逻辑 * 缓存部件 * 寄存器组：通用寄存器、暂存器、指令寄存器IR、程序计数器PC、程序状态字寄存器PSW、地址寄存器MAR、数据缓冲寄存器MBR（模型的MDR）、栈指针寄存器SP。 * 可被编程访问：R0-R3，PSW，PC，SP 不可访问：IR、MAR、MDR、C、D * PSW中有些位可以被编程修改 √ * 控制部件 * 时序系统 * 数据通路和控制通路 14. 寻址方式： * 立即寻址：直接在指令里读操作数 * 直接寻址：给出内存地址或寄存器号，以读取操作数 * 间接寻址：从某寄存器或主存中读取一个地址，然后再到这个地址读取操作数 * 变址寻址：如X(R0)，表示 取PC指向的地址里的值 加上R0里的值 得到操作数的有效地址 然后在这个地址里就可以找到操作数。实质是将形式地址作为基址地址，寄存器里的内容为偏移量。 * 基址寻址：将寄存器的内容作为基址地址，形式地址作为偏移量。 15. 模型机的一些寻址方式： * R： 寄存器的内容作为操作数 * (R)：寄存器的内容作为有效地址 * -(R)：寄存器的内容-1后作为有效地址 * (R)+：寄存器的内容作为有效地址，访问完成后寄存器的内容+1 * @(R)+：寄存器的内容为间接地址，访问完成后寄存器的内容+1 * X(R)：见14 16. 模型机的控制系统结构：微命令发生器、时序系统，以及对IR、PSW、PC的信息输入。 17. 控制系统的输入信号：IR、PSW、PC、时序系统、IO请求、复位信号 18. 时序系统：一条指令的完成（指令周期），分为若干个工作周期，每个工作周期又分为若干个时钟周期（节拍） 19. 并行加法器的运算速度取决于传递进位信号的逻辑电路（进位链） 20. 串行进位链：$C\_i = G\_i + P\_iC\_{i-1}$；并行进位链：$C\_i = G\_i + P\_iG\_{i-1} + P\_iP\_{i-1}G\_{i-2}+...+P\_i...P\_1C\_0$ 21. 四大基本工作周期： * 取址周期FT：完成将指令从M取出送进IR，以及修改PC * 源周期ST：读取操作数，暂存于C * 目的周期DT：读取目的地址放入MAR，或读取目的操作数，暂存于D * 执行周期ET：执行数据传输、运算等 22. 指令流程：重点一张图 ![](https://pic1.imgdb.cn/item/63687f3f16f2c2beb1929690.jpg) 23. 常见模型机指令流程（微指令）： * E开头：Enable，将寄存器内容打到总线上，如EMAR * R：从主存读内容到总线 * W：写内容到主存 * S开头：将（外）总线上的内容读入寄存器，如SIR，SMDR * 直接传递，如PC->A，用于将寄存器的值打入A或B，或简单的对寄存器的值传 * 直通A/B：直接让A/B穿过ALU * A加B：让ALU算A+B，然后输出 * DM：直接送出移位器 * CP开头：过ALU送出的值复制到寄存器 24. 处理X(R0)：X是一个地址，存在当前指令的下一个地址。处理时应取PC指向的地址（因为取值的时候PC已经+1，这时候就指向X）的值与R0的内容相加，得到操作数地址。处理完后PC要+1（略过X）。 ## 第四章 24. 存储器的主要性能：速度（T，用存储周期表示）、容量（S，用MB GB表示）、价格（C，用每位的价格表示） 25. `命中率`：H = N1 / (N1 + N2)，N1：对M1储存器的访问次数；N2：对M2储存器的访问次数 26. 存取方式分类： * RAM：随机访问存储器，如主存和高速缓存； * SAM：顺序访问存储器，按顺序遍历查找，如磁带 * DAM：直接访问存储器，可以先直接确定一块区域，然后再顺序查找，如磁盘 27. 存储器的技术指标： * 存取时间TA：进行一次读写的时间 * 存取周期TM：本次存取到下次存取开始的时间 TM = TA + 传输、复原等时间 * 数据传输率DTR，也叫传输带宽 28. 主存的逻辑设计： * 总容量 = 编制单元数\*位数，位数指每个编制单元的数据宽度。设计时用小容量芯片拼，例如4M \* 2 可以由 4个1M \* 2 或 2个4M \* 1 拼成。 * 设计过程： ![](https://i.328888.xyz/2022/12/08/fmXIo.png) ![](https://i.328888.xyz/2022/12/08/fmxuV.png) > 低位分配给芯片，高位用于片选逻辑。剩下的位留空。 > > 片选逻辑用来选择芯片。这里的片选实际上只用到了两个地质线A11-A12（能表示2^2个芯片）. ![](https://i.328888.xyz/2022/12/08/fmzPq.png) > 注意上面R/W那一条是控制总线 > 补充连线图： ![](https://i.328888.xyz/2022/12/08/fp4Bt.png) 29. 奇偶校验：约定校验码中1的个数为奇数/偶数，码距=1。例：偶校验：1011001 0 ; 1911911 1. 30. 海明校验：可以找出错误的位。m+k<=2^k-1，m表示数据位数，k表示校验码位数。海明校验的校验码分部于第2^0，2^1,2^2...位。其他位都是数据位。将其他位的位置转换为二进制，其对应位为1的位数2^a = 1，2^b = 0，2^c = 1 ，就说明这个位由2^a、2^c两个校验位负责校验。每个校验位都对其负责的位进行奇偶校验（异或）。接收方重新按检测位进行检验，如果发现不一致，综合所有检测位的结果，排除一致的检测位，算出有错的位。 ## 第五章 31. 总线定义：一组能为多个部件分时共享的信息传送线路；总线分类：CPU内总线、部件内总线、系统总线、外总线； 32. 接口定义：主机与外设间的连接逻辑，控制外设I/O操作；接口分类：并行接口（接口与系统）、串行接口（接口与外设）。 33. 中断定义：CPU暂停执行现行程序，转去执行为某个随机事态服务的中断处理程序。处理完毕后自动恢复原程序的执行。典型应用：管道中、低速I/O操作；处理故障。 34. 中断的流程：保护现场-中断服务处理-恢复现场-开中断-返回 35. DMA定义：直接存储器访问，是依靠硬件而不需要CPU的直接在主存与外围设备之间进行数据传送的方式，如磁盘IO。· # CSAPP Lab1. Datalab *** Datalab是第二章信息表示法的实验，主要涉及各种数据类型表示方法的应用。 这个lab需要按照要求用严格的代码规范完成。lab附带评分的程序。 ## 1. bitXor 手写按位异或，只允许用&和\~（按位取反）。 异或就是位不相等的时候才是0，也就是他们既不都是1，也不都是0. 都不是1，就是`~(x&y)`。都不是0，就是`~(~x & ~y)` ```c int bitXor(int x, int y) { return ~(x&y) & ~(~x&~y) ; } ``` ## 2. tmin 求最小的二进制补码。最小的补码就是符号位是1，其他全是0，这样就是$$2^{31}-0$$了。 ```c int tmin(void) { return 1<<31; } ``` ## 3. isTmax 给一个数，问是不是最大的二进制补码。 对int来说，二进制补码的最大值当然是符号位是0其他全是1，也就是$$2^{位数-1}$$。 题目只允许使用：! \~ & ^ | + 由于不允许使用循环结构，自然不能一位一位的用|或者&去试。这时候异或^和取反\~就成了我们最有用的工具。 考虑返回1的情况，如`011`,`01111`,`0111111`，再考虑返回0的情况，如`0110`,`11110`，我们发现最大补码的特点是第一位是0，其他位都是1. 要用到异或，这时候应该用可以用的加法+来使得异或可以发挥用处。 由于最大补码只有第一位是0，所以+1后一定变成如1000，其他任意情况都不满足这一性质。1000和他本身0111是相反的。于是就写成 `~x==(x+1)` 。但题目不允许用==，考虑到`a^a==0`， 于是可以改成：`!(~x^(x+1))` 但这里有个例外要写特判。-1（1111）+1以后为0，也满足我们的判断条件。所以要特判把-1排除掉。 怎么排除-1呢？-1+1当然==0了。注意到这里允许用!运算符，!x可以用来检测x是否为0. 于是用两个!即可排除-1（x+1=0）的情况。 ```c return !(~x ^ (x+1)) & !!(x+1); ``` ## 4. allOddBits 给一个数，判断是否他的二进制偶数位都是1. 判断的范围是int范围。 既然范围是$$2^{32}$$，那只需要设`a=10101010101010101010101010101010`（32位），然后判断a\&x是否等于a就行了。 这里等于还是用异或来判断。将a转换成十进制输入程序：2863311530。 ```c int allOddBits(int x) { int a = 2863311530; return !((x&a)^a); } ``` ## 5. negate 给一个数，输出他的相反数，当然不能用-。 考虑到补码编码，是用除了最高位的值减掉只看最高位表示的值，1可表示为0001，-1可表示为1111. 于是容易看出`-1 = ~1 + 1`。 推广一下，得到`-a = ~a + 1`。 ```c int negate(int x) { return ~x + 1; } ``` ## 6. isAsciiDigit 判断给定x是否 0x30<=x<=0x39。 其实就判断是否x-0x30 和 0x39-x 都>=0就行了。 如何判断>=0呢，对补码编码，最高位的那个bit就表示了正（或0）负。于是只要让他&(10000...（即0x80000000，只有第一位是1，或-2147483648，即int表示的最小值）)，就可以取到那一个特定位的值了。这个技巧还是蛮常用的。这里不给用减号，但前面正好写了negate()，当然要用了。 ```c int isAsciiDigit(int x) { int a = x+ negate(0x30); int b = 0x39 + negate(x); int c = -2147483648; return !(a&c) & !(b&c); } ``` 貌似其他博客不是我这样做的，不过我觉得这样做挺简单的。 ## 7. conditional 要求用位运算实现三目运算符一样的效果。 即：`if x == 0 then return z else return y` 不能用条件分支，那肯定需要用+来连接两个部分，每个部分在不相关的时候用位运算置0. 用位运算怎么置0呢，当然是`x & 0 = 0`了。那另外那边怎么保持原样呢？ 其实刚刚我们就发现，-1的二进制表示是111111...111。于是`x & -1 = x`。 这里可以用!!x和!x得到对应的1和0，再利用上面的negate()就可以得到-1和0了。 ```c int conditional(int x, int y, int z) { return (y&negate(!!x)) + (z&negate(!x)); } ``` 一行解决，貌似比我看到的题解都简单。 ## 8. isLessOrEqual 判断两个数是否小于等于。 上面我们写过判断>=了，把符号交换一下就可以复用了。 ```c int isLessOrEqual(int x, int y) { int a = y + negate(x); int b = -2147483648; return !(a&b); } ``` > 题目没有讲数据范围，如果数据范围大的话可能会爆int（事实上评测下来没有）。如果要写的很完善，可以额外写一个逻辑判断溢出（本不该发生改变的符号产生改变）。 ## 9. logicalNeg 实现!运算符。即`if x == 0 then return 1 else return 0` 考虑以下事实： 对补码，正数与零的最高位为0，而负数的最高位为1； 在negate（取相反数）操作时，正数和负数的最高位都会变换，而零在操作时最高位不会变换。 于是我们可以对x取相反数，将0和正数区分开来；而0和负数在表示上本质不同，很容易区分他们。 右移时，若最高位为1，则填充的bit为1，否则为0。于是得到技巧： 要得到最高位，可使x>>31，若值为-1（1111...11），则最高位为1；若值为0，则最高位为0。 于是我们可以用 `negate(x)| x` 来区分。对于正数，其值为1xxxx..xx | 0xxx..xx，对于负数，其值也为0xxx..xx | 1xxx..xx ，结果都为1xx..xx。于是我们右移31位，他们的结果都是-1；对于0，其值始终为0. 这样我们再最后给他+1，就达到为0返回1，其他返回0的效果了。 ```c int logicalNeg(int x) { return ( (negate(x)| x) >>31) +1 ; } ``` ## 10. howManyBits 求最高的一位有效位是多少。 这题有点奇怪，其实就是暴力位移了以后判断，要优化的话也就走一个倍增，不知道有没有更好的做法。 首先要处理负数，如果是负数就按位取反。原理是决定负数补码表示的值的位是左边数第一个0。例如1101和11101表示的值是一样的。按位取反以后0就变成1，1变成0，就和正数的处理方法一样了。取符号sign为0或1，结合&和|，就很好处理了。 接下来就暴力的倍增，设变量left16 left8 left4 left2 left1 left0，分别表示剩下的x位中是否有1。从16开始，每次进行一下位移，来检测剩下16位中是否有1.如果有，则右移16位，同时记录在变量上；如果没有则不移动。然后再到8,4，...以此类推。 最后把记录的移动的位数加起来，再+1（符号位也要算在内）就行了。 ```c int howManyBits(int x) { int left16,left8,left4,left2,left1,left0; int sign = x>>31; x = (sign & ~x) | (~sign & x); left16 = (!!(x>>16))<<4; x>>=left16; left8 = (!!(x>>8))<<3; x>>=left8; left4 = (!!(x>>4))<<2; x>>=left4; left2 = (!!(x>>2))<<1; x>>=left2; left1 = !!(x>>1); x>>=left1; left0 = x; return left16 + left8 + left4 + left2 + left1 + left0 + 1; } ``` ## 11. floutScale2 这题用整数模拟浮点数结构，要求把浮点数\*2. 首先题目要求判断是否是NaN，如果是的话就直接return。 32位单精度浮点数由1位符号位s，8位阶码（指数），23位尾数按顺序组成。 对于NaN和无穷，就是exp全是1的情况，按题目要求直接return uf。 下面要考虑两种编码形式。 规格化编码，即exp!=0时，用于编码>1的数。这时候flac的值=1+M（实际表示的尾数），所以不能直接乘2，而应该给阶码exp+1（相当于给指数+1）。 非规格化编码，即exp==0，用于编码<1的数。这时候flac的值就是M，因为编码的是<1的数，所以不能随便加exp。直接对M\*2. ```c unsigned floatScale2(unsigned uf) { unsigned s,exp,frac; s = (uf>>31)&1; exp = (uf&0x7f800000)>>23; frac = uf&0x7fffff; unsigned ans; if(exp == 0xff) return uf; if(exp == 0) ans = (s<<31) | (exp<<23) | frac<<1; else ans = (s<<31) | ((exp+1)<<23) | frac; return ans; } ``` ## 12. floatFloat2Int 题意是将给定浮点数表示转换成整数。 转换浮点数到整数的时候要注意到浮点数能表示的范围比int大得多，如果超出范围要按照题意返回0x80000000u。什么时候超出范围？E>=31的时候，int就32位，指数这么大换算到int里肯定超范围了。 剩下的都是规格化表示了。由于int是要舍掉小数精度的，由于尾数部分是23位，而E是阶数，如果E<23的话那尾数部分是不能全部位于小数点左边的，所以要右移(23-E)（不能在小数点左边的部分）舍掉。如果>=23的，就将阶数正常乘上去（左移）即可。 最后再处理下符号，return的时候改一下就行了。另外要注意在操作尾数之前要先把尾数隐含的头部的那个1给他补上。 ```c int floatFloat2Int(unsigned uf) { unsigned s,exp,frac; s = (uf>>31)&1; exp = (uf&0x7f800000)>>23; frac = uf&0x7fffff; int ans; int E = exp-127; if(E<0) return 0; if(E>=31) return 0x80000000u; ans = frac | 1<<23; if(E<23) ans>>=(23-E); else ans<<=(E-23); if(s) return -ans; else return ans; } ``` ## 13. floatPower2 题意：求$$2^x$$，要用浮点数表示。 这题难点主要在于判断各种范围。 首先浮点数的范围是$$2^{-149}\ 到\ 2^{127}$$，其中上界是由exp的最大值决定的，下界是由非规格数的最小值决定的。 参考图： ![](https://pic3.zhimg.com/80/v2-ae1fb4f12e764462dae73054af46950a_720w.jpg) 如果超出上界，返回无限（11110000..00），如果超出下界，返回0. 对于x<-126的情况，要拿非规格化数来表示；其他情况就拿规格化数来表示就好了。 构建规格化数，只需要改exp部分即可。非规格数就改flac部分。 ```c unsigned floatPower2(int x) { if(x<-149) return 0; if(x>127) return 0xff<<23; if(x<-126) return 1<<(x+149); return (x+127)<<23; } ``` 13个小任务做完，顺利拿到满分。 ![](https://s1.328888.xyz/2022/08/25/wnQXg.png) ### 补充 输入一个浮点数（以字符串形式输入），输出其用IEEE754格式的二进制表示，按int输出（不考虑非规格数）： ```c int my_int_float(){ char s[50]; int sign; scanf("%s",s); sign = (s[0]=='-'); //求符号位 int len = strlen(s); if(!sign){ // 统一正负形式 for(int i = len;i>0;i--){ s[i] = s[i-1]; } } int dot; //找小数点 for(int i = 1;i<=len;i++) if(s[i]=='.') dot = i; int upper_num = 0; int index = 0, tmp = 1; for(int i = dot-1;i>=1;i--){ //处理小数点左边 int num = s[i] - '0'; upper_num += num * tmp; tmp*=10; index++; } int lower_num = 0; int lower_len = len - dot; //处理小数点右边 index = 0; tmp = 1; int lower_tot = 0; for(int i = len;i>dot;i--){ int num = s[i] - '0'; lower_tot += num * tmp; tmp*=10; index++; } int target = 1; for(int i = 1;i<=lower_len;i++) target*=10; lower_num = target/lower_tot; tmp = 1; index = 0; while(tmp<=upper_num){ //拼接两边，求阶码 index++; tmp*=2; } int exp = index -1 + 127; lower_num >>=1; //根据小数点右边位的性质，舍掉一位 tmp = 1; index = 0; int right_len; //求小数点右边二进制表示的长度 while(tmp<=lower_num){ index++; tmp*=2; } right_len = index; int right_num = 0; for(int i = 1;i<=right_len;i++){ //求小数点右边的二进制表示（小数格式） right_num |= (((lower_num&(1<<(right_len-i)))>0)<<(i-1)); } int M_pre = upper_num; //求尾数（不考虑尾0） M_pre <<= right_len; M_pre |= right_num; tmp = 1; index = 0; int M; while(tmp<=M_pre){ //为尾数补0，减去默认的1 index++; tmp*=2; } M = (M_pre<<(23-index)) - (1<<22); M<<=1; int ans = 0; ans |= (sign<<31); //拼装符号位 ans |= M; //拼接尾数 ans |= (exp<<23); //拼接阶码 return ans; } ``` # CSAPP Lab2 Bomblab *** Bomblab是第三章 程序的机器级表示 的实验，主要涉及汇编语法和gdb调试。 这个lab要求反编译一个程序，得到六个密码。 ## Phase 1 使用`objdump`命令来反编译bomb： `objdump -d bomb > bomb.s` 在out.s里就可以看到整个程序反编译出的汇编代码了。 找到main函数的部分，然后找到有关调用phase\_1部分的代码，其之前的那一部分就是读入。 ``` 400e32: e8 67 06 00 00 call 40149e 400e37: 48 89 c7 mov %rax,%rdi 400e3a: e8 a1 00 00 00 call 400ee0 ``` 可以看到这里把`%rax`的内容移到`%rdi`储存，然后就调用了phase\_1 。于是可以推测输入的内容在`%rdi`里面。 再看phase\_1部分的代码。 ``` 0000000000400ee0 : 400ee0: 48 83 ec 08 sub $0x8,%rsp 400ee4: be 00 24 40 00 mov $0x402400,%esi 400ee9: e8 4a 04 00 00 call 401338 400eee: 85 c0 test %eax,%eax 400ef0: 74 05 je 400ef7 400ef2: e8 43 05 00 00 call 40143a 400ef7: 48 83 c4 08 add $0x8,%rsp 400efb: c3 ret ``` 很明显这个程序在比较输入的字符串是否相等，调用的部分是这个`strings_not_equal`。那么在调用之前，这个程序将地址`$0x402400` 移到了`%esi`，很明显就是给比较字符串的函数用的。于是可以推测地址 `$0x402400`就存了那个我们需要的固定密码。 现在用gdb调试来获取运行时那个地址储存的密码。 使用命令`gdb bomb`开始调试，然后在phase\_1处设置断点：`break phase_1` 接下来使用`r`命令来运行它，然后随便输一段密码使程序到达断点位置。 到达我们需要的位置后，输入`disas`来查看当前阶段的汇编代码，是phase\_1无误。 下面就是查看那个地址了。使用`x`命令即可：`x $0x402400` 获得密码：`Border relations with Canada have never been better.` ## Phase 2 还是一样，在phase\_2处设置断点，然后查看phase\_2处的汇编代码。 这里调用了一个函数`read_six_numbers`，查看它的代码，发现它的主要功能是利用`sscanf`函数读入6个整数。为什么知道是6个呢？因为`sscanf`的参数除了要读入的参数外还有两个，而`read_six_numbers`中将两个参数储存到内存中来传递。我们知道只利用寄存器我们可以给函数传递6个参数，剩下两个通过内存的就是额外的参数，于是我们知道总共传递了8个参数，其中6个是输入的数。 ``` 401480: be c3 25 40 00 mov $0x4025c3,%esi 401485: b8 00 00 00 00 mov $0x0,%eax ``` `sscanf`读入的整数会存在栈里，所以下面留意有关`%rsp`的操作。 再阅读phase\_2的代码： ``` Dump of assembler code for function phase_2: => 0x0000000000400efc <+0>: push %rbp 0x0000000000400efd <+1>: push %rbx 0x0000000000400efe <+2>: sub $0x28,%rsp 0x0000000000400f02 <+6>: mov %rsp,%rsi 0x0000000000400f05 <+9>: call 0x40145c 0x0000000000400f0a <+14>: cmpl $0x1,(%rsp) 0x0000000000400f0e <+18>: je 0x400f30 0x0000000000400f10 <+20>: call 0x40143a 0x0000000000400f15 <+25>: jmp 0x400f30 0x0000000000400f17 <+27>: mov -0x4(%rbx),%eax 0x0000000000400f1a <+30>: add %eax,%eax 0x0000000000400f1c <+32>: cmp %eax,(%rbx) 0x0000000000400f1e <+34>: je 0x400f25 0x0000000000400f20 <+36>: call 0x40143a 0x0000000000400f25 <+41>: add $0x4,%rbx 0x0000000000400f29 <+45>: cmp %rbp,%rbx 0x0000000000400f2c <+48>: jne 0x400f17 0x0000000000400f2e <+50>: jmp 0x400f3c 0x0000000000400f30 <+52>: lea 0x4(%rsp),%rbx 0x0000000000400f35 <+57>: lea 0x18(%rsp),%rbp 0x0000000000400f3a <+62>: jmp 0x400f17 0x0000000000400f3c <+64>: add $0x28,%rsp ``` 其实仔细看就会发现这是一个循环，循环部分是+25到+62。 还原一下，首先将栈顶（sscanf返回的值）与1比较，必须是1才能继续，说明第一个密码是1. 接下来eax来保存第一个数，然后\*2，与第二个数比较，然后给rbx+0x4，使得下一次比较的是第三个数。以此类推，就是要求是公比为2的等比数列，即1,2,4,8,16,32 密码：`1 2 4 8 16 32` ## Phase 3 一样的，反编译代码观察。 ``` => 0x0000000000400f43 <+0>: sub $0x18,%rsp 0x0000000000400f47 <+4>: lea 0xc(%rsp),%rcx 0x0000000000400f4c <+9>: lea 0x8(%rsp),%rdx 0x0000000000400f51 <+14>: mov $0x4025cf,%esi 0x0000000000400f56 <+19>: mov $0x0,%eax 0x0000000000400f5b <+24>: call 0x400bf0 <__isoc99_sscanf@plt> 0x0000000000400f60 <+29>: cmp $0x1,%eax 0x0000000000400f63 <+32>: jg 0x400f6a 0x0000000000400f65 <+34>: call 0x40143a 0x0000000000400f6a <+39>: cmpl $0x7,0x8(%rsp) 0x0000000000400f6f <+44>: ja 0x400fad 0x0000000000400f71 <+46>: mov 0x8(%rsp),%eax 0x0000000000400f75 <+50>: jmp *0x402470(,%rax,8) 0x0000000000400f7c <+57>: mov $0xcf,%eax 0x0000000000400f81 <+62>: jmp 0x400fbe 0x0000000000400f83 <+64>: mov $0x2c3,%eax 0x0000000000400f88 <+69>: jmp 0x400fbe 0x0000000000400f8a <+71>: mov $0x100,%eax 0x0000000000400f8f <+76>: jmp 0x400fbe 0x0000000000400f91 <+78>: mov $0x185,%eax 0x0000000000400f96 <+83>: jmp 0x400fbe 0x0000000000400f98 <+85>: mov $0xce,%eax 0x0000000000400f9d <+90>: jmp 0x400fbe 0x0000000000400f9f <+92>: mov $0x2aa,%eax 0x0000000000400fa4 <+97>: jmp 0x400fbe 0x0000000000400fa6 <+99>: mov $0x147,%eax 0x0000000000400fab <+104>: jmp 0x400fbe 0x0000000000400fad <+106>: call 0x40143a 0x0000000000400fb2 <+111>: mov $0x0,%eax 0x0000000000400fb7 <+116>: jmp 0x400fbe 0x0000000000400fb9 <+118>: mov $0x137,%eax 0x0000000000400fbe <+123>: cmp 0xc(%rsp),%eax 0x0000000000400fc2 <+127>: je 0x400fc9 0x0000000000400fc4 <+129>: call 0x40143a 0x0000000000400fc9 <+134>: add $0x18,%rsp 0x0000000000400fcd <+138>: ret ``` 这里还是用到了`sscanf`，注意到一个特殊点，第二个参数`mov $0x4025cf,%esi`，其实就是scanf那个格式化串，如"%d"这种。所以可以用命令`x 0x4025cf` 把它打出来看看： `0x4025cf: "%d %d"` 所以我们知道密码是两个整数。下面跟着流程继续走。 观察发现，`sscanf`的第三、四个参数分别是`0x8(%rsp)`（即%rsp+8）和`0xc(%rxp)`（即%rxp+c)。重点留意这两个地址。 由+39得，第一个参数得<=7. 注意到代码里有一部分很奇怪： `0x0000000000400f75 <+50>: jmp *0x402470(,%rax,8)` 它的意思是，跳转到(0x402470 + 8 \* %rax)的位置，而我们的%rax此时就是第一个输入，<=7。所以可以推测这是一个以0x402470为起始，8字节一个元素，有8个元素的数组。 用指令`x/8a 0x402470` 打印一下这个数组： ``` 0x402470: 0x400f7c 0x400fb9 0x402480: 0x400f83 0x400f8a 0x402490: 0x400f91 0x400f98 0x4024a0: 0x400f9f 0x400fa6 ``` 可以发现，这是一个根据第一个输入不同而决定跳转位置不同的跳转表。因此可以猜测原来的程序是一个switch结构。 继续观察结构，发现不同的跳表位置就是给%eax这个参数赋不同值。最后的判定就是%eax最后的值和第二个参数相同。所以我们可以假设第一个参数取0，于是下一步就跳到phase\_3+57，赋的值是0xcf（207）。所以我们就可以取密码为`0 207`。 ## Phase 4 复习一下寄存器相关的内容。对于32位的寄存器，%eax：储存函数返回值；%edi：第一个参数；%esi：第二个参数；%edx：第三个参数。 还是和前面一样分析sscanf，发现依然是读入两个整数。但是后面发现他将2和%eax的值进行了比较，%eax就是上面说的返回值的寄存器，也就是说这是scanf的返回值。scanf的返回值就是成功匹配的个数，也就是读入的数的个数。于是看到下面的部分就能明白，这是要求只能读入两个整数，否则爆炸： ``` 0x0000000000401029 <+29>: cmp $0x2,%eax 0x000000000040102c <+32>: jne 0x401035 ``` 接下来程序又进行了一个判断： ``` 0x000000000040102e <+34>: cmpl $0xe,0x8(%rsp) 0x0000000000401033 <+39>: jbe 0x40103a 0x0000000000401035 <+41>: call 0x40143a ``` 将第一个参数与0xe比较，参数必须<=0xe（14）才行，否则会爆炸。 下面有三组mov操作，可以看出这是在传参，给后面的`func4`调用做准备。 ``` 0x000000000040103a <+46>: mov $0xe,%edx 0x000000000040103f <+51>: mov $0x0,%esi 0x0000000000401044 <+56>: mov 0x8(%rsp),%edi ``` 传参分别是，第一个参数、0、14. 接下来跟着看下`func4`的代码。 出现了一个第一次见的指令，`shr $0x1f,%ecx` ，意思是逻辑右移。后面还有sar，意思是算数右移。 继续阅读，发现代码后面出现了这句：`callq 400fce ` 明显是在自己调用自己，也就是递归。 既然这是个递归的函数，最好把他写成C代码，这样方便知道他在干什么。 ```c int func4(int nums, int x, int y){ int ret = y - x; int k = (unsigned)(ret) >> 31; ret = (k + ret) >> 1; k = ret + x; if (k > nums) return 2 * func4(nums, x, k - 1); ret = 0; if (k < nums) return 2 * func4(nums, k + 1, y) + 1; return ret; } ``` 接下来看func4返回后程序干了什么。 ``` 0x000000000040104d <+65>: test %eax,%eax 0x000000000040104f <+67>: jne 0x401058 ``` 这是test指令的一个典型用法，用于判断返回值%eax 是否==0. 也就是说func4的返回值必须为0. 那么回过头去看func4，代入x=0，y=14尝试一下，可以写个暴力程序验证，发现0就可以使得func4不死循环且最终返回0. 后面还发现， ``` 0x0000000000401051 <+69>: cmpl $0x0,0xc(%rsp) 0x0000000000401056 <+74>: je 0x40105d ``` 所以密码的第二个数必须为0. 于是得到密码：`0 0` ## Phase 5 一样，看Phase5的代码。注意在main函数这里用了readline放在%rdi里传递给phase\_5，所以这次我们应该输入一个字符串。 注意到这里用了一个函数来获得字符串的长度，然后和6比较，因此得知我们必须输入6个字符。 ``` 0x000000000040107a <+24>: call 0x40131b 0x000000000040107f <+29>: cmp $0x6,%eax 0x0000000000401082 <+32>: je 0x4010d2 0x0000000000401084 <+34>: call 0x40143a ``` 接下来往下读，发现一个比较明显的回溯jump，并且还带计数和比较，所以可以发现这是一个for循环： ``` 0x000000000040108b <+41>: movzbl (%rbx,%rax,1),%ecx 0x000000000040108f <+45>: mov %cl,(%rsp) 0x0000000000401092 <+48>: mov (%rsp),%rdx 0x0000000000401096 <+52>: and $0xf,%edx 0x0000000000401099 <+55>: movzbl 0x4024b0(%rdx),%edx 0x00000000004010a0 <+62>: mov %dl,0x10(%rsp,%rax,1) 0x00000000004010a4 <+66>: add $0x1,%rax 0x00000000004010a8 <+70>: cmp $0x6,%rax 0x00000000004010ac <+74>: jne 0x40108b ``` 可以看出循环总共会进行6次。 循环里有一个神秘地址，用`x/s 0x4024b0`打出来看看： `0x4024b0 : "maduiersnfotvbylSo you think you can stop the bomb with ctrl-c, do you?"` 再回看上面的代码，就算不能完全理解意思，也可以大概猜到，我们输入的6个数是一个索引，程序在根据输入的索引在上面这个字符串里找出6个字符。 继续往下读，找到另外一个神秘地址，`x/s 0x40245e`打出来看看： `0x40245e: "flyers"` 所以尽管我们没有怎么研究其他的代码，我们已经知道这个程序是要我们从上面的长字符串中索引出六个字符“flyers"。那么这个索引可以是`9 15 14 5 6 7` 事实上，上面那些操作是取我们输入的字符的ascii码的右边四个bit，我们只用找最右边的四个bit对应上面6个数的6个字符就行了。 查表，任意找一组符合上面条件的字符。这里取：`)/.%&'` ## Phase 6 Phase\_6的代码反编译出来非常的长，足足被分了四页，说明开始有点复杂了。我们得一点点来看。 在看的时候，首先先观察各种jmp语句，把可能的程序结构给推测出来。 首先发现 `0x0000000000401151 <+93>: jmp 0x401114 ` 回跳很明显是一个循环，看看循环前面干了些什么。 首先是又调用了`read_six_numbers`，看来这次输入又是6个数，每次循环处理一个数。 在理解循环的时候，更多要忽略循环本身的那些操作，更加关注那些显得比较突兀的实际操作，比如下面： ``` 0x000000000040111b <+39>: sub $0x1,%eax 0x000000000040111e <+42>: cmp $0x5,%eax 0x0000000000401121 <+45>: jbe 0x401128 0x0000000000401123 <+47>: call 0x40143a ``` 翻译一下就是每个输入必须<=6，否则会爆炸。 在循环中往下读，竟然发现又一个回跳：`0x000000000040114b <+87>: jle 0x401135 ` 怎么理解呢？循环嵌套。 那么这个内层循环干了什么？ ``` 0x000000000040113b <+71>: cmp %eax,0x0(%rbp) 0x000000000040113e <+74>: jne 0x401145 0x0000000000401140 <+76>: call 0x40143a ``` 其中%eax是上一个循环的操作数。嗯，这样理解就是一个遍历，如果我们输入的数有任何一个出现相等就会炸。意思就是输入的六个数要互不相同。 读完这个大循环，我们知道输入必须<=6，且互不相同。 继续阅读，下面又发现一个新循环： ``` 0x0000000000401153 <+95>: lea 0x18(%rsp),%rsi 0x0000000000401158 <+100>: mov %r14,%rax 0x000000000040115b <+103>: mov $0x7,%ecx 0x0000000000401160 <+108>: mov %ecx,%edx 0x0000000000401162 <+110>: sub (%rax),%edx 0x0000000000401164 <+112>: mov %edx,(%rax) 0x0000000000401166 <+114>: add $0x4,%rax 0x000000000040116a <+118>: cmp %rsi,%rax 0x000000000040116d <+121>: jne 0x401160 ``` 这个循环很好理解，使得每个输入都等于7-它自己。 继续往下看，下面的代码是最难理解的一段。注意到其中有两行可疑的片段： ``` 0x0000000000401183 <+143>: mov $0x6032d0,%edx 0x00000000004011d2 <+222>: movq $0x0,0x8(%rdx) ``` 可以看到这里给%edx赋了一个神秘地址，然后后面又有大量对%edx相关的%rdx进行的8字节的偏移。于是合理猜测，那是个以8字节为单位的数组。我们试着8个字节的看一下这个地址的信息： `x/8 0x6032d0`，但是数据没有任何值得总结的，怀疑是因为数据没有输入和处理就被断点卡住了。取消该处断点，在炸弹爆炸处加一个断点，重新调试，这里密码尝试1 2 3 4 5 6。 结果： ``` 0x6032d0 : 0x0000014c 0x00000001 0x00000000 0x00000000 0x6032e0 : 0x000000a8 0x00000002 0x006032d0 0x00000000 ``` 可以看到第二行就是1 2，我输入的数字。再看名字，node1、node2，可以得出这是由结构体产生的数据。 理论上应该有6个数字，于是再扩大范围看看那些结构体： ``` (gdb) x/24 0x6032d0 0x6032d0 : 0x0000014c 0x00000001 0x00000000 0x00000000 0x6032e0 : 0x000000a8 0x00000002 0x006032d0 0x00000000 0x6032f0 : 0x0000039c 0x00000003 0x006032e0 0x00000000 0x603300 : 0x000002b3 0x00000004 0x006032f0 0x00000000 0x603310 : 0x000001dd 0x00000005 0x00603300 0x00000000 0x603320 : 0x000001bb 0x00000006 0x00603310 0x00000000 ``` 还是有点不明白这结构体有什么用，换个输入`6 5 4 3 2 1`试试看： ``` 0x6032d0 : 0x0000014c 0x00000001 0x006032e0 0x00000000 0x6032e0 : 0x000000a8 0x00000002 0x006032f0 0x00000000 0x6032f0 : 0x0000039c 0x00000003 0x00603300 0x00000000 0x603300 : 0x000002b3 0x00000004 0x00603310 0x00000000 0x603310 : 0x000001dd 0x00000005 0x00603320 0x00000000 0x603320 : 0x000001bb 0x00000006 0x00000000 0x00000000 ``` 似乎有变化！数据排序依然是从node1到6，但第三个数据变了。根据数据的顺序相反，两个结构体的属性的头和尾也会相反。。可以想到，这完全就是一个链表，第三个数据就是节点的next指针！ 好了，现在我们知道我们输入的六个数会被存在类似链表的结构中。下面理解（猜测）代码就会容易一些了。 继续往下阅读代码，找到又一个循环： ``` 4011df: 48 8b 43 08 mov 0x8(%rbx),%rax 4011e3: 8b 00 mov (%rax),%eax 4011e5: 39 03 cmp %eax,(%rbx) 4011e7: 7d 05 jge 4011ee 4011e9: e8 4c 02 00 00 call 40143a 4011ee: 48 8b 5b 08 mov 0x8(%rbx),%rbx 4011f2: 83 ed 01 sub $0x1,%ebp 4011f5: 75 e8 jne 4011df ``` 前面了解过，0x8(%rbx)的地址偏移刚好可以取到下一个数的对应地址。这时候比的就是两个node的第一个数据，假设为value。如果node1.value\ 0102030405 06070809 101112 1314 15 然后某人一站起身就一头撞在了楼梯上...他十分气愤，于是给了你一个整数n（n<8），请你输出这个n层\*n层的倒三角形的数字楼梯，每个数占两位。 ## 输入 1个整数(<8) ## 输出 1个倒三角数字楼梯 ## 输入输出样例 **输入** ``` 5 ``` **输出** ``` 0102030405 06070809 101112 1314 15 ``` *** ## 回答要求 * 附上你完成本程序的完整代码 * 详细解释for循环的组成及循环过程中执行的顺序 # C++每日一题 Day 6 插火把 *** lhy版权所有，禁止转载 ### 知识点：二维数组 *** ## 题目描述 有一天悠悠在“我的世界”开了一个n\*n的方阵，现在她有 m\*m 个火把和 k\*k 个萤石放在方阵里，没有光且没放东西的地方会生成怪物。请问在这个方阵中有几个点会生成怪物？ 火把的照亮范围是： ``` |暗| 光 |暗| |光|火把|光| |暗| 光 |暗| ``` 萤石： ``` |光| 光 |光| |光| 萤石 |光| |光| 光 |光| ``` ## 输入 输入共m+k+1行，第一行为n,m,k。 第2到第m+1行分别是火把的位置xi、yi。 第m+2到第m+k+1行分别是萤石的位置oi、pi。 注：可能没有萤石，但一定有火把。 所有数据范围都在int范围内。 ## 输出 会生成怪物的点的数量。 ## 输入输出样例 **输入** ``` 5 1 1 1 2 3 4 ``` **输出** ``` 7 ``` *** ## 回答要求 * 附上你完成本程序的完整代码 * 你有没有什么方法可以简化本题的代码？提示：数学方法 # C++每日一题 Day 7 贪吃蛇 *** lhy版权所有，禁止转载 ### 知识点：二维数组、循环 *** ## 题目描述 有一天某人无聊，用班上的西沃电脑做了一个很无聊的贪吃蛇游戏。贪吃蛇游戏的地图由 n\*n 个格子组成。阿肝看到了这个游戏，打算控制小蛇从左上角的点开始，沿上边往右前进到不能前进为止，然后转向下走，前进到不能前进为止，再向左走，前进到不能前进为止，再向上走... 总之，因为某人和阿肝都很无聊，所以他们决定用这种方式让小蛇爬过这个地图的每一个格子。 下面给出n，请输出各个格子被小蛇爬过的次序。 ## 输入 一个整数n（<10） ## 输出 n\*n 的整数方阵，表示各点被爬过的次序 ## 输入输出样例 ### 输入 ``` 4 ``` 输出 ``` 1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7 ``` # C++每日一题 Day 8 蒙德最强战力 *** lhy版权所有，禁止转载 ### 知识点：冒泡排序/选择排序 *** ## 题目描述 众所周知，每个蒙德居民对每个守护蒙德的人的战斗力都有自己的标尺。对派蒙而言，她的战斗力单位是野猪，而她的战力值是1/5野猪。派蒙希望得到一张蒙德战力排名，想看看荧能排到第几。于是荧和派蒙找到了琴团长，琴团长却说蒙德没有这样的排名。荧和派蒙只好偷偷窥视每一个可能上榜的人，记录下ta的战斗力。 下面给出她们记录下的战力表，请你进行排序并输出排序好的蒙德战力排行（从强到弱，战力单位：野猪） ## 输入 第一行为一个整数n，表示荧和派蒙记录的人的总数 第二行为n个字符串，用空格间隔，表示他们的名字 第三行为n个整数，用空格间隔，表示他们的战力（单位：野猪） ## 输出 第一行为n个字符串，第二行为n个整数，为排序好的战力表（名字与战力要对应） ## 输入输出样例 输入 ```java 5 迪卢克 荧 芭芭拉 可莉 琴 20 100 80 1000 120 ``` 输出 ```java 可莉 琴 荧 芭芭拉 迪卢克 1000 120 100 80 20 ``` *** ## 回答要求 * 从冒泡排序/选择排序中选择一种方法完成本题。 # C++每日一题 Day 9 璃月七星选举 *** lhy版权所有，禁止转载 ### 知识点：快速排序 *** ## 题目描述 众所周知，璃月是一个人民民主专政的资本主义国家。因为天叔当众叫甘雨姐姐导致其被暗杀，所以现在璃月正在全民投票选举出一位新的璃月七星。 现在给出所有的提名人和其获得的票数。但是由于璃月想获取政治权利的资本家太多了，凝光希望能在`nlogn`的复杂度之内结束计算，取得一份提名人及其票数的排行榜。听说你这个旅行者数学知识渊博，请你设计一个算法，比冒泡排序等简单排序更快地完成七星继承人的计算吧。 ## 输入 第一行为一个整数n，表示参选的人的总数 第二行为n个字符串，用空格间隔，表示他们的名字 第三行为n个整数，用空格间隔，表示他们的选票数（由于璃月人都跑去轻策庄养老了，所以选票不多于2000张） ## 输出 第一行为n个字符串，第二行为n个整数，为排序好的选票排行榜（名字与选票要对应） ## 输入输出样例 输入 ```java 4 香菱 胡桃 达达利亚 荧 200 100 0 1000 ``` 输出 ```java 荧 香菱 胡桃 达达利亚 1000 200 100 0 ``` *** ## 回答要求 * 使用快速排序算法解决问题。 * 其实C++自带的stl中有一个写好的sort()快排轮子可以秒杀本题（傻了吧），可以试试看使用这个sort()函数。 # C每日一题 Day 2 肥宅水 *** lhy版权所有，禁止转载 ### 知识点：变量，浮点型变量，变量运算 *** ## 题目描述 现在有 t 毫升肥宅快乐水，要均分给 n 名同学。每名同学需要 2 个杯子。现在想知道每名同学可以获得多少毫升饮料，以及一共需要多少个杯子。输入一个实数 t 和一个整数 n，使用空格隔开。输出两个数字表示答案，使用换行隔开。 ## 输入 100000≤*t*≤10000且不超过3位小数，10001≤*n*≤1000 ## 输入输出样例 **输入** ``` 500.0 3 ``` **输出** ``` 166.667 6 ``` *** ## 回答要求 * 附上你完成本程序的完整代码 * 为什么你的代码中声明变量时要使用float或double而不是int？简单讲讲你的理解 * 拓展：c语言中有什么办法可以限定输出的数字为n位小数？修改程序以使答案保留五位小数。 # C每日一题 Day 3 理五的凡尔赛风气 *** lhy版权所有，禁止转载 ### 知识点：逻辑运算符，布尔类，选择结构 *** ## 题目描述 数学成绩刚出但还没发布，4个理五班的同学都说自己考的差。于是他们决定按他们宣称的成绩从低到高站好，等老胡宣读他们的真实成绩。现在输入这4个同学的成绩（4个空格隔开的整数），如果他们的成绩依次递增，则输出“nb”，否则输出“烟雾弹！凡尔赛！” ## 输入 四个整数 ## 输出 题目要求的字符串 ## 输入输出样例 **输入** ``` 150 129 139 145 ``` **输出** ``` 烟雾弹！凡尔赛！ ``` *** ## 回答要求 * 附上你完成本程序的完整代码 * 说说if的作用。 * 你的代码是否非常复杂？如果是，请学习“逻辑运算符”。 * 讲讲各种逻辑运算符的作用。 * 对C++的拓展：c++中引入了新的一种类型字符串（string），尝试用String储存数据重新完成本题。（可能需要一些数组的知识，可以不做） c++中提供了一种新的基本数据类型，叫布尔类（或者逻辑类）。尝试在本题定义一个布尔变量，然后用它储存理五的同学是否凡尔赛。 # C语言每日一题 Day 1 荧妹好感队 *** > lhy版权所有 禁止转载 > > 知识点：程序结构 变量 *** ## 题目描述 假设我的荧妹好感队中角色的技能倍率都是100%，输入荧妹、香菱、神子、琴团长的面板攻击力，求这个队伍每人打一下能造成的总伤害。 ## 输出 四个整数，分别表示荧妹、香菱、神子、琴团长的攻击力。 ## 输出 一个整数，即这四个人的攻击力之和。 ## 输出输出样例 ### 输入 ``` 1600 1300 1700 1300 ``` ### 输出 ``` 5900 ``` *** ## 回答要求 * 附上你完成本题的完整代码 * 哪部分是对库的引用？哪部分是主函数？ * 什么是C语言中的函数？ * 什么是变量？ * C语言中，用什么函数进行输入/输出？ ```c #include 声明对库的引用，这里引用输入输出的库stdio.h int main(){ 声明主函数，包括int（返回值类型） main（函数名）和()（括号内是参数列表，这里没有参数） 程序的具体内容在函数内部实现 int a,b,c,d,e; 声明5个int（整数）类型的变量 scanf("%d %d %d %d",&a,&b,&c,&d); e = a+b+c+d; printf("%d",e); return 0; 返回0表示程序正常结束 } ```