p1098:应当充分使用库函数：isalpha(判断字符是否为字母),isdigit(判断字符是否为数字)。

p1065:答案中的now表示当前的零件，step[now]表示这个零件处在哪个步骤

p6363:cmath中round函数表示四舍五入,同时遇到四舍五入的题目应当在前面开double

p1786:sort排序是左闭右开，判断字符串是否相等时“”内多加一个空格都是错误的，应当记住！！！（害得我debug20分钟）.....

p1249:将一个数分解成不重复的多个数字，同时使得这些数字乘积最大，应当从贪心角度考虑：
任意一个大于4的自然数，其最大的乘积分解应该以2+3+…+n，这样乘起来才是最大的。
当这串数列大这个自然数1时，可以直接减去2，再在最大数+1，当大于1时，直接减去数列这个数
（反正我是想不到hh）

  p1045:sb题目给我恶心死了，用到了快速幂，同时注意j=0,j>=50才是一行50个数而不是j=1
  memcpy(a,b,sizeof a)代表将b复制到a中。cmath中自带log10

  p1059:去重可用algorithm中的unique函数，该函数返回重复元素之前的一个迭代器，还有int
  *i=&a[i](好久不用都忘了hh)

  p1116:本题其实就是考察逆序对的数量（但是这题由于数据范围很小所以暴力for循环就可以写出），最好的做法还是用归并（已经忘了特地去看了半个小时）

  p5143:cmath中有sqrt函数可以进行开平方根的效果，要想输出保留三位小数的dohle类型可以使用printf("%.3lf"，num),注意\n为换行而/n不是（差点搞错..)

  p1068:向下取整为floor，向上取整是ceil，而tolower和toupper是将字符转换大小写的（这两类搞混了都）

  p1012:采用贪心思想，一定是a+b>b+a(虽然不知道怎么想的)，考试中如果实在不会，可以用dfs来暴力搜索（拿点分）

  p2241:枚举所有矩形的右下角，正方形为min(i,j),长方形为i*j（不要问我怎么知道的...）记得开long long

  p2089:应该用dfs来解决

  p1618:用dfs将九个不同的数分成三个不同的部分，再调用另外的函数对这些组成的部分进行特判

  p1036:这题终于是我自己写出的第一道暴搜题hh，注意按照普通的dfs需要除以k!，因为dfs
  看成每个位置上还要选择但是题目不考虑每个位置的选择。

  p1157:本题思路与p1618三连击思路差不多，唯一不同的是这题若是用另外的函数特判（暴力fo
  r循环来判断）会导致两个点超时（第一次只拿了80...），一种思路再开一个数组存上一位
  的数，这样for循环只要让开始的i等于上一位存的数就可以让后面的数大于上一位的数。iomanip
  中的setw函数可以让每个数字有3个场宽。

  p1088:本题最简单做法：algortihm中的next_permutation，每运行一次排列出下一个全排序的序
  列，左闭右开。当当前排序已经是最大序列，则将这个序列变成最小的排序，并且函数返回值返
  回false。
    第二种做法是用dfs，因为N最多10000（阶乘可想而知有多恐怖），因此从给出的序列开始求排
    序，并且当已经找到需要的序列时就可以直接返回。（不得不说这题真难...）

p3392:这题一开始想用dfs发现根本用不出来...思路是枚举白蓝红的两条分界线，再在两层for循环
中枚举不同分界线情况下需要修改的格子数量取最小值即可。

 p3654:又是自己写出来hh，通过暴力枚举每一个点并通过另外的函数来判断，注意k！=1时需
 除以2，因为每一条路都会算两遍，但如果k=1时就直接计算所有.即可。

 p1149:（自己想用dfs做结果40分钟只是把一位以内的算出来...）通过自订的函数来检测每个数使
 用的火柴数，通过计算可知最大为1111，通过枚举所有数来检测。

 p3799:先利用桶排序检测所有边长度各个数量，随便两层循环外层循环先枚举两条相同不用合成的
 边，随后在内层循环中枚举所有需要合成的边，该边有两种情况首先是该边是两个相同的边合成的
 第二种情况是两个不同的边合成该边，注意由于防止重复计算内层循环应当小于i/2，由于该题目
 组合数只有1,2两种情况，因此求组合数函数中是特判情况。

 p2392:史中史，开始认为贪心可以做并且输入的几个例子都能过结果直接爆0，调到很大的数据才
 终于出现错误答案...看了题解用dp做了出来，这题01背包问题，f[i][j]表示左脑处理前i个题目
 不超过j分钟解题时间的集合，注意属性为max，因为若为min则1意味着右脑那边就很大，但此题要
 求左右脑应该很均衡（因此j不大于这个科目总时间的一半），题目相当于i，时间为j，时间也相
 当于01背包的价值...

 p2036:一道简单的dfs，不过注意当刚进入dfs时不能一开始就判断差是否最小（因为1，0是人为
 输入进去的）。

 p1255:如果用暴搜只能拿50,要用到高精度f[i,j]，f[i]表示是第i个台阶的方案数，而j是这个方
 案数的第j位。由递推得f[i]=f[i-1]+f[i-2]，因此需要设置f[1],f[2]。

 p1044:注意dp问题应该考虑这一步是由哪种状态转移过来（即上一步的状态），f[i,j]表示i个已
 经入栈，j个已经出栈，当f[i,0]时表示上一步一定是入栈，因此f[i,0]=f[i+1,0]，因为f[n,0]为
 1，所以所有的f[i,0]=1，同时注意i>=j，当i==j时一定是从出栈这一步转移所已只等于f[i,j-1]。

p1028:通过递推可知f[i]=(f[1]+....+f[i/2])+1，因此首先将所有f[i]赋值为1，然后递归的求结
果（看了题解豁然开朗但是自己就是做不出来...）

