专栏文章

Sol abc418d

CClay_L
AT_abc418_d题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miobdm1l
此快照首次捕获于
2025/12/02 16:26
3 个月前
此快照最后确认于
2025/12/02 16:26
3 个月前
查看原文

D

题意

给定长度为 nn 的 0101 串 ss。现有操作：对于一个 0101 串 aa，选定一个 i(1≤i<n,i∈Z)i\left(1\le i<n,i\in\Z\right)，若 ai=ai+1a_i=a_{i+1}，则将 aia_i 和 ai+1a_{i+1} 替换为 11，否则替换为 00。
对于 aa 串是否合规，当且仅当任意操作后 ∣a∣=1|a|=1 且 aa 中只有一个 11 存在。
问 ss 中有多少个合规的子串。

算法

一眼 dpdp。
设 dpi,1dp_{i,1} 为以第 ii 个元素结尾的子串中合规的子串个数，dpi,0dp_{i,0} 为以第 ii 个元素结尾的子串中不合规的子串个数。
合规的子串处理后会变为 11，不合规的会变为 00。
若第 ii 位为 11，则它与以第 i−1i-1 位结尾的任何一个合规子串结合都是合规的，反之则不合规。
同理，若第 ii 位为 00，则它与以第 i−1i-1 位结尾的任何一个合规子串结合都是不合规的，反之则合规。
综上所述：
dpi,1={dpi−1,1+1(si=1)dpi−1,0(si=0),dpi,0={dpi−1,1(si=1)dpi−1,0+1(si=0).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} .
此时答案为：
∑i=1ndpi,1\sum^n_{i=1}dp_{i,1}
对应代码：
CPP
#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;
}
还能再优化一小点。
因为以第 ii 个元素结尾的子串共 ii 个，则有 dpi,0+dpi,1=idp_{i,0}+dp_{i,1}=i。
可推出 dpi,0=i−dpi,1dp_{i,0}=i-dp_{i,1}。
由此可省去一维。
所以 dpdp 方程可化为：
dpi={dpi−1+1(si=1)i−1−dpi−1(si=0)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}
此时答案为：
∑i=1ndpi\sum^n_{i=1}dp_i
对应代码：
CPP
#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.

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...