Rockdu's Blog
“Where there is will, there is a way”
亲 您的浏览器不支持html5的audio标签
Toggle navigation
Rockdu's Blog
主页
数据结构
字符串算法
图论
数论、数学
动态规划
基础算法
[其它内容]
计算几何
科研笔记
归档
标签
小马恶魔城：D 希望
? 解题记录 ?
? 洛谷 ?
? 点分治 ?
? 贪心 ?
? 哈希 ?
? stl ?
2018-10-06 17:42:56
461
0
0
rockdu
? 解题记录 ?
? 洛谷 ?
? 点分治 ?
? 贪心 ?
? 哈希 ?
? stl ?
# 题解 for D：希望 [D.pdf](http://leanote.com/api/file/getAttach?fileId=5bb6b276ab644123c7001160) 我们来看看这道题的部分分： 首先明确本题的贪心策略：一旦有放置魔法符文的方案就放，这个贪心策略是显然正确的。 对于$Subtask1$：枚举树上$O(N^2)$条路径，每一条路径都$O(N)$判断是否可以用于激活点。总复杂度：$O(N^3)$。 对于$Subtask2$：不难发现我们可以将判断和枚举放到一起——我们枚举每一个点作为魔法符文的放置端点，然后向外延伸。这样同样可以枚举出所有满足条件的路径，总复杂度降为$O(n^2)$。 但是这样的做法在随机数据下表现十分优秀，因为剪枝非常充分，所以本题使用了$Subtask$，23333 。 暴力已经不能往下继续了，那么接下来的问题就来了。 ## 如何优化？ 处理树上的路径问题，我们可以采用点分治。 现在我们着重考虑在一层分治内怎么做，也就是处理经过一层重心的所有路径怎么做。 考虑用魔法符文激活树上点的这个过程是十分麻烦的，我们可以从结果来考虑。发现最后的结果一定是从重心向下参差不齐地延伸的。 进一步考虑，我们定义一个点$u$从根到自己的路径组成的符文串叫$s_u$，自己到根的路径组成的符文串叫$p_u$。 那么一个$u$可以被覆盖当且仅当以下两种情况： 1、$s_u$是魔法符文串的一个后缀，且在其他子树中存在$v$满足$p_v$是$s_u$对应的前缀。 2、$p_u$是魔法符文串的一个前缀，且在其他子树中存在$v$满足$s_v$是$p_u$对应的后缀。 匹配前缀和后缀，我们使用哈希预处理，$long long$自然溢出，使用$map$即可做到$O(logN)$查询。如果我们依次处理一层内的所有子树，复杂度为$O(NlogN)$。总的复杂度为$O(Nlog^2N)$。 将$map$改为手写哈希或者$unordered\_map$，复杂度降为$O(NlogN)$。但是由于常数太大，实际效果不佳。 同时，本题如果询问最少用多少次符文也是可以做的，为了降低比赛难度(~~其实是出题人懒qwq~~)没有更深入，大家可以稍作思考。
上一篇:
小马恶魔城：C 逃亡
下一篇:
小马恶魔城：E 最后的斗争
0
赞
461 人读过
新浪微博
微信
腾讯微博
QQ空间
人人网
提交评论
立即登录
, 发表评论.
没有帐号?
立即注册
0
条评论
More...
文档导航
rockdu
Rockdu's Blog
没有帐号? 立即注册