泪痕 @ 铁憨憨
辗转当作浮生妖,流离惊似尘世鬼
Stern-Brocot 树与 Farey 序列 Stern-Brocot 树与 Farey 序列
摘要 Stern-Brocot树是一种维护分数的优雅的数据结构。它分别由Moritz Stern在1858年和Achille Brocot 在1861年发现这个结构。 概述Stern-Borcot 树从两个简单的分数开始: \frac{
2019.07.17
约瑟夫问题 约瑟夫问题
摘要 约瑟夫问题由来已久,而这个问题的解法也在不断改进,只是目前仍没有一个极其高效的算法(log以内)解决这个问题。 问题描述 n个人标号 逆时针站一圈,从 号开始,每一次从当前的人逆时针数 个,然后
2019.07.16
[Luogu2022] 有趣的数 [Luogu2022] 有趣的数
摘要 题意:Q(N,K) 表示把 1-N 按字典序从小到大排列后 K 的排名。给出 K,M,最小化 N,且 Q(N,K)=M. 无解输出 0。 一道思路很清奇的题。首先可以想到这些结论: 关于 i 单调递增(非严格)
2019.06.08
[POI2011]LIZ-Lollipop [POI2011]LIZ-Lollipop
摘要 题意:给一个只有 1 和 2 的序列,每次询问有没有一个子串的和为 x. . 一道很考人的思维题。暴力的思路就是直接预处理前缀和,然后每次 查询前缀和的差. 注意到这个序列只有 0 和 1
2019.04.05
[POI2010]GIL-Guilds [POI2010]GIL-Guilds
摘要 之前文化课要准备月考,颓了一会儿 Hexo 博客配置,现在考完了,刷点水题恢复一下 给一张无向图,要求你用黑白灰给点染色,且满足对于任意一个黑点,至少有一个白点和他相邻;对于任意一个白点,至少有一个黑点与他相邻,对于任意一个灰点
2019.04.02
讲题 讲题
摘要 Day2T1 无向图对每种权值判断是否有边(没边就做完了),每次删边判连通 50 分直接计算,复杂度 . 从小到大枚举权值 动态图问题,要求支持加边,删边,问图是否连通 如果只有加边,可以用并查集判断是否连通 发现在
2019.03.07
杂题整理 杂题整理
摘要 水题泛做 ZROIZROI332 摆花 对于一个整数序列和 m 个区间,定义序列的某一区间 的价值为 (即 sg 函数的 mex). 而这个序列的价值定义为这
2019.03.05
构造题自闭 构造题自闭
摘要 鸽鸽给我们讲课啦 竞赛中有一类要求构造特定解的题,被称为构造题 构造题没有固定的套路,它要求选手对该领域知识有深层次的理解 URAL1979 对于一个 阶的魔方,要求把
2019.03.02
二分小结 二分小结
二分概述二分不同于分治,它根据问题的单调维度求解的特点,在该维度上折半查找答案,使复杂度系数由 降低到 . [TJOI2007] 路标设置求最大距离的最小值,典型的二分答案 #include<bit
2018.12.19
搜索小结 搜索小结
搜索概述搜索问题的解,其实就是在问题对应的状态空间中进行映射与遍历. 使用递归,循环,数据结构等对状态空间的单调性,对称性,有解性进行排列归纳,加以搜索,以快速找到问题的答案 LuoguP1120 小木棍DFS 剪枝,在洛谷的毒瘤时间范围下
2018.12.19
单调队列小结 单调队列小结
单调队列故名思义,单调队列旨在维护一个队列,其中元素始终以某一关键字单调的顺序排列 单调队列的思想广泛用于最优解的维护,用于优化 1D/1D 动态规划 朝花中学 OI 队的奋斗历程——浅谈单调队列 [NOIP2016] 蚯蚓优先队列每次取最
2018.12.19
贪心小结 贪心小结
小 TAG观察(贪心思路) 猜测(减少决策数量) 证明(从最优解转化为贪心解,并且不改变最优性质,从而证明) 多个贪心组合 贪心与非线性算法 贪心的单调性 贪心性质 贪心算法是一种形式及其多样的算法。它的应用方式很广,简单的简单,难的难。
2018.12.19