【arc072e】AtCoder Regular Contest 072 E - Alice in linear land
2024-10-07 23:53:39
题意
给定一个D,以及一个长度为N的序列a,顺序执行这些数字:
对于一个数字x,会使得D=min(D,abs(D-x))
有Q次询问,每次询问独立,给出i,能否修改a[i],使得D最后不为0.
n,q<=500000
解法
我们设Low[i],表示当前D执行i+1..n的数字之后,不为0的最小值。
我们知道,对于每一次询问i,
求出前i-1个数字执行后的结果D,
通过修改a[i],我们可以使得D变成[1,D],
那么如果D>=Low[i+1]就回答"YES",否则回答"NO"。
现在问题变成了怎样求出Low数组,
\[边界:Low[n+1]=1,
Low[i]=Low[i+1]+a[i]*(a[i]<2*Low[i+1])\]
当a[i]<2*Low[i+1]时,这次的数字操作有效,
为了走到Low[i+1],所以Low[i]要加上a[i].
最新文章
- angularJS: shop chart
- hdu 1712, multiple-choice knapsack, 分类: hdoj 2015-07-18 13:25 152人阅读 评论(0) 收藏
- Java 多线程submit和execute
- [工具]IL Mapper2(C# ->; IL 转换器)
- Java日志终极指南
- uvc摄像头代码解析5
- 使用HTML5 Canvas做些什么
- What is the difference between Debug and Release in Visual Studio?
- python为运维人员打造一个监控脚本
- [LeetCode] Increasing Subsequences 递增子序列
- 为什么「margin:auto」可以让块级元素水平居中?
- Cesium 中阻止镜头飞至地表以下
- Spring Cloud学习资料
- TensorFlow实战Google深度学习框架5-7章学习笔记
- 把ResNet-L152模型的ckpt文件转化为pb文件
- JavaScript大杂烩12 - 理解Ajax
- 2017ACM/ICPC广西邀请赛-重现赛
- day 018 面向对象--约束和异常处理
- laravel 5.1 使用Eloquent ORM 操作实例
- 在CentOS上编译安装MySQL 5.7.13步骤详解