aceS0

摘要： 鉴于被 noip2025 的 t2 创飞，决定恶补计数题。 目录trick1.拆贡献2.两个连通块大小之积 \(\iff\) 两个联通块内有序点对个数3.计数转期望4.若有排列转换，可以将排列位置和转换到的位置连边分析5.打表6.二项式反演7.生成函数8.容斥9.正难则反题目P3214 [HNOI2 阅读全文

摘要： 巴巴博弈 这里只介绍 nim 游戏。 在博弈论中，设 \(sg(x)\) 表示当前局面。那么若 \(k\) 局面先手必败，则 \(sg(k) = 0\)；若 \(k\) 先手必胜，那么 \(sg(k) \ne 0\)。设终止的必败的局面（即题目中直接给的必败条件）为 \(0\)，且 \(sg(0) 阅读全文

摘要： P3214 [HNOI2011] 卡农 很好的计数题呢，代码很短很 atcoder 的题。 思路 考虑 dp。 设 \(dp_i\) 表示有 \(i\) 个片段的合法种数。这是不好直接算的。我们注意到假设我们随意选了 \(i - 1\) 个不重区间，为了让每个音阶都被演奏偶数次，我们第 \(i\) 阅读全文

摘要： 范德蒙德卷积 看之前你需要会基础的生成函数。 \([x ^ k]\) 表示生成函数第 \(k\) 项系数。 前置：插板法与生成函数 对于生成函数，可以证得： \(\frac{1}{1 - x} = \sum_{k = 0}^{\infty} x ^ k\)。 所以对于 \(\frac{1}{1 - 阅读全文

摘要： wqs 二分 适用条件 对于一些满足以下要求的题目： 1.其有形似恰好 \(k\) 个的形式。 2.如果没有恰好 \(k\) 的形式是十分可做的。 3.设恰好选 \(k\) 个的答案为 \(f(k)\)，那么由 \((k, f(k))\) 构成的图像为一个凸包。 ps：第三条一般打表找规律。 那么我 阅读全文

摘要： 动态树 目录动态树前置：splayrotate(x)splay(x)LCT思想：实链剖分实现splay 部分fa[x]push_up(i)push_down(i)isrt(x)lazytag(i)get(x)rotate(x)splay(x)access(x)find(x)makeroot(x)li 阅读全文

摘要： 100 + 0 + 100 + 20 rk3 考场 拿到题先把 4 道题看了一遍。T1 的 75pts 特别好拿并且感觉正解不难。T2 直觉像是类似线性筛，筛出无法被重复拼出来的字符串然后排序，但时空都要炸死，感觉不可做。T3 第一眼没什么想法但感觉不算很难。T4 一眼 dp 但没什么想法。最终决定 阅读全文

摘要： 写博客写上瘾了。 集训是3.25 ~ 4.6，于是将3.25作为了day1。 day-1 本身请假了16：00回家收东西，走之前和踢班赛的同学练了一会结果手机和校服一起被偷了。一直折腾到了18：00才找到手机，校服直接失踪了。索性把班赛的半决赛看完了再走。双杀四班还是很爽，我们班挺进了决赛。看完就回 阅读全文

摘要： 分数 100 + 80 + 0 + 20 rk5 考场 考试之后先看了t1，发觉这个并不是签到题，这意味着这次考试并不简单。想到了dp，和之前做的一堆斜率优化的题看着很像，于是推出了这个式子： \[dp_i = \max\{ dp_j + (i - j) \times (p_i + p_j) \} 阅读全文

摘要： 限于作者水平不高，就讲一些水题。 做完你就数据结构入门了。 分为多个部分。 目录RMQP14638 [NOIP2025] 序列询问思路代码P2048 [NOI2010] 超级钢琴思路代码二维数点 / 扫描线P8339 [AHOI2022] 钥匙思路代码P5524 [Ynoi2012] NOIP201 阅读全文