immix's blog

填坑。 前两期： 网络流初步 —— 最大流算法 (2023/01/25) 网络流初步（2）—— 最小割 (2023/01/26) 费用流 现在，网络中新增了一个属性：费用。 设边 u,vu,vu,v 的费用为 w(u,v)w(u,v)w(u,v)。则当 (u,v)(u,v)(u,v) 的流量为 f(u,v)f(u,v)f(u,v) 时，费用为 f(u,v)w(u,v)f(u,v)w(u,v)f(u,v)w(u,v)。 现在，你需要保证流量最大的前提下，使费用最小，称作最小费用最大流（Min Cost Max Flow）。 做法 算法 用贪心算法。只需每次找费用最小的增广路，然后不断增广即可，证明略去，但是记住只要没有负圈这个算法就是正确的。（注意：原图费用不可以出现负圈） 数据结构 怎么存图？注意在费用流中是需要处理重边问题的，还需要方便的获取反向边。 习惯上，我们采用的是边表+邻接表记录出边在边表中的下标的数据结构。一条边和他反向边是存在一起的，即在边表的下标可以通过异或 1 得到。（0^1=1，1^1=0，6^1=7,7^1=6） 如果不明白，看以下代码理解。 1234567891 ...

数！论！ 逆元是个好东西，不会也要背板子。 乘法逆元 定义 若 ax≡1(modp)ax\equiv 1 \pmod pax≡1(modp)，则称 xxx 为 aaa 在模 ppp 意义下的乘法逆元，记作 a−1a^{-1}a−1。 此时存在 x/a≡xa−1(modp)x/a\equiv xa^{-1} \pmod px/a≡xa−1(modp)。这样就可以方便的计算在模意义下的除法操作。 例：在 p=13p=13p=13 时，3×9≡1(mod13)3\times 9 \equiv 1 \pmod {13}3×9≡1(mod13)。则对于任意 xxx，都有 x÷3≡9x(mod13)x\div 3\equiv 9x \pmod {13}x÷3≡9x(mod13)。 验证一下：27÷3=9,27∗9=243=18×13+927\div 3 = 9, 27*9 = 243 = 18 \times 13 + 927÷3=9,27∗9=243=18×13+9。 为什么？ 为什么若 aa−1≡1(modp)aa^{-1}\equiv 1 \pmod paa−1≡1(modp)，则 x/a ...

来学数学！ 拓展欧几里得算法 (EXGCD) 求 ax+by=gcd⁡(a,b)ax+by=\gcd(a,b)ax+by=gcd(a,b) 的整数解。 例：求 6x+15y=gcd⁡(6,15)=36x+15y=\gcd(6,15)=36x+15y=gcd(6,15)=3 的整数解。 有一组整数解 x=3,y=−1x=3,y=-1x=3,y=−1。（解不唯一） 求一组可行解 设存在 x1,y1,x2,y2x_1,y_1,x_2,y_2x1​,y1​,x2​,y2​，满足 {ax1+by1=gcd⁡(a,b)bx2+(a mod b)y2=gcd⁡(b,a mod b)\left\{ \begin{aligned} &ax_1+by_1=\gcd(a,b)\\ &bx_2+(a\bmod b)y_2=\gcd(b,a\bmod b)\\ \end{aligned} \right. {​ax1​+by1​=gcd(a,b)bx2​+(amodb)y2​=gcd(b,amodb)​ 因为 gcd⁡(a,b)=gcd⁡(b,a mod b)\gcd(a,b)=\gcd(b,a\ ...

学习一下如何在 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) ...