noi.ac 第五场第六场
2024-10-08 15:33:56
t1应该比较水所以我都没看
感觉从思路上来说都不难（比牛客网这可简单多了吧）
第五场
t2:
比较套路的dp
f[i]表示考虑前i个数，第i个满足f[i]=i的最大个数
i能从j转移需要满足
j<i ai>aj i-j>=ai-aj
比较easy的套路就是由2,3可以推出1
于是按照ai排序再拿个树状数组维护就行了
t3:
考虑一段编号能否成立
等价于求树链的并
然后发现对于l1>l2 r1>=r2 也就是说右端点单调
于是我们考虑做two-point-two
至于树链的并就看sdoi寻宝游戏那题吧
第六场
t2:
首先比较显然的dp方程是
f[i][i1][i2][i3][i4]
表示当前在i层，第x块木头隔了ix
转移是O(1)枚举的
这样时间复杂度n*h^4
然后我们注意到有一层一定差了1
于是f[i][i1][i2][i3][i4]
其中i1记录差了1的是第几层，然后后面三维按顺序
注意这样还不行，我们还得记录不能到达目标的情况
所以每一维都+1（到达上限说明不能到达）
其实因为我们并不关心当前到底在哪一层
所以i1 0/1表示当前放的那个点能不能到达就可以了
t3:
这题放在t3水了
考虑枚举r
那么当r移动的时候只有一个颜色的改变
所以我们支持区间+1，区间-1，区间求和
询问的话离线下来就可以了吧
nlogn
最新文章
- office 2010 word每次启动都需要配置
- Ubuntu 14.04 下 Chromium 出现 未安装Adobe Flash Player 问题解决
- zepto阻止事件冒泡
- Delphi编程建议遵守的规范1---缩进、各种语句的用法
- 《Linux内核分析》第一周 计算机是如何工作的？
- 构造函数模式自己定义js对象
- SqlServer将表中数据复制到另一张表
- Magento 前台的logo更改
- Nodepad ++
- Android应用开发-小巫CSDN博客clientJsoup篇
- JavaScript模式读书笔记 文章3章 文字和构造
- 前端笔记之ES678&Webpack&Babel（上）初识ES678&Babel&let和const&解构&语法
- Node.js如何执行cmd
- 微信中音乐播放在ios不能自动播放解决
- Vant UI 安装
- Python读取一个目录下的所有文件
- suricata 配置文件threshold
- Asp.Net配置不允许通过url方式访问目录下的资源
- Guava HashMultiset（MultiSet）
- 高性能分布式哈希表FastDHT