玖的数学&算法录

const int MAXN = 2e5 + 10;
int n,m;
int nxt[MAXN],f[MAXN];
char s[MAXN],p[MAXN];
//kmp head

void kmp() {
    n = strlen(s + 1);
    m = strlen(p + 1);
    int j = 0;
    nxt[1] = 0;
    for(int i = 2; i <= m; i++) {
        while(j > 0 && p[j + 1] != p[i]) 
            j = nxt[j];
        if(p[j + 1] == p[i])
            j++;
        nxt[i] = j;
    }

    j = 0;
    //回退
    for(int i = 1; i <= n; i++) {
        while((j == m) || (j > 0 && p[j + 1] != s[i]))
            j = nxt[j];
        if(p[j + 1] == s[i])
            j++;
        f[i] = j;
    }
}

时间复杂度

O（n + m)

Question 1: KMP板子题

给你两个字符串 a,b，字符串均由小写字母组成，现在问你 b 在 a 中出现了几次。

题解：很裸。

const int MAXN = 2e5 + 10;
int n,m;
int nxt[MAXN],f[MAXN];
char s[MAXN],p[MAXN];
//kmp head

void kmp() {
    //算nxt
    n = strlen(s + 1);
    m = strlen(p + 1);
    int j = 0;
    nxt[1] = 0;
    for(int i = 2; i <= m; i++) {
        while(j > 0 && p[j + 1] != p[i]) 
            j = nxt[j];
        if(p[j + 1] == p[i])
            j++;
        nxt[i] = j;
    }

    j = 0;
    //回退 算f
    for(int i = 1; i <= n; i++) {
        while((j == m) || (j > 0 && p[j + 1] != s[i]))
            j = nxt[j];
        if(p[j + 1] == s[i])
            j++;
        f[i] = j;
    }

    int ans = 0;
    for(int i=1;i<=n;i++) {
        if(f[i] == m) ++ans;
    }
    if(!ans) {
        std::cout << -1 << endl;
        std::cout << -1 << endl;
    } else {
        std::cout << ans << endl;
        for(int i=1;i<=n;i++) {
            if(f[i] == m)
                std::cout << i - m + 1 << " ";
        }
        std::cout << endl;
    }
}


void JiuCherish(){
    std::cin >> s + 1 >> p + 1;
    kmp();
}

Question 2:最小循环覆盖

给你一个字符串 a，你需要求出这个字符串的最小循环覆盖的长度。

b 是 a 的最小循环覆盖，当且仅当 a 是通过 b 复制多次并连接后得到的字符串的前缀，且 b 是满足条件的字符串中长度最小的。

输入一个字符串 a，输出一个数表示最小循环覆盖 b 的长度。

题解：

简单来说就是找任意一段字符，然后后面每一段字符和你找的字符是相同的。

妙妙结论题：找到的长度其实就是 m - nxt[m];

int n,m;
int nxt[MAXN],f[MAXN];
char s[MAXN],p[MAXN];
//kmp head

void kmp() {
    //算nxt
    n = strlen(s + 1);
    m = strlen(p + 1);
    int j = 0;
    nxt[1] = 0;
    for(int i = 2; i <= m; i++) {
        while(j > 0 && p[j + 1] != p[i]) 
            j = nxt[j];
        if(p[j + 1] == p[i])
            j++;
        nxt[i] = j;
    }

    j = 0;
    //回退 算f
    for(int i = 1; i <= n; i++) {
        while((j == m) || (j > 0 && p[j + 1] != s[i]))
            j = nxt[j];
        if(p[j + 1] == s[i])
            j++;
        f[i] = j;
    }
    std::cout << m - nxt[m] << endl;
}


void JiuCherish(){
    std::cin >> p + 1;
    kmp();
}

Question 3:[UVA 12467] Secret word

给你一个字符串 s，你需要找出 s 中最长的 secret word，一个字符串 p 是 secret word 需要满足：

p 是 s 的子串（p 可以与 s 相等）；
将 p 翻转后是 s 的前缀。

