immix's blog

埃氏筛 筛到一个质数后，把它所有的倍数全部删去。非常简单易懂。 复杂度 O(nlog⁡log⁡n)O(n \log \log n)O(nloglogn)。 （证明略去） 123456789101112131415bool prime[N];void solve(int n){ for(int i=2;i<=n;i++)prime[i]=1; for(int i=2;i<=n;i++){ if(!prime[n])continue; // 优化：从质数 i 的 i 倍开始筛 // 因为 i 的 2~(i-1) 倍一定有一个更小的质数因子 // 所以已经被筛掉了 for(int j=i*i;j<=n;j+=i){ prime[j]=0; } }} 线性筛（欧氏筛） 埃氏筛的效率还是不够高，我们尝试构建一个复杂度为 O(n)O(n)O(n) 的筛法。 线性筛的思路是对于一个数（不一定是质数）， ...

正式比赛的理论环境是 NOI Linux 2.0（虽然上海市目前还是 Windows+Linux 双系统，共享分区，最后用极域上传文件）。总结一下 NOI Linux 中的一些操作，也是为下半年做个准备。 安装 NOI Linux 2.0 的镜像可以从 NOI 官网下载。(https://www.noi.cn/gynoi/jsgz/2021-07-16/732450.shtml) 可以采用 Virtual Box 或者 VMWare 来安装虚拟机（不建议安装实体机，如果想要尝试 Linux 环境，推荐使用 WSL 2.0，亦或用实体机安装 Ubuntu 发行版）。 安装教程有很多，这里就不在赘述了，可自行搜索。总之，安装之后就可以进入系统了。 编辑器 NOI Linux 提供了很多编辑器（没有 Dev C++ www）。 TL;DR：建议使用Code::Blocks。下面详细介绍各个编辑器的利弊。 VS Code 作为编辑器的神（我自己编程的时候全部用的是 VS Code），具有轻量级的优点。但是，因为无法使用 C++ 插件，导致只有最基本的高亮功能，不能补全。因此并不推荐。 Su ...

概念 欧拉回路：通过图中每条边恰好一次的回路 欧拉通路：通过图中每条边恰好一次的通路 欧拉图：具有欧拉回路的图 半欧拉图：具有欧拉通路但不具有欧拉回路的图 判断存在欧拉回路/欧拉通路 有向图 欧拉通路：图弱连通，且至多 1 个点出度比入度大 1，至多 1 个点入度比出度大 1，其余点入度等于出度。（特别的，此时通路起点是出度比入度大 1 的点） 欧拉回路：图弱连通，且所有点入度等于出度。 无向图 欧拉通路：图连通，且至多有两个度为奇数的点。（特别的，此时通路起点是两个奇点中任意一个） 欧拉回路：图连通，且没有度为奇数的点。 总结 对于一张图，判断是否存在欧拉回路/通路要做两件事情： 把这张图当作无向图，判断是否连通（可以用并查集，或者 dfs） 判断特殊点的个数是否符合要求（奇点、出度入度差 1 的点） 寻找欧拉回路/欧拉通路 使用 dfs，每经过一条边就把这条边删了。最后在递归结束的时候加入栈，即可正确找出路径。 来看一个例子： 对于这张图，实际的运行情况如下： 搜索 1 ├───搜索 2，删除边(1->2) │ ├───搜索 3，删除边(1->3) ...

总结一下图论里的最短路。 Dijkstra 算法 Dijkstra 算法可用于非负权值的图，可以表示为如下流程。 将源点的距离设为 0，其他点的距离设为无穷大。 从图中找出距离最小且未标记的点 uuu，并标记点 uuu。松弛所有与 uuu 相邻的节点。（松弛：尝试将 s→vs\rightarrow vs→v 的路径用 s→u→vs\rightarrow u \rightarrow vs→u→v 的距离更新，即 dis[v]=min(dis[v],dis[u]+w[u][v])） 重复第二步，直到所有节点都被标记。 如果需要输出路径，可以在松弛成功时记录每个节点的前驱。 根据在第二步找出距离最小的点的处理方法不同，Dijkstra 算法有不同的复杂度。 暴力实现 依次遍历所有 nnn 个节点，找出最小权值。这样第二步的复杂度为 O(n)O(n)O(n)，总共执行 nnn 次，总复杂度为 O(n2)O(n^2)O(n2) 123456789101112131415161718192021222324252627282930313233343536373839const int N = ...

经典的区间三个贪心问题。再总结一下，以作复习。 选择不重叠区间 有 nnn 个区间 [li,ri][l_i,r_i][li​,ri​]，选择尽量多的区间，使得区间之间不重叠（端点可以重叠）。 将右端点从小到大排序（左端点可以随便排序），然后先选择右端点比较小的（不与之前选过的重叠）。 这样的贪心策略是正确的。 考虑如下一个例子。先选择右端点最小的 [1,4][1,4][1,4]，然后右端点次大的 [2,5],[3,5][2,5],[3,5][2,5],[3,5] 重叠无法选择，然后是右端点最大的 [4,6][4,6][4,6] 可以选择。即最多可以选出两个区间。 假设一开始没有选择右端点最小的，选择了 [2,5][2,5][2,5]， 那么 [1,2][1,2][1,2] 的部分就被浪费了，还额外占用了 [4,5][4,5][4,5] 的空间，所以一定从右端点小的开始选更划算。 区间选点问题 有 nnn 个区间 [li,ri][l_i,r_i][li​,ri​]，选择尽可能少的点，使得每一个区间内都有点。 事实上，这个问题的答案和选择不重叠区间的答案是一样的。 为什么两个问题的答案相 ...

二分图最大匹配 给定一张二分图，有 nnn 个点，mmm 条边。求最大匹配。 可以使用匈牙利算法求解，复杂度 O(nm)O(nm)O(nm)。 如果使用 dinic 算法，可以做到复杂度为 O(nm)O(n\sqrt{m})O(nm​) dinic 算法详见 网络流初步-最大流算法。 具体来说，建立超级源点和超级汇点，然后建容量为 1 的边，跑最大流即为最大匹配。 匈牙利算法的本质就是找增广路，基于贪心思想。我们来看一个例子。 首先考虑给节点 1 寻找匹配。发现可以匹配右边的节点 1，则成功匹配。 然后考虑给节点 2 寻找匹配。发现能匹配的唯一一个节点 1 已经被占用，尝试让左边的节点 1 换一个匹配，即等价于找一个增广路。 这样就找到了这张图的最大匹配（3）。我们接下来考虑写一个递归函数实现这种协商找增广路的算法。 匈牙利算法 我们定义一个递归函数 bool dfs(int u)，代表为节点 u 寻找匹配。 数组 int match[v] 表示右部图中节点 v 已经匹配上的左部图节点。 数组 bool used[v] 表示右部图中节点 v 是否已经在本轮中访问过。 则可以 ...

导言 命令行是一种强大、快捷的工具。有时候可以比 GUI 操作更加便捷。其另一大优点是可以极其容易的通过 ssh 控制其他机器。 初识命令行 在 Windows 下，常见 shell 有命令提示符(cmd)，PowerShell 两种。我们主要阐述 cmd。在 linux 平台上你还会见到 bash。bash 和 cmd 的命令是有一部分重合的。 打开 cmd 的一种方式是按 Windows 键，然后搜索 cmd；另一种方式是 Win+R，再输入 cmd 运行。 打开 cmd 后，你会见到这样的界面（因为我安装了 Windows Terminal，与你的电脑外观略有不同，但是内容是一样的）。 在提示符（>）后输入命令，然后按回车就可以看到命令的结果。你学过了 ping 和 ipconfig 命令，但让我们从头开始，学习最基本，使用频率最高的命令。 基本命令 基本命令只有两个（好耶），一个切换目录，一个查看当前目录内容。 cd cd = Chang Directory = 改变目录 用来改变当前的工作目录。在 cmd 中，使用 Tab 可以补全路径。使用 ↑ 键可以找到历史命令 ...

突发奇想，研究一下 ACG 歌词的用词特点。 获取歌词 找到了一个共有 4572 首歌（2023-5-10）的歌单，https://music.163.com/#/playlist?id=66652611 ，尝试获取其中所有歌的歌曲 id。 首先尝试查找有没有合适的 API，失败，尝试从歌单页面入手。 可以看到，网易云网页查看别人创建的歌单只可以看到前 20 首歌曲。但是如果我们将歌单复制到自己的自建歌单，则可以显示 1000 首。理论上可以创建 5 个歌单，然后进行获取。 分析网页结构，可以发现每个歌曲都是一个 a 标签，里面的 href 就是我们要的内容。 尝试在控制台编写一个 JS 来获取所有个歌曲 id。 1document.querySelectorAll("div.f-cb span.txt > a") 尝试使用这个选择器，发现能够成功获取所有 a 标签，接下来就是获取所有 a 标签的 href 属性。 12let result = ""document.querySelectorAll("div.f-cb spa ...

引入 洛谷P6175 无向图的最小环问题 给定一张带权无向图，求图中至少包含 333 个点的环，环上节点不重复，并且环上所有边权值和最小。 解法 我们考虑对 Floyd 算法进行修改，找出最小环。 设最小环由节点 V1−V2−⋯−VnV_1 - V_2 - \dots - V_nV1​−V2​−⋯−Vn​ 组成。 其中编号最大的节点为 VmV_mVm​ 与其相连的节点为 VpV_pVp​，VqV_qVq​。 则最小环可以表示为 Vp−{Vp,Vq之间不包含Vm的最短路}−Vq−VmV_p - \{V_p,V_q\text{之间不包含}V_m\text{的最短路}\} - V_q - V_mVp​−{Vp​,Vq​之间不包含Vm​的最短路}−Vq​−Vm​。 如下图： 这是可以证明的： 假设不是最短路：则最短路权值一定更小； 假设包含了 VmV_mVm​：则出现了重复的节点。 在 Floyd 算法中，我们知道，枚举中转点到 k 时，此时数组内下标小于 k 的值保存的是 1~(k-1) 内部之间的最短路。 因此在 Floyd 算法中枚举 i，j 的循环前面再添加一个循环即可。G[i] ...

前言 什么是类？ 类（Class）：可以片面的理解为一类相似事物的抽象。 以圆为例，圆具有半径这样一个相似的属性，并且都可以执行面积、周长等运算。 为什么用类？ 为了是代码更加抽象，封装。事实上，我们以前写的每个 python 代码里都创建了各种各样的类。 一些例子比如 DataFrame 类。 你可能会用 read_csv 创建一个 DataFrame 类，可能也会用下标运算符，来获取它的某一列，也可能会用它的 drop_duplicates 方法。事实上，你并不关心 DataFrame 是怎么把数据排在一起的，你也不关心为什么 drop_duplicates 就能把所有重复的去除，但是，通过这一个抽象的类，你可以方便的调用它的功能。 DataFrame类，将整个表的数据，仅仅用一个变量，就全部包含起来，就像是封装在了一个小小的纸板箱中📦。 需要注意的是，pandas 库并不是魔法，而是正常的 python 语法。一切 pandas 库的功能都是我们也可以实现出一模一样的。 比如说，为什么 df[(df['a']>5) & (df['b']<8)] 中用的是 & ...