p1464:首先语法问题：a==b==c==-1和a==-1&&b==-1&&c==-1是不同的，第一个是从左往右依次计算
比较的，首先计算a==b得到一个布尔值，布尔值再和c比较，最后再和-1比较。本题因为递归多次会
导致时间太大，可以用记忆化搜索（即用一个三维数组存放20以内所有的数，当再次用到时直接
用数组里的数据就行），因为当a,b,c<=0和a,b,c>20都已经提前做了处理，所以不存在数组越界的
情况。

p1928:好难...通过递归来实现（根本想不到），不过注意因为递归导致初入最后一个]时依然无法
跳出循环，因此需要在while中cin>>ch改成(ch=getchar())!='\n'，并在函数最后加一个return
因为cin会自动忽略换行符

p2437:斐波那契数列：0 1 1 2 3 5....即这一项是前两项的和，本题与数楼梯类似，可以得到递推
式：f[i]=f[i-1]+f[i-2]。符合斐波那契数列，从n到m符合f[n-m+1]（第一项从第一个1开始）。因
为斐波那契数列很大（第1000项约1e300），所以必须用高精度

p1164:题目不难，就是初始化想了一会，应该初始化f[i][w[i]]=1.可以优化成一维，不过一维时
f[0]=1，代表此时情况钱为0正好成立而不是f[w[i]]=1

p1990:（好难啊！！！）这题设f[i]为前i列*2行铺满总面积的方案，当只有长方形的砖头的时候可
以得到f[i]=f[i-1]+f[i-2]。当L形砖头时，设k(i)为前i列都满了，第i列涂了1个。因此可以得到
f[i]=f[i-1]+f[i-2]+2*k[n-1]。又可知k[i]=k[i-1]+f[i-2]。因为存在i-2，所以要将1，2的情况
都初始化。从3开始枚举（代码很简单但是分类很复杂...）,注意只输出后4位意味着对1e4取模
（我还以为要用高精度...）

P1259:可以看出当总数2*n+2>=10时有规律可言，当2*n+2<=8时就没有规律，因此在8时进行特判即
可。

p1010:通过简单计算可知2^15一定大于题目给的范围，所以只需要自己手写出1-14的分解方式，然
后从大到小依次求出组成的数（即2的几次方），然后在根据1-14的分解方式就可以轻松求出答案

p1228:（好难...）将一个大的长为2^n的正方形划为四个2^n-1的小正方形，通过分类确定公主在
哪个小正方形，然后另外三个小正方形的三个相邻的顶点就可以铺上一个地毯，然后就可以继续通
过递归将这三个顶点+公主都看成障碍物递归求2^n-2的结果，最后基准情况边长为1就直接返回
（反正我是想不到...）

p1498:好难...递归这边的题目真心难，已经不知道怎么讲了...
https://www.bilibili.com/video/BV18T411u7HG/?spm_id_from=333.788.videopod.sections&vd_source=eaa1685b9a7c0412de82c8ee63c5136b
视频讲的虽然会写但自己单独写写不出来
cmath库中的Pow(2,n)可以返回2^n次方

p1803：基础课的模板贪心题...还是忘了第一次写只拿了20分，需要先依照右端点从小到大进行排
序，然后比较下一个区间的左端是否大于等于此时的ed即可

p1090:轻松的模板题，看到要用最小堆的提示就知道怎么写了。

p3817:稍微难一点的贪心就做不出来了...，本题思路是首先判断第一个盒子是否超过x，如果超过
就减去使得第一个变成x。然后for循环从2开始检测每两个相邻的盒子糖果总数，因为吃第一个盒
子的糖果只会改变一组糖果总数，而吃第二组的糖果数可以改变两组，所以要尽量吃第二组的糖果
这也是为什么要预处理第一个盒子的糖果，第一组处理完再看第二组，因为第二组的第一个是第一
组的第二个，也就是已经处理好了第二组的第一个，只要处理第二个就可以，依次类推就可以。

p1106:自己写了一堆复杂的结果就拿了44分...思路：找到高峰值就直接删掉。要注意前导0.

p5019:题目虽然是贪心但是看完题解觉得用搜索递归会更理解...思路：先找到h到e中的最小值，
将所有路段减去这个最小值，这个时候再通过递归调用h到des-1和des+1到e。sb的是我还在好奇如
果des是一个全局变量那么函数调用它的时候岂不是一直修改，那么递归回来des不是已经不是原来
des了吗？后来才搞懂是值传递，根本不会改变真正的des罢了（基础知识薄弱...）

p4447:第一道绿题（虽然是看的题解...）本题思路：类似于蜘蛛纸牌，将数组排序，然后依次检
测是否有可以放置的位置（即这个堆下一个该放的数字），如果找到则更新下一个该放的数字，并
更新这个堆的大小，如果未找到，则新创建一个堆。可以用algorithm中的lower_bound，使用方法
lower_bound(f+1,f+1+n,q[i])在f[1,n]中找到第一个不小于q[i]的位置，lower_bound返回的是已
排序序列中可以插入目标值的位置，同时保证插入后的序列任然有序，如果全小于q[i].则返回n+1
注意返回的是迭代器，也就是指针因此如果f是数组那么就会返回元素地址因此如果要求数组下标
需要减去一个f。注意插入堆时要保持堆的有序性因此如果需要找到最后一个放该元素的堆。

p1080:目前为止最难的题目...目前功力不够照着把大致代码理解了一下然后跟着写了一下以后慢
慢看...

p1102:以前做过的题只知道大概思路忘记怎么写了...，第一种办法：哈希表unordered_map，将每
个数组元素都映射成s<num,times>即数字和出现次数，随后每个元素减去c，遍历哈希表累加就可
得到答案。第二种办法：利用upper_bound（a[i]>x）和Lower_bound(a[i]>=x)相减得到正好为
a[i]+c的数的个数即可（注意要开long long 不然会爆）

