Educational Codeforces Round 153 D-E dp，bfs-Toy模板网

这篇具有很好参考价值的文章主要介绍了Educational Codeforces Round 153 D-E dp，bfs。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1860D Balanced String
首先只能是0和1交换，1在 $i$ 位置，0在 $j$ 位置，每交换一次产生的贡献是 $2 * (i - j)$ ，所以我们可以先算出原01串中所需要的贡献 $m$ ，我们发现找到 $t o l$ 个1和0的位置 $i_k,j_k$ 且 $\sum_{k}^{tol} i_k-j_k=m$ ，我们可以拆开 $\sum_{k}^{tol} i_k- \sum_{k}^{tol} j_k=m$ ，然后分别dp出选tol个数，0,1的位置和分别有那些状态可以达到，易证位置和小于 $n^2$ ，然后枚举 $t o l$ ，枚举1的位置和，算出0的位置和，判断两个状态是否能达到
时间复杂度 $O(n^4)$

void solve(){
    std::string s;
    std::cin>>s;
    int n=s.length();

    std::vector<int> a(n+1);
    int sum=0,m=0;
    for (int i=1;i<=n;i++){
        a[i]=s[i-1]-'0';
        if (a[i]){
            m-=i-1-sum;
        }else{
            m+=sum;
        }
        sum+=a[i];
    }

    m>>=1;
    std::vector<std::vector<int>> dp0(n+1,std::vector<int>(n*n+1)),dp1(n+1,std::vector<int>(n*n+1));
    dp0[0][0]=dp1[0][0]=1;
    for (int i=1;i<=n;i++){
        for (int j=i;j>=1;j--){
            for (int k=n*n;k>=i;k--){
                if (a[i]){
                    dp1[j][k]|=dp1[j-1][k-i];
                }else{
                    dp0[j][k]|=dp0[j-1][k-i];
                }
            }
        }
    }
    m=-m;
    for (int i=0;i<=n;i++){
        for (int j=0;j<=n*n;j++){
            int k=j-m;
            if (k>=0&&k<=n*n&&dp1[i][j]&&dp0[i][k]){
                std::cout<<i;
                return;
            }
        }
    }
}

1860E Fast Travel Text Editor
首先注意到是小写字母，说明最多 26 * 26 种组合方式，然后发现题意每次操作代价都为1，考虑建图，发现连边和对点的定义不好搞，考虑bfs，定义 $dis_{i,j,x}$ ，表示当前点 $x$ ，到某个形如 $^{'} a^{'} + i,^{'} a^{'} + j$ 位置的最小距离，这样我们每次询问只要枚举 26 * 26 次，类似Floyed找中转点的方法， $min(y-x,dis_{i,j,x}+dis_{i,j,y}+1)$ 。

我们枚举每个 $i, j$ ，然后从形如 $^{'} a^{'} + i,^{'} a^{'} + j$ 的位置出发，bfs向外扩展，更新各点的 $dis_{i,j,x}$ ，每次扩展除了到 $x + 1$ 和 $x - 1$ 点外，还要让 $x$ 通过第三种操作跳跃到其它点，由于每个点最多入队一次，所以时间复杂度为 $O(26^2\vert s \vert)$
总时间复杂度 $O(26^2 (m+\vert s \vert))$ 文章来源地址https://www.toymoban.com/news/detail-658559.html

const int inf=1e9;
void solve(){
    std::string s;
    std::cin>>s;
    int n=s.length();
    std::vector<int> pos[26][26];
    for (int i=1;i<n;i++){
        pos[s[i-1]-'a'][s[i]-'a'].push_back(i);
    }

    std::vector dis(26,std::vector(26,std::vector(n+2,inf)));
    for (int i=0;i<26;i++){
        for (int j=0;j<26;j++){
            std::queue<int> q;
            for (auto x:pos[i][j]){
                q.push(x);
                dis[i][j][x]=0;
            }
            std::vector<std::vector<int>> vis(26,std::vector<int>(26));
            vis[i][j]=1;

            while (!q.empty()){
                int x=q.front();
                q.pop();

                if (x-1>=1&&dis[i][j][x-1]==inf){
                    dis[i][j][x-1]=dis[i][j][x]+1;
                    q.push(x-1);
                }
                if (x+1<n&&dis[i][j][x+1]==inf){
                    dis[i][j][x+1]=dis[i][j][x]+1;
                    q.push(x+1);
                }
                int l=s[x-1]-'a',r=s[x]-'a';
                if (!vis[l][r]){
                    vis[l][r]=1;
                    for (auto v:pos[l][r]){
                        if (dis[i][j][v]==inf){
                            dis[i][j][v]=dis[i][j][x]+1;
                            q.push(v);
                        }
                    }
                }
            }
        }
    }

    int m;
    std::cin>>m;
    while (m--){
        int x,y;
        std::cin>>x>>y;
        int ans=abs(x-y);
        for (int i=0;i<26;i++){
            for (int j=0;j<26;j++){
                ans=std::min(ans,dis[i][j][x]+dis[i][j][y]+1);
            }
        }
        std::cout<<ans<<"\n";
    }
    
}