何曾有丶飞的梦想

POJ刷题记录

CCF(6) C语言(1) git(1) Java(3) Linux(3) PAT(7) python(1) 分层图(1) 区间操作(2) 可持续化数据结构(1) 图论(2) 数学(1) 最近公共祖先(1) 汇编(1) 算法(6) 英语(2) 蓝桥杯(1) 计算机组成原理(1) 计算机网络(1) 题解(1)

/ 注册

全部文章 / POJ刷题记录（共21篇）

POJ 1324 BFS+二进制状态标记

STL容器开在函数体内和体外还能卡超时？涨姿势了 #include<iostream> #include<cstring> #include<queue> using namespace std; const int maxr = 30, maxc = 30...

2019-12-25

0 665

POJ 2449 A*+最短路

是的不压行就不会作死，当你调试半天调不对的时候一般是你很sb的随手打错一行你以为肯定不会错的代码，就当锻炼纠错能力了(本质还是菜。。) #include<iostream> #include<cstring> #include<queue> using na...

2019-12-19

0 552

POJ 1724 分层图最短路

分层图的两种建法 1：直接建k-1层图 2：给dis或vis或你需要记录信息的数组额外增加一维模拟n层图的效果至于分层图的理解，个人认为就是有一些干扰信息时，比如免费经过一些路径或者有特殊限制的时候，可以从当前图免费跳到下一层或上一层图来转换状态。 #include <cstdio...

2019-12-18

0 410

poj 生日蛋糕剪枝+dfs

头一次见这么夸张的剪枝操作。这个点也很难想 2*r*h=S * r*r*h=V * => V*2/r = S S + sumS >= best => return; #include <cstdio> #include<algorithm> ...

2019-12-18

0 523

POJ 1376 bfs

建图的方式有点特别，建在方格的四个顶点处 vis三维数组，第三维记录走过节点的方向 #include<cstdio> #include<cstring> #include<queue> #include<algorithm> #include&...

2019-12-17

0 563

POJ1475 双bfs 找最短路

第一层bfs找箱子移动的最短路，第二层找人到箱子后边位置的最短路。难点可能是第一层bfs的vis数组需要开三维，需要同时记录走过点的方向。其实字符串的处理，路径输出也很恶心。。。属于稍微有点错就得调半天那种 #include<iostream> #include<alg...

2019-12-16

0 663

POJ 3190 Stall Reservations 贪心算法

优先队列模拟处理一下 #include<cstring> #include<cstdio> #include<algorithm> #include<queue> using namespace std; const int maxn = 1e5...

2019-12-12

0 509

POJ 1390 Blocks 区间DP

区间DP的核心：把大区间分解成相同规模的小区间，小区间返回子结构的值给大区间从而得到最优解。但是怎么就能根据不同的题模拟出特定的比较合适的子结构呢？我觉得与其说这是一种编码的熟练度问题，不如说是对实际问题建模的敏感度问题。如何设计优秀的子结构问题真的很考验一个人的最基本最核心的创造力和分析能力，刷题...

2019-12-12

0 638

POJ 2373 Dividing the Path 单调队列dp

两个队列 p和q p存储当前所有已经访问过的节点 q对p中的节点进行筛选选出可以对当前节点进行状态转移的节点，头节点就是最小值，维护这两个队列，时间复杂度就可以降下来但是不清楚为什么模拟队列的时候永远是h = 1，t = 0 #include<iostream> #incl...

2019-12-12

0 449

POJ 炮兵阵地 (状态压缩dp)

真的很难，状态转移方程太难推了，智商不够，努力来凑 #include<iostream> #include<algorithm> #include<cmath> #include<cstring> using namespace std; cons...

2019-12-10

0 477