p1837:二分真的好难...此题利用增加高度获得的总值就减少，减小高度总值增加，因此一定是有
序的可以用二分，l为0，r为最高的数，求出tmp临时获得的树数目，如果比需要的少，就要增加
树的数量，即让r=mid-1减小高度增加木材，如果多就要让l=mid+1增加高度减少木材。注意while
循环要l<=r，并且答案为r或者l-1。本题要求尽可能最大的值所以应当往高度大的方向搜因此当
tmp==k时要归到l=mid+1那一类。

p1024：小数的二分，只要让while(r-l>=1e-8)即可，本题先遍历-100到100所有的数，因为两个根
一定差一定大于1所以r=l+1先判断l是否满足方程满足则输出接下来就检测方程（l）和方程（r）
的乘积是否小于0小于0就进入while循环二分查找，注意小数缩小区间直接令l=mid，r=mid即可。
注意求double的平均值不可以用>>.

p1678:可以使用lower_bound，先对学校分数进行排序，然后枚举每个学生分数，利用lower_bound
找到学校分数中不小于学生分数的位置，然后比较前一个位置和当前位置的分数差。注意需要特判
学校分数都小于学生分数和都大于学生分数的情况。要开Longlong!以后所有题目我都开long long
第二种方法就是手卢二分，在二分中创建一个min,记录最小的差，但是二分不依靠这个min，当学
校分数等于学生分数直接返回0，如果学校分数大于学生分数（右边差一定比当前还大）就往左边
搜，如果小于（那么更左边一定大于当前差值）就往右边搜，刚开始想用这个方法结果这个没推出

p2440：算是第一道自己独立做出来的二分...和砍树那题很像，如果数量小于k就减小l，如果大于
k就增加l

p2678:二分的是最小跳跃距离，先构造一个check函数，依次枚举每个石头，如果石头要跳跃的距
离大于等于最小跳跃距离则更新前一个跳跃点，如果小于最小跳跃距离就要增加搬的石头，最后看
所需要搬石头的数量确定false 和true剩下的就是常规二分了。注意如果check成立要开一个ans来
存因为虽然可能右边更好但是可能右边依不行。

p3853:本题与上题类似，唯一的不同是tot的更新，当不符合最优时应当插入新标，而插入新标要
重新检测i,因此要多一个i--。注意要用ans存最后结果不然会显示错误答案。

p1182：这题开始中间想的就有些偏差导致80分后想了好久才理解，首先还是和前几题一样二分最
大值，然后和要求的段数，不同的是，这里的num<m时不一定是错误的因为分的每一段都差不多是
最大值，num<m也可以将每一段都拆分这样最大值还是没有改变，所以当num<=m时是一组，num>m是
一组。

p1163:简单的一道小数二分但是不会推公式...注意不可开辟一个新ans存答案因为小数二分可能不
会等于w0，只会无限接近因此答案是Mid

p3743:对题目理解偏颇，充电并非是普通的充电而是相当于所有设备连接在一个充电宝上，而不是
一段一段充电直到充到所需要的电量。所以二分只要判断总的需要电量和充电宝电量进行对比即可

p1135和p1443；都是简单的bfs应用不过注意的bfs求的一定就是最短路，因为bfs是一层一层向外
搜索，如果存在更短路径，按照一层一层搜索会更早发现。

p2859:一道还是挺难的bfs题，复杂在于对不同时间导致可访问的点不同，因此需要开两个数组，
一个times表示这个点被陨石砸的时间即不可访问的时间（如果无陨石就是-1）.vis表示这个节点
是否访问过。还要有一个person的结构体包含人的坐标还有时间。在bfs中人的时间是不断+1的这
样就可以模拟时间的流逝并查看点是否可访问，遇到第一个为times为-1的点就可以直接输出。在
while循环结束就可以直接输出-1。
今天又重新做了一遍发现主要遗落点：x,y可以大于300,陨石会有重叠的可能需要取最小值，bfs
需要用v数组记录哪些点被访问过了，如果没有的话环的图会导致一直循环。

p1433:一道状态压缩dp问题耗费了我将近3个小时从理解题解到debug完...。首先对于位运算的一
些补充：1<<n表示将n向左移n位表示2^n，dp中最外层的k循环就是这个。f[i][j]表示走到第i个
奶酪且走过的二进制状态j时最短距离。例如当j=110(二进制)表示第二个和第三个点走过。在正式
dp前要对f[i,j]预处理,每一个f[i][1<<(i-1)]=a[0][i]，其中f[i][1<<(i-1)]例：i=2时1向左移
动1一位为10表示从起点走到2这个点只经过2，所以就等于a[0][i]，i从1开始。而后在三层循环中
第二层循环for(int i=1;i<=n;i++)表示要检查k&(1<<(i-1))是否为0，如果为0意味着此时并没有
包含i这个点就直接continue，如果有i这个点则进入for(int j=1;j<=n;j++)第三层循环首先检查
i==j如果相等直接continue以及重复第二层循环检查j是否在k中。然后就直接写出方程：
f[i,k]=min(f[i,k],f[j][k-(1<<(i-1))]+a[i][j])后面这个式子表示到达j这个点且不经过i这个
点随后再经过i这个点。随后的答案就是从f[i][(1<<n)-1]找出最小值。1<<n表示将1左移n位减去
1则表示都是1，例如1000减去1则表示111.还是表示n个1.状压dp时间复杂度：o(n^2*2^n)，通常
只能通过n<=21的数据。

p1605:一道简单dfs...但我居然没看出来以为要用dp结果提交发现只拿了40分析后发现dp的话四个
方向不可能在它之前更新然后用dfs顺利做出。

