集训Day7
2024-10-20 11:59:01
在做过的试题里ran的...发现之前做的题有些已经生疏了
bzoj3626 LCA
一棵树，每次询问在$[l,r]$区间内的每个节点$i$与$z$的最近公共祖先的深度之和
假的LCA
有一个很平凡的想法是，如果你把x到root这条路径都赋值为1，那$DEPTH_{lca(x,y)}$就是y到root的边权和
我们离线操作
从1到n每个点做一次上述的赋值1+查询的操作就可以了
同时我们注意到$[l,r]$实质上可以化为两个前缀之差
于是这题就做完了
bzoj2946
给你5个串，求他们的最长公共子序列
串长不超过2000
建出第一个串的SAM，后面几个串依次在上面跑，一个串的len取max，五个串的len取min就可以了
bzoj2724（我为什么会ran到这道题
强制在线区间众数
分块，我们用$ZS_{i,j}$表示第i块到第j块的众数
然后注意到我们查找一个数在一个区间里出现次数只用把序列按权值和位置两个关键字排序然后二分查找
这样我们对于完整的块直接询问
不完整的块暴力二分
预处理众数...yy一下就可以了
最新文章
- JavaScript数组删除重复元素（去重）的方法
- c++实现矩阵类矩阵行列式，伴随矩阵，逆矩阵
- 编写一个程序对Largest函数进行测试,找出一组数据的最大值
- Linux VPS 免费管理面板推荐
- hello world of hibernate Annotation
- uva 10655 - Contemplation! Algebra(矩阵高速幂)
- Python网络01 原始Python服务器
- URAL 6089 Nine
- 基于Windows服务的WCF
- DevExpress设置默认皮肤及各种皮肤样式
- java基础编程题练习（二）
- PHP Lumen Call to a member function connection() on null 报错
- 移动电源、3G路由拆机
- Unity3D 批处理场景的工具
- 也谈.Net中间语言——破解Delphi2CS行数和时间限制
- AFNetworking 源码解析
- Win10系列：C#应用控件基础2
- 数据仓库专题19-数据建模语言Information Engineering - IE模型（转载）
- HTML Dog 初级教程中关于 forms 的翻译
- DevExpress 使用条形码二维码控件打印