\(IDA^*\)

说实话，这道题我一开始没想出正解，于是写了一个\(IDA^*\)。。。

但神奇的是，这个\(IDA^*\)居然连字符串长度分别为\(2500,4000\)的数据都跑得飞快，不过数据发下来之后我测了一下只有45分。

就在不断优化\(IDA^*\)的过程中，我突然就想出了正解的做法，看来以后遇事不决先暴力。

\(DP\)求解第一个询问

考虑一个\(DP\)，我们设\(f_{i,j}\)表示当前在第一个字符串中是第\(i\)位，第二个字符串中是第\(j\)位的最小步数。

若记录\(nxt1_{x,0/1},nxt2_{x,0/1}\)分别表示两个字符串在\(x\)位后下一个\(0/1\)出现的位置，那么我们就可以得到这样的转移：

\[f_{nxt1_{i,0},nxt2_{j,0}}=min(f_{nxt1_{i,0},nxt2_{j,0}},f_{i,j})\]

\[f_{nxt1_{i,1},nxt2_{j,1}}=min(f_{nxt1_{i,1},nxt2_{j,1}},f_{i,j})\]

这样就能解决第一个询问了。

\(BFS\)求解第二个询问

考虑如果我们在\(DP\)的时候记录一个\(lst\)表示转移来的位置，就可以输出方案了。

但题目要求字典序最小，普通的\(DP\)或者\(DFS\)形式的\(DP\)都无法满足这一条件。

于是我们就可以想到\(BFS\)。

按照\(BFS\)的顺序进行\(DP\)，我们就可以保证其必然满足字典序最小的条件了。

代码

#include
    
     #define Tp template
     
      #define Ts template
      
       #define Reg register#define RI Reg int#define Con const#define CI Con int&#define I inline#define W while#define N 4000using namespace std;int n,m;string s1,s2;class DpSolver//BFS+DP{    private:        string ans;short qx[(N+2)*(N+2)+5],qy[(N+2)*(N+2)+5],nxt1[N+5][2],nxt2[N+5][2];        short f[N+5][N+5],gx[N+5][N+5],gy[N+5][N+5];bool glst[N+5][N+5];    public:        I void Solve()        {            RI i,j,x,y,H=1,T=0,p[2];s1="%"+s1,s2="%"+s2;            for(p[0]=p[1]=n+1,i=n+1;~i;--i) nxt1[i][0]=p[0],nxt1[i][1]=p[1],p[s1[i]&1]=i;//初始化nxt1            for(p[0]=p[1]=m+1,i=m+1;~i;--i) nxt2[i][0]=p[0],nxt2[i][1]=p[1],p[s2[i]&1]=i;//初始化nxt2            for(i=0;i<=n+1;++i) for(j=0;j<=m+1;++j) f[i][j]=m+1;f[0][0]=0,qx[++T]=0,qy[T]=0;//初始化f数组和BFS队列            W(H<=T) i=qx[H],j=qy[H++],//取出队首                f[x=nxt1[i][0]][y=nxt2[j][0]]==m+1&&(qx[++T]=x,qy[T]=y),//未访问过就入队                f[i][j]+1
       
        >s1>>s2,s1.length()>s2.length()&&(swap(s1,s2),0),n=s1.length(),m=s2.length();    return D.Solve(),0;}