chx2026-07-31
一种在多路径前提下计数不同结果数量的方法
记录一类统计结果的计数题的方法 很多题目就是初始给你一个对象，然后就是你可以对这个对象进行若干次操作，然后问你能有多少结果 这一类题目就是会遇到非常棘手的情况，就是可能有多个生成路径能生成同一个结果，然后统计路径就是会记重的，基本的做法 …
标签浏览
ideas(of oi)
这里包含当前标签及其所有子标签下的文章。
2026-07-31
一种用点分治来解决双树型限制问题的做法
简述题面： 你有两棵树，$T_1$ ，$T_2$ ，然后你需要对于每个点求出 $\min_{j\not=i}(dist(T_1,i,j)+dist(T_2,i,j))$ 要求时间复杂度 $O(n\log^2 n)$ 或更优 做法： 考虑 …
2026-07-31
一种树状数组上二分的方法
前言 近日鄙人通过剽窃一位神的提交记录碰巧学会了树状数组的新的应用，再加上在OIwiki上的查阅后颇有理解，故写此文以记之。 原理 首先树状数组的结构是很巧妙的，下标为 $i$ 的节点统计的是下标为 $i-lowbit(i)+1$ ~ …
2026-07-31
一种神奇的DP-树上覆盖DP
遇到做过的题不会做，以后要好好改题 :( $\color{blue}\textbf{[例题]}$ ZRtes AB day1 t3 2022syzx夏季训练4 poj#2152 fire 模型 #basic： 在树上选择若干个点，每个点 …
2026-07-31
一种巧妙的优化DP的方法-pht转化
P6944 [ICPC2018 WF]Gem Island 之前一直都没有弄懂pht转化有什么用，现在懂了，故作文以记之。 直接从CYJ的题解开始讲起，这种阶梯DP是人都想得出来，只不过是 $O(n^4)$ 或者 $O(n^3ln …
2026-07-31
一种巧妙的DP优化方法-限制提前
$\color{green}\textbf{[记录一种巧妙的dp优化方法]}$ 这是一种巧妙的优化状态的方法，通过把状态提前（或者说是把状态转化为限制）的方法来避免记录一些别的信息，这种优化方法相比起数据结构优化更加强大，故作文记之 …
2026-07-31
一种平面图上的构造方法-GZOI2022T3
今天GZOI挂了，T3不会做，就是考试的时候方向错了，一直在发掘性质，发掘了两个半钟，寄。 赛后与罗老师亲切交流后发现自己真的很蠢，方向完全想错了，就是这种题目假如你知道了某一整行和某一整列之后，你就可以把整个矩阵构造出来，这个是显然的 …
2026-07-31
一种计数DP-树形限制的排列生成问题
对于这类树形限制的生成排列的题记录两种不同的做法 $\color{blue}\textbf{[例题]}$ 第一种方法(暴暴暴暴暴力dp) P4099 [HEOI2013]SAO P3757 [CQOI2017]老C的键盘 第二种方法(容 …
2026-07-31
一种处理异或运算下不等式的技巧-逐位比较
真的恶心，妈的放道D1恶心人，D1跟D2正解毛关系都没有，傻逼比赛 题号 CF1720D2 Xor-Subsequence (hard version) 简单转化一下题意就是求这样的一个 dp 数组： …
2026-07-31
一些数据结构懒标记时间戳差异的问题
对于数据结构打 lazytag 后节点时空不统一问题的解决 可以看看之前写的一篇文章 线段树初步理解 ，里头初步介绍了懒标记的作用与使用懒标记所带来的时空不统一的问题。实际上是可以将懒标记拓展到其他数据结构上的。 就以经典的 毛毛虫链剖 …
2026-07-31
一些期望与概率DP
本人概率期望菜的一批，写一下博客来加深印象 期望的基本定义 首先期望本身是一个加权平均值，表示把每种情况按照概率发生后总和除以总的发生次数，这是定义法，然后合并一下就是: $$E= \sum_i p_i \times val_i$$ 其 …
2026-07-31
一些解题的科技与套路
有些时候通过线段树分治可以把撤销/删除操作去掉，具体的就是统计每一个 “增加-删除“对 对于询问序列的影响的区间，然后扔到序列线段树上 如果你要算所有点的贡献，但是点之间具有对称性（比如两个点只是编号不同），那么你可以算一个点的贡献， …
2026-07-31
一些计数方法的总结
记录系统性解决计数问题的方法 就是总结了一下《组合数学》上的内容 概念： ①生成：按照某种给定的方法来构造一个规模为 n 的对象，使其满足一系列关系。 ②限制：对于一个规模为 n 的对象，对象内的元素之间满足的一系列关系，感性理解一下， …
2026-07-31
一些关于斜率优化DP的个人见解
关于斜率优化 今天我去复习斜率优化，然后看了半天书没看懂，然后去网上看了一篇博客，觉得 写得挺好的，然后还有了一点自己的理解，顾记此博客。 斜率优化是用于优化线性dp的，所以一般的线性dp都会涉及到最大最小值问题，然后就可以定义状态然后 …
2026-07-31
一些个人已知的线性代数科技
本文比较杂，涉及多方面 #1 矩阵 *1 矩阵乘法 $$\left[ \begin{array}{ll} 1&0&0\\ 0&1&0\\ 0&0&1 \end{array} …
2026-07-31
一些对线段树的初等的理解
今天ZRtes爆零咯，就不在tes里写了 引言：以前一直只会用线段树2，线段树也是一直当做工具使用，一切线段树的科技除了线段树分治基本都不会，因此特作此文记之 线段树的 lazytag 与 pushdown 为了保证时间复杂度，线段树在 …
2026-07-31
一些博弈论
因为博弈一直很菜所以撰写此文以记之 基础模型 Wilson博弈 Nim博弈 SG函数 破题关键 如果是两个人在对抗可以考虑引入纳什平衡的思想 即在一方一组支配策略下，对手再蠢也不会低于一个值，对手再聪明也不会高于一个值 而且随着一步一步 …
2026-07-31
一些DP的思路与套路
多发现题目的性质，从性质上下手 dp转移可以通过更改顺序来消除一些限制 把dp转移需要的条件写进dp状态里 dp的用途是广泛的，包括计数、最优化、可行性等等，其根本就是利用记忆化避免重复计算 看到奇怪的限制应该考虑将其形式化，常规化 看 …
2026-07-31
一个序列划分的结论
题面 划分序列（divide） 给定一个长度为 的序列 ，现在要求把这个序列分成恰好若干段（每一段是一个连续子序列，且每个元素恰好属于一段），并且每段至少有一个元素，使得和最大的那一段的和最小。 请你求出这个最小值。 输入格式 第一行两 …