Asahana_Yuho
把原来放在 Luogu 博客的一些博文拿了过来。
都是一些个人感觉有点意思的题。
当然也有一些无聊题。。。
笔记
-
- 其实就是主定理推导，不过没有运用定积分这些不太初中的方法
- 初中生应该就能看懂了吧？
数据结构题
P7706 「Wdsr-2.7」文文的摄影布置
- 线段树题，对理解线段树传参比较有帮助。
P4211 [LNOI2014]LCA
- 离线转化神题
P6647 [CCC 2019] Tourism
- 线段树加单调栈优化 DP
- 用 $\infty$ 减少讨论
CF438D The Child and Sequence
- 取模操作次数有限，支持局部暴力
- 类似的题 P4145 上帝造题的七分钟 2 / 花神游历各国，这里开根的次数是有限的
P4137 Rmq Problem / mex
- 线段树上二分
P5103 [JOI 2016 Final]断层
- nb 题
- 一个基本的斜化直的思想
P3253 [JLOI2013]删除物品
- 一个两栈顶相接的思想（简化模拟）
P4587 [FJOI2016]神秘数
- 求 $\operatorname{mex}$ 就要往值域上考虑
- 利用好指数级的增长性，不要怂
P4216 [SCOI2015]情报传递
- 复习（真的有点忘了）
P1972 [SDOI2009]HH的项链
- 一个必须掌握的统计思想
P5677 [GZOI2017]配对统计
- 奇妙的计数思想
P4588 [TJOI2018]数学计算
- 小思维题
图论题
P6175 无向图的最小环问题
P1613 跑路
- 位运算类最短路，建立单位 $2^k$ 边
P6833 [Cnoi2020]雷雨
- 最短路建模
P6066 [USACO05JAN]Watchcow S
- 无向图欧拉回路（带回走的）实际就是在有向图上跑 Hierholzer
P3199 [HNOI2009]最小圈
- 论文题
- 有标准 $O(nm)$ 做法
DP 题
P5336 [THUSC2016]成绩单
- 以值域定义状态
P1758 [NOI2009] 管道取珠
- 从意义上解决计数题
P2467 [SDOI2010]地精部落
- 转换视角计数
P5664 [CSP-S2019] Emiya 家今天的饭
- 容斥 DP
- 复习
CF11D A Simple Task
- 状压 DP
- 图上的一个小技巧
P2704 [NOI2001] 炮兵阵地
- 状压 DP
- 三进制状压
P5024 [NOIP2018 提高组] 保卫王国
- 倍增优化 DP
- 然而我写得很屑
P3188 [HNOI2007]梦幻岛宝珠
- 分组 DP
- 状态合并
P6647 [CCC 2019] Tourism
- 数据结构优化 DP
P1950 长方形
- 线性结构优化 DP
- 略带一点转化技巧
P2473 [SCOI2008] 奖励关
- 期望 DP
P5369 [PKUSC2018]最大前缀和
- 状压 DP
P4163 [SCOI2007]排列
- 套路状压 DP
- 一类有关数字整除的 DP
P2607 [ZJOI2008]骑士
- 基环树最大独立集
P1552 [APIO2012]派遣
- 可并堆优化 DP
P1450 [HAOI2008]硬币购物
- 完全背包容斥实现物品数较少的多重背包
P3216 [HNOI2011]数学作业
- 动态构造矩阵转移
P1081 [NOIP2012 提高组] 开车旅行
- 倍增优化 DP
T189318 C. 数学题【NOIP 计划 · 模拟赛 #1】
- 赛题
- 一个 Trivial 的 DP 技巧？
字符串
P7114 [NOIP2020] 字符串匹配
- ExKMP
- DP
- 复习
贪心
P5665 [CSP-S2019] 划分
- 比较难想
CF939E Maximize!
- 不太显然的贪心
P3574 [POI2014]FAR-FarmCraft
- 比较神奇的贪心
P2168 [NOI2015] 荷马史诗
- Huffman 树类贪心
P1966 [NOIP2013 提高组] 火柴排队
- 贪心小技巧
- 一个有关逆序对的结论
杂题
P6902 [ICPC2014 WF]Surveillance
- 环上倍增
- 类似题目 P4155 国旗计划，区别在于这题需要三倍断环为链
CF1548A Web of Lies
- 小 Trick 题，从结果的角度思考（或者说是现象）
- 想起来一个数学题，$n$ 个屋子里人员流动，平方和公式的递增性解释
CF1542B Plus and Multiply
- 同样是小 Trick
- 转换变量与系数观察
P7567 「MCOI-05」魔仙
- 打表找规律
- 利用奇偶性
- 构造
- 待定系数
- 总之很神奇的小学奥数题
P7077 [CSP-S2020] 函数调用
- 神奇题
P5023 [NOIP2018 提高组] 填数游戏
- 神奇题
- 打表找规律
P2717 寒假作业
- CDQ 分治
CF1148F Foo Fighters
- 神奇构造题
- 按位考虑，消除后效性
P7115 [NOIP2020] 移球游戏
- 神奇构造题
- 复习
CF1103C Johnny Solving
- 神奇构造题
- 一般图构造常用技巧（生成树）
CF468C Hack it!
- 神奇构造题
- 消除后效性
P5411 【XR-2】伤痕
不可做构造题- 图上的构造：对称，等差，均摊，奇偶变换
CF1567C Carrying Conundrum
- 思维题
- 转换视角，就是奇偶分开的加减法
AT4142 [ARC098B] Xor Sum 2
- 小思维题
- 对 xor 的理解
AT5759 ThREE
- 构造题
- 图上构造技巧：二分图染色
P4219 [BJOI2014]大融合
- 离线替代 LCT 的一类树剖方法
P1600 [NOIP2016 提高组] 天天爱跑步
- 树上计数
- 复习
P5553 电学实验
- 数学题
CF632D Longest Subsequence
- 调和级数复杂度分析
P4139 上帝与集合的正确用法
- nb 题
- 同样是化无限为有限
P2568 GCD
不就是 YY 的 GCD 吗- 不用反演的知识解决
P1226 【模板】快速幂||取余运算
- 光速幂
- 讲了一个适应更大幂运算的小技巧
CF582A GCD Table
- 由大到小不断确定解的过程
P1168 中位数
- 中位数维护技巧
P3166 [CQOI2014]数三角形
- 组合计数题
P2746 [USACO5.3]校园网Network of Schools
- 一个 DAG 式的环构造
P1318 积水面积
- 套路单调栈（复习）
P1429 平面最近点对（加强版）
- 分治统计
- 当板子题
T189317 B. 有向图【NOIP 计划 · 模拟赛 #1】
- 构造题
- 图上构造技巧：度数奇偶讨论
P1197 [JSOI2008]星球大战
- 逆向思维的一个小 Trick
- 好像挺 Common 的
CF1438D Powerful Ksenia
- 构造题
- 奇偶讨论的技巧
P2680 [NOIP2015 提高组] 运输计划
- 树上差分与二分
AT4168 [ARC100C] Or Plus Max
- nb 题？
P5666 [CSP-S2019] 树的重心
- 重心相关性质
P3629 [APIO2010]巡逻
- 树的直径相关性质
P1395 会议
- 很无聊的一个技巧
P7073 [CSP-J2020] 表达式
- 普及题
- 很无聊的技巧但我当时没做出来
P5836 [USACO19DEC]Milk Visits S
- 普及题
- 一个巧妙的并查集思路