主页 · 3
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 题解
一道有趣简单的构造题。

