专栏文章

题解：P13832 【MX-X18-T4】「FAOI-R6」绿茶

bbaibaieee
P13832题解参与者 1已保存评论 0

文章操作

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

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

题目分析

观察题目，∣A−C∣=2k\lvert A-C\rvert =2^k, 所以有两种情况。
  1. C=A+2kC=A+2^k
当该位为 00 时，AorCA \mathbin{\mathrm{or}} C 相当于将 AA 中该位变为 11。
当该位为 11 时，AorCA \mathbin{\mathrm{or}} C 相当于将 AA 中该位之前的最后一个 00 的位置变为 11。
  1. C=A−2kC=A-2^k
当该位为 00 时， AorCA \mathbin{\mathrm{or}} C 相当于将 AA 中该位到该位之前的最后一个 11 中的位置都变为 11。
当该位为 11 时，操作无效果。
所以原题的操作转化成为：
  1. 将某一位由 00 变为 11，花费的代价为该位到与它连续的 11 的最后一位的 cic_i 的最小值。
  2. 将某一位到该位之前的最后一个 11 中的位置都变为 11，花费 cic_i。（需要保证 Ai=0A_i=0 且存在 j<ij < i，Ai=1A_i=1。）

处理过程

我们称 BB 中连续的 11 的区间为“ 11 段”。
我们将每一段位于“ 11 段”的 AA 取出，单独处理，设其为 [L,R][L,R]。
我们将该段的前导零与后面的序列分离。
  1. 先处理非前导零部分，设其为 [l,R][l,R]。
我们从后往前进行DP。
设 dpi,udp_{i,u} 表示将这个“ 11 段”末尾到第 ii 位都变为 11 所需的最小花费，uu 表示是否在当前是否使用过操作 22。
设 ml,rm_{l,r} 为 min⁡i=lrci\min_{i=l}^{r} c_i。
若 Ai=1A_i=1 ，则 dpi,0=min⁡{dpi+1,0,dpi+1,1}dp_{i,0}=\min\{dp_{i+1,0},dp_{i+1,1}\}。（使用过操作二的影响到它前面的最后一个 Ai=1A_i=1 就会失效。）
若 Ai=0A_i=0 ，则 dpi,0=dpi+1,0+mi,Rdp_{i,0}=dp_{i+1,0}+m_{i,R}， dpi,1=min⁡{dpi+1,1,dpi+1,0+ci}dp_{i,1}=\min\{dp_{i+1,1},dp_{i+1,0}+c_i\}。
  1. 对于前导零部分，我们设其区间为 [L,r][L,r]。
假设有一个位置 pp ，我们在这上面先进行一次操作一。
pp 之后可以仿照可以使用操作二，仿照非前导零部分处理。
pp 之前只能使用操作一，花费为 ∑i=Lp−1mi,R\sum_{i=L}^{p-1}m_{i,R}。（注意此处是区间 [i,R][i,R] 的最大值。）
所以总花费为 ∑i=Lp−1mi,R+cp+min⁡{dpp+1,0,dpp+1,1}\sum_{i=L}^{p-1}m_{i,R}+c_p+\min\{dp_{p+1,0},dp_{p+1,1}\}。
枚举位置 pp ，取最小值即可。
总时间复杂度 O(n)O(n) 。

代码

CPP
#include<bits/stdc++.h>
using namespace std;
const int MAXN=100005;
string s1,s2; 
long long T,n,a[MAXN],c[MAXN],ans,dp[MAXN][2],m[MAXN];
void init_min(int l,int r){
	m[r+1]=1145141919810LL;
	for(int i=r;i>=l;i--)m[i]=min(m[i+1],c[i]);
} 
long long solve_allz(int l,int r,int r2){
	//cout<<"solve a_all_0 "<<l<<" "<<r<<endl;
	init_min(l,r2);
	long long ans=0,tmp=0;
	for(int i=l;i<=r;i++)tmp+=m[i];
	//for(int i=l;i<=r;i++)cout<<m[i]<<" ";
	//cout<<tmp<<endl;
	ans=tmp; 
	for(int i=l;i<=r+1;i++)dp[i][1]=dp[i][0]=1145141919810LL;
	dp[r+1][0]=0;
	for(int i=r;i>=l;i--){
		dp[i][0]=dp[i+1][0]+m[i];
		dp[i][1]=min(dp[i+1][1],dp[i+1][0]+c[i]);
		tmp-=m[i];
		//cout<<i<<" "<<tmp<<" "<<tmp+c[i]+min(dp[i+1][0],dp[i+1][1])<<endl;
		ans=min(ans,tmp+c[i]+min(dp[i+1][0],dp[i+1][1]));
	}
	return ans;
}
long long solve(int l,int r){
	//cout<<"solve b_all_1 "<<l<<" "<<r<<endl; 
	long long ans=0;
	for(int i=l;i<=r+1;i++){
		if(s1[i]=='1'||i==r+1){
			if(i!=l)ans=solve_allz(l,i-1,r);
			l=i;
			break;
		}
	}
	if(l>r)return ans;
	for(int i=l;i<=r+1;i++)dp[i][1]=dp[i][0]=1145141919810LL;
	dp[r+1][0]=0;
	init_min(l,r);
	for(int i=r;i>=l;i--){
		if(s1[i]=='1')dp[i][0]=min(dp[i+1][1],dp[i+1][0]);
		else{
			dp[i][0]=dp[i+1][0]+m[i];
			dp[i][1]=min(dp[i+1][1],dp[i+1][0]+c[i]);
		}
	}
	ans+=dp[l][0];
	//cout<<ans<<endl; 
	return ans;
}
int main(){
	cin>>T;
	while(T--){
		cin>>n;
		cin>>s1>>s2;
		for(int i=1;i<=n;i++)cin>>c[i];
		s1="0"+s1+"0",s2="0"+s2+"0";
		bool flag=0;
		for(int i=1;i<=n;i++){
			if(s1[i]=='1'&&s2[i]=='0'){
				flag=1;
				break;
			}
		}
		if(flag){
			cout<<-1<<endl;
			continue;
		}
		ans=0;
		int fs=0;
		for(int i=1;i<=n+1;i++){
			if(s2[i]=='0'&&fs){
				//cout<<fs<<" "<<i-1<<endl;
				ans+=solve(fs,i-1);
				fs=0; 
			}
			if(s2[i]=='1'&&!fs)fs=i;
		} 
		cout<<ans<<endl; 
	} 
  	return 0;
}

评论

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

正在加载评论...