碼迷,mamicode.com
首頁 > 其他好文 > 詳細

【2019.8.14 慈溪模擬賽 T1】我不是!我沒有!別瞎說啊!(notme)(BFS+DP)

時間:2019-08-15 17:23:58      閱讀:45      評論:0      收藏:0      [點我收藏+]

標簽:隊列   oid   ++i   取出   cout   space   題目   fine   c++   

\(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;
}

【2019.8.14 慈溪模擬賽 T1】我不是!我沒有!別瞎說啊!(notme)(BFS+DP)

標簽:隊列   oid   ++i   取出   cout   space   題目   fine   c++   

原文地址:https://www.cnblogs.com/chenxiaoran666/p/Contest20190814T1.html

(0)
(0)
   
舉報
評論 一句話評論(0
登錄后才能評論!
? 2014 mamicode.com 版權所有 京ICP備13008772號-2
迷上了代碼!
河北十一选五基本走势