p11218(玄关)
  • 板块题目总版
  • 楼主liyuan2023
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/10/20 19:41
  • 上次更新2024/10/20 21:02:39
查看原帖
p11218(玄关)
1188691
liyuan2023楼主2024/10/20 19:41

思路对吗?

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
char x;
int n,t,m,f[N],c[N],ans;
struct node{
	int sv,cnt,now;
}dp[N];
bool a[N],b[N];
int main(){
	cin>>x>>t;
	while(t--){
		cin>>n>>m;
		ans=-n*2;
		for(int i=1;i<=n;i++){
			cin>>x;
			if(x=='1'){
				a[i]=1;
			}
			else{
				a[i]=0;
			}
		}
		for(int i=1;i<=n;i++){
			cin>>x;
			if(x=='1'){
				b[i]=1;
			}
			else{
				b[i]=0;
			}
		}
		for(int i=1;i<=n;i++){
			if(a[i]+b[i]==0){
				f[i]=-1;
				c[i]=0;
			}
			else if(a[i]+b[i]==1){
				f[i]=1;
				if(a[i]==1){
					c[i]=1;
				}
				else{
					c[i]=2;
				}
			}
			else{
				f[i]=2;
				c[i]=3;
			}
		}
		dp[0].sv=0;
		dp[0].cnt=0;
		dp[0].now=3;
		for(int i=1;i<=n;i++){
			dp[i]=dp[i-1];
			if(dp[i].sv<0){
				dp[i].sv=0;
				dp[i].cnt=0;
				dp[i].now=3;
			}
			if(f[i]==2){
				dp[i].sv+=2;
				dp[i].now=3;
			}
			else if(f[i]==1){
				if(dp[i].now==3){
					dp[i].sv++;
					dp[i].cnt++;
					dp[i].now=c[i];
				}
				else if(c[i]!=dp[i].now){
					dp[i].now=3;
				}
				else{
					dp[i].sv++;
					dp[i].cnt++;
				}
			}
			else if(f[i]==-1){
				dp[i].sv--;
			}
			ans=max(ans,dp[i].sv-min(2*m,dp[i].cnt));
			/*
			if(dp[i].cnt<=m){
				ans=max(ans,dp[i].sv-dp[i].cnt);
			}
			else if(dp[i].cnt>m&&dp[i].cnt<=2*m){
				ans=min(ans,dp[i].sv-dp[i].cnt);
			}
			else if(dp[i].cnt>2*m){
				ans=max(ans,dp[i].sv-2*m);
			}
			ans=max(ans,dp[i].must*2);
			*/
		}
		cout<<ans<<endl;
	}
	return 0;
}
2024/10/20 19:41
加载中...