p1019:好难的一道dfs...,首先要对每个字符串最小重叠数进行计算并预处理为一个二维数组。预
处理中check函数从a(后面要接字符串)从a的末尾遍历至a[0]，第二层循环从上一层停留的位置开
始，和b字符串进行比较（正向遍历），如果检测到不同直接退出，如果相同继续遍历如果flag没
有发生变化说明匹配成功就返回i字符串-i(最小折叠)，否则返回0.在dfs中，依次遍历每个字符串
，字符串不能超过2次并且要有重合并且两个字符串不可包含关系，即ch[x][i]不可等于x或i的长
。还有一点注意要在dfs中开一个flag，初始为false，如果可以匹配就改成true，在循环结束的末
尾检查flag如果为false表示已经没有可以匹配的字符串就进行赋值。总之这题很难。

p1101:今天又重新想了一下写了一下这题确实是比较奇特的dfs没见过所以没写出来，这题唯一不
同点就是只能朝一个方向遍历还有就是必须整个字符串相等才可以将vis赋为1.第一点不难，难的
是第二点，因此用递归调用。首先检测当前层的x和y是否和字符串对应位置相等并且检查zx和zy是
否在数组范围内，然后再嵌套一个if语句dfs下一层，最后当q>=6即最后一个字符时进行一次检测
如果最后一个也匹配成功则可以递归的将之前几个都赋值为1.

p2404:一道简单dfs，唯一的难点就是怎么去除重合：只要检测他们的排序如果非单调增就直接跳过

p1596:就是一道常规的bfs的题目结果m输成ndebug至少20分钟...下次要注意。

p1162:一道简单bfs题目唯一在做的时候的困扰是突然不知道是否要用vis数组[染色]。问过ai才知
道，在基础课求最短路时,d=-1就相当于已经是vis数组了，如果d不为-1代表说明已经访问过一次。

p1032；一道很狗屎的题目首先这题可以用双向bfs，但是我不会...看题解更更改改。因为当超过
10次就可以直接返回，所以可以开一个struct存每个字符串的更改次数。这题不同于普通的dfs，
这题对于每种可能的情况要在当前字符串从前到末依次检查是否包含r[j]。在已知包含的情况下不
能退出而是还要从下一个位置检测到末尾。因为假如有两个r[j]，就意味着会有两种情况，所以在
for循环中还要一个while循环。string的find(string a,pos)从pos这个位置检测是否包含a，如果
包含就返回a出现的起始位置。如果没有则返回-1,rfind则是从后往前搜。replace(pos.num1,string a)
从pos这个位置将num1的长度替换为a。这题最坑的一点是没有告诉你对应的数量，题解中的while
(cin>>r[i]>>l[i) i++;可以在洛谷上过，但是在vs中却会陷入无尽循环....

p1825；一道只需要特判传送门的bfs(但我还是调半天...)，首先第一个易错点是传送门的vis不能
变为true。因为有可能一个传送门挡在终点面前，这时就必须经过两次传送才可以到达终点。第二
点也不算坑点：在findsame中(i,j)!=(x,y)应该是i!=x||j!=y而不是i!=x&&j!=y如果(3,4)和（3，5）
时直接跳过了。

p2196:因为数据很水所以dfs可以过，不过需要注意的是题目给出的只能选择一条路，这就导致一
个问题：题目虽然没说通道是单向还是双向，但是因为只能选择一条路径就说明不能返回上一层。
因此道路要设成单向。dfs也需要有dfs，而这个题目的vis就是看有哪些地窖已经经过。
dp做法：f[i]表示以第i个地窖结束的最大数量。可得公式f[i]=max(f[j)+a[i](不是以包不包含
第i-1个划分！！而是以由1,2,3...i过来),路径问题可以使用pre，当f[i]变化直接让pre赋成由哪
一个地窖变到i。
又复习了一下，换了种定义：f[i]为以i地窖为开始的最大炸弹数，因为题目要求只能从小走到大
那么就可以倒着遍历地窖前一个地窖由后面的地窖可以推出来，那么pre就变成了back，就这些变
化

p8824:一道简单模拟不知道为什么可以到普及+的地步...，唯一要注意的是总文件从1开始还是从0
开始，更推荐从1开始，这样的话在touch中需要先更新idx（初始为0）再操作，而从0开始就是最
后再更新idx，不过0比较坑的是最后sort和for循环idx是开区间...

p8825：简单的bfs，唯一注意的是取mod是答案取模（我傻乎乎的让Num也取模导致错了两次），最
后就是pow返回的是double值，所以不能对其取模会报错。

p8838:这道题我想的是贪心（貌似不对），看完题解知道是bfs，依次将每个指令和机器比较看看
是否匹配。因为bfs第一遍深搜就是最小字典序。所以答案出来后令flag为true，标记退出循环，
反正我根本想不到要用bfs...不过似乎难度也不是普及+

p1434:基础课中的一道题目，虽然之前做过但是理解不深：用到了记忆化搜索，什么是记忆化搜索
：将搜过的数据存起来。例如搜（2，2）这个点，如果周围只有（1，2）点符合下一步就搜（1，2）
而为了搜(1,2)只能继续往下搜。这是普通搜索，但如果把（1，2）的数据保存，那么搜（2，2）
就可以直接搜（1，2）。注意在dfs中如果f[x][y]==-1要将f[x][y]赋值为1（这个点本身）

p4017:要用到拓扑排序，入度为0的点就是生产者，出度为0的点就是最高消费者。模板和拓扑排序
差不多，让所有入度为0的点入队列，检测每个点的出度点，将出度点的入度-1，随后利用推出的
公式f[t]+=f[j].如果入度变为0就将这点入队列。最后利用for循环检测有多少个出度为0的点并求和。

p1115:一道很简单的dp问题但我还是没想出来f[i]表示以第i个结尾的序列，可知f[i]=max(f[i-1]+a[i],a[i])
还是题目做的不够多...今天又做了一下发现昨天还是写的很多余...在dp中原先判断这个i-1是否
访问过如果访问过就判断是否大于0，如果没有访问还要手动算一遍，但是本身就已经算出了下一
个i-1即当前i的f，根本不需要这么复杂。只需判断f[i-1]是否大于0即可...

p1616:完全背包问题模板，但是优化版才能够，特地复习了一下...

p1077:不会的dp...f[i,j]表示前i个花已经放了j个位置。因为题目中给出了按顺序摆放所有大大
简化了dp，因为一种花最多a[i]个所以要开三重循环，f[i,j]=f[i-1,j]+f[i-1,j-1]+...+f[i-1,j-k]
k=min(m,a[i])。第一重循环枚举每种花，第二个循环枚举摆了j个位置，第三层循环枚举每种花摆
了k个花盆，注意j>=k。随后就可以写出。初始化f[0][0]=1表示什么都不选为1种方案

p3842:一道很好的dp题目：f[i,1/0]表示第i行在右端点（1）和左（0）完全经过这一行的结束点
。因此每一个都可以由上一行两个状态（1,0)推过来。可以得到递推公式最后可以解答。

p1064:是我见过最简单的一道绿题...但对我而言还是很难，这题就是背包问题的翻版，唯一的不
同是这题枚举每一个主件，每一个主件分成5种情况：不选这个主件，只选这个主件，选这个主件
并且选1号配件，选这个主件且选这2号配件，选这个主件并且选1，2两个配件，其他的就和正
常背包问题一样。确实是写过的5道绿题里最水的了。。。

p1020:如果只用dp做法还是很好理解：f[i]表示以第i个元素结尾的最长不上升子序列。则f[i]可
推的f[i]=max(f[j]+1)j<i,h[j]>=h[i]。第二问则可以通过Dilworth，定理，该定理断言：对于任
意有限偏序集，其最大反链中元素的数目必等于最小链划分中链的数目。此定理的对偶形式亦真，
它断言：对于任意有限偏序集，其最长链中元素的数目必等于其最小反链划分中反链的数目。
说人话就是：把序列分成不上升子序列的最少个数，等于序列的最长上升子序列长度。把序列分成
不降子序列的最少个数，等于序列的最长下降子序列长度。所以第二问可以变成求f[i]最长上升子
序列。和第一问一样。但是dp会TLE,优化做法用贪心，求最长不上升子序列时l[i]为长度为i最长
不上升子序列。由基础课中知识可知当bi<=l[r2]时，可以直接将bi加入到l,否则在l中找到第一个
小于b[i]的数字将l中的数字替换为b[i]，而最长上升子序列同理。注意：最长不上升子序列用的
是upper_bound(,,greater<int>())表示通过二分找到一个小于的数，上升子序列则是lower

p5318:开始认为很简单写了一会发现不会果断看题解...发现要用一种新的存储方式，用vector进
行存储，struct edge包含了u,v起点和终点。vector<edge>s，来存每条边，随便对每条边进行排
序。按照起点从小到大如果起点相同那么终点从小到大。开一个vector<int>e[1e5],e[i]表示每条
边的起点，e[i].push_back(i)表示为每个顶点的每条边起不同编号。随后就可以进行搜索。

p3916:1e5的数据在o(n^2)时间复杂度下会超时，所以朴素版做法不行，需要用到反向建边，再通
过从N开始的for循环，一个ans数组，如果ans[i]不为0说明已经有前面较大的数可以到达该点，因
此直接continue，如果ans[i]为0就dfs（i,i)，令ans[i]=i,for循环再查看有没有与它相邻且ans
为0的点。知识点：反向建图。

