Sprooc

本周主要学习内容：树状数组、线段树、ST表、石子合并问题。 树状数组前半周主要学了树状数组，可以很熟练地把模版敲出来了。相关题目可以看leetcode315)，以及当时写的小结：[leetcode]315. 计算右侧小于当前元素的个数 | Sprooc。 线段树接下来系统梳理了线段树，掌握了懒惰标记和动态开点的方法，参考文章：线段树 从入门到进阶（超清晰，简单易懂）_线段树怎么写-CSDN博客699. 掉落的方块 - 力扣（LeetCode） Sparse Table模版题目：P3865 【模板】ST 表 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) CSP真题周六限时做了202203的CSP真题。前三题满分还是挺轻松的。第四题写了一个小时，暴力求“通信对”超时拿了50分。后来想改成实时维护“通信对”数量，但总该不对，大概有些细节问题，没有细究了。第五题一脸懵，直接放弃了。三个小时拿了350分。 石子合并问题做csp202203-5时了解到石子合并问题，找了些资料学了一学。参考资料： 石子合并问题（直线版） - jiu~ - 博客园 (cnblogs.com)算法 ...

石子合并问题：有N堆石子，现要将石子有序的合并成一堆，规定如下：每次只能移动相邻的2堆石子合并，合并花费为新合成的一堆石子的数量。求将这N堆石子合并成一堆的总花费最小（或最大）。 这是一道典型的动态规划题目。令dp[i][j]为将第i到j堆石子合并成一堆的最小代价w[i][j]为第i到j堆石子的总数。就可以写出状态转移方程： dp[i][j] = min_{k=i}^{j-1}(dp[i][k] + dp[k+1][j]) + w[i][j]直接暴力求解就可以，复杂度O(n3)。 改进方法是用平行四边形不等式优化，缩小k的范围，复杂度O(n2) :算法学习笔记(79): 四边形不等式优化DP - 知乎 (zhihu.com) 问题的变种是让石子环形排列，即第一堆和最后一堆看成是相邻的。解决方法是在n堆石子后面再加上与前面一样的n堆石子，这样最后一堆和第一堆就相邻了。把总堆数看成2n，用上面的方法解出来就可以了。最后还需要遍历一下dp数组，求出2n堆石子里面结果最小的n堆石子作为最终结果。 P1880 [NOI1995] 石子合并 - 洛谷 | 计算机科学教育新生态 (luogu.co ...

Sparse Table简称ST，用于对一组静态数据进行区间查询。 例如： RMQ：区间最大（最小）值 RGQ：区间最大公因数 这两个问题都可以用线段树解决。但线段树的查询时间是O(logn)，ST可以在O(1)时间内完成查询。代价是是ST不能对数组进行动态维护，数组在查询之前就固定下来。因此，如果需要动态维护数组，用线段树；反之，用ST。 什么样的问题可以用ST解决？例如说，求区间最小值，我们可以先把一个区间分成两个小区间，两个小区间的的最小值就是大区间的最小值。最大公因数也同理，求一个大区间的最大公因数，先求两个小区间的最大公因数，再求这两个数的最大公因数就是大区间的最大公因数。类似这类问题都能用ST解决。形式化的，ST能解决的问题为： 求数组的某一区间S的某一性质F(S)，性质F满足： 若{s_1}\cup {s_2}=S，则F(S)=F(F(s_1),F(s_2)).可以验证，min和gcd都满足以上要求。 详细内容参照这篇文章算法笔记-CSDN博客](https://blog.csdn.net/narcissus2_/article/details/89423591 ...

力扣315，没有花里胡哨的题面，属于树状数组的模版题了。正好复习一下BIT。先看题目： [计算右侧小于当前元素的个数] Category Difficulty Likes Dislikes algorithms Hard (43.45%) 1032 - 给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。 示例 1： 1234567输入：nums = [5,2,6,1]输出：[2,1,1,0] 解释：5 的右侧有 2 个更小的元素 (2 和 1)2 的右侧仅有 1 个更小的元素 (1)6 的右侧有 1 个更小的元素 (1)1 的右侧有 0 个更小的元素 示例 2： 12输入：nums = [-1]输出：[0] 示例 3： 12输入：nums = [-1,-1]输出：[0,0] 看完题目，很自然想到用树状数组来做。关于树状数组，可以参考这篇文章：算法学习笔记(2) : 树状数组 - 知乎 (zhihu.com) 思路大概是： 通过排序 ...

近日思绪繁多，终得明朗，记于此。 近日常思考今后的学习方向，是研究技术搞开发，还是研究算法搞理论。不是算法学不起，学习技术更有性价比。学习算法成本高风险大。但若学有所成，不论是对学业还是未来工作都大有所益。故算法这条道虽难走，但亦值得一试。犹豫之时，忽忆起前日前辈经验分享会上一席话：“你们才大二，有的是试错的机会。如果犹豫走哪个方向，不如都试一试。“既然如此，即可放手一搏，研究算法之道。既定下决心，记于此处，以自勉。 今日起，日刷力扣五题，并力肝算法导论一书。每周末小记本周学习心得与收获，总结反思，亦可记录成长的足迹。 “行路难！行路难！多歧路，今安在？”。惟愿“长风破浪会有时，直挂云帆济沧海”！

记录一下pa的完成过程。前面的pa1和pa2没有记录，等以后有机会二刷再补上吧。 PA3-1PA3的第一阶段是实现异常响应机制。为实现异常响应，需要添加几个特殊寄存器，称为控制和状态寄存器（CSR）。PA中需要用到的包括： CSR 功能 mepc 存放触发异常的PC mcause 存放触发异常的原因 mstatus 存放处理器的状态 mtvec 存放异常入口地址 触发异常前，需要调用cte_init()函数进行初始化，将异常入口地址存到mtvec寄存器中，并注册一个事件处理回调函数，当触发异常时，将会以上下文信息和信息为参数调用此回调函数，执行异常处理操作。 RISCV32通过ecall指令触发自陷。具体来说，ecall指令执行的操作为： CSR[mepc] <- pc CSR[mcause] <- 异常号 PC <- CSR[mtvec] （执行异常响应程序） 完成异常响应程序后，恢复上下文信息，通过mret指令将PC从mepc中恢复（并+4），从中断处继续执行。 大致理解机制之后，再RTFM和RTFSC之后就可以敲代码了。 ...

诞生于2023/11/14。