【AtCoder Grand Contest 020 D】Min Max Repetition | Mrsrz's blog

贪心，构造。

题目大意：

多组询问，每次给定 $a,b,l,r$，要求用 $a$ 个 A 和 $b$ 个 B 组成字符串，满足：

• 最长的连续相同字符段的长度最短。
• 在此基础上字典序最小。

要求输出第 $l\sim r$ 个字符。

题解：

假设 $a\geq b$。

设最短的最长的连续相同字符段长度为 $x$。

那么要满足 $(b+1)x\geq a$（每 $x$ 个 A 后跟一个 B，最后还可以跟 $x$ 个 A）。

可以得到 $x=\lceil\frac{a}{b+1}\rceil$.

然后考虑构造字典序最小的解。

要求字典序最小，我们显然要尽可能把 A 放前面。

那么我们的方案是，最前面放若干组 AA...AB（有 $x$ 个 A），中间放若干个 A，然后再放若干个 B，然后再放若干组 ABB...B（有 $x$ 个 B）。

最前面的组数，我们可以通过二分得到，最后的组数，可以通过余下的 A 和 B 的个数算出来，然后中间就把剩余的插入即可。

对于 $a\lt b$ 的情况，相当于前面先放 AA...AB，后面放 ABB...B。实际上，把 $a$ 和 $b$ 交换后，按照 $a\geq b$ 的情况得到的串，把 A和 B 互换，再翻转，就是 $a\lt b$ 的情况。

Code：

#include<cstdio>
#include<stdint.h>
#define int long long
int T,a,b,L,R,x,l,r,ans;
inline bool check(int c){
    int aa=a-(c/(x+1)*x+c%(x+1)),bb=b-c/(x+1);
    return aa*x>=bb;
}
int32_t main(){
    for(scanf("%lld",&T);T--;){
        scanf("%lld%lld%lld%lld",&a,&b,&L,&R);
        x=((a>b?a:b)-1)/((a<b?a:b)+1)+1,l=1,r=(a+b)/(x+1),ans=0;
        while(l<=r){
            const int mid=l+r>>1;
            if(check(mid*(x+1)))l=(ans=mid)+1;else r=mid-1;
        }
        ans*=x+1;
        int aa=a-(ans/(x+1)*x+ans%(x+1)),bb=b-ans/(x+1);
        int exta=aa-bb/x,extb=bb%x;
        for(int i=L;i<=R;++i)
        if(i<=ans)putchar(i%(x+1)?'A':'B');else
        if(i<=ans+exta)putchar('A');else
        if(i<=ans+exta+extb)putchar('B');else
        putchar((i-ans-exta-extb)%(x+1)==1?'A':'B');
        putchar('\n');
    }
    return 0;
}