Turn Off The Light HDU - 6307
题目大意
是有n个位置有灯,告诉你每个位置灯是开着的还是关着的,告诉你你的初始位置p,你可以往左或者右移动一步(在1到n的范围里移动),
并且在移动后必须按下开关(就是使当前打开的灯关上,当前未打开的灯打开),求出使得所有灯都关上的最少移动步数z[p],
求出p为1-n时所有的答案,输出sum{z[i]*i} %(1e9+7)(1<=i<=n)
首先我们看对于起点为最左边的点,我们可以贪心地往右走,就是若当前的位置为1,那么我们往右走一步再往左走一步走到原来的位置,那么此时的位置上1就变成0了,后一个位置的值取反,若是再往后走,那么后一个位置又会变为自己之前的值;若当前位置为0,就直接往右走一步。直到右边没有1了。
比如111 '1'11 ->1'0'1->'0'01->0'1'1->01'0'->0'0'0 单引号表示当前所在的位置,那么我们可以知道对于111,p=1的情况,z[p]=5
若是我们初始位置p是在中间的话,那我们可以选择先往左走到最左边的点,然后按照上面的方法再做一次,或者先走到最右边的点,重复上面的方法走,取这两种走法的最优值就是z[p]的值了。
那么我们就可以很容易地知道一个O(n^2)的做法了。(就是模拟上面说的走法)
至于怎么优化到O(n) 就是疯狂前缀和了。
我们仍先假设p为最左边的点,我们设最后一个出现的1的位置是last,那么我们需要统计的是(last-p)+2*(走到该点时为1的点的数量),那么重点就是统计在从p走到last的图中有多少个点在被走到时为1。那么我们将所有的s[i]^1以后计算前缀异或和(因为走到这个点这个点必须要改变,所以我们直接算异或1以后的前缀异或和),这就是我们需要统计的值。最后判断一下p-1点的前缀异或就可以知道我们需要累计的答案是哪一部分了。
至于p为中间的点时,我们再算s[i]的前缀异或,这样在先走到一端时,我们可以把走过的部分都取异或,然后和不变的部分拼接起来,按照和之前一样的方法计算就可以了
转载至https://blog.csdn.net/BinGoo0o0o/article/details/81190093
上面这个链接写的是思想,代码的细节这个博客写的更好 https://blog.csdn.net/qq_18869763/article/details/81193622
最新文章
- 监听JVM的几个命令(可用于linux 本机)
- php如何妩媚地生成执行的sql语句
- android 获取当前位置
- Orace数据库锁表的处理与总结<;摘抄与总结三>;
- tasklet和工作队列
- 编译kernel:配置
- 【Java学习笔记之十一】Java中常用的8大排序算法详解总结
- 细说Web页面与本地电脑通讯
- list转换string
- deepin 开机进入 initramfs,无法开机
- [Android] Android 类似今日头条顶部的TabLayout 滑动标签栏 效果
- bootstrap 使用总结
- Linux下clock计时函数学习
- duilib进阶教程 -- TreeView控件(6)
- 使用Python自带difflib模块进行文件内容差异对比
- TCP长连接保持连接状态TCP keepalive设置
- 福大软工1816 &#183; 评分结果 &#183; Alpha冲刺
- ECharts 与struts的后台交互之柱状图
- CSDN专栏收集
- 【传输协议】发送https请求,由于客户端jdk版本过高,服务端版本低。导致异常:javax.net.ssl.SSLHandshakeException: Server chose SSLv3, but that protocol version is not enabled or not supported by the client.