标签 洛谷 下的文章
- 首页
- 洛谷
[题解]洛谷P2680:运输计划
原题链接:P2680 运输计划总结:树上差分入门好题。题目大意:给出一棵$n$个点的树,边带边权;同时给出$m$条树上路径;允许将一条边的边权钦定修改为0,最小化路径的最大值。考虑暴力,枚举每条边,将其边权暴力修改为0后统计答案。枚举边的复杂度为$O(n)$,暴力dfs统计答案需要枚举$m$条给出的路径,对每条路径暴力求长度,则复杂度为$O(nm)$,总复杂度为$O(n^2m)$,显然不可过...
[题解]洛谷P1189:`SEARCH`
切完这道题我只有一句话想说:DFS要打标……原题链接:P1189 `SEARCH`本题既可DFS又可BFS,输入输出也颇具可视化风格(但样例敲的真心累死),不过首次提交却只有30分,好端端一dfs你给我跑T……那么我也没话可说。暴搜路径这种操作没什么需要注意的。但是打标记就很重要了。经过思考我们可以发现搜索中存在很大重复的部分,在同一深度可能会对一个相同的点进行很多次搜索,极大地浪费了时间,...
[题解]洛谷P1605:迷宫
起因是最近教练讲了DFS,找水题做的时候发现这题我只有40分?!于是就随手把它清算了。原题链接:P1605 迷宫大概是珂以DP的,但是数据范围小的一批用DFS也能3ms搜过去。开一个N*M大小的布尔型标记数组维护能不能走,设计函数dfs(nx,ny)搜索从坐标(nx,ny)到(FX,FY)的路径;显然,对一个点至多有四种走法(上下左右),但需要事先判断合不合法(直接看标记),于是就宏定义一个...
[题解]洛谷P1063:能量项链
原题链接:P1063 能量项链这道题我在数月前曾经试图做过,但是没有什么结果(10分)。现在回顾一下,就先从这个错误的搞法说起。最开始是前置知识~当然这部分肯定是正确的~本题是环,又要进行dp,所以取模显然有点不合适,这时我们拆环为链!怎么做呢?可以将整个串储存两遍,这样,在锁住“截取长度不超过原本环的长度”之后,就能够轻松dp(雾)而不忽略环的特性导致少考虑情况啦~当然,对应地,既然储存了...
[题解]洛谷P2734:游戏 A Game
原题链接:P2734 游戏 A Game本题的大体思路是很明确的,初见有点Nim游戏的意思(当然似乎也能用博弈论搞,只是我太弱了,区间DP都要写一下午),审过之后发现是个比较容易想到的区间dp,只是我的方程似乎和题解的不太一样。这道题有一点非常迷,就是你初见很难看懂它想让你干什么,一旦审错就会GG,收不了。这可能是翻译的锅,毕竟原题出自USACO,洛谷评级为绿题(普及+/提高),我觉得比较客...