已凭暂雨添秋色

分类

/ 注册

全部文章（共4篇）

题解 | #【模板】链表#

刚学，就当写小记捋一下思路。链表的创建：以结构体的形式通过保存下一个目标的地址指针来访问，由此不断推进。struct list{ int data; list *next;//...

2022-10-31

0 257

题解 | #【模板】差分#

对于修改区间，如果进行遍历修改的话时间会非常大。我个人愚以为差分的思想是只看区间左右的变化，我们只要关注到进入区间前的变化和离开区间后的变化即可。for(int i=1;i<=m;++i){ ...

2022-10-31

0 294

题解 | #矩阵的最小路径和#

只能向下或者向右走，就是所在点只能由左边或者前边的点走过来，对于当前的点就有 dp[i][j]=a[i][j]+min(dp[i-1][j],dp[i][j-1])考虑到i=1，j=1的情况，直接对dp[1][1]赋值并且循环时跳过他，同时考虑到在i=1或者j=1时可能会越界，对二维dp数组先进行描...

2022-10-31

0 237

题解 | #最大子矩阵#

暴力：o（n^4），遍历每一个点及其对应的1到i,1到j的所有点。前缀和优化：o（n^3），同理先算出前缀和，考虑如何利用前缀和来减少一个变量的遍历。可知前缀和[l,r]=sum[r]-[l-1],此时已经确定了上下俩个点的之间的一维区间，那只需要将其往没有累积的方向逐个扩展即可。for(int&n...

2022-10-31

0 299