chx2026-07-31
一种在多路径前提下计数不同结果数量的方法
记录一类统计结果的计数题的方法 很多题目就是初始给你一个对象，然后就是你可以对这个对象进行若干次操作，然后问你能有多少结果 这一类题目就是会遇到非常棘手的情况，就是可能有多个生成路径能生成同一个结果，然后统计路径就是会记重的，基本的做法 …
标签浏览
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） 给定一个长度为 的序列 ，现在要求把这个序列分成恰好若干段（每一段是一个连续子序列，且每个元素恰好属于一段），并且每段至少有一个元素，使得和最大的那一段的和最小。 请你求出这个最小值。 输入格式 第一行两 …
2026-07-31
PHT2022-10-21
传送门 T1 算贡献 T2 算贡献+矩乘维护动态dp T3 类似于 CCPC2021 K ，用矩乘维护斐波那契和 T4 妙题，就是先让 x[i]=A[i]-B[i] ，然后显然就是要判断何时 $forall$x[i]=0 ，然后就是感性 …
2026-07-31
NOIP2022集训10.26
被gtyz供的题创死了，但本质上还是菜… 》 T1 简单想一想就发现其实你不会跳超过 $\log_2$ 次，然后对每个节点维护每种权值对应的下一个元素是谁，可以用一个 last 数组来做，非常简单 》 T2 手玩样例发现 …
2026-07-31
NOIP2022集训10.22
cqnk供的题，不知是不是上次给的难度太高，然后被喷了，这次难度直接下了一档 T1 比较 ==noip T1 ，又或者是我刚睡醒脑袋不太好使，反正瞎搞了一会儿才发现其实暴力就行了。具体的就是每次保证至少消掉一辆坦克即可，然后就是模拟 》 …
2026-07-31
NOIP2022集训10.20
跟着 lsy 糊正睿的题（主要是要去看妹子体育节） 》 听 lsy 说 T1T2 很水，就没看，直接看 T3 是计数题，大喜，乍一眼看了没啥思路就开始手玩样例，发现实际上是一坨环之间连边，然后继续分析性质，发现每个环只能向大小是自己大 …
2026-07-31
NOIP2022集训10.19
成都外国语供的题，说实话由于成外上次给的题直接爆原题，印象非常不好，本来就没怎么看好，结果这场质量竟然还不错? 》 T1 ==noip T1 贪心+分讨，细节比较多，就是要让位数最少，然后注意一些特殊情况，创死人了 》 T2 …
2026-07-31
NOIP2022集训10.15
今天做 cmb 花费重金从 hwy 那里买下的题，质量不错？ 》 T1 > noip T1 ，看着题面想了将近半个钟发现不会做，然后再读一遍题发现是 $n$ 个点， $n$ 条边，这不基环树吗，降智了，不过对于签到题而言码量还是 …
0001-01-01
ZR20220816
T1、T3没人会，感觉很没必要 T2：有意思的 dp 题目本质上就是要求一个排列，使得操作次数最少，状压暴力是 $O(2^m m^2n + 2^mm^2)$ 的，考虑可以均摊一下复杂度，发现其实转的次数就是夹在两个元素之间的元素，因此就 …
0001-01-01
ZR20220812
妈的挂分挂麻了，怒挂 55+100 分，菜死了 T1 根号分类把，经典结论就是 $\sum a_i=n$ 的话 $a_i$ 至多有 $\sqrt n$ 种取值，且 $a_i\ge\sqrt n$ 的至多 $\sqrt n$ 项 …
0001-01-01
ZR20220808
T1 暂时还不会，会60分 今天早上60分卡了一会，一直卡在不知道谁和谁配对，小睡了一下，发现我其实并不关心谁和谁配对，我更关心的是谁对答案造成了正的贡献，而谁造成了负的贡献，因此就是给元素安排 $0/1/-1$ 罢了，而且之前在 和苏 …
0001-01-01
ZR20220728
由于今天出山，因此没有报名比赛，只是看题口胡 T1 随便手玩一下样例发现每次就是削去一个半径差为2的环，然后就是大模拟把感觉挺难写的 T2 分析策略知道一定是能合并就合并，一开始想 树形dp 两次但是发现并不会写，然后不难发现至多会合并 …
0001-01-01
ZR20220725
真就暴力大赛，其实T1是可以想出来的，但是脑塞了 T1 这题非常阴间，部分分和正解一点关系都没有，这是真的阴间。 部分分就是典型的计算贡献： 把不含加号的极长连续段称之为一段，由于加号之间是独立的，因此每段的所有方案之和本质上只与段长有 …
0001-01-01
ZR20220724
T1 有意思的博弈题 题意：总共有 $n$ 堆石子，第 $i$ 堆石子有 $a_i$ 颗石子，两个人轮流取石子，每个人每次可以选择一堆取走若干个石子，但是不能不取，然后每次取走的石子的数量不能多于上一个人取走的石子的数量，以及第一次取石 …
0001-01-01
ZR20220723
T1 不会 T2 题意：给定两棵树，统计总共有多少个点对 $(x,y)$ 满足 $x$ 在 $y$ 的子树中, $n\le 300000$ 一开始以为是树形dp，后面假了，因为并不满足 $(x~in~y),(y~in~z) …