2023NOIP A层联测10 T4 子序列
Ps:链接来自accoderOJ。
考场2小时才做完 T1,抱着试一试的心态看了 T4,然后想到做法了,调了 1 个多小时没调除了,赛后发现数组开小了,因为与正解做法稍有不同,于是又调了一下午……
转移方程
设状压dp \(f[i][state][0/1]\) 是到第 \(i\) 个字母,\(state\) 中有两位标位了 \(1\) ,不妨设标 \(1\) 的是第 \(x\) 位和第 \(y\) 位表示使用了第 \(x\) 个和第 \(y\) 个字母(\(x<y\)),\(0\) 表示是 第 \(x\) 个字母是上一个字母,\(1\) 表示是第 \(y\) 个是上一个字母。
那么不难得到有如下转移
若 \(s[i]\) 是第 \(x\) 个字母:
若 \(s[i]\) 是第 \(y\) 个字母:
若 \(s[i]\) 都不是:
统计答案
那我们要怎么样统计答案呢?
可以想到用 \(l-1\) 位置时与 \(r\) 时的同一个状态 \(state\) 作差求出最大长度。
观察一手性质,发现对于每一个状态而言,最靠近 \(l\) 的那个字母做开头一定可以得到最长,而结尾两者皆可,于是有:
若靠近的是第一个字母:
Ps:第一个字母前面肯定接的是第二个字母。
若靠近的是第二个字母:
预计时间复杂度:\(O(2^{26}n)\)
优化
这种复杂度暴力都心累,于是乎我们要优化。
dp 优化
先使用滚动优化,优化掉第 \(1\) 维,那么转移方程变成:
若 \(s[i]\) 是第 \(x\) 个字母:
若 \(s[i]\) 是第 \(y\) 个字母:
若 \(s[i]\) 都不是:
由于 \(state\) 有效状态为 \(26\) 个字母中选 \(2\) 个字母不重复的状态,那么我们可以给每一个编号表示一个状态,即表示一种两个字母的方案,这样的编号有 \(C^2_{26}=325\) 个。
而且当前 \(s[i]\) 已经确定,相当于已经确定了 \(1\) 个字母,所以转移时枚举另外一个字母组成答案即可。
dp 时间复杂度优化至 \(T(25n)\)。
统计优化
但这样子我们同时也需要记录在 \(l-1\) 与 \(r\) 位置时 \(f\) 数组的值,便于后面进行答案统计。
统计答案是可以将每一个查询按 \(l\) 大小排序,将同个字母的位置从小到大压入队列中。
维护每个队列顶 \(\geqslant l\)。
每次通过 \(l\) 查询每个状态最近字母时,该字母堆顶就是答案。
维护堆总时间负载度 \(O(n)\),维护均摊 \(O(1)\),查询 \(O(1)\)。
统计答案时间复杂度 \(T(C^2_{26}n)\)。
但我们(也可能只有我)的空间复杂度较高,记录数组大小高达 \(2*10^5*325*2=1.3*10^8\)。
考虑进行优化,发现对于 \(r\) 而言,只关心 \(0/1\) 中的最大值,于是记录 \(r\) 端点的数组只需要记录最大值即可。
将 \(r\) 的记录数组与 \(l\) 的剥离开,减小了 \(\frac{1}{4}\) 的空间,由于基数大,于是多出了 \(4*10^7\) 的数组空间可以使用。
代码仅供参考:
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
const int maxn=3*5e5+5,maxm=13*25+5,maxz=1e5+5;
struct node
{
int l,r,id;
}t[maxz];
struct ANS
{
int val;
pair<char,char>c;
}Ans[maxz];
int m,n,cnt,ctl,ctr;
int f[maxm][2],gt[maxz][maxm],g[maxz][maxm][2],mp[2627],fpl[maxn],fpr[maxn];
//gt 为 r 的统计数组,g 为 l 的统计数组,mp 是 二元组的第一位*100+第二位 后得出的编号
bool vis[maxn];//记录该位置是不是左端点
bool cis[maxn];//记录该位置是不是右端点
pair<char,char>p[maxm];//编号对应的一组字母
char s[maxn];
queue<int>st[27];
bool cmp(node a,node b){return a.l<b.l;}
inline int chs(char a,char b){return (a-'a'+1)*100+(b-'a'+1);}
inline void ycl()//预处理二元组编号及编号对应二元组
{
for(char i='a';i<='z';i++)
{
for(char j=i+1;j<='z';j++)
{
if(j==i) continue;
p[++cnt]=make_pair(i,j);
mp[chs(i,j)]=cnt;
mp[chs(j,i)]=cnt;
}
}
}
int main()
{
freopen("seq.in","r",stdin);
freopen("seq.out","w",stdout);
cin>>s+1;
n=strlen(s+1);
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&t[i].l,&t[i].r);
t[i].id=i;
vis[t[i].l-1]=1;
cis[t[i].r]=1;
}
sort(t+1,t+m+1,cmp);
for(int i=1;i<=n;i++) st[s[i]-'a'+1].push(i);
for(int i=1;i<=26;i++) st[i].push(n+1);//队列优化统计
ycl();
for(int i=1;i<=n;i++)
{
for(int j='a';j<='z';j++)//转移
{
if(j==s[i]) continue;
pair<char,char>k=make_pair(s[i],j);
if(k.F>k.S) swap(k.F,k.S);
if(k.F==s[i]) f[mp[chs(k.F,k.S)]][0]=f[mp[chs(k.F,k.S)]][1]+1;
else f[mp[chs(k.F,k.S)]][1]=f[mp[chs(k.F,k.S)]][0]+1;
}
if(vis[i])//l 端点记录
{
ctl++;
fpl[i]=ctl;
for(int j=1;j<=cnt;j++) g[ctl][j][0]=f[j][0],g[ctl][j][1]=f[j][1];
}
if(cis[i])//r 端点记录
{
ctr++;
fpr[i]=ctr;
for(int j=1;j<=cnt;j++) gt[ctr][j]=max(f[j][0],f[j][1]);
}
}
for(int i=1;i<=m;i++)//求答案
{
pair<char,char>cans;
cans={0,0};
int ans=0;
for(int j=1;j<=cnt;j++)
{
pair<char,char>x=p[j];
while(st[x.F-'a'+1].front()<t[i].l) st[x.F-'a'+1].pop();//维护队列
while(st[x.S-'a'+1].front()<t[i].l) st[x.S-'a'+1].pop();
int fi=st[x.F-'a'+1].front();//最靠近 l 的字母
int se=st[x.S-'a'+1].front();
if(fi>t[i].r&&se>t[i].r) continue;
if(fi<se)
{
if(ans<gt[ fpr[t[i].r] ][j]-g[ fpl[t[i].l-1] ][j][1])
{
ans=gt[ fpr[t[i].r] ][j]-g[ fpl[t[i].l-1] ][j][1];
cans=x;
}
else if(ans==gt[ fpr[t[i].r] ][j]-g[ fpl[t[i].l-1] ][j][1])
{
if(cans>x) cans=x;
}
}
else if(fi>se)
{
swap(x.F,x.S);
if(ans<gt[ fpr[t[i].r] ][j]-g[ fpl[t[i].l-1] ][j][0])
{
ans=gt[ fpr[t[i].r] ][j]-g[ fpl[t[i].l-1] ][j][0];
cans=x;
}
else if(ans==gt[ fpr[t[i].r] ][j]-g[ fpl[t[i].l-1] ][j][0])
{
if(cans>x) cans=x;
}
}
}
Ans[t[i].id].val=ans;
Ans[t[i].id].c=cans;
}
for(int i=1;i<=m;i++) printf("%d %c%c\n",Ans[i].val,Ans[i].c.F,Ans[i].c.S);
}