题目大意
\(T\)(\(T\leq10\))组询问
每组询问给出一个字符串\(A\)(\(|A|\leq10^4\))，\(n\)(\(n\leq4\))个\(A\)的子串\(B_1,B_2,B_3,...,B_n\)(\(\forall i \in[1,n],|B_i|\leq10^3\))
如果\(|B_i|=r-l+1\)且\(B_i\)的每一个字符依次与\(A_l,A_{l+1},...,A_{r}\)相等，那么区间\([l,r]\)每个位置都被覆盖了一次
求如果必须把\(B_1,...,B_n\)全部用上，那么字符串\(A\)至少有几个位置被覆盖不少于一次？至多有几个位置被覆盖不少于一次？
题解
至少：
如果一个串\(B_i\)是\(B_j\)的子串，那么让\(B_i\)覆盖被\(B_j\)覆盖的部分会更优，所以先去掉“是别的串的子串的串”
设\(f(S,j)\)表示已经用过的子串集合为\(S\)，目前覆盖的最靠右的位置为\(j\)
因为已经去掉了“是别的串的子串的串”，所以以\(j\)为结尾的\(B\)串只有一个，假设它是\(B_x\)
有两种情况：1.在选取\(B_x\)前(此时已用过的子串集合为\(S\bigoplus\{ x\}\))，被覆盖的区域与\(B_x\)有交；2.在选取\(B_x\)前，被覆盖的区域与\(B_x\)没有交
1.\(f(S,j)=min\{ f(S\bigoplus\{ x\},k)+j-k \mid j-|B_x|+1\leq k\leq j\}\)因为已经去重，所以集合\(S\bigoplus\{ x\}\)里最靠后的子串的起点一定不会比\(j-|B_x|+1\)更靠右，加入\(B_x\)后新覆盖的区域为\(j-k\)
因为没有“是别的串的子串的串”，所以当\(j\)右移时\(j-|B_x|+1\)也右移，用单调队列维护
2.\(f(S,j)=min\{ f(S\bigoplus\{ x\},k) \mid 0\leq k\leq j-|B_x|+1\}+|B_x|\)，维护前缀最小值就行
时间复杂度\(\Theta(2^n*|A|*n)\)或\(\Theta(2^n*|A|)\)
至多：
发现并不能去重
暴力枚举\(n\)个串的顺序，暴力枚举每个串与之前的部分是否有交
有交就让交的部分尽可能小，没有交就尽可能把这个串往前放
时间复杂度大概\(\Theta(n!*2^n*n)\)
代码
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<iomanip>
#include<iostream>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<vector>
#define rep(i,x,y) for(register int i=(x);i<=(y);++i)
#define dwn(i,x,y) for(register int i=(x);i>=(y);--i)
#define maxn 10010
#define maxm 1010
#define pii pair<int,int>
#define fi first
#define se second
#define mp(x,y) make_pair(x,y)
#define maxs (1<<5)
#define chmn(x,y) x=min(x,y)
using namespace std;
int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)&&ch!='-')ch=getchar();
if(ch=='-')f=-1,ch=getchar();
while(isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
return x*f;
}
void write(int x)
{
if(x==0){putchar('0');return;}
int f=0;char ch[20];
if(x<0)putchar('-'),x=-x;
while(x)ch[++f]=x%10+'0',x/=10;
while(f)putchar(ch[f--]);
return;
}
int T,pos[5][maxn],n,lens,lent[5],fa[5][maxm],ord[20],ord2[20],vis[5],f[maxs][maxn],maxans,minans,cntnd,hsh[5],ext[5][maxn],pref[maxs][maxn];
char t[5][maxm],s[maxn];
pii a[20];
struct deque
{
int w[maxn],tim[maxn],hd,tl;
void reset(){hd=1,tl=0;}
void push(int x,int y){while(hd<=tl&&w[tl]>=x)tl--;w[++tl]=x,tim[tl]=y;}
void del(int y){while(hd<=tl&&tim[hd]<y)hd++;}
int empty(){return hd>tl?1:0;}
}q[maxs];
bool cmp1(int x,int y){return lent[x]<lent[y];}
bool cmp2(int x,int y){return a[x].fi==a[y].fi?a[x].se<a[y].se:a[x].fi<a[y].fi;}
int calmx()
{
rep(i,1,cntnd)ord2[i]=i;
sort(ord2+1,ord2+cntnd+1,cmp2);
int now=0,lenth=0;
rep(i,1,cntnd)
{
now+=a[ord2[i]].se;
if(i==cntnd||a[ord2[i+1]].fi!=a[ord2[i]].fi){if(now)lenth+=a[ord2[i+1]].fi-a[ord2[i]].fi;}
}
return lenth;
}
int getpla(int step,int maxp)
{
if(step==n+1){return calmx();}
int now=ord[step],res=0;
int l=1,r=pos[now][0],ans=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(pos[now][mid]-lent[now]+1<=maxp){l=mid+1;ans=max(ans,mid);}
else r=mid-1;
}
if(ans!=0&&pos[now][ans]>=maxp)a[++cntnd]=mp(pos[now][ans]+1,-1),a[++cntnd]=mp(pos[now][ans]-lent[now]+1,1),res=getpla(step+1,pos[now][ans]),cntnd-=2;
if(ans+1!=pos[now][0]+1&&pos[now][ans+1]>=maxp)
a[++cntnd]=mp(pos[now][ans+1]+1,-1),a[++cntnd]=mp(pos[now][ans+1]-lent[now]+1,1),
res=max(res,getpla(step+1,pos[now][ans+1])),cntnd-=2;
return res;
}
void getord(int step)
{
if(step==n+1){cntnd=0;maxans=max(maxans,getpla(1,0));return;}
rep(i,1,n)if(!vis[i])vis[i]=1,ord[step]=i,getord(step+1),vis[i]=0;
return;
}
int main()
{
T=read();
while(T--)
{
scanf("%s",s+1);lens=strlen(s+1);maxans=0;
n=read();memset(ext,0,sizeof(ext));
rep(i,1,n)
{
pos[i][0]=vis[i]=0,scanf("%s",t[i]+1),lent[i]=strlen(t[i]+1);
fa[i][0]=-1,fa[i][1]=0;
rep(j,2,lent[i])
{
int k=fa[i][j-1];
while(k&&t[i][k+1]!=t[i][j])k=fa[i][k];
if(t[i][k+1]==t[i][j])fa[i][j]=k+1;
else fa[i][j]=0;
}
int k=0;
rep(j,1,lens)
{
while(k&&(k==lent[i]||t[i][k+1]!=s[j]))k=fa[i][k];
if(t[i][k+1]==s[j]){k++;if(k==lent[i])pos[i][++pos[i][0]]=j,ext[i][j]=1;}
else k=0;
}
}
getord(1);
rep(i,1,n)ord[i]=i,vis[i]=0;
sort(ord+1,ord+n+1,cmp1);
rep(i,1,n)
rep(j,i+1,n)
{
int fl=0,k=0;
rep(l,1,lent[ord[j]])
{
while(k&&(t[ord[i]][k+1]!=t[ord[j]][l]))k=fa[ord[i]][k];
if(t[ord[i]][k+1]==t[ord[j]][l]){k++;if(k==lent[ord[i]]){fl=1;break;}}
else k=0;
}
vis[ord[i]]|=fl;
}
cntnd=0;
rep(i,1,n)if(!vis[i])hsh[++cntnd]=i;
int fulls=(1<<cntnd)-1;
rep(i,0,fulls)q[i].reset();
memset(f,0x7f,sizeof(f)),memset(pref,0x7f,sizeof(pref));
int inf=minans=f[0][0];f[0][0]=pref[0][0]=0;q[0].push(0,0);
rep(j,1,lens)rep(s,0,fulls)
{
int num=0;pref[s][j]=pref[s][j-1];
if(!s)continue;
rep(i,1,cntnd)
{
if(ext[hsh[i]][j]&&((1<<(i-1))&s))
{
num++;
int pres=s^(1<<(i-1));
q[pres].del(j-lent[hsh[i]]);
if(!q[pres].empty())f[s][j]=min(f[s][j],q[pres].w[q[pres].hd]+j);
if(j-lent[hsh[i]]>=0)f[s][j]=min(f[s][j],pref[pres][j-lent[hsh[i]]]+lent[hsh[i]]);
pref[s][j]=min(pref[s][j],f[s][j]);if(f[s][j]!=inf)q[s].push(f[s][j]-j,j);
}
}
}
rep(j,1,lens)chmn(minans,f[fulls][j]);
write(minans),putchar(' '),write(maxans),putchar('\n');
}
return 0;
}
/*
2
hello
4
he
l
l
o
abacaba
4
ab
ba
a
c
*/
一些感想
片手玩得好不是大佬，笛玩得好才是。——吹笛子时被车的片手流