Sol abc418d

· · 题解

D

题意

给定长度为 n 的 01 串 s。现有操作：对于一个 01 串 a，选定一个 i\left(1\le i<n,i\in\Z\right)，若 a_i=a_{i+1}，则将 a_i 和 a_{i+1} 替换为 1，否则替换为 0。

对于 a 串是否合规，当且仅当任意操作后 |a|=1 且 a 中只有一个 1 存在。

问 s 中有多少个合规的子串。

算法

一眼 dp。

设 dp_{i,1} 为以第 i 个元素结尾的子串中合规的子串个数，dp_{i,0} 为以第 i 个元素结尾的子串中不合规的子串个数。

合规的子串处理后会变为 1，不合规的会变为 0。

若第 i 位为 1，则它与以第 i-1 位结尾的任何一个合规子串结合都是合规的，反之则不合规。

同理，若第 i 位为 0，则它与以第 i-1 位结尾的任何一个合规子串结合都是不合规的，反之则合规。

综上所述：

dp_{i,1}=\begin{cases}dp_{i-1,1}+1\left(s_i=1\right) \\ dp_{i-1,0}\left(s_i=0\right) \end{cases} , dp_{i,0}=\begin{cases}dp_{i-1,1}\left(s_i=1\right) \\ dp_{i-1,0}+1\left(s_i=0\right) \end{cases} .

此时答案为：

\sum^n_{i=1}dp_{i,1}

对应代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200010;
int n,dp1[N],dp0[N];
string s;
signed main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>s;
    s=' '+s;
    for(int i=1;i<=n;i++){
        if(s[i]=='1'){
            dp1[i]=dp1[i-1]+1;
            dp0[i]=dp0[i-1];
        }
        else{
            dp1[i]=dp0[i-1];
            dp0[i]=dp1[i-1]+1;
        }
        dp1[n+1]+=dp1[i];
    }
    cout<<dp1[n+1];
    return 0;
}

还能再优化一小点。

因为以第 i 个元素结尾的子串共 i 个，则有 dp_{i,0}+dp_{i,1}=i。

可推出 dp_{i,0}=i-dp_{i,1}。

由此可省去一维。

所以 dp 方程可化为：

dp_i=\begin{cases}dp_{i-1}+1\left(s_i=1\right) \\ i-1-dp_{i-1}\left(s_i=0\right) \end{cases}

此时答案为：

\sum^n_{i=1}dp_i

对应代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=200010;
int n,dp[N];
string s;
signed main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(nullptr),cout.tie(nullptr);
    cin>>n>>s;
    s=' '+s;
    for(int i=1;i<=n;i++){
        if(s[i]=='1')dp[i]=dp[i-1]+1;
        else dp[i]=i-dp[i-1]-1;
        dp[n+1]+=dp[i];
    }
    cout<<dp[n+1];
    return 0;
}

然后没有了 qwq.