202311月大联盟 B题七里香

题面（简化）

给定一个长度为 $n$ 的字符串 $s$ ，要求选择一个长度尽可能短的子串，使得字符串 $t$ （长为 $m$ ）是它的子序列。输出该子串的左右端点 $l, r$ 。

在长度最短的前提下使得 $l$ 尽可能小。

字符串 $s$ 与 $t$ 用两个序列表示。

简化后的题面可能难以理解，防一组样例来进一步说明：

s : 5 3 5 3 6 6

t : 3 5 6

符合题目要求的子串为 3 5 3 6，输出为：2 4

题目有多组测试，数据范围： $1 \leq m \leq n \leq 10^{6}$ 。每种字符在字符串 $t$ 中至多出现 $1$ 次。

题解

1.从暴力出发

这题的暴力非常简单，直接枚举左端点 $l$ 然后向右匹配就可以。

这样的复杂度很显然是 $O (n^{2})$ ，可以在这道题拿到 $20 p t s$ 的分数。

如果你已经打完了这个暴力，那么恭喜你，其实你已经接近 $100 p t s$ 了。或许你不会相信，但是接下来的两个很简单的优化却可以完美地利用人性的弱点，创造出一个 复杂度错误 、可以被很简单地卡掉 ，但可以 A掉本题 、爆杀正解（可能比正解还是慢一点） 的抽象玄学代码，让你得以领略到暴力的优美。

让我们重走一遍我考试时的心路历程。

2.优化

一个很简单的优化：匹配之前预处理出 $s$ 中所有等于 $t_{1}$ 的位置，然后再对于每个这样的位置暴力向右匹配。

这个优化看似没什么用，但是它会把时间复杂度从 $O (n^{2})$ 变成：

$O (n * [s_{j} = t_{1}]), j \in [1, n]$ 。

可以发现 $[s_{j} = t_{1}] \leq n$ ，所以优化后复杂度不严格优于优化前。

3.进一步优化

在刚才的优化基础上，我们再进一步优化。

考虑一个问题：为什么一定要预处理出 $s$ 中等于 $t_{1}$ 的位置呢？

实际上，任何一个 $t_{i}$ 都可以胜任这个位置。只不过如果 $i$ 不为 $1$ 的话我们就需要向左右两个方向匹配了，那好像也没什么难的。

若预处理出 $s$ 中所有等于 $t_{i}$ 的位置，那么复杂度为 $O (n * [s_{j} = t_{i}]), j \in [1, n]$

考虑怎样选择 $t_{i}$ :显然 $t_{i}$ 在 $s$ 数组里出现的次数越少越好。等等，在 $s$ 中出现次数最少的 $t_{i}$ —— 这也是可以 $O (n)$ 预处理出来的！

为方便讲述，我们下面把在 $s$ 中出现次数最少的 $t_{i}$ 称为基准值，记为 $c$ 。

显然的， $c$ 在 $s$ 中最多出现 $\frac{n}{m}$ 次，即 $[s_{j} = c] \leq \frac{n}{m}$ ，则总复杂度为 $O (\frac{n^{2}}{m})$ 。

是不是感觉有点奇怪？ $m$ 是给定的 $t$ 数组长度极限值，但是它出现在了复杂度的分母上！

也就是说， $m$ 越大，对我们越有利； $m$ 较小时，复杂度可能退化为 $O (n^{2})$ ，我们就可以被卡掉。

那么来吧，放手一搏！我们就赌这道题目没有 $n$ 很大而 $m$ 很小的数据点，出题人一般都是把 $m$ 尽可能变大的！

显然，至少在这题，我们赢下了这场豪赌。

4.反思

虽然这道题确实是过了，但是我们还是得居安思危。这题不卡并不是所有题目都不会卡，在考后还是要多看正解。

这里有 @ShwStone 的 dp 做法，应该是正解：Link

下面有完整代码与自己干出来的一组 $h a c k$ 数据。

完整代码

代码中用桶进行了预处理，最后在 33~34 行得到了基准值 $c$ 与它在 $t$ 数组里的下表 $s v$ 。

36~62 行是匹配，还是有一点细节的，但是不难写。

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') w=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
	return s*w;
}
const int N=1e6+5;
vector<int> st;
int T,s[N],t[N],bkt[N],bks[N];
int main()
{
    //freopen("qlx.in","r",stdin);
    //freopen("qlx.out","w",stdout);
    T=read();
    for(int ccc=1,n,m;ccc<=T;ccc++)
    {
        int mins=INT_MAX,c=0,sv=0,flag=0,minl=INT_MAX,ans1=0,ans2=0;
        memset(bkt,0,sizeof(bkt));
        memset(bks,0,sizeof(bks));
        st.clear();
        n=read(),m=read();
        for(int i=1;i<=n;i++) s[i]=read();
        for(int i=1;i<=m;i++) t[i]=read(),bkt[t[i]]++;
        for(int i=1;i<=n;i++) if(s[i]<N) if(bkt[s[i]]) bks[s[i]]++;
        for(int i=1;i<=m;i++) if(bks[t[i]]&&bks[t[i]]<mins) mins=bks[t[i]],c=t[i];
        for(int i=1;i<=m;i++) if(t[i]==c){sv=i;break;}
        for(int i=1;i<=n;i++) if(s[i]==c) st.emplace_back(i);
        for(int i=0;i<st.size();i++)
        {
            int v=st[i],q=sv+1,resr=n,flag1=0,flag2=0;
            for(;v<=n;v++)
            {
                if(q>m) break;
                if(s[v]==t[q]) q++;
                flag1=1;
            }
            if(q<=m) continue;
            resr=v-flag1,v=st[i],q=sv-1;
            for(;v>=1;v--)
            {
                if(q<1) break;
                if(s[v]==t[q]) q--;
                flag2=1;
            }
            if(q<1)
            {
                if(resr-(v+flag2)+1<minl)
                {
                    ans1=v+flag2,ans2=resr;
                    minl=resr-(v+flag2)+1;
                }
                flag=1;
            }
        }
        if(flag) printf("%d %d\n",ans1,ans2);
        else printf("-1\n");
    }
}

hack数据

hack 数据生成代码：

#include<bits/stdc++.h>
using namespace std;
int n,len,m;
int main()
{
    freopen("qlx.in","w",stdout);
    cout<<1<<"\n";cout<<"1000000 2"<<endl;
    for(int i=1;i<=1000000/2;i++) cout<<"1 ";
    for(int i=1;i<=1000000/2;i++) cout<<"2 ";
    cout<<endl;
    cout<<"1 2"<<endl;
}

多测组数为一组， $s$ 数组前一半是 $1$ ，后一半是 $2$ 。 $n = 1 e 6, m = 2$ 。 $t$ 数组为：1 2。

就这么个玩意儿程序跑了 $3$ 分钟才给出答案，相当于 $180000 m s$ ，T 飞了。

上篇20231110 A题多树题解

下篇CSP-S游记 && CSP-S游寄 &&（基本上是）退役记