输入一行字符串 s，输出一行字符串为你求得的 p。

题解：就是讲字符串延长2倍，然后跑一个kmp，找到最大的nxt值，最后反向打印即可。

int n,m;
int nxt[MAXN],f[MAXN];
char s[MAXN],p[MAXN];
//kmp head

void kmp() {
    //算nxt
    n = strlen(s + 1);
    m = strlen(p + 1);
    p[m + 1] = '#';
    for(int i = m + 2,j = m; j; --j, ++i)
        p[i] = p[j];
    int j = 0;
    nxt[1] = 0;
    for(int i = 2; i <= m + m + 1; i++) {
        while(j > 0 && p[j + 1] != p[i]) 
            j = nxt[j];
        if(p[j + 1] == p[i])
            j++;
        nxt[i] = j;
    }

    j = 0;
    //回退 算f
    for(int i = 1; i <= n; i++) {
        while((j == m) || (j > 0 && p[j + 1] != s[i]))
            j = nxt[j];
        if(p[j + 1] == s[i])
            j++;
        f[i] = j;
    }
    int x = 0;
    for(int i=m+2;i<=m+m+1;i++) {
        x = std::max(x,nxt[i]);
    }
    for(int i = x;i>=1;i--) {
        std::cout << p[i];
    }
}


void JiuCherish(){
    std::cin >> p + 1;
    kmp();
}

扩展KMP（Z algorithm）

与kmp区别：两者求next数组不同，一个是到字符s[i]结束，另一个是从字符s[i]开始。

思路：

代码解读：

对于满足 i > 1 的位置 i , z[i] 表示字符串 s 和后缀 s[i]~s[n] 的最长公共前缀的长度。

如何求 z 数组呢？

首先 z[1] = 0 ，开始往后枚举每个位置，去计算。

若是算第 z[i] 的值，此时从 1 到 i 的结果一定是算好的。

对于 j, 有 s[j] … s[j + z[j] - 1] 和 s[1] … s[z[j]] 完全相等。

为了计算 z[i] ，在枚举 i 的过程中，我们需要维护一个 R 最大的区间 [L,R]。

其中 L = j (j < i), R = j + z[j] - 1。

情况一：假如 i <= R

我们知道：s[L] 到 S[R] 一定和区间 S[1] 到 S[R - L + 1] 是一一映射的关系。

