题解 – 七里香（qlx.cpp）

题目描述

给定一个长度为 n 的数字串 a，和一个长度为 m 的数字串 b，保证 b 中出现的元素在 a 中都出现过，且 b 中任一元素只出现过一次。现求一个 a 的长度尽可能短，且尽可能靠左的子串，使 b 成为其子序列。

数据范围

多测

• $1≤T≤1000$
• $1≤m≤n≤10^6$
• $1≤∑n≤5×10^6$
• $1≤∑m≤10^6$
• $1≤s_i≤10^9$
• $1≤t_i≤10^6$

题解

1.错误解法：

正序枚举一遍 a，找出最开始的最后一个 b_1，再找出最前面一个 b_m。
显然，这样如国在 a 中现有一半的序列，再有完整的序列，答案是不完整的。

（对于这个思路其实我还抱着挣扎，但显然它不是很完整）

2.dp正解

思路来源：ShwStone

首先可以想到，对于 b 中的每一个元素，都有一个在 b 中的特定序号。对于每一个 a_i，首先判断存在于 b_i 。如果存在，那么就可以进行状态更新。我们可以设 dp_i 表示 a 中取到 b_i 时 在 a 中的最大左值。那么如果 a_i \in b，状态就从上一个 b_i 转移过来，由于求的是子序列问题，前面的取值就已经是当前最优，可以 dp。

AC Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxd(x, y) ((x) > (y) ? (x) : (y))
#define mind(x, y) ((x) < (y) ? (x) : (y))
#define abs_sub(x, y) ((x) > (y) ? (x) - (y) : (y) - (x))
const double eps = 1e-8;
const double pi = acos(-1.0);
const int N = 1e6 + 10;
inline int read() {
  char ch = getchar(); int p = 1, x = 0;
  while(!isdigit(ch)) {{if(ch == '-') p = -1;} ch = getchar();}
  while(isdigit(ch)) {x = x * 10 + ch - '0'; ch = getchar();}
  return x * p;
}
int T;
int rec[N];
int a[N];
int b[N];
int dp[N];
//每种字符在t中最多出现一次
int main()
{
  // freopen("qlx.in", "r", stdin);
  // freopen(".out", "w", stdout);
  scanf("%d", &T);
  while(T--) {
    memset(rec, 0, sizeof(rec));//多测清空
    memset(dp, 0xcf, sizeof(dp));//最小值（对于int来说稍大于-1e9）
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++) {
      a[i] = read();
    }
    for(int j = 1; j <= m; j++) {
      b[j] = read();
      rec[b[j]] = j;//记录这个数字在第二个串中出现的位置，由于只会出现一次，所以记录一次
    }
    pair<int, int> ans = make_pair(0x3f3f3f3f, -1);//first 记录长度，pair比较，second记录右值
    for(int i = 1; i <= n; i++) {
      int j = a[i] <= 1e6 ? rec[a[i]] : 0;
      if(j) {
        if(j == 1) dp[j] = max(dp[j], i);
        else dp[j] = max(dp[j], dp[j - 1]);
      }
      ans = min(ans, make_pair(i - dp[m] + 1, i));
    }
    if(ans.first > n) printf("-1\n");
    else printf("%d %d\n", ans.second - ans.first + 1, ans.second);
  }
  // cerr<<clock()<<endl;
  return 0;
}