LXNHB

分类

c++基础(2) 三分法(1) 二分法(2) 操作系统(7) 算法(2) 题解(68)

/ 注册

TA的专栏 82篇文章 0人订阅

竞赛奋斗日志

74篇文章 610人学习

操作系统知识总结

8篇文章 0人学习

二分法——区间与选择
HIT操作系统学习——系统启动背后的故事

全部文章（共14篇）

题解|#F. Array Stabilization (GCD version)# cf 来自专栏

本题暴力循环是使不得的，本人亲测。首先分析得到，n个数进行gcd操作的结果就是最终的相同的数（自行举几个例子就可以得出这个结论）。我们注意到转换的步骤有几次，i就和他后面几个数进行gcd操作，而操作次数一定是单调的，所以可以采用二分来优化。二分出操作次数后，就进行区间查询的操作，在[i,i+m...

C++ 动态规划 st表倍增

2023-12-15

0 342

题解|#区间最大值# 蓝桥来自专栏

st表模板题 #include<bits/stdc++.h> using namespace std; const int M=5e5+5; int a[M]; int st[M][21]; int getMax(int l,int r){ int k=log2(r-l+1); ...

C++ 动态规划 st表倍增

2023-12-15

0 286

题解|#E. Sending a Sequence Over the Network# cf round 826 来自专栏

这个题的原问题是，从1n有没有一个正确的序列划分，可以缩小为子问题，从1i有没有正确的序列划分，由于子问题和原问题的求解方式一样，且原问题需要由子问题推来，这就说明了这个题需要用动态规划来求解（不过蒟蒻一开始也没想到动态规划，还是太菜了）。考虑递推方程怎么写，由于只用判断整体区间划分能否正确，所以...

C++ 动态规划

2023-12-15

0 260

题解 | #石子合并# 来自专栏

区间dp模板题 #include<bits/stdc++.h> using namespace std; int n; const int M=305; const int INF=0x3f3f3f3f; int a[M],sum[M]; int dp[M][M]; int main()...

C++ 动态规划区间dp

2023-12-11

0 220

题解 | #「木」迷雾森林# 来自专栏

这题虽然蛮简单，但是困扰了很久这是AC代码 #include<iostream> using namespace std; int m, n; const int M = 3005; int mp[M][M]; const int mod = 2333; int dp[M][M]; i...

C++ 动态规划

2023-12-11

0 264

题解 | #免费馅饼# 来自专栏

一、思考状态转移方程如何写 1、原问题和子问题：原问题：一个人可以左右移动去接饼，当游戏结束时，接到的饼的最大价值。子问题：一个人可以左右移动，当到达某一时刻时，接到的饼的最大价值。可见子问题的求解方式与原问题相同。 2、使子问题是最优解显然是比较每一个由相同状态转移来的状态，得到最优解就是...

C++ 动态规划

2023-12-11

0 357

题解 | #花店橱窗# 来自专栏

一、考虑状态转移方程怎么写： 1、首先考虑子问题是怎么样的，原问题是求把编号为1~ f的花束，随机放进1~v这v个瓶子里面，且需要按照编号顺序放置，每个花瓶只能放一朵花，的最美观方案。子问题就可以是，把编号为1~ i的花束，随机放进1~j这j个瓶子里面的最美观方案。显然子问题和原问题的求解方法是一...

C++ 动态规划

2023-12-09

0 310

题解|#数字三角形# poj 来自专栏

简单动态规划问题，把求从头到尾的最大加和化简为求从i行到j行的最大加和。 #include<bits/stdc++.h> using namespace std; const int M=105; int mp[M][M]; int dp[M][M]; int main(){ int...

C++ 动态规划

2023-12-09

0 236

题解|#C. Yarik and Array# 来自专栏

经典动态规划求最大子序和的问题，思路不算难，但是数据量比较大，这里应用一个小技巧将dp的初始化大小始终设置为n+1的大小，这样能避免memset给许多不必要的下标内容赋值，可以减少时间复杂度 #include<bits/stdc++.h> using namespace std; co...

C++ 动态规划最大子序和

2023-12-06

0 261

题解 | #[NOIP2008]传球游戏# 来自专栏

一、判断是否可以用递归 1.原问题：小球从小曼手里传出去经过三次传递又回到小曼手里的可能方案数。子问题：从1开始传球第i次传递时到达j的手里的方法数符合具有相同子问题的条件 2.符合最优决策： 3.解决当前的决策与之前怎么决策的没有关系满足无后效性二、递推公式易错，因为是环形站位，所以还...

C++ 动态规划

2023-12-06

0 411