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₁23…m<=n，
题目保证存在满足要求的数列P, 现在要求max(P_i+1 - P_i) [1<=i

分析：

其实就是找一个从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);
}

我们可以写两个二分查找的函数，来返回最小的大于 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;
}

以及最大的小于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;
}

我们可以从前往后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];}

然后从后往前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];}

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

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

完整代码：

#include 
#include 
#include  
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;
}

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

//31ms
#include 
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;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！