题目描述

给定一个长度为 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$
测试点编号 $m \le$ $n \le$ $\sum n \le$ $t_i \le$
$1 – 4$ $10$ $10^3$ $10^4$ $10^6$
$5- 8$ $10^2$ $10^5$ $ 10^6 $ $10^2$
$9- 12$ $10^2$ $10^5$ $10^6$ $10^6$
$13- 17$ $10^6$ $10^6$ $10^6 $ $10^6$
$18- 20$ $10^6$ $10^6$ $5 \times 10^6$ $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;
}