update 2024-02-11 ：话说是不是在这里加一个目录啊，字数已经 3w+ 了欸。 总览妙用 $\text{stable_sort}$ $+$ 数据接近有序的排序发现答案有分化然后用二分加速枚举省略不必要的状态加速递归，类似二分以身入局的贪心非常直观从最为容易的决策入手一步步考虑贡献贪心（一般是从最终到初始）从题目展现出特殊的地方入手从简单的状态开始考虑倒推手玩数据 | 补图与原图相关性质考虑问题是否具有特殊性质，如序列必定连续等爆搜剪枝利用 bitset 存储二进制状态，考虑限制转换 $1-24$ P1309 [NOIP2011 普及组] 瑞士轮 $\small{对排序算法的理解}$ $\large{\text{Solution}}:$ 挺有意思的一题，原先按照题意模拟考虑轮用一次 $\text{sort}$ 没想到时限太紧 $\color{darkblue} T$ 了（ $O(R\cdot n\log n)$ 确实慢），但是根据题解的思想直接把 $\text{sort}$ 换成 $\text{stable_sort}$ 居然过了？？？题解思路，考虑胜者...

前言这篇博客主要是给已经掌握了用 Hexo 在 github.io 搭建博客的人使用，仅作为一个类似备忘录的东西作为参考——提供一些在转移博客后台时可能用到的指令。 预备环境搭建 Hexo blog 后台需要一下工具： nodejs git VScode（或其他文本编辑器） 也许需要一个 steam++ 为你的网站加速 我当然已经为你们准备好了。 部署 Hexo来到装 blog 的文件夹，打开cmd 设置 GitHub 账户信息 12git config --global user.name "用户名"git config --global user.email "注册email" 然后就是建立一个 SSH 密钥，用于后续上传用 1ssh-keygen -t rsa -C "注册的邮箱地址" 输入完指令后连续按4下回车，若看到一个随机图案生成则成功。 然后把路径 C:\Users\用户名\.ssh\id_rsa.pub 下的东西复制到 github 账户新建的 SSH Keys 下即可。 接着来到博客的跟目录，开...

闲话第一次打 USACO ，真是太刺激太好玩了，会弄就多弄点。 BronzeT1Question给定一个 $n$ 个数的序列 $a$，定义一次操作为在序列中选定一个区间，若区间的某个数的个数大于区间长度的一半，那么就可以将这个区间全部变为这个数。问有哪些数可以经过若干次操作后使得整个序列都变成这个数。 Solution考虑选一个长度不大于 $3$ 的区间，如果里面有至少两个数相同，那么另外一个数必然可以变得相同，于是这样一次次操作的扩张，序列就会变成同一个数。于是我们就有了策略：如果一个数 $x$ 距离它两格以内还有一个 $x$ ，那么整个序列都能变成 $x$。 Code代码有点细节，考场上稀里糊涂的调过了。 点击查看代码 12345678910111213141516171819202122232425262728293031323334#include <bits/stdc++.h>using namespace std;int T,n,a[100010];bitset<100010> v;int main(){ ios::sync...

VScode 的安装以及使用基础（C++配置） 经过多次反复安装VScode的经验，本文于 2023.7.18 进行了整改。 由于配置 VScode 所需东西较多，每次都逐一下载稍微繁琐，这里作者为大家已经整理好了，里面包含下文所需的所有资源。 点这里下载 VScode 安装资源包 VScode 的安装进入VScode官网，点击 Download for windows 即可得到安装程序，运行即可。 编译器G++的配置下载 MinGW，将其保存至任意磁盘中（下面默认C盘）。将 MinGW 下的 bin 文件夹的路径加入到环境变量中。 右键“此电脑”选择属性，点击“高级系统设置” 点击“环境变量” 点击“系统变量”一栏中的 “Path” 点击新增,将之前保存的路径（bin 文件路径）输入进去即可 操作完毕后，重启电脑 即可。 如果不方便重启电脑或者其他什么情况的话，也可以用更简单的方式设置这个环境变量。新建一个后缀名为 “bat” 的文件，里面写入 setx "Path" "保存的路径;%path%;"。然后运行这个 ba...

前言在小学中，我们接触到了整数除法，其中会有一个概念名为余数。当然，这个概念在小学五年级学小数的时候就被抛弃了，但是在数论的知识中，它再次卷土重来，折磨众生。 整除概念对于一个整数 $a$ 和 $m$，我们取 $a\div m$ 下的余数，记为 $\color{Blue} a \bmod m$易得，整除的概念为除以 $m$ 的意义下余数为 $0$，即$a \bmod m=0$：一般的，对于整数 $a$ 和 $m$，$\color{Blue} 若 a \bmod m=0，我们记为 \color{Blue} m \mid a$，此时 $m$ 为 $a$ 的因子，$a$ 为 $m$ 的倍数。 根据 $\mid$ 的意义可得，若 $a \mid m$，则定有一个整数 $k$，使得 $a=km$ 接下来我们来考虑整除有什么特殊的性质。 $\boxed{若 a \mid b，c \mid d，则有 ac \mid bd}$证明：$\because a \mid b,c \mid d\\\therefore \exist k,m\in \Z,b=ka,d=mc\\\theref...

