aceS0

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

摘要： 题目链接 博客 前言 莫队好题，比较板但又比较考转移的思维。 思路 很简单的发现是对操作序列进行莫队。 先对问题进行转换。 首先对于两种修改，第一种修改显然是没有第二种好写的，考虑将第一种转换为第二种。想到对于每一次第一种修改可以单开一个点，将其值赋值为要修改的值，这样就可以将第一种修改转换为第二种 阅读全文

摘要： 原题链接 博客 曼波~ \(n^2\) 过百万，暴力踩标算。 实则不是百万。 思路 注意到输入范围最后一行，表示每次询问两个起冲突的部落是一定互不相同的（当然即使相同也可以记忆化），那么每次询问对两个部落之间的龙进行暴力枚举枚举是均摊 \(O(n^2)\) 的，与 \(q\) 无关。题目中 \(n\ 阅读全文

摘要： 题目链接 博客 思路 观察到 \(n\) 最大只有 \(8\) ，可以考虑爆搜。我们可以考虑将折好的纸展开。显然，展开成最开始的正方形纸片后，纸片上有多少孔，那么最开始打的孔就穿过了多少层。 至于怎么展开，考虑将每个孔关于每个折痕求对称点，对称点便是展开一层后点的位置（显然应该按照折纸的顺序倒序展开 阅读全文

摘要： \(\mathit{Möbius反演}\) 前置 前置函数 单位根函数 \(\epsilon(x)\) 当 \(x = 1\) 时，\(\epsilon(x) = 1\)；当 \(x \neq 1\) 时，\(\epsilon(x) = 0\)。 幂函数 \(Id_k(x)\) \(Id_k(x) 阅读全文

摘要： 二项式反演 前置知识：二项式定理 对于 \(a\), \(b\)，显然有 \[(a + b)^n = \sum_{k=0}^{n} \binom{n}{k} a^{n-k} b^k. \]二项式反演公式 设 \(f(n)\) 和 \(g(n)\) 是定义在非负整数集上的两个函数。如果对于所有非负整数 阅读全文

摘要： 写了有点久，基本都写得oiwiki上的但自认为写的更好(至少对于我自己的理解来说) 定义基础 排列 从 \(n\) 个元素中考虑顺序地选出 \(k\) 个元素的方案数，写作 \(A_n^k\)。 显然： \[A_n^k = \frac{n!}{(n - k)!} \]圆上排列 一个长度为 \(n\) 阅读全文

摘要： CF1276B 给你一张n个点m条边的无向图，给定两个点a和b，问有多少点对(x,y)之间的路径必须经过a和b两个点 x,y \(\neq\) a,b \[1 \le n \le 2 *10^5, 1 \le m \le 5*10^5 \]hint1 判断a,b都是割点 CF999E 给你一个n个点 阅读全文

摘要： 题目描述 给你一个小写字母组成的字符串，求出一个这样一个最长子串，满足： 其在原串的不同位置出现了两次(起始位置不同，可以部分重叠) 其反串在原串中出现了一次(与前面两次无关) 数据范围 字符串长度 \(n \le 5e4\) 方法 考虑前缀哈希 + 二分。 如果说假设满足要求的子串为 \(s\) 阅读全文

摘要： 介绍 在我们使用vscode时，我们会用到代码块。 代码块十分好用，可以帮我们自动补全代码，也可以存各种板子。虽然会损失人的代码能力，但能提升做题效率。但我们注意到，vscode的代码块是使用json编辑的，对于不会json的人就显得十分麻烦。而且，也不是把代码直接放上去就能用的，需要改各种格式，比 阅读全文