1 条题解

  • 0
    @ 2022-1-5 10:21:23

    考虑贪心,首先一个显然的结论 SS 通过交换变成 TT,那么所有 00 的相对位置必然不变。

    那么我们就可以得到每个 00 可能存在区间。

    想让美丽值最大,就要考虑尽量让 00 直接放在一起。

    那就直接贪心,可以放在一起就放在一起。

    注意此时有一个问题,就是 00 可能可以放在最前面更优(比如样例一),因为这样可以让 11 尽量放在一起。

    所以分别对 0011 做一遍贪心,取一个最大值就好了。


    代码
    #include<bits/stdc++.h>
    using namespace std;
    const int N=3e5+5;
    int n,m;
    char a[N],b[N];
    struct Line{int l,r;}p[N];
    vector<int> veca,vecb;
    int solve(int x){
    	if(!x)return 0;
    	return x-1;
    }
    int work(){
    	int S=0;
    	veca.clear(),vecb.clear();
    	for(int i=1;i<=n+m;i++){
    		if(a[i]=='0')veca.push_back(i);
    		if(b[i]=='0')vecb.push_back(i);
    	}
    	for(int i=0;i<n;i++)p[i+1]=(Line){min(veca[i],vecb[i]),max(veca[i],vecb[i])};
    	int x=1;
    	p[n+1].r=n+m+1;
    	while(x<=n){
    		int now=p[x].r,s=0;
    		s++;
    		while(p[x+1].l<=now+1&&x<n){
    			now++,s++,x++;
    		}
    		S+=s-1;
    		S+=solve(p[x+1].r-now-1);
    		x++;
    	}
    	S+=solve(p[1].r-1);
    	return S;
    }
    int ans;
    int main(){
    	scanf("%d%d",&n,&m);
    	scanf("%s",a+1);
    	scanf("%s",b+1);
    	ans=work();
    	for(int i=1;i<=n+m;i++){
    		if(a[i]=='0')a[i]='1';else a[i]='0';
    		if(b[i]=='0')b[i]='1';else b[i]='0';
    	}
    	swap(n,m);
    	ans=max(ans,work());
    	printf("%d",ans);
    }
    
    • 1

    信息

    ID
    66
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者