p1113:知道要用拓扑排序但是不知道这个时间怎么算...看了题解知道了f[i]=max(prej)+tiems[i]
用一个ans存每个点消耗的时间这样在拓扑中就是ans[j]=max(ans[j],ans[t]+times[j])

p1807:开始用二维数组存结果死活不对...换了数组模拟邻接表总算对了。这题依然是拓扑，不过
和前面不同的是，这题除了1这个入度为0的点，遇到其他入度为0的点时，不能直接将他放入队列
不然会对一些本来1不可到达点造成影响，需要做的是将除1外的所有入度为0点先放进队列，对于
和它有连接的点减去1个入度再判断入度是否是0，如果为0也是要排除的点。其余和正常拓扑一样

p8831:一道恶心的模拟题先本年以前所有天数再算本年本月以前的所有天数，注意本年的月天数要
根据本年在1582.10.15以前和以后区分。这题还有两点恶心：第一点输入方式开始用了一种很复杂
的读入方式，看了别人的题解才知道了可以用 int day,char m1,m2,m3,int year这种格式来输入
最后m1,m2,m3可以成一个字符串不过注意：a+=(m1+m2+m3)表示将m1,m2,m3三个ascll码相加。
包括a+=m1+m2+m3也是，只有a=a+m1+m2+m3才是正确的。
第二点：1582年以前的闰年只要整除4就可以，1582以后的两种：整除4且不整除100，整除400题目
没说清楚都！！

p2285:一开始以为是三维dpf(x,y,t)发现空间太大。看完题解知道还是可以转换为最长上升子序列
问题：f[i]表示以第i个鼹鼠结尾的最多杀死数。如果前1-i-1中第j个鼹鼠满足距离小于等于timesi
-timesj。可以则更新f[i]=max(f[i],f[j]+1)。思路很奇妙

p1091:独自完成的第一道线性dp!题目还是比较简单：可以看出求最长上升子序列+最长下降子序列
最长，最长上升子序列还是和之前用f[i]来求。而最长下降子序列用g[i,j]表示从i到j的最长下降
子序列。最后枚举求出最大值即可，时间复杂度：o(n^3)。不过看完题解发现做复杂了：我们先看
从T1到Ti这一段单调递增的序列，再看Ti到TK这一段单调递减的序列，那么问题就解决了。先
从1到n求一趟最长升，然后从n到1也求一趟，最后枚举中间的Ti，然后从众多Ti中挑个大的。

