算法详解 - 素数
算法详解 - 素数 定义 素数，又被称为质数。我们一般定义质数为除了 \(1\) 和自身之外没有其他因数的数，特别的 $1 $ 不是质数。 判断 试除法 我们考虑如何判断质数，一种很显然的思路就是枚举这个数的因数。假设这个数是 \(x\)，则我们可以枚举 \([2,\,\sqrt{x}]\) 之间的整数，判断是否可以整除，如果没有找到一个可以整除的数，那么可以认为这是一个质数。时间复杂度是 \(O
CodingCow's Blog - Code solves everything
算法详解 - 重链剖分
算法详解 - 重链剖分 简介 重链剖分，也被称为树链剖分，一般的，OIer 口中的树链剖分就是指重链剖分。今天我们就来一起学习重链剖分。 概念 重儿子 既然是重链剖分，那么我们就要理解什么是重。我们定义一个点的子节点中子树最大的点为这个点的重儿子。我们可以通过下面的一个例子来理解： 其中，节点 \(1\) 的子节点有三个，分别是 \(3,\,5,\,6\)，它们的子树大小分别是 \(4,\,1,
算法详解 - 自适应辛普森法
算法详解 - 自适应辛普森法 前置知识 我们可以看道一个奇怪的式子： \[ \int^R_L f(x)\, \textrm{d}x \] 究竟是什么意思呢？其实就是求函数 \(f(x)\) 在 \(L\) 到 \(R\) 之间的定值积分。在讲求值之前，要先讲一下映射、函数和积分。 映射 再讲函数之前，先要讲一讲映射。首先我们考虑有两个非空集合 \(X\) 和 \(Y\)，如果存在一种法则 \(f\
OiClass P2688 简单计算题解
OiClass P2688 简单计算题解 思路 我们简单导一下柿子： \[ \begin{align*} \sum_{i=0}^{p} \left\lfloor\frac{iq}{p}\right\rfloor &= \left\lfloor\frac{0q}{p}\right\rfloor + \left\lfloor\frac{1q}{p}\right\rfloor + \cdots
TYOI 省选集训 and 2024 GD 省选游记
TYOI 省选集训 and 2024 GD 省选游记 集训 Day -INF 知道可以来集训，感觉特别开心，因为可以合法逃学两周！ Day -3 \(\sim\) Day 0 大年初五就从潮州回到广州，收拾了一下东西，年初七大家就到了学校。 很好，又和高中生一起住，不过这次我们来得很早，所以高二还没有开学。一开始宿舍里面只有我、includeCPP、jr_linys 三个人。所以 includeC
CF1244C 题解
CF1244C 题解 思路 我们看到题目，给定四个数 \(n\)、\(p\)、\(w\)、\(d\)，求解三元一次不定方程组： \[ \left\{ \begin{array}{l} x\cdot w+y\cdot d=p\\ x+y+z=n \end{array} \right. \] 观察一下你就会发现 \(z\) 的值是你可以随便指定的，因为他只对 \(n\) 产生影响，而不对方程一产生任何
AT_abc255_e 题解
AT_abc255_e 题解 思路 朴素做法 首先我们考虑一定可以有一个点是幸运数，于是我们可以考虑遍历每一个 \(S_i\)，钦定 \(a_i\) 是一个幸运数，然后我们就可以反推出 \(a_1\) 的值。然后我们统计 \(a_1\) 重复被计算出的次数。因为只要有一个 \(a_i\) 被确定了，整个序列就确定了。也就是说，\(a_1\) 的重复次数就是我们要求的最多的幸运数个数，因为他们都是同
OiClass 2024 CSP-J 公益赛 #4 题解
引言 这场比赛出题人认为是 \(\approx\) CSP-J + 的难度，预估的平均分在 \(200\) 分左右。比赛的命题思路简单来说就是第一题水题但是考虑在题面里面写很多抽象的东西混淆视听；第二题有些思路的结论题，如果猜出了结论复杂度应该还是非常优秀的；第三题是本场比赛最难的题，算法本身并不难，但是这个思路上有一个优化很难想，这就给很多选手做题带来了很大的困扰，可能无人 AC；第四题是原题加