hhz 杂题选讲。 IOI2023 最罕见的昆虫 我们考虑最小值具有什么性质。 将权值列出直方图，发现最小值下的数的个数都是 \(k\tiems num\) 种，这是最大值并且取到的。 实际上，这个是在说明最小值信息具有单调性。 那首先考虑问出种类数，我们可以一个一个加入并查询众数。这需要 \(n\) 次询问。 然后二分最小值，这也可以通过一个一个加入查询众数来计算出现 \(\le mid\) 次的点的个 2023-01-14
复建记录 真实的复建记录。真实的啥也不会。 [NOI2009] 二叉查找树 题意：给你一个treap，你可以花 \(k\) 任意改变一个点的堆权值。让你最小化 代价+深度*出现次数。 题解 先不考虑出现次数。给你一颗树，怎么计算最少花费的代价。 发现因为任意改变（实数），那肯定能改的数只有 \(O(n)\)。 所以从底到顶dp即可。 原问题发现可以类似做，总复杂度 \(n^4\) 2022-12-21 simple thoughts
5e10的小石子 5e10的小黑子 感谢qiu老师的长期连载系列让我入门整式递推/bx/bx part1 基础推导 首先观察到我们每一行必须有 \(2\) 个数，然后每一列之多两个数。 我们把同一行的连边，同一列的连边。 不难发现每个点的度数 \(\le2\) 连出的一定就是环或者链。 那么考虑实际上他本质上是一个二元egf（需要同时分配行列）。 考虑一个 \(n\times n\) 矩阵嵌入环 2022-12-02 数学
noip2022 完全失败。 很失败，被构造题搞了。 所以就拿这个博客来记一记构造题把。 noip2022t2 题意，你每次按顺序把 \(m\) 个数放入 \(n\) 个栈里。 如果两个栈栈底相等，可以删掉这两个数。 如果有相邻两个数相等也可以将这两个数删掉。 一共只有 \(2n-1\) 种数。 题解 菜死，不会构造。 首先 \(k=2n-2\) 的是怎么做的呢？ 相邻匹配最后形成的串是 2022-11-28
~11-13 部分题解。 密码xoi。 因为前几周太摆了。所以题解从后往前写。 11-12 T1 euclid 根号分治，值得注意的是复杂度形式为： \[ \sum_{p,q} \frac{n}{\max(p,q)}=\sum_{p} \frac{n}{p}*p \] 很是神奇。 T2 euclid dp。 首先考虑 \(dp\)，我们发现如果记录 \(m!\) 的顺序的信息其实很亏。 那么很 2022-11-13
？ 胡策 R14？T3 不用vscode写了。 旋转是线性变换。镜像也是线性变换。 那么对点可以直接维护矩阵乘积（没有修改的情况）。 如果是对变换矩阵的修改呢？发现可以看成对空间的变换，实际上我们在改变基。那么可以使用基变换。 （考场时候想的是转置，而实际上就是逆。） 一个线性变换 \(A\) ,一个对基的线性变换矩阵 \(E\)。 正常一个列向量 \(v\) 经过这个线性变换后得到 2022-11-02 数学
胡策部分题解 R1 T1 题目大意：将 \(0/1\) 串分成若干段，任意拼接，最后的lis最短长度。 推一波式子：\(\max_{i}(A_i+s_b-(i-A_i))=\max_{i}(2A_i-i)+s_b\)。 也就是看成 \(A_i=0\) 有 \(1\) 的贡献 \(A_i=1\) 有 \(-1\) 的贡献。 我需要拆成若干子区间，一个区间的权值是上面说的和 \(0\) 取 \(max\ 2022-11-01
CF506E link 首先 \(nl^2\) 的 dp。 我们可以记录状态 \(\mathrm{dp[k][l][r]}\),表示当前加入了 \(k\) 个数，前缀匹配到 \(l\),后缀匹配到了 \(r\)。 update at 10-27 很抱歉我真的不知道这个从头到尾的想法是如何得到的。 我只能得到一个丑陋无比的DP，复杂看不出逻辑的自动机，以及无穷无尽的口胡。 大体思路是这样的，我们建出来 2022-10-27 dp dp 神仙题