当前位置:网站首页>【学习笔记】线段树选做
【学习笔记】线段树选做
2022-07-07 10:59:00 【仰望星空的蚂蚁】
全是暴力
打线段树好累
Fibonotci
一看这个线性递推关系显然是矩阵乘法
码码码 。。。
呼 。。写完了 。
Two Permutations
序列 hash ?
毋宁称之为线段树维护序列 hash 值的好题
类比 Permutation 。本质在于将复杂状态用一个整数表示,这样复杂度更优 。
Strange Addition
显然线段树维护 dp 。
注意细节 。以及不要算重 。
如果实现精细的话可以不用去前导零。轻微卡常。
Strange Array
膜拜 wicton 。
这题做法没那么明显 。
考虑从 [i,i] 进行扩展
分区间奇偶性讨论
考虑一个 < a i <a_i <ai 的数和 > a i >a_i >ai 的数会抵消
把 a i a_i ai 看成 < a i <a_i <ai 和 > a i >a_i >ai 两种情况考虑两次,这样不会出现相等的元素
将 ≤ a i \leq a_i ≤ai 的数看成 1 1 1 , > a i >a_i >ai 的数看成 − 1 -1 −1
分别向左右扩展 ,找最大子段和 a n s ans ans ,贡献为 ⌊ a n s − 1 2 ⌋ \lfloor\frac{ans-1}{2}\rfloor ⌊2ans−1⌋
将 ≥ a i \geq a_i ≥ai 的数看成 1 1 1 , < a i <a_i <ai 的数看成 − 1 -1 −1
分别向左右扩展 ,找最大子段和 a n s ans ans ,贡献为 ⌊ a n s 2 ⌋ \lfloor\frac{ans}{2}\rfloor ⌊2ans⌋
码码码 。。。
呼 。。写完了 。
Phoenix and Memory
行百里者,半九十 。
首先贪心求一组方案
如果要得到不同的序列的话,一定存在 ( i , j ) (i,j) (i,j) ( i ≠ j ) (i\ne j) (i=j)使得 l i ≤ a j ≤ r i l_i\leq a_j\leq r_i li≤aj≤ri 并且 l j ≤ a i ≤ r j l_j\leq a_i\leq r_j lj≤ai≤rj
感性理解的话,如果你在贪心的最优方案上换的越多,方案也就更劣 。
证明略了 。
边栏推荐
- 【Presto Profile系列】Timeline使用
- layer弹出层的关闭问题
- HZOJ #240. Graphic printing IV
- The difference between cache and buffer
- How does MySQL create, delete, and view indexes?
- NPM instal reports agent or network problems
- Leetcode brush questions: binary tree 19 (merge binary tree)
- ICLR 2022 | 基于对抗自注意力机制的预训练语言模型
- Design and implementation of communication protocol
- visual stdio 2017关于opencv4.1的环境配置
猜你喜欢
opencv的四个函数
Blog recommendation | Apache pulsar cross regional replication scheme selection practice
红杉中国完成新一期90亿美元基金募集
Talk about four cluster schemes of redis cache, and their advantages and disadvantages
2022 examination questions and online simulation examination for safety production management personnel of hazardous chemical production units
Smart cloud health listed: with a market value of HK $15billion, SIG Jingwei and Jingxin fund are shareholders
Leetcode skimming: binary tree 21 (verifying binary search tree)
ACL 2022 | small sample ner of sequence annotation: dual tower Bert model integrating tag semantics
Leetcode brush question: binary tree 24 (the nearest common ancestor of binary tree)
MySQL master-slave replication
随机推荐
[learn microservices from 0] [03] explore the microservice architecture
Ip2long and long2ip analysis
API query interface for free mobile phone number ownership
环境配置篇
How does MySQL create, delete, and view indexes?
.Net下极限生产力之efcore分表分库全自动化迁移CodeFirst
谷歌浏览器如何重置?谷歌浏览器恢复默认设置?
.Net下极限生产力之efcore分表分库全自动化迁移CodeFirst
飞桨EasyDL实操范例:工业零件划痕自动识别
滑轨步进电机调试(全国海洋航行器大赛)(STM32主控)
[difficult and miscellaneous]pip running suddenly appears modulenotfounderror: no module named 'pip‘
详解ThinkPHP支持的URL模式有四种普通模式、PATHINFO、REWRITE和兼容模式
opencv的四个函数
SSM框架搭建的步骤
基于鲲鹏原生安全,打造安全可信的计算平台
. Net ultimate productivity of efcore sub table sub database fully automated migration codefirst
Master公式。(用于计算递归的时间复杂度。)
The URL modes supported by ThinkPHP include four common modes, pathinfo, rewrite and compatibility modes
HZOJ #236. Recursive implementation of combinatorial enumeration
@What is the difference between resource and @autowired?