p1095:一道很早就做过的dp大体上记得挺清楚，不过为了巩固还是写一下：涉及三个状态：闪，走
等。然而闪和等涉及蓝量会导致变得很复杂。不如把闪等和走分开处理。显然有闪一定会闪。接下
来处理走:f[i]=max(f[i],f[i-1]+17)如果大于等于s直接返回i就可以了。

p8872:不会的贪心题...https://www.luogu.com.cn/problem/solution/P8872
题解讲的很清楚了不过注意的是while循环并不是找所有的aj，而是找最小的j，同时u=i-1<=m，所
以i=min(n,m+1).

p1541:四维的dp，f[a][b][c][d]表示a张1号,b张2号,c张3号,d张4号。由于考虑的是先后打出牌的
顺序，所以可得f[a][b][c][d]=max(f[a-1][b][c][d],f[a][b-1][c][d],...,)+s[1+a+b*2+c*3+d*4] 注意s坐标要加个1因为坐标是从1开始的。

p8871:恶心的字符串题。不可以用cin，因为cin遇到空格，制表符\t，换行符\n就会分割输入内容
，需要用到getline，它会读入直到遇到\n或文件尾EOF为止。用法：while(getline(cin,t))。还
有to_string这个函数，可以将内容转化位字符串。这样就可以很快算出位数。最后再来说一下ge
tchar：如果要用这个应该为while((ch==getchar())!=EOF)

