immix's blog

学习一下如何在 C++ 中合理、现代地生成一些高质量随机数。 rand 函数 生成一个在 [0, RAND_MAX] 范围内的随机数。使用 srand 设置种子。 在 Windows 下, RAND_MAX 的值一般为 32767，而在 linux 环境下，RAND_MAX 的值一般为 2147483647。因此，千万不要在交上去的代码中写出 rand()<<15|rand() 这样的代码（在 Windows 环境下工作正常，但是在 linux 环境下会有符号整数溢出）。 如果要生成一个在 [l, r] 范围内的随机数，可以使用 rand()%(r-l+1)+l （注意：[l, r] 内每个数的概率是不同的，但是一般来说，这样也够用了）。 示例 1234567891011121314#include<bits/stdc++.h>using namespace std;int rand_int(int l,int r){ return rand()%(r-l+1)+l;}int main(){ srand(time(0) ...

A. Cipher Shifer 题意 给定一个加密过的字符串，要求求出原串。 加密方法为：对每个字符，在其后添加任意（可能为零）个与其不同的字符后，再多添加一个自己。 解法 显然对于每个字符，只用往后找到第一个与其相等的字符即可。 AC 代码 12345678910111213141516171819202122232425262728293031323334353637383940#include<bits/stdc++.h>using namespace std;using ll=long long;using ull=unsigned long long;using pii=pair<int,int>;#define begend(x) x.begin(),x.end()#define mem0(x) memset(x,0,sizeof(x))#define YES puts("YES")#define NO puts("NO")int read(){ int f=1,x=0;char c=getc ...

又还是只能做到 C，太菜了 看看能不能有时间练练 D A. The Good Array 题意 给定整数 nnn，kkk。 构造一个 0−10-10−1 序列 a1,a2,…,ana_1,a_2,\dots,a_na1​,a2​,…,an​，满足： 前 iii 个元素中至少有 ⌈ik⌉\lceil \frac{i}{k} \rceil⌈ki​⌉ 个 111。 后 iii 个元素中至少有 ⌈ik⌉\lceil \frac{i}{k} \rceil⌈ki​⌉ 个 111。 解法 正解是 O(1)O(1)O(1) 的（请查看官方题解）。 当时随便写了一个贪心，把 iii 从小往大枚举，如果不够就尽量往中间放 111。 我觉得这个贪心很对，但是我不会证，反正确实是对的。 AC 代码 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970#include<bits/stdc++ ...

打算写一点不涉及算法的指南。这是第二篇。讲讲怎么使用 GDB 来调试代码。要调试代码，最简单的方式就是直接打印出来看，但有时候不想打印，这时候就需要依靠一些外部工具来进行调试了。 GDB 全名为 GNU symbolic debugger，是 GNU 开发的一个支持调试多种语言的调试器。 打开 GDB GDB 是一个命令行的调试器，意味着其没有任何 UI，全部需要通过输入指令来完成调试操作。你应该习惯这种操作，并也习惯用命令行来编译 C++ 程序，而不是使用 IDE 自带的编译。 linux linux 下你的发行版在安装 gcc 的时候就会附带 gdb，在终端输入 gdb 即可。 Windows 如果你使用的是 MinGW，那么在 bin 文件夹下就有一个 gdb.exe，将这个文件夹加入 PATH 即可（如果你之前就可以用 g++ 来命令行编译程序，那么你应该已经加入了）。如果你使用的是其他编译器，请自行查询。 加入 PATH 之后就可以在命令行直接输入 gdb 来调出程序了。 基础使用 首先，编译你的代码。在编译时要加入 -g 选项，将调试信息也编译进可执行文件中。注意 - ...

埃氏筛 筛到一个质数后，把它所有的倍数全部删去。非常简单易懂。 复杂度 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 是否已经在本轮中访问过。 则可以 ...