题解 P7919 【[Kubic] ABC】

VinstaG173 · 2021-11-04 01:30:28 · 题解

简单结论+构造题。

显然若 x+1<l，l \le x<r 或 x \ge r，则有 x,x+1 位置上的字母相同性在对 [l,r] 任意操作后不变，即原来相同操作后也相同，原来不同操作后也不同。故一次操作 [l,r] 最多只可能让相邻不同对数增加 2。故设最初相邻相同对数为 x，至少要 \left\lceil\dfrac{x}{2}\right\rceil 次操作才能使得相邻均不相同。

以下给出构造。由以上分析得每次操作 [l,r] 必然在 l-1,l 与 r,r+1 两个相邻位置均由相同变为不同。特别的，若 x 是奇数，则有一次操作只需要对 [l,n] 将 l-1,l 变为不同。这样我们只要找出相邻相同组再任意分组即可。事实上直接取头尾很容易实现。时间复杂度 O(n)。

感觉开这个数据范围是 checker 的缘故。

Code:

#include<cstdio>
int n,x,y,t;
char s[5003];
int l[5003],r[5003];
int main()
{
    scanf(" %d %s",&n,s+1);x=1,y=n;
    while(x<y)
    {
        while(x<y&&s[x]!=s[x+1])++x;
        while(y>x&&s[y]!=s[y-1])--y;
        if(x==y)break;
        l[++t]=++x,r[t]=--y;
    }
    printf("%d\n",t);
    if(l[t]>r[t])r[t]=n;
    for(int i=1;i<=t;++i)printf("%d %d BCA\n",l[i],r[i]);
    return 0;
}