immix's blog

例题来自《信息学奥赛一本通·提高篇》。 哈希函数 设字符串为 s=c1c2…cms=c_1c_2\ldots c_ms=c1​c2​…cm​，定义哈希函数 f(s)=(c1bm−1+c2bm−2+⋯+cmb0) mod Mf(s)=(c_1b^{m-1}+c_2b^{m-2}+\dots+c_mb^0)\bmod Mf(s)=(c1​bm−1+c2​bm−2+⋯+cm​b0)modM。其中 MMM 为一大质数，bbb 为小于 MMM 的任意整数。 比如说这样： 123456789const int b=114,M=1e9+9;int h(char* str){ int l = strlen(str); int res=0; for(int i=0;i<l;i++){ res=((ll)res*b+str[i])%M; } return res;} O(1) 求子串哈希 先预处理数组 HiH_iHi​ 代表字符串 sss 前 iii 位的哈希值。则字串 [l,r][l,r][l,r] 的哈希值可以表 ...

约定下标从 1 开始。 字符串匹配问题 给定字符串 s1s_1s1​，以及模式串 s2s_2s2​，求 s2s_2s2​ 在 s1s_1s1​ 内的所有出现位置。 一个很朴素的想法就是一位一位进行比较，复杂度 O(MN)O(MN)O(MN)，M,NM,NM,N 为两字符串长度。 123456789101112131415const int N = 1e6+5;char s1[N],s2[N];void brute_force(){ int l1 = strlen(s1); int l2 = strlen(s2); for(int i=0;i+l2<=l1;i++){ bool flag=1; for(int j=0;j<l2;j++){ if(s1[i+j]!=s2[j]){ flag=0;break; } } if(flag)printf("match at ...

众所周知，平衡树是提高数据结构。 平衡树 平衡树首先是一颗二叉搜索树 (BST)。二叉搜索树的定义如下： 空树是二叉搜索树。 若二叉搜索树的左子树不为空，则其左子树上所有点的附加权值均小于其根节点的值。 若二叉搜索树的右子树不为空，则其右子树上所有点的附加权值均大于其根节点的值。 二叉搜索树的左右子树均为二叉搜索树。 我们不难发现，在二叉搜索树上可以很方便的进行如下操作： 从大到小遍历 查询最值 插入元素 删除元素 求元素排名 求排名为 k 的元素 除了第一个操作复杂度为 O(n)O(n)O(n)，其他这些操作的复杂度都是 O(h)O(h)O(h) 的，其中 hhh 为树的高度。最坏情况下，二叉搜索树会退化成一条链，于是复杂度都退化为 O(n)O(n)O(n)，这是我们不希望看到的。因此，出现了平衡树的概念。平衡指：每一个结点的左子树和右子树高度差最多为 111，这样就可以保证所有复杂度都是在 O(log⁡n)O(\log n)O(logn) 级别完成的。 set 首先，在你写平衡树之前，先想想 STL 的 set （或者 multiset） 够不够你用。 从大到小遍历：可以 ...

U N R A T E D 今回のコンテストは、採点の遅れの影響で、Unratedとさせていただきます。申し訳ありません。 /　Due to the delay in scoring, this contest will be Unrated. We are sorry for the inconvenience. A. Echo 题意 给定一个字符串。每个字符输出两遍。 代码 1234567891011#include<bits/stdc++.h>using namespace std;int main(){ int x;cin>>x; string s;cin>>s; for(auto x:s){ cout<<x<<x; } return 0;} B. Base 2 题意 给定 A0,A1,…,A63A_0,A_1,\ldots,A_{63}A0​,A1​,…,A63​ 求 A020,A121,…,A63263A_02^0,A_12^1 ...

填坑。 前两期： 网络流初步 —— 最大流算法 (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++ ...