「AGC020D」 Min Max Repetition

首先这个东西的连续字符个数你可以二分。但事实上没有必要，这是可以直接算出来的。

即 \(k=\max\{\lceil\frac{A}{B+1}\rceil,\lceil\frac{B}{A+1}\rceil\}\)。

证明你就考虑把每一个 B 或者 A 分成一段过后另一种最少每段放几个。

然后接下来就非常神奇，由于要求字典序最小，这个字符串一定形如 \(\texttt{AAA...BAAA...BAAA...BBB...ABBB...A}\)

然后可以二分两种类型分割的边界，然后暴力check能不能填的上就完事了。

当然这里存在方法可以通过分类讨论来做到不需二分。

/*---Author:HenryHuang---*/

/*---Never Settle---*/

#include<bits/stdc++.h>

using namespace std;

int a,b,c,d,k;

bool check(int mid){

	int u=a-mid/(k+1)*k-mid%(k+1);

	int v=b-mid/(k+1);

	return 1ll*v<=1ll*u*k;

}

int main(){

	ios::sync_with_stdio(0);

	cin.tie(0),cout.tie(0);

	int T;cin>>T;

	while(T--){

		cin>>a>>b>>c>>d;

		k=max(ceil(1.0*a/(b+1)),ceil(1.0*b/(a+1)));

		int l=0,r=a+b+1;

		while(l<r){

			int mid=(l+r)>>1;

			if(check(mid)) l=mid+1;

			else r=mid;

		}

		int u=a-l/(k+1)*k-l%(k+1);

		int v=b-l/(k+1);

		r=l+v-u*k+1;

		for(int i=c;i<=min(d,l);++i){

			if(i%(k+1)) cout<<"A";

			else cout<<"B";

		}

		for(int i=max(c,l+1);i<=d;++i){

			if((i-r)%(k+1)) cout<<"B";

			else cout<<"A";

		}

		cout<<'\n';

	}

	return 0;

}

巴特西

「AGC020D」 Min Max Repetition

「AGC020D」 Min Max Repetition

最新文章

热门文章