AT3858 [AGC020D] Min Max Repetition
GreenDay
2020-04-27 22:11:51
`WA`了1个晚上 最终还是看了`editorial`,我果然还是太菜了qwq
---
## 题意
[链接](https://www.luogu.com.cn/problem/AT3858)
## 做法
直观上看这道题需要大量分类讨论，似乎根本不可做。
事实上，这道题非常巧妙，**几乎没有分类讨论**，直接使用**二分**进行构造。
首先，我们有最小连续长度 $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 |$
是分成两部分的。
- 前一部分贪心的填`A`，但是不能打破`k`的限制
- 后一部分不得已就填`B`
我们二分这个边界`p`，使得`p`的右半部分满足：$b > ak$.**这样可以使得两边都满足条件，而且可以保证分界线的左边是`A`,右边是`B`.**
输出时候分两半判断。可以看代码。
```cpp
#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;
}
}
```