P1868:挺难的dp...将草地看作一格一格，枚举每个格子的右端点，f[i]表示前i格最多吃多少草。
显然fi>=fi-1。多吃一个格子肯定不会变少。设这个格子左端点为i，可知fj>=f(i-1)+j-i+1为什
么是i-1?这是因为要避免有相交所以代表不能选fi，也就是f(i-1),转移方程可得：f[j]=max(f[j-
1],max(f[i-1]+j-i+1)。当i=0时可能会出现越界。所以不妨在确定x,y关系时同时让二者++。用
vector存储y和x的关系：s[++y].push_back(++x)即可。

p1757:一道模板的分组背包不过要注意的是它并没有直接说是多少组所以枚举就直接按照最大100
来，不过注意的是组数下面就是紧跟枚举空间，而不是先判断这个组是否为空，否则就出现中间有
空的情况下无法转移的情况。

p5194：剪枝剪了半天不会就拿了60分，看完题解知道要用前缀和，因为本题数据有限制：第三个
起a一定大于等于前两个数的重量。所以从后往前搜肯定更好，然后当前g和这个位置之前一个的前
缀和如果小于等于ans就不用搜了直接返回就可以了，剩下一些的剪枝就可有可无了。

p1797:复习前缀和那块知识正好刷了这题开始还错了...思路就是枚举矩阵左上点和右下点预处理
矩阵和就行，不过开始错是以为换行时y2要从1开始但是这样的话就会导致相当于枚举了右上和左
下这当然不对。改成下面每一列都必须大于等于枚举左上的列就行。

p8835:吓死我以为要用kmp不过暴力就能过但是最巧妙的还是用string里的substr就可以轻松完成。

p5440：放在搜索题单结果是枚举....首先将所有合法的年月日存入数组中，注意闰年的判别：分
别是被4整除不被100整除，能被100整除也能被400整除。这样就可以加年*10000+229了。随后进行
判断如果s[i]不为"-“且和枚举的ans不同说明不符，否则答案就+1，说也说不明白...

p1832:虽然是普及-但是看了好久...题目其实就考察了两个知识点：筛质数和完全背包问题的方案
数。筛质数用埃氏筛就可以因为在1e6以下和线性筛速度差不多。第二个就是完全背包问题的方案：
与价值推导差不多：f[i][j]=f[i-1][j]+f[i][j-v[i]]。如果是一维就是f[j]=f[j]+f[j-v[i]]。本
题中将n看成体积。i个素数。因为求的是恰好等于n，所以初始化应该是f[0][0]表示1种方案，如果
是求小于等于n那么初始化应该是f[0][j]=1表示选0种，剩j个体积都是1种方案，通过这题看出我对
较难的背包问题和背包问题变形不太熟悉需要加强。

p1203:放到了dp题单中但是模拟更简单...需要将环断成链即在s[n]后再放n个相同的字符，枚举每
个断裂点求每个断裂点获得的珠子即可，不过注意截断点为W时应让x等于下一个字符，否则会出现
问题，在另一端也要相同处理。最后就是如果求的长度大于n则说明整个链一定是联通的直接返回n。

p2846:用一维的01背包方案拿了80分...正解是f[i][j]表示前i个奶牛能力取模于f的方案数。如果
f为5，10，2就分别是0，2。所以方程：f[i][j]+=f[i-1][j]+f[i-1][(j-r[i]+f)%f]。注意可能会
出现j-r[i]<0的情况，由于取模的性质，f=5,j-r[i]=-2时相当于就是3，因此只需要+f再取模即可。

p1535:为了这题记忆搜索专门写了篇，不会的话就直接去看。

p2340:写了一下最高81分。设f[i][j]表示前i种奶牛在j智商下j的情商最大数。显然是01背包的变
形，但必须用一维否则会超时。同时因为智商会有负数的情况那就进行偏移：让最小可能+4e5即可
，所以j范围是0-8e5。还有一点注意也是我认为本题最难的一点：如果智商为负数，那么j-a[i]就
比j还要大，这样就会用到j-a[i]的f，如果还是和普通一维从大到小遍历显然j-a[i]就被更新了就
被污染了，所以小于0时要从小到大。这题让我对一维背包有更深的理解了。

p2858:不会的区间dp...只有两侧可以拿可以想到区间dp(不知道为什么)，f[i][j]表示从i到j区间
可获得的最大价值，区间dp模板：https://www.acwing.com/solution/content/13945/
这里记一下为什么不可以依次枚举起点终点，因为[i,j]表示从i到j这一区间，他是由一个个小区
间组成的，如果枚举起点终点就会漏掉很多小区间。区间dp len==1时要特判，这题就是v[i]*n。
转移方程：f[i][j]=max(f[i+1][j]+v[i]*(n-len+1),f[i][j-1]+v[j]*(n-len+1))为什么要乘以
n-len+1,这是因为题目中最大要求，这个区间价值最大显然就是在n-len+1个数中最后去掉。

p1435:dp真的好难啊....因为是回文字符串，所以正过来反过来都应该一样，由于这个特征可以借
助最长公共子序列：将字符串正过来反过来用dp求二者最长回文子串，答案就是字符串长度-最长
回文子串，说的容易根本想不到...

p1564:今天的dp真的一道都不会而且脑袋很混乱...想到了要用前缀和也用了，但一直想区间dp怎
么做试了一下发现根本做不了...线性dp想了下没往下想...题目思路：f[i]表示为从1到i的最小数
量，枚举i，同时枚举j,j表示[j,i]可划分成一个区间，满足划分条件：这一段全为2或1或者二者
差小于等于m，很容易看出利用前缀和维护。转移方程：f[i]=min(f[i],f[j-1]+1)，注意要初始化
f为0x3f。

p1103:想了好久可惜还是没能调对...，转化为类似于背包问题已学的模型：选择n-k个使得最小宽
度差最小。我一直在纠结如何确定最近的一本的位置该怎么知道，首先就是开第三个维度m表示最
新书的位置发现逻辑很混乱，答案也不对就放弃了。看完题解知道了其实可以枚举的，就跟p1564
一样虽然只有一维却可以枚举。通过这题我也知道了一些dp问题的未知量可以枚举。开始时f[i][j
]表示前i本书选了j本书。然后习惯的分为了选择第i本和不选第i本。但是这里这样分小的情况和
大的情况会不一样，也就是小的无法推到大的。正解应该是表示前i个选j本最后一本为i。这样最
后一个位置就确定了，转移方程：f[i][j]=min(f[i][j],f[m][j-1]+abs(...))。

p1833:光看题目应该就能发现是混合背包的问题第一次写结果全WA...发现了一篇很好理解的题解
：https://www.luogu.com.cn/article/pnl8x3m6.就是先分类先分成完全背包和非完全背包。先在
完全背包中去掉残次品：即观赏度小于其他的且时间还比其他的长。剩下的完全背包的物品因为有
时间限制所以最多的次数：t/T，向下取整。然后就可以得到一个多重背包，再利用二进制优化将
它变成01背包即可。提交了好几次一直RE结果发现是关流的问题...

p2853:bfs,dfs图这边的知识忘记了特地做道题复习一下：思路利用Bfs枚举每个点能否到达奶牛的
位置即可。注意：应该反向建图。因为这是单向图...如果没有反向建图相当于是求这个点能否到
达奶牛位置。第一次正向建图只得了50分。

p1854:虽然没有做对，但是错的是求路径，动态规划转移方程是对的，也就是第一个答案是对的。
思路和p1103那题类似，都是属于前面的会影响后面的。所以可以设置f[i,j]表示为前i朵花插入了
j个花瓶，且第i朵花正好插在第j个花瓶，注意这时候j的范围是i到V-F+i。不然就无法插入全部的
花。然后再枚举第i-1朵花的位置，范围和j类似：i-1到V-F+i-1。注意k还应该要小于j不过求路径
这边就错了：原本是直接用pos[i-1]=k覆盖，但是不对。正确思路还是用pre[N][N]，记录第i种花
在位置i时前一朵花的位置，最后在寻找最大的f[F][j]时可直接找到最后一朵的位置，利用pos[i]
=pre[i+1][pos[i+1]]即可完成。

p1063:今天状态真不错啊，这道dp的绿题自己独立做出来了hh:看了题目应该就知道应该是和区间
dp有关，因为这个题目和基础课中石子合并类似可以说基本一致。但是这题是环形的，不要紧可以
破环成链。开一个4n的数组，例如2 3 5 10前2n个就是2 3 3 5 5 10 10 2，而后2n个和前2n相同
设f[i][j]表示从i到j可获得的最大能量。len应该从4开始枚举，4时要特判，len枚举到4n。起点
的位置是1，3，5等奇数，终点则是偶数，间断点应同为奇或偶。。最后只需要注意枚举起点1-2*n
长度2n的范围找最大值就可以了。

p5662:不会的完全背包...可以较清楚知道这和背包联系很大，今天手里的钱：容量，明天卖的钱
：价值，今天的价格：消耗。一个很重要的转化条件是虽然不知道哪一天卖但是比如第4天卖：p2-
p1+p3-p2+p4-p3。正好和第一天全买第二天全卖这种依次类推。所以不必考虑跨天卖只有关注当天
卖即可（还是不太理解...）。这样每一种纪念品都是一次完全背包。每一天完全背包结束后都要
将上一天的钱+今天赚到最多的钱。f[i]表示I钱下明天卖出最多的利润。由于是一维且每天价格没
有联系就要每天之前初始化背包套一维背包模板（但是根本不知道怎么从三次推导到1次的）总的
来说这题还有很多不理解...

p2015:又是一道恶心的Dp题...本题是树状dp
https://www.luogu.com.cn/article/gzt16p6t感觉直接看这篇文章会更好。一些细节很恶心：需
要双向建边。这样检测是否有子节点就不是看是不是-1了，而是看是否有下一个点不是父节点。
左右子节点也要满足不等于父节点这个要求。这道题加深了对基础课邻接表的理解，里面的e[idx]
中的idx其实就相当于是一条边了。

p1043:刚开始看觉得是区间dp但是因为有一个分割M份不知道这种区间dp怎么写...看完题解知道了
这种多一维的区间dp怎么写了。f[i,j,k]表示在区间[i,j]分成了m份。遇到这种环状问题很自然就
知道了要断环成链，即开2倍空间。转移方程：f[i][j][k]=max(or)min(f[i][j][k],f[i][s][k-1]
*mod(s[r]-s[k]))。S意思是枚举最后一个分割点前i到s有k-1个分割点。剩下区间s[r-k]就是最后
一个分块。先初始化时候q==1时只有一个区块就是整体的值。开始dp:首先枚举q=2->m，q块区块。
再枚举len区间长度，这时候len要至少等于q，不然没法分q块。再枚举L起点，len+l-1表示终点。
最后就是枚举分割点k，由于要求前i-K有q-1块，所以k只能从len+i-2（或Len+i-1，前者k<=r，后
者k<r）开始。最后枚举起点1-n，区间长度n，区块m的最值。很多都是宝石项链那题很像。但是多
了一维，len,k有了限制。

p1087:一道较为简单的dfs题，按照要求设置函数dfs(l,r),因为要求后序输出，所以先dfs左边，
在dfs右边，最后输出[l,r]的树。唯一的记忆点是string.find，find("01",l,r)并不是在l,r这个
范围找是否有"01"，而是从l为起点，长度为r的字符串。这一点要注意。

p8742:一道很奇特的背包问题...:考虑类似利用桶计数的性质：f[i][j]表示前i个砝码称出质量j
的情况。如果可以称出f[i][j]=1,不可则为0.转移方程：f[i,j]=f[i-1][j]|f[i-1][j+a[i]]|f[i-
1][abs(j-a[i])]。|是按位或，所以很奇特。注意j要从0开始枚举，代表的是第i个砝码不放。最
后枚举1-sum[n]查看每个值的可能情况。这道题确实巧妙和普通dp不同在于一般01背包方案都是相
加，而这题是按位或。

p1040:奇特的区间dp。原本看这题脑袋都疼，不过最终还是写出来（虽然跟题解相比很复杂）。首
先说明原本的做法：因为中序遍历所以有个特点就是点i的左边所有子树节点都小于i，右边都是大
于j。考虑每个区间都可以组成一个小子树那么很可能和区间dp有关，于是设出f[i,j,k]表示在区
间[i,j]上以k为根的最大加分。当左右子树都存在：f[i][j][k]=max(f[i][j][k[.f[i][k-1][w1]
*f[k+1][j][w2]+a[k])。w1,w2分别是左右两个子树的根，那么这个dp就要五层循环：一个枚举长
度，一个枚举起点，三个枚举根。数据最大为30，显然不会超时。当w1==i或w2==j时，分别表示没
有左子树和右子树，那么只有让左或者右的那个表达式为1就行。再开一个Next[i][j][k][2]，表
示在区间[i,j]上以k为根左/右子节点。最后只要用dfs就可以求出前序。
当然我想的还是太复杂了，其实根本不用考虑子树的根节点。只需要枚举这颗树的根节点就行，因
为子树加分最大的根节点已经求出来了。那么就设f[i,j]表示在[i,j]区间上最大加分即可。这样
就只要三重循环，区间长度，起点，和根。f[i,j]=max(f[i,j],f[i,k-1]*f[k+1,j]+f[k][k])。至
于左右子树没有的情况根第一种类似。这种方法就直接开root[l,r]求每个区间的根就行。

p1141:好久没写过有思维的搜索题了...如果单纯用bfs会超时，思路就是在一个连通块中的点他们
能到达的格数都是一样的，所以在Bfs内开一个Vector存储在一个连通块的点，并开一个ans记载这
个点的步数，最后在Bfs内赋值给所有连通块的点即可。说容易但难想到。

p8599:一到全排列的题，以后看到这种要求1-9必须出现且只出现一次应该就该往全排列上靠，题
目简单来说就是求a+b/c=n。开始我想先枚举a，再枚举b，找c，但这样太复杂了。可以把他看成是
一个全排列，例如8+12354/679就可以看成812354679。这样我们就可以枚举间断点也就是这个加号
和这个除号。注意枚举第一个间断点是从1到7，因为剩下两个数至少是各位数，第二个就是从i+1
到9。

p1006:开始两个dfs直接0分...正解应该是dp。两个其实都可以看成从（1，1）点出发到达(m,n)点
，则可以设：f[i,j,k,l]分别表示第一条路到达(i,j)和第二条路到达（k,l）好感之和的最大值。
观察可得两条路的总步数一定是相等的，也就是（i，j）变化一次那么(k,l)一定变化一次。那么
就一定只有4种情况：第一条向下，第二条向下；第一条向下，第二条向右...以此类推。由于要保
证不重复，就需要来考虑：通过画图知道两条不重复的路一定分为上下两条。假设（i，j）枚举的
是下面这一条。而(k,l)是上面那一条，由于不能有重复，由于都是从（1,1）出发显然是重复的，
所以i是2-m，j为1-n。下面的这条就确定了那就考虑上面那一条：每一步的l和对应的j一定是j+1
<=l<=n,1<=k<=i-1。由此就确定了k,l的范围。

p8602:没学过树的直径所以做不出来...由题目条件看出来这是一颗树。让我们求某一点到另一点
最长就是求树的直径：首先就是用两次dfs:任取一点求这点到其他点最大距离的一点，再对最大距
离的这个点用一次dfs找出离他最远的一个点，他们的距离就是树的直径，不过该方法缺点是无法
是求负边。还有一种方法是树上dp求解，不过多赘述等会写一篇分享...

p1470:又是一道奇特的dp问题，其实开始想过用这种方法但是觉得不对遂放弃。定义:f[i]表示前i
个字符可以被表示，1为可以表示，0为不可以。枚举s中每个字符i，再通过枚举p中每个元素，查
看是否存在一个j比i小，s[i-j+1]到s[i]这一段等于p中某个元素。还有恶心的一点是s的输入，在
vs中如果是while(cin>>ss) s+=ss，这样会陷入死循环...哪天花点时间去搞vscode了。因为p中元
素个数最多为200，而s最长为2e5，也就是4e7,正常应该不会超时。