玖的数学&算法录
0%

置顶 | 发表于 更新于
本文字数： 790 阅读时长 ≈ 1 分钟

致谢

首先我能够有这一个博客，与我的朋友remy有很大的关系，这里特别感谢他这几天一直来帮我debug。

该博客会以数学与算法为主，其中数学以分析方向为主，其他方向我不擅长，算法里面的数学内容大概率会更新，但不会有太多。

特别提醒：该日志会不断更新（？

2023 寒假

牛客寒假训练营好玩，经常写一会就睡着了。

2023寒假训练营第一场

2023寒假训练营第二场

2023寒假训练营第三场

2023寒假训练营第四场

2023寒假训练营第五场

2023寒假训练营第六场

2022 暑假

数学：

数学分析每日一题

2022牛客多校：（太坐牢了，不想补了）

2022牛客多校第一场

2022牛客多校第二场

2022牛客多校第三场

2022牛客多校第四场

2022牛客多校第五场

2022牛客多校第六场

2022牛客多校第七场

2022牛客多校第八场

2022牛客多校第九场

2022牛客多校第十场

标签

数学分析：

一个常见无穷积分的证明

一道非数学系竞赛题的推广

数列极限的几种计算方法

算法笔记：

算法笔记（00）：STL专题

算法笔记（01）：排序中的算法

算法笔记（02）：背包问题

算法笔记（03）：树状数组与线段树

算法笔记（04）：基础dp

算法笔记（05）：并查集

Codeforces讲解:

Educational Codeforces Round 124 (Rated for Div. 2)

Educational Codeforces Round 131 (Rated for Div.2)

受牛客多校队友影响，也开始了Codeforces补千题的计划

Codeforces补题

代码模板

对于该ACM代码模板，不保证里面的代码能考虑到所有的情况，因此如果借用模板没通过，多读读题。

链接

板子

2022目标

Codeforces rank 蓝名门槛至中间 (多练)

以及EDG夺冠的Flag（希望毕业前能完成）：

Stein 《复分析》第四版

啃裴砖、樊砖

公众号：玖的数学天地MathUniverse

发表于 更新于
本文字数： 5.4k 阅读时长 ≈ 5 分钟

前缀和

截断数组（acwing）

题面：

给定一个长度为 n 的数组 a

现在，要将数组从中间截断，得到三个 非空 子数组。

要求，三个子数组内各元素之和都相等，问有几种截法。

数据范围：

$$1 \leq n \leq 10^5 , -10000 \leq a_i \leq 10000$$

题解：

如果整个数组之和 除不尽3，那么一定分割不成功，如果现在的段刚好为sum / 3那么说明这一段能分出来，用 a去记录可以分成几段，最后在找一个位置，使得sum / 3 * 2的位置即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void JiuCherish(){
   int n;
   std::cin >> n;
   i64 sum = 0;
   for(int i=1;i<=n;i++) {
      std::cin >> a[i];
      b[i] = b[i - 1] + a[i];
      sum += a[i];
   }
   int aa = 0;
   i64 ans = 0;
   if(sum % 3) {
      std::cout << 0 << endl;
      return;
   } else {
      for(int i=1;i<n;i++) {
         if(b[i] == sum / 3 * 2)  ans += aa;
         if(b[i] == sum / 3) aa++;
      }
      std::cout << ans << endl;
   }
}
前缀和

题面：

给你一个长度为 n 的整数序列。

在进行 m 次询问，每次询问输入一对l,r

问：区间[l,r]的和。

数据范围：

$$1 \leq l \leq r\leq n$$

$$1 \leq n,m \leq 100000$$

$$-1000 \leq a_i \leq 1000$$

题解：

模板题。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
void JiuCherish(){
    int n,q;
    std::cin >> n >> q;
    for(int i=1;i<=n;i++) {
        std::cin >> a[i];
        b[i] = b[i - 1] + a[i];
    }
    while(q--) {
        int l,r;
        std::cin >> l >> r;
        std::cout << b[r] - b[l - 1] << endl;
    }
}
子矩阵的和

题意：

给n 行 m 列的整数矩阵，在给 q次询问

问 x1,y1,x2,y2 所围成的矩阵数值之和是多少？

数据范围

$$1 \leq n,m \leq 1000$$

