Zhangmh's Blog

允许一切发生，但只解决问题

前缀和应用

上一篇简单复习了一下前缀和的基础知识，做几个题练练手~ 1273 WY的矩阵学校oj上的一个题，思考方式有些不同，很容易看出是用DP做，但这个题也用到前缀和来完成。我们易知在一维数组中求连续子序列和最大值操作为： 1234for(int i=1;i<=n;i++){ f[i]=max(a[i],f[i-1]+a[i]);} 对于二维数组，我们采用的解决方法是：......

Posted by zhangmh on 2021-11-24

前缀和

前缀和基础

前缀和和差分之前就讲过了，有一段时间没用过了，之前学习的时候也是只做了几个板子题，现在有点遗忘了，再做几个题复习一下吧，，，

前缀和和差分之前就讲过了，有一段时间没用过了，之前学习的时候也是只做了几个板子题，现在有点遗忘了，再做几个题复习一下吧，，，以几个板子题 1657 前缀和Ⅰ 1658 前缀和Ⅱ 1659 前缀和Ⅲ 1660 前缀和Ⅳ 为例复习一下前缀和，应用写到下一篇里吧~差分要在后面了QAQ 前缀和：指序列中前n项的和，可以类比数学中数列的前n项和，只不过数学中数列的前n项和在这里是一维前缀和，我们要......

Posted by zhangmh on 2021-11-24

前缀和

BFS记录路径

BFS记录路径

前段时间学完BFS很开心地发现oj上有些题可以做了！但是记录路径又把我难住了，，，赶紧去学习一下，本篇算是复习BFS和它的记录路径方法吧。还是以题引例：1086 迷宫问题 1220 Look for homework 1654 Treasure House 以1654为例： 1654 Treasure House 选这个题是因为学这种方法的时候就是做的这个题啦 :P（才不是因为要把师......

Posted by zhangmh on 2021-11-22

BFS

C++ STL之map基本知识

STL基本是刚入队的时候讲的知识点，当时用的栈和队列比较多，map，vector，pair等用的较少，今天做题发现map一点也不会用了QAQ，赶紧复习一下，，，

STL基本是刚入队的时候讲的知识点，当时用的栈和队列比较多，map，vector，pair等用的较少，今天做题发现map一点也不会用了QAQ，赶紧复习一下，，，以题目为例：1058 人名查询 1185 统计数字 1321 众数 map：map是STL中的一个关联容器，它提供一对一（其中第一个（first）可以称为关键字key，每个关键字只能在map中出现一次，第二个（second）可......

Posted by zhangmh on 2021-11-22

C++ STL

双线程DP

前段时间师哥讲了DP，在练习过程中发现了还有双线程DP，现记录一晚上学习成果：是看到学校oj上的题 1032 机器人 1460 方格取数 1194 传纸条 1422 传纸条是看这篇学习的啦链接戳我以方格取数为例： Description 设有N*N的方格图(N< =10),我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。某人从图的左上角的A 点(1,1)出......

Posted by zhangmh on 2021-11-19

动态规划