那么我们约定一个数 k = i - L + 1，那么此时在[L,R]中的位置对应了 k 在 [1,R - L + 1] 中的位置，此时 s[i] 到 S[R] 和 S[k] 到 S[R - L + 1 是一一映射的。

Case1 : 如果 z[k] < R - i + 1，那么匹配不到右边，此时只能z[i] = z[k]

Case2 : 如果 z[k] >= R - i + 1 那么 i 是能匹配到 R 的，这时从 R + 1 开始暴力向后匹配即可。

情况二：假如 i > R

那么暴力枚举匹配即可。

求出 z[i] 后需要更新 L 和 R。

void exkmp() {
    int L = 1, R = 0;
    z[1] = 0;
    for(int i = 2; i <= n; i++) {
        if(i > R)  z[i] = 0;
        else  {
            int k = i - L + 1;
            z[i] = std::min(z[k],R - i + 1);
        }
        while(i + z[i] <= n && s[z[i] + 1] == s[i + z[i]]) ++z[i];
        if(i + z[i] - 1 > R)
            L = i,R = i + z[i] - 1; 
    }
}

时间复杂度：O(n)

Question 1: exkmp板子题（同上面的kmp板子）

给你两个字符串 a,b，字符串均由小写字母组成，现在问你 b 在 a 中出现了几次。

const int MAXN = 2e5 + 10;
int n,m;
int z[MAXN];
char s[MAXN],p[MAXN];
//exkmp head

void exkmp() {
    n = strlen(s + 1);
    m = strlen(p + 1);
    p[m + 1] = '#';
    for(int i = m + 2, j = 1; j <= n; i++, j++) p[i] = s[j];
    int L = 1, R = 0;
    z[1] = 0;
    for(int i = 2; i <= n + m + 1; i++) {
        if(i > R)  z[i] = 0;
        else  {
            int k = i - L + 1;
            z[i] = std::min(z[k],R - i + 1);
        }
        while(i + z[i] <= n + m + 1 && p[z[i] + 1] == p[i + z[i]]) ++z[i];
        if(i + z[i] - 1 > R)
            L = i,R = i + z[i] - 1; 
    }
    int ans = 0;
    for(int i = m + 1;i <= n + m + 1;i++) {
        if(z[i] == m) ++ans;
    }
    if(!ans) 
        std::cout << -1 << endl << -1 << endl;
    else {
        std::cout << ans << endl;
        for(int i = m + 2;i <= n + m + 1;i++) {
            if(z[i] == m)
                std::cout << i - m - 1 << " ";
        }
        std::cout << endl;
    }
}

void JiuCherish(){
    std::cin >> s + 1 >> p + 1;
    exkmp();
}

Question 2:[CF 126B] Password

给你一个字符串 s，由小写字母组成，你需要求出其中最长的一个子串 p，满足 p 既是 s 的前缀，又是 s 的后缀，且在 s 中以非前缀后缀的形式出现过。如果找不到输出 Just a legend。

输入一行一个字符串 s，输出一行一个字符串 p。

const int MAXN = 1e6 + 10;
int n,m;
int z[MAXN];
char s[MAXN];
//exkmp head

void exkmp() {
    n = strlen(s + 1);
    int L = 1, R = 0;
    z[1] = 0;
    for(int i = 2; i <= n; i++) {
        if(i > R)  z[i] = 0;
        else  {
            int k = i - L + 1;
            z[i] = std::min(z[k],R - i + 1);
        }
        while(i + z[i] <= n + m + 1 && s[z[i] + 1] == s[i + z[i]]) ++z[i];
        if(i + z[i] - 1 > R)
            L = i,R = i + z[i] - 1; 
    }
    int ans = 0,x = 0;
    for(int i=1;i<=n;i++) {
        if(i + z[i] - 1 == n) {
            if(x >= z[i]) {
                ans = std::max(ans,z[i]);
            }
        }
        x = std::max(x,z[i]);
    }
    if(!ans) {
        std::cout << "Just a legend" << endl;
    } else {
        for(int i=1;i<=ans;i++) std::cout << s[i];
    }
}

void JiuCherish(){
    std::cin >> s + 1;
    exkmp();
}

ABC283

发表于 2023-01-01 更新于 2023-01-10
本文字数： 2.1k 阅读时长 ≈ 2 分钟

D - Scope

题面

给你一个字符串只包括了”(“,”)”和小写字母，如果通过以下步骤，能使字符串为空，那么称字符串是好的：

删除所有小写字母
不停地删除连续的**()**

给定一个好的字符串，并且你有一个盒子，你有以下的操作：

1.如果当前 s[i] 是小写字母，将小写字母放入盒子中，盒子中不能出现两个相同的小写字母。

2.如果当前 s[i] 是 “(“ ，那么什么都不做。

3.如果当前 s[i] 是 “)” ，取小于 i 的最大的 j , 使 Si ~ Sj 这个子串是好的，将 j 到 i 操作中放入的小球全部取出。

如果违背了1，那么输出No，否则输出Yes。

数据范围

$$1 \leq |S| \leq 3 \times 10^5$$

思路：模拟

1：如果当前字符为”(“，那么将cnt 增加1，为一个左括号。

2：如果当前字符为小写字母，如果说当前字符没有出现过，那么让它的值为cnt，反之输出No。

3：如果当前字符为”)”,那么遍历一次26个字母，如果满足等于cnt，那么将其清0。

代码

int st[30];

void JiuCherish(){
    std::string s;
    std::cin >> s;
    int n = s.length();
    int cnt = 1;
    memset(st,false,sizeof(st));
    for(int i=0;i<s.length();i++) {
        if(s[i] == '(') ++cnt;
        else if(s[i] >= 'a' && s[i] <= 'z') {
            if(st[s[i] - 'a']) {
                std::cout << "No" << endl;
                return;
            } else {
                st[s[i] - 'a'] = cnt;
            }
        } else if(s[i] == ')'){
            for(int j=0;j<26;j++) {
                if(st[j] == cnt) st[j] = false;
            }
            --cnt;
        }
    }
    std::cout << "Yes" << endl;
}

E - Don’t Isolate Elements

题面

给定一个 n * m 的 01 矩阵 a,称位于第 i 行第 j 列的元素为 ai,j。

你可以进行如下的操作任意次（可以为0次）：

选择任意一行，翻转此行内的所有元素。

如果当前 [i,j] 的 01 性与 [i-1] [j], [i + 1] [j], [i] [j - 1],[i] [j + 1] 均不相同，那么我们称其点为被隔离点。

请输出使得给定矩阵中没有元素被隔离所需要的最小操作数，如果无论如何操作都无法满足要求则输出 -1。

数据范围

$$2 \leq n,m\leq1000$$

F - Permutation Distance

题面：

你有一个1~n 的排列 p = (p1,p2,…,pn)

你需要对每个 i 求得

$$\displaystyle D_i = \min_{j \neq i} {(|p_i - p_j| + |i - j|)}$$

数据范围：

$$\displaystyle 2 \leq n \leq 2 \times 10^5$$

思路一：暴力

对于每个点，向两边暴力枚举更新答案，如果下标太远则不可能更新到。

时间复杂度：O(n ^ {3 / 2})。

没明白：copy by ppip的思路

复杂度证明：显然一个点向两边最多跑 O(D_i) 次就会停止。所以复杂度为 O*(∑D**i)。

而每个点取离它最近的一个点连边，这个显然能构成一个基环树森林。

同时，在最小生成基环树森林中，每个点都必须要有一个出边，所以给每个点钦定最短的那个出边是一定能构成最小生成基环树森林的。

而平面曼哈顿距离最小生成基环树（森林）在点的横纵坐标范围均是 [1,n] 的整数时，上界是 O(n\sqrt n) 的。

代码

int a[MAXN];

int dis(int x,int y) {
    return abs(x - y) + abs(a[x] - a[y]);
}

void JiuCherish(){
    int n;
    std::cin >> n;
    for(int i=1;i<=n;i++) std::cin >> a[i];
    for(int i=1;i<=n;i++) {
        int d = 1e9; 
        for(int j = i + 1;j - i < d && j <= n;j++) {
            d = std::min(d,dis(i,j));
        }
        for(int j = i - 1;i - j < d && j >= 1;j--) {
            d = std::min(d,dis(i,j));
        }
        std::cout << d << " ";
    }
}

思路二：

算法笔记（05）：并查集

发表于 2022-10-25 更新于 2024-09-29
本文字数： 1.1k 阅读时长 ≈ 1 分钟

并查集

并查集是一种树形数据结构，经常用于处理集合之间的操作（如元素查找、集合合并。

n元素，m次查询

复杂度：O(m)，最坏复杂度：O（mlogn)