前言 终于入门了python打包这个大话题，将目前学到的技能分享一下。 pycharm启动虚拟环境pipenv 缩小打包 和很多博客说的一样，打包那么大是因为打包了多余的库，因此想要缩小就需要一个干净的，没有多余的库的环境进行打包。也就是虚拟环境。 想要在 pycharm 启动虚拟环境，先要安装一个 pipenv。按下 win+r 后输入 cmd 打开命令面板，输入 pip install pipenv 即可安装。 安装后，我们需要得到名为 “pipenv.exe” 文件的路径，也就是 pipenv 虚拟环境的安装路径。查看的方法有很多，或许是能力原因本人试过的都不怎么好使，还是最朴素的方法最稳定： 是的，直接点开此电脑在右上角搜索文件即可（慢是慢了点但是亲测有效）！ 然后我们打开 pycharm 选择新建项目 点击三角形符号， pycharm 就会为这个项目创建一个干净的虚拟环境。 然后选择好虚拟环境的类型，也就是上面安装的 pipenv。 如果pipenv可执行文件那一栏是空着的，那么就把上一步中得到的 “pipenv.exe” 的路径...

前言话说每次讲跟 $newton$ 有关的东西，都得先 $\%$ 一下这位大佬。 引入我们很早就知道伽罗瓦证明了五次及以上方程不具有普遍的求根公式，但是高次方程却充斥着我们的生活，因此在不同的领域求解不同的高次方程变得尤为困难。 在高中我们就学过，对于在 $[l,r]$ 上单调的函数 $f(x)$，若 $f(l)$ 与 $f(r)$ 异号，即 $f(l)\cdot f(r)\le0$ ，则在此区间内定有且仅有一个该函数 $f(x)$ 的根。 结论很直观，这里就不赘述了。看到单调性，我们很容易想到可以通过二分的方法来快速找到函数在区间 $[l,r]$ 内的根，这也是课本里教的方法。二分的复杂度已经是 $\Theta(\log_2 n)$ 的了，可谓是极其优秀，但是随着时代的进步，这种 求近似根 的方法已经显得效率有点低了。 想必大家都知道 $C++$ 中自带的 $STL$ 函数 $sqrt(a)$，它的作用是求 $a$ 的算术平方根，我们也可以理解为求解一个 $x^2-a=0$ 的方程，或者说找到函数 $f(x)=x^2-a$ 的正零点，亦可想到可以用我们学过的二分实现。 但是已经...

引入给出 $n$ 个点 $(x_i,y_i)$，求一个 $n-1$ 次的多项式 $G(x)$，满足 $G(x_i)=y_i$，求出 $G(k)$ 的值。 largrange 插值根据待定系数法的推论，若已知 $n$ 个点，就可确定一个 $n-1$ 次的多项式。而通过点的坐标来求多项式的过程叫做 插值。 显然，问题就是让我们求过点 $(x_i,y_i)$ 的 $n-1$ 次多项式。 当然可以考虑高斯消元，也就是计算机模拟待定系数法。但是这样的复杂度是 $\Theta(n^3)$。当待定系数的时间复杂度无法满足需求时，我们就可以使用 $\mathbf{largrange}$ 插值（拉格朗日插值） 我们考虑对单点进行求解，构造一组多项式 $F_i(x),i\in [1,n]$，使得 $F_i(x)$ 满足以下条件： $F_i(x_i)=y_i$ $F_i(x_j)=0,j\ne i$ 若拥有这组多项式，那么最终的 $G(x)=\sum\limits_{i=1}^{n}F_i(x)$，显然满足所要求的条件。 现在考虑构造 $F_i(x)$,若要满足条件 $2$，则可考虑利用因式定理，...

引入给出 $t(t\le500)$ 个正整数 $x(x\le2^{63}-1)$，判断 $x$ 是否为质数。 Miller Rabin 素性检验显然在这个 $x$ 的范围下，试除法判断质数是不行的。 $\mathbf{Miller Rabin}$ 素性检验就是一种用来 判断大数是否为质数 的 随机性 算法。它在计算机科学中的用途是用来判断工业质数 $(\ge2^{1024}的质数)$，在这个范围下它的判断是否正确存在随机性，但是在 $OI$ 范围下 $(\le 2^{63}-1)$ 确是一种 错误率极低 的 确定性 算法。 在 引入 的问题中，我们可以考虑使用 $\mathbf{Miller Rabin}$ 素性检验来判断质数。在 $\mathbf{Miller Rabin}$ 素性检验中，我们要先了解它判断素数的理论基础： 费马素性检验 二次探测定理 费马素性检验费马小定理： 若p是质数，\gcd(a,p)=1,则\ a^{p-1}\equiv1\pmod p证明： $考虑P=\{m_1,m_2,m_3,\cdots ,m_{p-1}\}，m_i<p，显然有 m...

概念$若a,b\in\Z,\gcd(a,b)=1,则称a与b\color{Blue}互质\\\color{black}对于n\in\Z,将区间[1,n]中与n互质的个数称为\color{Blue}{欧拉函数},记作\varphi(n)$ 欧拉函数\boxed{考虑n=p_1^{c_1}\cdot p_2^{c_2}\cdot p_3^{c_3}\cdots p_m^{c_m},则有\color{Red}\varphi(n)=n\cdot\prod\limits_{i=1}^{m}(1-\dfrac{1}{p_i})}证明：若一个数质因数与n的质因数都不相同，则这个数和n互质，因此我们只需要考虑不是n的质因数的质数可以构成多少$[1,n]$内的正整数即可。$\because 对于n的质因数p_i,都在[1,n]内有n\cdot \dfrac{1}{p_i}个数与n有共同的质因数p_i\\\therefore 对于质因数p_i,都在[1,n]内有n\cdot (1-\dfrac{1}{p_i})个数不是质因数p_i的倍数\\\therefore 不是n任何一个质因数倍数的数在[1,...