【2019.8.14 慈溪模拟赛 T1】我不是！我没有！别瞎说啊！（notme）（BFS+DP）

- 日理万妓 2021-10-29 11:16 145阅读 0赞

### \\(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<bits/stdc++.h> #define Tp template<typename Ty> #define Ts template<typename Ty,typename... Ar> #define Reg register #define RI Reg int #define Con const #define CI Con int& #define I inline #define W while #define N 4000 using 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<f[x][y]&&(f[x][y]=f[i][j]+1,gx[x][y]=i,gy[x][y]=j,glst[x][y]=0),//更新f和g f[x=nxt1[i][1]][y=nxt2[j][1]]==m+1&&(qx[++T]=x,qy[T]=y),//未访问过就入队 f[i][j]+1<f[x][y]&&(f[x][y]=f[i][j]+1,gx[x][y]=i,gy[x][y]=j,glst[x][y]=1);//更新f和g x=n+1,y=m+1;W(x||y) ans=(char)(glst[x][y]+48)+ans,i=gx[x][y],j=gy[x][y],x=i,y=j;//倒着找答案 cout<<ans<<endl;//输出答案 } }D; int main() { freopen("notme.in","r",stdin),freopen("notme.out","w",stdout); cin>>s1>>s2,s1.length()>s2.length()&&(swap(s1,s2),0),n=s1.length(),m=s2.length(); return D.Solve(),0; }

转载于:https://www.cnblogs.com/chenxiaoran666/p/Contest20190814T1.html