0103abc 的网站

选自 11 月做题笔记。 039. [P6012 [P5087] 数学 加强版](https://www.luogu.com.cn/problem/P6012) 这是不是生成函数板子啊/yun，容易发现答案就是 $[x^k]\prod\limits{i=1}^n(aix+1)$，这个东西形如 $n$...

先考虑比较暴力的做法。枚举选择的子序列最中间的位置 $i$，这样一来根据经典贪心结论，左右两侧都分别需要选 $\frac k2$ 个（对 $2\mid k$ 的情况需要处理左边多选一个还是右边多选一个）。对每个值不和 $i$ 相等的值，求出 $i$ 左右两侧第一个和其值相同的位置...

~~你说的对但是我今天刚学会可持久化线段树~~ 这题怎么没题解啊/yun 先给出一个简要题意： 给定两个长度为 $n$ 个排列 $a,b$ 和一个参数 $k$，定义这两个排列的权值为：在 $a,b$ 中各选取一个长度为 $k$ 的连续子段，其组成集合的交集最大值。 有 $Q$...

选自 11 月做题笔记。 031. [P3641 [APIO2016] 最大差分](https://www.luogu.com.cn/problem/P3641) 第一问是简单的，直接从两端往中间问即可。 对于第二问，先求出序列的最小值 $mi$ 和最大值 $mx$，此时根据抽屉原理可知答案有下界...

选自 11 月做题笔记。 029. [P6790 [SNOI2020] 生成树](https://www.luogu.com.cn/problem/P6790) 前置知识：广义串并联图 核心操作是： 删一度点：若图上一个点 $u$ 的度数为 $1$，则直接删除该点。 缩二度点：若图上一个点 $u$...

选自 11 月做题笔记。 028. [P10832 [COTS 2023] 传 Mapa](https://www.luogu.com.cn/problem/P10832) 题目给出了明确的提示“把 $xi,yi$ 看成一个整体组来考虑”，于是容易想到 Lagrange 插值插出 $f$...

选自 11 月做题笔记。 这题真没啥思维含量吧，非常容易想到先考虑什么时候怪物会被抓住（后面是我的思考过程）： （$1$）只有一个点，此时怪物必然在这个点上，直接选这个点怪物就必然被抓住。 （$2$）树形如一条链，此时考虑从链的一头开始，按照顺序依次选链的每一个点。...

选自 $11$ 月做题笔记。 011. [P14315 [Aboi Round 2] Faputa](https://www.luogu.com.cn/problem/P14315) 考虑竞赛图 SCC 计数的经典结论：设 $\degi$ 表示竞赛图上 $i$ 点的入度，则该竞赛图 SCC...

Lagrange 插值 给出 $n$ 个点 $(xi,yi)$ 满足 $xi\neq xj$，可以唯一确定一个 $n-1$ 次多项式 $y=f(x)$ 过上述所有 $n$ 个点。 现在给出 $k$，求 $f(k)$ 的值。 一个简单的想法是直接 Gauss 消元，可以 $O(n^3)$ 解出这个...

如果你不会做这个题，请注意题目询问的限制条件求的是 $\max$ 而不是 $\min$（）我绷不住了 $\text{mex}$ 运算有一些比较有用的性质，例如：在任意一个给定的序列 $a$ 中，$\text{mex}(l:r)\le \text{mex}(l:r+1)$...