#算法

#算法

共 21 篇文章

关于dp状态转移方程的设计4
我们有的时候会发现一个问题,题目给的数据范围或者是某些引导让我们的dp状态设计非常显然,但是可能转移的时候会遇到难以维护或者复杂度不对的情况。
#算法
01分数规划学习笔记
起因:P1642 规划
#算法#学习笔记
关于动态规划的转移1
对于一道dp题,它可能让你转移的时候维护两个优先级,那么我们暴力一点,如果不满足两个条件的话就不转移,比如求两个最小值,总会有一个是最优先考虑,那么选的如果超出第一优先级的话就一定是错误的,所以在小于等于第一优先级的时候再去考虑第二优先级。
#算法
P6413 [COCI2008-2009#3] NAJKRACI 题解
之前没有接触过最短路图,退役前正好趁这道题学习一下。
#算法#题解
01BFS学习笔记
本人随机跳题到了一道看起来是最短路的题,但是本人并不想去暴力建图懒,发现如果抽象成一张图的话边权只有 0 或者 1,于是去学了个01BFS。
#算法#学习笔记
关于需要处理复杂依赖关系的题
多考虑图论转化,比如求解依赖关系中的最小值,第一眼容易开成dp,没思路时不妨想想求解连通性的最值算法,最小生成树。
#算法
关于dp状态转移方程的设计3
对于一些需要优化空间的dp题,单纯地让dp方程每一维表示一个条件的话无法确切表示出一个无后效性的状态,那么我们可以另这个方程加一些限制条件,但是不表示在方程里,比如对于一个线性dp,我们规定 dp[i][j] 为到第 i 位选择 j 个,但是我们另外规定第 i 个必须选,这样在一些题中就可以满足无后效性了。
#算法
关于拓扑排序的应用
P2017
#算法
字符串读入踩坑1
对于有些题目来说我们读入字符串如果不想一个一个读入判断的话我们就一定要使用 getline() 函数,但是我们要注意一点是如果在要读入的字符串前面读入过其他形式的数据,那么这个函数会把上一行剩下来的换行符当做一行来读入,那么我们便会少读入一行字符串,所以我们要在读入字符串前调用一次 getline() 函数,这样就可以覆盖掉上一行的换行符。
#算法
搜索踩坑1
有些搜索最短路程的长度的题目,我们如果直接返回第一个搜索到的答案很可能是错的,因为有些路程计算方式和我们的BFS步数并不成正比,但是我们知道路程长度随BFS步数有单调性,那么我们便需要在搜索的时候扩展一点范围,比如在大于当前最小答案后再将这个点ban掉,这样就会保证正确性。
#算法
关于dp状态转移方程的设计2
对于一些状态转移方程较好写的dp题,但是复杂度很难看,并且很难在数学方面上进行优化的dp题,我们可以考虑重构状态转移方程,比如要dp双线程操作的话,我们可以把一个线程写在方程里,另一个记录在数组的值里,这样就可以把看似暴力的方程优化成一个最普通的背包,相当于抽象了背包dp的重量和价值,这样的方程看起来有一种偏重关系,而且这样写兴许还可以处理两个线程的优先级,但是我还没见到过这样的题。
#算法
关于dp状态转移方程的设计1
对于一些按照题意模拟设计 dp 毫无思路的情况下,考虑正难则反,比如让你从一个字符串中删去不合法的字符,这样看起来只有暴力,但是反过来思考成我们在这个字符串中按顺序选择若干个字符使其组成的字符串合法且代价最小,那么这样就很容易设计状态转移方程了。
#算法
P9705 「TFOI R1」Unknown Graph 题解
一道有趣简单的构造题。
#算法#题解
P5032 经验 题解
同机房同学找到的题,一看 \mathrm{tag},什么?队列?不会怎么办?
#算法#题解
P4645 [COCI2006-2007#3] BICIKLI 题解
一道很好的图论练手题。
#算法#题解
P3112 [USACO14DEC] Guard Mark G 题解
有一说一这道题和 国王游戏 很像,但是多了一个高度的维度,当然起先我只认为用这个判断是否合法然后取最优解就好了,然后写了一发爆切57 pts。
#算法#题解
P2530 [SHOI2001] 化工厂装箱员 题解
首先我第一眼看到这道题时以为这是一道贪心,贪心策略是对于每一次手里的 10 个货物都优先放下个数最多的。当然这后来想一想便是错误的,因为如果假如手里有 6 个 A,但是手里有 4 个 B,而且 6 个是一个 A,5 个 C,那么这个贪心策略很明显就不满足最优解了。
#算法#题解
P4209 学习小组 题解
我第一眼看到这道题的平方建边的时候我还以为需要一些数学方面的优化,但是同机房大佬瞅了一眼跟我说暴力建边能过,我心里一群草泥马奔腾而过。。。
#算法#题解
SP688 SAM - Toy Cars题解
其实我第一眼看到这道题的时候以为是一道 \texttt{DP},但是想了想就发现要记录的状态实在太多,于是就去想贪心。
#算法#题解
P3005 [USACO10DEC]The Trough Game S题解
首先看到这道题的数据范围就可以想到是枚举暴力。
#算法#题解
P1653 [USACO04DEC] Cow Ski Area G
一句话:输出缩点后的出度为 0 的点的个数和入度为 0 的点的个数的最大值
#算法#题解
Profile Image of the Author
热尘
游戏开发者 · AI 爱好者
公告
欢迎来到我的博客!这是一则示例公告。
分类
标签
站点统计
文章
38
分类
5
标签
12
总字数
46,029
运行时长
0 天
最后活动
0 天前
站点信息
构建平台
GitHub Actions
博客版本
Firefly v6.16.8
文章许可
CC BY-NC-SA 4.0

当前页面没有目录

文章目录

当前页面没有目录