$$1 \leq q \leq 200000$$

$$1 \leq x_1 \leq x_2 \leq n$$

$$1 \leq y_1 \leq y_2 \leq m$$

$$-1000 \leq a_i \leq 1000$$

题解：

模板题

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void JiuCherish(){
    int n,m,q;
    std::cin >> n >> m >> q;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            std::cin >> a[i][j];
        }
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            b[i][j] = b[i - 1][j] + b[i][j - 1] - b[i - 1][j - 1] + a[i][j];
        }
    }
    while(q--) {
        int x1,x2,y1,y2;
        std::cin >> x1 >> y1 >> x2 >> y2;
        std::cout << b[x2][y2] - b[x2][y1 - 1] - b[x1 - 1][y2] + b[x1 - 1][y1 - 1] << endl;
    }
}
k倍区间

题意：

给长度为 n 的数列，约定 k 倍区间表示 数列区间[i,j]的和是 k 的倍数。

问数列中有几个 k 被区间。

数据范围

$$1 \leq n,k \leq 100000$$

$$1 \leq a_i \leq 100000$$

题解：

只需要知道

$$(a + b)mod c 等价于 a modc + bmod c$$

即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void JiuCherish(){
    int n,k;
    std::cin >> n >> k;
    i64 sum = 0;
    for(int i=1;i<=n;i++) {
        std::cin >> a[i];
        b[i] = b[i - 1] + a[i];
    }
    res[0] = 1;
    for(int i=1;i<=n;i++) {
        sum += res[b[i] % k];
        res[b[i] % k]++;
    }
    std::cout << sum << endl;
}

差分

改变数组元素

给定一个空数组 V 和一个整数数组a。

现在对数组V进行 n 次操作

第 i 次操作的具体流程如下：

  1. 从数组 V 尾部插入整数 0。
  2. 将位于数组 V 末尾的 ai 个元素都变为 1（已经是 1 的不予理会）。

注意：

  • ai 可能为 0，即不做任何改变。
  • ai 可能大于目前数组 V 所包含的元素个数，此时视为将数组内所有元素变为 1。

请你输出所有操作完成后的数组 V。

数据范围

$$1 \leq T \leq 20000$$

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

$$0 \leq a_i \leq n$$

保证 $$\sum T * n < 2 \times 10^5$$

题解：

维护区间，用当前数是k，就把该数和该数前面k个数变成1。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void JiuCherish(){
    int n;
    std::cin >> n;
    for(int i=1;i<=n;i++) std::cin >> a[i];
    int l = 1e9;
    std::vector<int> ans;
    for(int i=n;i>=1;i--) {
        l = std::min(l,i - a[i] + 1);
        if(l <= i) {
            ans.pb(1);
        } else {
            ans.pb(0);
        }
    }
    std::reverse(ans.begin(),ans.end());
    for(auto x : ans) std::cout << x << " ";
    std::cout << endl;
}
差分

给你一个 长度为 n 的数组

你有 m 次操作，包括了 l,r,c，表示将数组 [l,r] 之间的每个数都加上 c

请你输出进行完成所有操作后的数组。

数据范围：

$$1 \leq l \leq r\leq n$$

$$1 \leq n,m \leq 100000$$

$$-1000 \leq c \leq 1000$$

$$-1000 \leq a_i \leq 1000$$

题解

模板

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void JiuCherish(){
    int n,q;
    std::cin >> n >> q;
    for(int i=1;i<=n;i++) {
        std::cin >> a[i];
        b[i] = a[i] - a[i - 1];
    }
    while(q--) {
        int l,r,x;
        std::cin >> l >> r >> x;
        b[l] += x;
        b[r + 1] -= x;
    }
    int x = 0;
    for(int i=1;i<=n;i++) {
        x += b[i];
        std::cout << x << " ";
    }
}
差分矩阵

输入一个 n 行 m 列的整数矩阵，再输入 q 个操作，每个操作包含五个整数 x1,y1,x2,y2,c，其中 (x1,y1)(x1,y1) 和 (x2,y2)(x2,y2) 表示一个子矩阵的左上角坐标和右下角坐标。

每个操作都要将选中的子矩阵中的每个元素的值加上 c。

请你将进行完所有操作后的矩阵输出。

