CUMT21曾虹荐

分类

未归档(1) 题解(10)

/ 注册

全部文章（共11篇）

[JSOI2008]最大数MAXNUMBER

思路一：直接上线段树，这个没什么好讲的，线段树最基本的操作思路二：单调栈+二分这里上单调栈是一个很妙的地方，我们可以始终维护出一个线型递减的关系二分即二分我们的目标区间左端在那个区间里，返回区间的右界就好思路三：单调栈+并查集这里的并查集使用又是在二分上的一个优化，同样是用单调栈先维...

C++ 二分查找并查集线段树栈

2022-05-23

0 294

食物链——并查集

我认为这题很好的揭示了并查集的一个本质，即将任何有关联的元素整合到一个集合里。首先是一个常规解法，思路是通过边的权值来维护两者间的关系。这题对于并查集的的考察并没有很常规，我们还可以用另一个思路，把情况拆分一下，更加简洁 #include<bits/stdc++.h> usi...

并查集

2022-04-08

0 411

动态规划与记忆化搜索的异同

相同点:1.两者都需要满足一个条件，即我这一步的最优决策是可以基于上一步决策确定后的结果来求出的。意思说我在上一步决策确定后，我做这一步决策是不会影响上一步决策的。 2.都利用了递归的思想，即在一个结果的基础上去求解下一个结果，最后求出目标解不同点：I.动态规划：动态规划的关键在于推出一个递推方...

C++ 动态规划

2022-04-06

0 516

花店橱窗（动态规划）

这题符合动态规划的条件，即在每选一盆花时，选这盆花的操作不受上次选择的干扰，每一次维护数组时，都维护出了选第i盆花时的最优解 #include<bits/stdc++.h> using namespace std; typedef long long ll; int f,v; int m...

C C++ 动态规划

2022-04-05

0 414

PTA——L2-3 完全二叉树的层序遍历

这题用到了分治思想，后序遍历的存图方式是：左->右->根，所以反过来存图的话顺序应该是：根->右->左，然后进行一个存图即可 ```#include<bits/stdc++.h> using namespace std; int a; int numb[50]; ...

C++

2022-03-24

0 521

PTA——L3-1 那就别担心了 (30 分)

知识点：链式前向星存图+记忆化搜索（dfs）每个节点到终点的路径为他的所有子节点到终点路径的数量和，边界即为该节点就是终点，此时这个节点到终点的路径条数为1； ">using namespace std; const int N=550; int n,m; int x,y; int e[N*N],...

C++

2022-03-22

0 571

PTA——L2-4 网红点打卡攻略 (25 分)

本质上就是一个链式前向星建图加一个简单地查找（注意这里是双向图），没什么太大的难点，但是样例中的第四条路线过不了（但是我感觉是可行的），所以代码无法处理第四条路线这样的数据。 ">using namespace std; int n,m;//点个数和路径条数 int x,y,z;//点1,点2，费用...

C++

2022-03-22

0 762

题解 | #取数游戏2#

学到动态规划学到后面反而忘了他最重要的本质，动态规划的本质是一个状态和一个状态之间的转换。本来开了个三维数组dp[i][j][k],代表的是从左拿了个，从右拿了j个，现在是第几个，其实简化后就成了dp[i][j]。代码中的实现在两层循环可以实现，第一层枚举现在一共选了n个数，然后第二层枚举从左...

2022-03-09

1 396

题解 | #[NOIP2004]合唱队形#

从左边求一次最大上升子串，再从右边选一次，每一个人只有两个状态：选或者不选，每次维护后求解一段区间的最大值，符合动态规划思想，以下为代码 ">using namespace std; int n; int stu[500],l[500],r[500]; int main(){ cin>...

C++

2022-03-05

0 310

前缀和与后缀和的预处理

#include<bits/stdc++.h> using namespace std; int main() { int o[100],u[100],s[100]; memset(o,0,sizeof(o)); memset(s,0,siz...

C++

2021-12-03

0 688