并查集初始化

void init(int n) {
    for(int i = 1; i <= n; i++) {
        fa[i] = i;
        sz[i] = dep[i] = 1;
    }
}

集合合并

讲元素x,y所在的集合合并。

首先先找到 x,y 对应的代表元（fa 等于自己的元素）

将其中一个代表元的 fa 指向另外一个，那么原来在这个代表元下的所有元素的代表元都会指向另外一个。

int Findset(int x) {
    if(fa[x] == x) return x;
    return Findset(fa[x]);
}

void Union(int x,int y) {
    int fx = Findset(x),fy = Findset(y);
    if(fx == fy) return;
    fa[fx] = fy;
}

路径压缩

通过缩短并查集的路径，具体是查询过程中，把沿途的每个节点的 fa 都设为集合代表元。

int Findset(int x) {
   if(x == fa[x]) return x;
   fa[x] = Findset(fa[x]);
   return fa[x];
}

或者

1
2
3

int Findset(int x) {
   return x == fa[x] ? x : (fa[x] == Findset(fa[x]));
}

启发式合并

合并两个集合优化的方法。

在合并集合的时候，我们尽量选择包含元素个数少的集合，将它合并到另一个集合中，使需要改变代表元的元素数量尽可能少。

小集合合并到较大集合称为启发式合并。

