AGC020D Min Max Repetition

有生之年想出来的 AGC 构造题，值得记一下。

Link

多组询问。每个询问给定四个整数 \(A,B,C,D\)，求一个满足这个条件的字符串：

1. 长度为 \(A+B\)，由 \(A\) 个字符 \(\mathtt{A}\) 和 \(B\) 个字符 \(\mathtt{B}\) 构成。

2. 在此基础上，连续的相同字符个数的最大值最小。

3. 在此基础上，字典序最小。

输出这个字符串的第 \(C\) 位到第 \(D\) 位。

不妨先考虑一下，\(A=B\) 的时候我们会如何安排。显然，由于要满足条件 \(2\)，我们一定会交叉放置。而由于条件 \(3\)，我们会安排成 \(\underbrace{\mathtt{AB\cdots AB}}_{若干个\mathtt{AB}}\)。

现在如果我们放了上述个 \(\mathtt{A,B}\)，还多出若干个 \(\mathtt{A}\)，那么多出的 \(\mathtt{A}\) 就一定会插入到前半部分的 \(\mathtt{AB}\) 中，形成 \(\mathtt A\underbrace{\cdots}_{若干个\mathtt{A}} \mathtt B\)。经过这样操作之后，我们发现我们条件 \(2\) 的需求放宽了，也就是说我们原本的某些 \(\mathtt{B}\) 可以向后调整。最终，整个序列会变成这样：

\[ \mathtt{(A\cdots B)\cdots|A\cdots AB\cdots B|(B\cdots A)\cdots} \]

其中 \(\cdots\) 表示前部分的反复。

容易得到 \(k=\lceil\dfrac{a+b}{\min(a,b)+1}\rceil\)，\(k\) 是的连续相同字符个数，

那么我们可以二分出来中间的 \(\mathtt{A\cdots AB\cdots B}\) 的 \(\mathtt{AB}\) 中界，然后就可以按照构造的方式输出。发现如果我们当前还剩 \(a\) 个 \(\mathtt A\)，\(b\) 个 \(\mathtt B\)，我们需要满足 \(b>ak\)。输出的时候分为左右两边判断即可。

bool check(int mid)
{
    int a = A - mid / (k + 1) * k - mid % (k + 1);
    int b = B - mid / (k + 1);
    return b <= a * k;
}

void Main()
{
    read(A, B, C, D);
    k = (A + B) / (min(A, B) + 1);
    int l = 0, r = A + B + 1, mid;
    while(l < r)
    {
        mid = (l + r) >> 1;
        if(check(mid)) l = mid + 1;
        else r = mid;
    }
    int a = A - l / (k + 1) * k - l % (k + 1);
    int b = B - l / (k + 1);
    r = l + 1 + b - a * k;
    for(int i = C; i <= D; i++)
        if(i <= l) printf("%c", (i % (k + 1)) ? 'A' : 'B');
        else printf("%c", ((i - r) % (k + 1)) ? 'B' : 'A');
    printf("\n");
}