咕了两天 blog 了,原因是都在颓废。
P5410
是 \(Z\) 函数的板子!
它与 \(KMP\) 的思想差不多,同时我认为它更接近 \(manacher\),都是由之前的转到当前的,再进行总复杂度 \(\Theta(n)\) 的暴力check。
P3407
非常简单的似乎没什么算法的题,\(\Theta(n)\) 扫两遍,第一遍正着扫求出向西走的最远距离,第二遍倒着扫求出想东走的,然后就可以轻松求出每个询问的答案了。多亏了 \(\color{Black}{c}\color{Red}{xz\_0}\) 给我拍了一下,让我发现我没有开 \(longlong\),差点见祖宗了。
P5673
跟 HH的项链 差不多,算是加强版吧,预处理了一大坨指针并用线段树草过去了。
P7519
状压 DP,有非常优雅的、我在 \(NOIp\) 考场上绝对想不出来的技巧。
令 \(\large{f_{s,i,j}}\) 表示当前已经揭露了 \(b\) 的队伍的集合(包括 \(i\)),当前揭露的是 \(i\)(一定要注意当前揭露的 \(i\) 会排到第一名啊啊啊啊啊啊啊啊啊),\(\large{j = \sum b}\),表示的是目前全局(包括 \(s\) 之外的)总共加的 \(\large{b}\)。
这就有点类似于 关路灯,在某个状态中考虑全局费用,这好像叫费用提前计算。
我们会发现,这样设计状态就可以通过直接计算与上一个第一名的题数差值来转移,而不用考虑 \(b_i\) 的单调了,因为我们每一次转移时就会给还未揭榜的队伍加上当前加上的 \(b\) 值,这就相当于是枚举差分数组了。
注意 若两支队伍过题数相同,则编号小的队伍排名靠前。
这个条件。
原文地址:http://www.cnblogs.com/cotsheep/p/16913170.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性