题解：CF1394C Boboniu and String

_abcd_ · 2024-12-12 09:46:54 · 题解

[CF1394C] Boboniu and String

为什么题解都带 \log 啊，是否有点极端了。

为了方便起见，下文将 \rm BN 串替换为 01 串。注意到“相似的”的判定相当于 0 和 1 的个数都相等。并且，若设 0 的个数为 c_0 ， 1 的个数为 c_1 ，每次操作都可以将 c_0 或 c_1 加一或减一，或者将 c_0 和 c_1 同时加一或减一。

那么将 ( c_0, c_1 ) 变成 ( x, y ) 的步数显然是：若 ( c_0 - x ) ( c_1 - y ) \ge 0 ，则答案为 \max( | c_0 - x |, | c_1 - y | ) ，否则答案为 | c_0 - x | + | c_1 - y | 。手玩以下就能发现答案等同于 \max( c_0 - x, x - c_0, c_1 - y, y - c_1, c_0 - x + y - c_1, x - c_0 + c_1 - y ) 。

考虑设 x_1, x_2, y_1, y_2, s_1, s_2 分别表示 c_0, c_1, c_0 - c_1 的最小值和最大值，那么答案就可以表示成 \max( x - x_1, x_2 - x, y - l, r - y ) ，其中 l = \min( y_1, x - s_2 ), r = \max( y_2, x - s_1 ) 。显然当 y = \frac{l+r}{2} 时最优。直接枚举 x 并计算即可。复杂度为 O(n) 。

#include<bits/stdc++.h>
#define ll long long
#define pn putchar('\n')
#define mset(a,x) memset(a,x,sizeof a)
#define mcpy(a,b) memcpy(a,b,sizeof a)
#define all(a) a.begin(),a.end()
#define fls() fflush(stdout)
#define maxn 500005
using namespace std;
int re()
{
    int x=0;
    bool t=1;
    char ch=getchar();
    while(ch>'9'||ch<'0')
        t=ch=='-'?0:t,ch=getchar();
    while(ch>='0'&&ch<='9')
        x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return t?x:-x;
}
void gx(int &x,int y)
{
    if(y>x)
        x=y;
}
void gn(int &x,int y)
{
    if(y<x)
        x=y;
}
int n;
char a[maxn];
signed main()
{
    n=re();
    int x1=1e9,x2=0,y1=1e9,y2=0,s1=1e9,s2=-1e9;
    while(n--)
    {
        scanf("%s",a+1);
        int m=strlen(a+1);
        int c1=0,c2=0;
        for(int i=1;i<=m;i++)
        {
            if(a[i]=='B')
                c1++;
            else
                c2++;
        }
        gn(x1,c1),gx(x2,c1);
        gn(y1,c2),gx(y2,c2);
        gn(s1,c1-c2),gx(s2,c1-c2);
    }
    int ans=1e9,x,y;
    for(int i=x1;i<=x2;i++)
    {
        int l=min(y1,i-s2),r=max(y2,i-s1);
        int j=l+r>>1;
        int t=max({i-x1,x2-i,j-l,r-j});
        if(t<=ans)
        {
            ans=t;
            x=i,y=j;
        }
    }
    printf("%d\n",ans);
    while(x--)
        putchar('B');
    while(y--)
        putchar('N');
    pn;
    return 0;
}