Educational Codeforces Round 153 (Rated for Div. 2)

https://codeforces.com/contest/1860

D. Balanced String

题意

给定一个 $01$ 串 $s$。每次操作可以交换两个元素，求最小操作次数，使得 $s$ 中 $01$ 子序列个数和 $10$ 子序列个数相等。保证可以通过操作使得 $s$ 合法。

数据范围：$3\leq |s|\leq 100$。

题解

一个观察是：交换位置 $i$ 的 $0$ 和位置 $j$ 的 $1$ 对最终结果产生的影响是 $-2\times (j-i)$。但是考虑每个 $0$ 和哪个 $1$ 进行了交换比较麻烦，赛时没有想到解决的办法。一个解决办法是，注意其贡献与为左端点还是右端点无关，位置 $i$ 的 $0$ 贡献始终是 $2\times i$，位置 $j$ 的 $1$ 贡献始终是 $-2\times j$。那么直接dp，考虑每个位置选或不选就可以了。

另一个观察是：最终的序列中各子序列的数量是确定的。我们考虑设 $f_{i,j,k}$ 表示前 $i$ 个位置选了 $j$ 个 $1$ 且 $01,11$ 子序列总量为 $k$ 的方案数，有转移：

• 若第 $i$ 个位置填 $0$，$f_{i,j,k}=f_{i-1,j,k}$
• 若第 $i$ 个位置填 $1$，且 $s_i=1$，$f_{i,j,k}=f_{i-1,j-1,k-i}$
• 若第 $i$ 个位置填 $1$，且 $s_i=0$，$f_{i,j,k}=f_{i-1,j-1,k-i}+1$

其中 $i$ 下标从 $0$ 开始。第一处转移之所以没有考虑 $s_i$ 是什么，是因为我们将一次 $01$ 交换的贡献放在了 $1$ 处计算。第二、三处第三维的转移容易理解：若该位置填 $1$，它将与前面所有的位置构成目标子序列。这时就体现出了这样设计状态的好处，方便转移。

代码

#include <bits/stdc++.h>
using namespace std;
int f[105][105*105];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;cin>>s;
    int n=(int)s.size();
    int c0=0,c1=0;
    for(int i=0;i<n;i++)
        if(s[i]=='0') c0++;
        else c1++;
    int need=(n*(n-1)/2-c0*(c0-1)/2+c1*(c1-1)/2)/2;
    memset(f,0x3f,sizeof(f));
    f[0][0]=0;
    for(int i=0;i<n;i++)
        for(int j=c1;j;j--)
            for(int k=i;k<=need;k++)
                f[j][k]=min(f[j][k],f[j-1][k-i]+(s[i]=='0'));
    cout<<f[c1][need]<<'\n';
    return 0;
}

E. Fast Travel Text Editor

题意

给出一个字符串 $s$。有一个游标，位于两个字符之间。每步可以执行以下三种操作之一：

• 游标左移
• 游标右移
• 记当前游标左侧字符为 $x$，右侧字符为 $y$。移动到另一个满足该条件的位置。

有 $q$ 次询问，每次询问给出起点和终点。问最少需要走多少步。

数据范围：$2\leq |s|\leq 5\times 10^4,1\leq m\leq 5\times 10^4$。

题解

感觉这道题比 D 简单。

由于所有具有相同左右侧字符的位置可以互相抵达，所以可以新建一个点。即新建点 $(x,y)$，向所有左侧为 $x$，右侧为 $y$ 的点连权值为 $0$ 的边，这些点向该点连权值为 $1$ 的边。然后，枚举每对 $(x,y)$，处理出它到每个位置的距离，并处理出每个位置到前后 $(x,y)$ 第一次出现的位置，就可以更新答案了。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=5e4+5;
int d[N+26*26],X[N],Y[N],ans[N],pre[N],suf[N];
bool vis[N+26*26];
struct edge
{
    int v,w;
};
vector<edge> g[N+26*26];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;cin>>s;
    int n=(int)s.size();
    for(int i=1;i<=n-1;i++)
    {
        int x=s[i-1]-'a',y=s[i]-'a';
        g[n+x*26+y].push_back({i,0});
        g[i].push_back({n+x*26+y,1});
    }
    for(int i=1;i<n;i++)
    {
        if(i>1) g[i].push_back({i-1,1});
        if(i<n-1) g[i].push_back({i+1,1});
    }
    int m;cin>>m;
    for(int i=1;i<=m;i++) 
    {
        cin>>X[i]>>Y[i];
        if(X[i]>Y[i]) swap(X[i],Y[i]);
        ans[i]=Y[i]-X[i];
    }
    for(int x=0;x<26;x++)
        for(int y=0;y<26;y++)
        {
            memset(d,0x3f,sizeof(d));
            memset(vis,0,sizeof(vis));
            d[n+x*26+y]=0;
            deque<int> q;
            q.push_front({n+26*x+y});
            while(!q.empty())
            {
                int u=q.front();q.pop_front();
                if(vis[u]) continue;
                vis[u]=1;
                for(auto i:g[u])
                {
                    int v=i.v,w=i.w;
                    if(d[v]>d[u]+w)
                    {
                        d[v]=d[u]+w;
                        if(!w) q.push_front(v);
                        else q.push_back(v);
                    }
                }
            }
            pre[0]=-1e9;
            for(int i=1;i<n;i++)
            {
                pre[i]=pre[i-1];
                if(i<n&&s[i-1]-'a'==x&&s[i]-'a'==y) pre[i]=i;
            }
            suf[n]=1e9;
            for(int i=n-1;i>=0;i--)
            {
                suf[i]=suf[i+1];
                if(i>0&&s[i-1]-'a'==x&&s[i]-'a'==y) suf[i]=i;
            }
            for(int i=1;i<=m;i++)
            {
                if(pre[X[i]]>0) ans[i]=min(ans[i],d[Y[i]]+X[i]-pre[X[i]]+1);
                if(suf[X[i]]<n) ans[i]=min(ans[i],d[Y[i]]+suf[X[i]]-X[i]+1);
            }
        }
    for(int i=1;i<=m;i++) cout<<ans[i]<<'\n';
    return 0;
}