AT3858 [AGC020D] Min Max Repetition

· · 题解

WA了1个晚上 最终还是看了editorial,我果然还是太菜了qwq

题意

链接

做法

直观上看这道题需要大量分类讨论，似乎根本不可做。

事实上，这道题非常巧妙，几乎没有分类讨论，直接使用二分进行构造。

首先，我们有最小连续长度 k=\max \{ \left\lceil\dfrac{a}{b+1}\right\rceil , \left\lceil\dfrac{b}{a+1}\right\rceil \} ,我们可以贪心的去证明。

然后，我们非常大胆的猜测了这个串串的形式是：

|A \cdots ABA \cdots AB \cdots \cdots |B \cdots BAB \cdots BA \cdots \cdots |

是分成两部分的。

我们二分这个边界p，使得p的右半部分满足：b > ak.这样可以使得两边都满足条件，而且可以保证分界线的左边是A,右边是B.

输出时候分两半判断。可以看代码。

#include <iostream>
using namespace std;

int main() {
    int T , A , B , C , D , k;
    for(cin >> T ; T ; T--) {
        cin >> A >> B >> C >> D;
        k = (A + B) / (min(A , B) + 1);
        int a , b;
        auto getAB = [&] (int p) {
            a = A - p / (k + 1) * k - p % (k + 1) , 
            b = B - p / (k + 1);
        };
        int l = 0 , r = A + B , mid;
        while(l < r) {
            mid = (l + r) >> 1;
            getAB(mid);
            if(b <= (long long)a * k) l = mid + 1;
            else r = mid;
        }
        getAB(l);
        r = l + 1 + b - a * k;
        for(int i = C ; i <= D ; ++i) {
            if(i <= l) {
                if(i % (k + 1) != 0) cout << 'A';
                else cout << 'B';
            } else {
                if((i - r) % (k + 1) != 0) cout << 'B';
                else cout << 'A';
            }
        }
        cout << endl;
    }
}