数据范围：

$$1 \leq n,m \leq 1000$$

$$1 \leq q \leq 100000$$

$$1 \leq x_1 \leq x_2\leq n$$

$$1 \leq y_1 \leq y_2\leq m$$

$$-1000 \leq c \leq 1000$$

$$-1000 \leq a_i \leq 1000$$

题解

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void JiuCherish(){
    int n,m,q;
    std::cin >> n >> m >> q;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            std::cin >> res[i][j];
            ans[i][j] = -res[i - 1][j] - res[i][j - 1] + res[i - 1][j - 1] + res[i][j];
        }
    }
    while(q--) {
      int x1,x2,y1,y2,val;
      std::cin >> x1 >> y1 >> x2 >> y2 >> val;
      x2++;
      y2++;
      ans[x1][y1] += val;
      ans[x1][y2] -= val;
      ans[x2][y2] += val;
      ans[x2][y1] -= val;
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            res[i][j] = res[i - 1][j] + res[i][j - 1] - res[i - 1][j - 1] + ans[i][j];
            std::cout << res[i][j] << " ";
        }
        std::cout << endl;
    }
}

增减序列

给定一个长度为 n 的数列，每次可以选一个区间 [l,r] 使下标在这个区间内的数都加一或者都减一。

求至少需要多少次操作才能使数列中的所有数都一样，并求出在保证最少次数的前提下，最终得到的数列可能有多少种。

数据范围：

$$0 < n \leq 10^5$$

$$0 \leq a_i < 2147483648$$

题解：

找到中位数即可。

最少操作次数就是最少的pos或neg 加上这两个差值的绝对值。

结果就是：差值绝对值+1。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void JiuCherish(){
    int n;
    std::cin >> n;
    for(int i=1;i<=n;i++) {
        std::cin >> a[i];
        b[i] = a[i] - a[i - 1];
    }
    i64 pos = 0,neg = 0;
    for(int i=2;i<=n;i++) {
        if(b[i] > 0) pos += b[i];
        else neg -= b[i];
    }
    std::cout << std::min(pos,neg) + std::abs(pos - neg) << endl;
    std::cout << std::abs(pos - neg) + 1 << endl;
}

二分

数的范围

给一个升序的长度为 n 的整数数组，以及 q 个查询。

对于每个查询，返回一个元素 k 的起始位置和终止位置（从 0 开始计数）

如果数组中不存在该元素，返回两个 -1 -1。

数据范围：

$$1 \leq n \leq 100000$$

$$1 \leq q \leq 10000$$

$$1 \leq k \leq 10000$$

题解：

第一次二分看看左边界是否能找到数，找不到直接结束。

输出第一次左边界找到的。

第二次二分找到最右边是否能找到数。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void JiuCherish(){
    int n,q;
    std::cin >> n >> q;
    for(int i=0;i<n;i++) std::cin >> a[i];
    while(q--) {
        int x;
        std::cin >> x;
        int l = 0,r = n - 1;
        int mid = 0;
        while(l < r) {
            mid = l + r >> 1;
            if(a[mid] >= x) r = mid;
            else l = mid + 1;
        }
        if(a[l] != x) {
            std::cout << "-1 -1" << endl;
            continue;
        }
        std::cout << l <<" ";
        l = 0,r = n - 1;
        while(l < r) {
            mid = l + r + 1 >> 1;
            if(a[mid] <= x) l = mid;
            else r = mid - 1;
        }        
        std::cout << l << endl;
    }
}

发表于 更新于
本文字数： 7.4k 阅读时长 ≈ 7 分钟

感受：感觉整场都是诈骗题和一小部分妙妙结论题。

难度：

签到：ALCH

简单：DKM

中等偏下：GFE

中等偏上：BIJ

阅读全文 »

发表于 更新于
本文字数： 5.5k 阅读时长 ≈ 5 分钟

kmp

注意：next数组不要用next命名（可能和关键字重复）。

简单介绍：

字符串匹配问题：字符串 s 中查找某个字符串 p 是否出现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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 中出现了几次。

题解：很裸。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
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];

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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值，最后反向打印即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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 中出现了几次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
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。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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();
}

发表于 更新于
本文字数： 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。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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) 的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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 << " ";
    }
}

思路二：