专栏文章

题解：CF1394C Boboniu and String

__abcd_
CF1394C题解参与者 2已保存评论 1

文章操作

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

当前评论
1 条
当前快照
1 份
快照标识符
@miqt564r
此快照首次捕获于
2025/12/04 10:19
3 个月前
此快照最后确认于
2025/12/04 10:19
3 个月前
查看原文

[CF1394C] Boboniu and String

为什么题解都带 log⁡\log 啊，是否有点极端了。
为了方便起见，下文将 BN\rm BN 串替换为 0101 串。注意到“相似的”的判定相当于 00 和 11 的个数都相等。并且，若设 00 的个数为 c0c_0，11 的个数为 c1c_1，每次操作都可以将 c0c_0 或 c1c_1 加一或减一，或者将 c0c_0 和 c1c_1 同时加一或减一。
那么将 (c0,c1)( c_0, c_1 ) 变成 (x,y)( x, y ) 的步数显然是：若 (c0−x)(c1−y)≥0( c_0 - x ) ( c_1 - y ) \ge 0，则答案为 max⁡(∣c0−x∣,∣c1−y∣)\max( | c_0 - x |, | c_1 - y | )，否则答案为 ∣c0−x∣+∣c1−y∣| c_0 - x | + | c_1 - y |。手玩以下就能发现答案等同于 max⁡(c0−x,x−c0,c1−y,y−c1,c0−x+y−c1,x−c0+c1−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 )。
考虑设 x1,x2,y1,y2,s1,s2x_1, x_2, y_1, y_2, s_1, s_2 分别表示 c0,c1,c0−c1c_0, c_1, c_0 - c_1 的最小值和最大值，那么答案就可以表示成 max⁡(x−x1,x2−x,y−l,r−y)\max( x - x_1, x_2 - x, y - l, r - y )，其中 l=min⁡(y1,x−s2),r=max⁡(y2,x−s1)l = \min( y_1, x - s_2 ), r = \max( y_2, x - s_1 )。显然当 y=l+r2y = \frac{l+r}{2} 时最优。直接枚举 xx 并计算即可。复杂度为 O(n)O(n)。
CPP
#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;
}

评论

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

正在加载评论...