ZR提高失恋测3
ZR提高失恋测3
(感觉这一场比以往的简单了一些)
估分 100 + 40 + 40
得分 100 + 60 + 40
???
A
首先,我们能够想到一个比较简单的\(n^2\)做法,
枚举答案子序列中两个\(1\)之间\(0\)的个数(就是题目中的距离),直接贪心能选就算,肯定不会似的答案更劣
这样就有了\(60\)分的好成绩
我们考虑如何优化这个暴力,
由于0的个数不具有可二分性,所以不能对外层枚举进行优化,那么我们只能对这内层循环下手了
发现我们每次暴力找\(x\)的\(0\)这个过程太慢了,我们想到两个方式去优化
首先 二分
我们维护一下前缀\(1\)的个数
每次二分查找一下下一次跳\(x\)次\(0\)的位置
其次
倍增,感觉道题同二分把,把\(x\)二进制拆分然后求\(k\)级祖先
注意写代码的时候有一个需要一个细节,就是如果最后一个匹配成功的是\(1\)
或者最后一段的\(0\)没有匹配满的时候,最后一个的\(100\dots\)的贡献是要减去的
B
首先这个\([dis,1.1\times dis]\)就肯定要搞点东西
首先,还是非常朴素的暴力,我们对于每个点,都去维护一下到这个点的所有的路径的长度
然后暴力合并
之后读进来一个询问点就暴力lower_bound一下判断合法不合法,这样就有60分了
我们上面的暴力并没有用到\(1.1\times dis\)这个东西,我们仔细想一下有什么用?
如果一个点有三条路径\(x,y,z\)满足
\(\frac{z}{1.1} <x < y < z\)
那么\(y\)这一条路径是没有用的
因为
也就是\(y\)的功能能够完美的被\(x,z\)去代替
这也就提示我们需要存的路径不会太多,那么有多少呢
我们发现上面的情况
\(1.1 ,1.1^2 ,1.1^3,\dots 1.1^x\)
极限情况也要是这样的数列才不会出现上面的情况
而\(1.1^{450} > 10^{18}\)
所以一个点的合法路径条数不会超过\(450\)
我们可以考虑去只维护合法的部分
我们维护一个递增的数组表示路径
每次对于一条边\(x->y\)
我们直接把两个数组类似归并排序的方式合并就好了
只要在合并过程中出现
上面\(x,y,z\)的情况,就把\(y\)踢掉
最后依旧二分查一下答案就好
C
大分类讨论
先咕咕咕
最新文章
- 深入浅出设计模式——原型模式(Prototype Pattern)
- android sdk 更新那些文件
- [转载] Android中Xposed框架篇---利用Xposed框架实现拦截系统方法
- Numpy中的矩阵合并
- 基于XMPP的即时通信系统的建立(四)— 组件介绍
- Effective C++ 第二版 5)new和delete形式 6) 析构函数里的delete
- php call_user_func和call_user_func_array
- 从MSSQL server 2005中移植数据到Oracle 10g
- 高阶自定义View --- 粒子变幻、隧道散列、组合文字
- MongDB开启权限认证
- 自定义Retrofit转化器Converter
- idea使用错误及技巧总结合集(一)
- 自己练习的一个小的demo的时候a标签关于href链接的问题
- Ubuntu英文变为中文
- 【转】Windows系统中ckplayer视频边下边放,视频转码mp4及";last atom in file was not a moov atom";问题
- jquery中对父节点和子节点的利用
- Hyperledger超级账本在Centos7下搭建运行环境
- 分段覆盖率TPR
- java.lang.NoSuchMethodError: No static method getFont
- ElasticSearch入门 第四篇:使用C#添加和更新文档