Codeforces #704 (Div. 2) C. Maximum width Apare_xzc_c》maximum width

Codeforces #704 (Div. 2) C. Maximum width

Apare_xzc

---

题目链接： Maximum width

题意：

         两个字符串s, t, 长度分别为n, m (1<=m<=n<=2E5)
现在要求把t的每一位对应到s相同字符的位置上，即t[i] = s[P_i] 对于每个1<=i<=m都成立，并且要求1<=P₁<P₂<P₃…<P_m<=n，
题目保证存在满足要求的数列P, 现在要求max(P_i+1 - P_i) [1<=i<m]

分析：

其实就是找一个从t到s的映射关系P1， P2, … Pm, 使得t[i] = s[P_i], 并且P数列递增。有若干个满足条件的数列P，题目 保证一定有一个，求数列间相邻元素距离的最大值

显然我们可以知道，相邻元素的最大值一定出现在Pi+1 - Pi,
我们为了满足能都映射上去，肯定保险起见，贪心地每次Pi取当前未被映射的最左边的位置，即：P_i取大于P_i-1的，最小的位置pos，满足s[pos] = t[i]

为了满足最大的相邻距离最大化，我们肯定贪心地让其他的距离最小化，来迁就最大值的位置。如果让P_i+1和P_i的距离最大，那么我们肯定让P₁, P₂, …P_i-1每个都取最靠左的可行解，让P_m, P_m-1, P_m-2,…P_i+2都取最靠右的可行解。

我们设dpL[i] 表示t[1],t[2]…t[i] 这个前缀从左到右按顺序完全映射到字符串s上，P_i的最小值
设dpR[i]表示t[m], t[m-1]…t[i] 这个后缀从有到左按顺序完全映射到字符串s上，P_i的最大值

因为题目保证有合法的P，那么我们这样很谨慎从左到右取最小值，和从右到左取最大值，一定是合法的。
所以我们的答案就是max(dpR[x] - dpL[x]) (1<=x<=m)

那么我们如何求dpL和dpR呢？
显然我们可以递推。
dpL[x] ：大于dpL[x-1]的最小的t[x]这个字符在s中出现的位置。
显然我们可以二分查找来找到这个最小的大雨dpL[x-1]的位置。
因为题目说字符串仅出现小写英文字母，所以我们可以吧每一个字母出现的所有位置放到一个vector中，便于我们后续二分

vector<int> v[26];
for (int i = 0; i < n; ++i) {
    v[s[i] - 'a'].push_back(i);
}

vector<int> vt[26];
for (int i = 0; i < m; ++i) {
    vt[t[i] - 'a'].push_back(i);
}
1
2
3
4
5
6
7
8
9

我们可以写两个二分查找的函数，来返回最小的大于 pre的位置，

int get_first_index(const vector<int>& v, int pre) { 
    int len = v.size();
    int left = -1, right = len - 1;
    while (right - left > 1) {
        int mid = (left + right) >> 1;
        if (v[mid] > pre) {
            right = mid; //(]
        } else {
            left = mid;
        }
    }
    return right;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

以及最大的小于pre的位置

int get_last_index(const vector<int>& v, int pre) {
    int len = v.size();
    int left = 0, right = len;
    while (right - left > 1) {
        int mid = (left + right) >> 1;
        if (v[mid] < pre) {
            left = mid; //[)
        } else {
            right = mid;
        }
    }
    return left;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

我们可以从前往后dp推出dpL[0->m-1]:

 int pre_pos = -1;
 int ans = 0;
 for (int i = 0; i < m; ++i) {
     int pos = t[i] - 'a';
     int leftest_index = get_first_index(v[pos], pre_pos);
     dpL[i] = v[pos][leftest_index];
     pre_pos = dpL[i];
 }
1
2
3
4
5
6
7
8

然后从后往前dp推出dpR[m-1->0]:

  pre_pos = n;
  for (int i = m - 1; i >= 0; --i) {
      int pos = t[i] - 'a';
      int rightest_index = get_last_index(v[pos], pre_pos);
      dpR[i] = v[pos][rightest_index];
      pre_pos = dpR[i];
  }
1
2
3
4
5
6
7

最后只需要循环一遍，维护dpR[x] - dpL[x]的最大值即可

int ans = 0;
for (int i = 0; i < m-1; ++i) {
    ans = max(ans, dpR[i+1] - dpL[i]);
}
1
2
3
4

---

完整代码：

#include <cstdio>
#include <algorithm>
#include <vector> 
using namespace std;
const int N = 2E5+10;

int get_first_index(const vector<int>& v, int pre) { 
    int len = v.size();
    int left = -1, right = len - 1;
    while (right - left > 1) {
        int mid = (left + right) >> 1;
        if (v[mid] > pre) {
            right = mid; //(]
        } else {
            left = mid;
        }
    }
    return right;
}

int get_last_index(const vector<int>& v, int pre) {
    int len = v.size();
    int left = 0, right = len;
    while (right - left > 1) {
        int mid = (left + right) >> 1;
        if (v[mid] < pre) {
            left = mid; //[)
        } else {
            right = mid;
        }
    }
    return left;
}

int main(void) {
    static char s[N];
    static char t[N];
    int n,m;
    static int dpL[N]; // 最左的位置
    static int dpR[N]; // 最右的位置
    while (scanf("%d%d", &n, &m) != EOF) {
        scanf("%s%s", s, t);
        vector<int> v[26];
        vector<int> vt[26];
        
        for (int i = 0; i < n; ++i) {
            v[s[i] - 'a'].push_back(i);
        }
        for (int i = 0; i < m; ++i) {
            vt[t[i] - 'a'].push_back(i);
        }

        int pre_pos = -1;
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            int pos = t[i] - 'a';
            int leftest_index = get_first_index(v[pos], pre_pos);
            dpL[i] = v[pos][leftest_index];
            pre_pos = dpL[i];
        }
        
        pre_pos = n;
        for (int i = m - 1; i >= 0; --i) {
            int pos = t[i] - 'a';
            int rightest_index = get_last_index(v[pos], pre_pos);
            dpR[i] = v[pos][rightest_index];
            pre_pos = dpR[i];
        }
        
        for (int i = 0; i < m-1; ++i) {
            ans = max(ans, dpR[i+1] - dpL[i]);
        }
        printf("%d\n", ans);
    }
    return 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
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

当然，就算我们不二分，得到dpL和dpR也只需要O(n)遍历一遍即可，反而会更快一点

//31ms
#include <bits/stdc++.h>
using namespace std;
const int N = 2E5+10;
int rightest[N];
char s[N], t[N]; 
int main(void) {
	int n,m;
	while(scanf("%d%d", &n, &m) != EOF) {
		scanf("%s%s", s, t);	
		int ans = 0;
		for(int i = m-1, j = n-1 ; i>0; --i,--j) {
			while (s[j] != t[i]) {
				--j;
			}
			rightest[i] = j;
		}
		for(int i = 0, j = 0; i < m-1; ++i, ++j) {
			while (s[j] != t[i]) {
				++j;
			}
			ans = max(ans, rightest[i+1] - j);	
		}
		printf("%d\n", ans);	
	}
	
	return 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
27
28

---