时间复杂度：log

void Union(int x,int y) {
    int fx = Findset(x),fy = Findset(y);
    if(fx == fy) return;
    if(sz[fx] > sz[fy])
        std::swap(fx,fy);
    fa[fx] = fy;
    sz[fy] += sz[fx];
}

按深度合并

深度小的集合合并到深度大的一方。

时间复杂度：log

路径压缩过程中，有可能破坏我们维护的深度值，但总体复杂度不会差。

void Union(int x,int y) {
    int fx = Findset(x),fy = Findset(y);
    if(fx == fy) return;
    if(dep[fx] > dep[fy])
        std::swap(fx,fy);
    fa[fx] = fy;
    if(dep[fx] == dep[fy]) //只有两棵树深度相等时才会更新
        dep[fy]++;
}

算法笔记（05）：并查集

发表于 2022-10-25 更新于 2024-05-06
本文字数： 1.1k 阅读时长 ≈ 1 分钟

并查集

并查集是一种树形数据结构，经常用于处理集合之间的操作（如元素查找、集合合并。

n元素，m次查询

复杂度：O(m)，最坏复杂度：O（mlogn)

并查集初始化

void init(int n) {
    for(int i = 1; i <= n; i++) {
        fa[i] = i;
        sz[i] = dep[i] = 1;
    }
}

集合合并

讲元素x,y所在的集合合并。

首先先找到 x,y 对应的代表元（fa 等于自己的元素）

将其中一个代表元的 fa 指向另外一个，那么原来在这个代表元下的所有元素的代表元都会指向另外一个。

int Findset(int x) {
    if(fa[x] == x) return x;
    return Findset(fa[x]);
}

void Union(int x,int y) {
    int fx = Findset(x),fy = Findset(y);
    if(fx == fy) return;
    fa[fx] = fy;
}

路径压缩

通过缩短并查集的路径，具体是查询过程中，把沿途的每个节点的 fa 都设为集合代表元。

int Findset(int x) {
   if(x == fa[x]) return x;
   fa[x] = Findset(fa[x]);
   return fa[x];
}

或者

1
2
3

int Findset(int x) {
   return x == fa[x] ? x : (fa[x] == Findset(fa[x]));
}

启发式合并

合并两个集合优化的方法。

在合并集合的时候，我们尽量选择包含元素个数少的集合，将它合并到另一个集合中，使需要改变代表元的元素数量尽可能少。

小集合合并到较大集合称为启发式合并。

时间复杂度：log

void Union(int x,int y) {
    int fx = Findset(x),fy = Findset(y);
    if(fx == fy) return;
    if(sz[fx] > sz[fy])
        std::swap(fx,fy);
    fa[fx] = fy;
    sz[fy] += sz[fx];
}

按深度合并

深度小的集合合并到深度大的一方。

时间复杂度：log

路径压缩过程中，有可能破坏我们维护的深度值，但总体复杂度不会差。

void Union(int x,int y) {
    int fx = Findset(x),fy = Findset(y);
    if(fx == fy) return;
    if(dep[fx] > dep[fy])
        std::swap(fx,fy);
    fa[fx] = fy;
    if(dep[fx] == dep[fy]) //只有两棵树深度相等时才会更新
        dep[fy]++;
}

算法笔记（00）：STL专题

发表于 2022-10-04 更新于 2022-10-07
本文字数： 4.4k 阅读时长 ≈ 4 分钟

阅读全文 »

2022牛客多校第十场

发表于 2022-08-20 更新于 2022-08-15
本文字数： 0 阅读时长 ≈ 1 分钟