ywy_c_asm题
2024-08-24 16:14:10
未知出处
题意:
定义一个无穷长的数列,满足以下性质:
$1.X_{2n}=-{X_{n}}$
$2.X_{2n}=(-1)^{(n+1)}*X_{n}$
$3.X_{2n-1}=(-1)^{(n+1)}*X_n$
1e5个询问,求:
$1.X_k$
$2.S_k$即前缀和
(大概是这样)
画一画递推式的图,或者观察2n,n可以看到转移类似一个二叉树。
第一个点要特判
树高logn
左右儿子有不同的边权
可以类似二进制差分,一路走到$X_k$即可求出第一问
第二问,
发现是一个连续的子树块
往1点走,发现可以把两边的子树分别算上,而且都是完全二叉树!
可以dp[deep][0/1][0/1]表示深度为deep的完全二叉树的根节点权值-1/+1,奇偶性0/1时,子树的和(这个是固定的)
logn走一下即可。
特判1点
最新文章
- js,jquery,css,html5特效
- 版本管理工具SVN
- ThinkPHP动态版本控制
- Server Name Indication(SNI)
- ARCGIS如何进行可视域分析
- [Android Pro] android 4.4 Android原生权限管理:AppOps
- 使用forever管理nodejs应用
- support HTML5 in IE8
- Java:静态代理 and 动态代理
- 团队作业 -- beta版本
- php编译安装参数说明
- log4net面面观之Repository
- C语言的本质(19)——预处理之一:宏定义
- 虚拟机在 OpenStack 里没有共享存储条件下的在线迁移[转]
- putty完全使用手册--多窗口---git提交---连接数据库--自动日志显示
- WIN下的Django安装
- Matlib
- web前端(4)—— 常用标签1
- 小程序flex容器
- 从统计局采集最新的省市区县数据,纯js
热门文章
- Ping隧道
- 使用python中读取配置文件
- Cannot assign requested address (connect failed)
- 题解 CF191C 【Fools and Roads】
- [Clr via C#读书笔记]Cp13接口
- 深度学习笔记 (二) 在TensorFlow上训练一个多层卷积神经网络
- 冥冥中转到了mac 上进行开发
- window.open()与window.showModalDialog区别
- 八:The YARN Timeline Server
- “Hello World!”团队第三周召开的第一次会议