[AGC020D] Min Max Repetition 讲解

zrl123456 · 2024-07-12 13:08:06 · 题解

[AGC020D] Min Max Repetition

题目考察：贪心，数学，二分。
题目简述：

• 1\le a,b\le 5\times 10^8
• 1\le c\le d\le a+b
• 1\le d-c+1\le 100

  首先我们肯定可以得出最小的最大连续相同字符数是 \displaystyle k=\max(\lceil\frac{a}{b+1}\rceil,\lceil\frac{b}{a+1}\rceil)。
  我们让 B 尽可能靠后，那么这个字符串长成这样：

  \text{AAA\dots ABAAA\dots ABAAA\dots ABAAA\dots ABB\dots BABB\dots BABB\dots BB}

  那么我们可以二分找出其分界点，那么我们还需要一个判断条件。
  设分界点为 x，则 A 在前面使用了 \displaystyle\lfloor\frac{x}{k+1}\rfloor\times k+x\bmod (k+1) 个，那么 A 在后面就要使用 \displaystyle a-\lfloor\frac{x}{k+1}\rfloor\times k-x\bmod (k+1) 个；B 在前面使用了 \displaystyle\lfloor\frac{x}{k+1}\rfloor 个，那么 B 在后面使用了 \displaystyle b-\lfloor\frac{x}{k+1}\rfloor 个。
  则我们得到判断条件：

  (a-\lfloor\frac{x}{k+1}\rfloor\times k-x\bmod (k+1))\times k<b-\lfloor\frac{x}{k+1}\rfloor

  然后我们发现在前半部分当 i\bmod (k+1)=0 时 s_i 是 B，A 反之；在后半部分当 (a+b-k+1)\bmod (k+1)=0 时是 B，A 反之。

单次询问时间复杂度为 \Theta(\log_2(a+b)+(d-c))。
代码：

#include<bits/stdc++.h>
#define inl inline
#define reg register
#define int long long
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define rep(i,x,y) for(reg int i=x;i<=(y);++i) 
#define per(i,x,y) for(reg int i=x;i>=(y);--i)
#define rpr(i,x,y,z) for(reg int i=x;i<=(y);i+=z)
#define epe(i,x,y,z) for(reg int i=x;i>=(y);i-=z)
#define endl '\n'
#define INF (int)1e16
#define pb push_back
#define fi first
#define se second
#define lcm(x,y) x/__gcd(x,y)*y
#define ull unsigned long long
#define prr make_pair
#define pii pair<int,int> 
#define gt(s) getline(cin,s)
#define at(x,y) for(reg auto x:y)
#define ff fflush(stdout)
#define mt(x,y) memset(x,y,sizeof(x))
#define idg isdigit
#define fp(s) string ssss=s;freopen((ssss+".in").c_str(),"r",stdin);freopen((ssss+".out").c_str(),"w",stdout);
#define sstr stringstream 
using namespace std;
inl bool check(int x,int k,int a,int b){
//  cout<<(a-x/(k+1)*k-x%(k+1))<<' '<<b-x/(k+1)<<endl;
    return (a-x/(k+1)*k-x%(k+1))*k<b-x/(k+1);
}
inl int lower(int l,int r,int k,int a,int b){
    reg int mid=0,ans=-1,fl=l,fr=r;
    while(l<=r){
        mid=l+r>>1;
//      cout<<mid<<endl;
        if(check(mid,k,a,b)){
            r=mid-1;
            ans=mid;
        }else l=mid+1;
    }
    if(ans!=-1) return ans;
    else if(fl==l) return -1;
    else return r+1;
}
inl void solve(){
    reg int a,b,c,d,k,x;
    cin>>a>>b>>c>>d;
    k=max(max((int)ceil(a/(b+1.0)),(int)ceil(b/(a+1.0))),1ll);
    x=lower(0,a+b,k,a,b);
//  cout<<k<<' '<<x<<endl;
    rep(i,c,d)
        if(i<=x)
            if(i%(k+1)) cout<<'A';
            else cout<<'B';
        else if((a+b-i+1)%(k+1)) cout<<'B';
        else cout<<'A';
    cout<<endl;
}
signed main(){
    fst;
    reg int t;
    cin>>t;
    while(t--) solve();
    return 0;
}