AT_agc020_d [AGC020D] Min Max Repetition 题解

思路

先打表，二分出 $h$ 为所有完全由同一个字母组成的子串的最短长度，注意到答案中前面一部分一定为多个 $A...A(h个A)B$，后面一定为多个 $AB...B(h个B)$，中间是 $AB...B$。

因为要字典序最小，所以考虑计算 $A...AB$ 最多有多少个。

如果要判断一组 $n,m,h$ 是否合法，需要满足条件 $(\min(n,m)+1)h\ge\max(n,m)$。

所以我们可以二分出 $A...AB$ 的最大数量，即删去 $mid\times h$ 个 $A$ 和 $mid$ 个 $B$ 后后面是否合法，不过注意到前面的最后一个字符为 $B$，所以判断合法的公式是 $(n+1)h-1\ge m$（由于减去的 $n$ 更多，所以最后的 $n$ 一定更小）。

然后只需要给后面填上多个 $AB...B(h个B)$，中间填上 $AB...B$ 即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef __int128 ll;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin>>t;
	while(t--){
		int n,m;
		cin>>n>>m;
		int a,b;
		cin>>a>>b;
		ll l=1,r=max(n,m);
		while(l<r){//二分计算h 
			ll mid=(l+r)>>1;
			if((min(n,m)+1)*mid>=max(n,m))r=mid;
			else l=mid+1;
		}
		ll h=l;
		l=0,r=max(n,m);
		while(l<r){//二分计算出A...AB的最大数量 
			ll mid=(l+r+1)>>1;
			ll nn=n-mid*h,mm=m-mid;
			if(nn<0||mm<0)r=mid-1;
			if((nn+1)*h-1>=mm)l=mid;//判断是否合法 
			else r=mid-1;
		}
		n-=l*h;m-=l;
		ll st=l*(h+1);//前面的长度 
		ll x=min(m/h,(ll)n),len=x*(h+1);//后面AB...B的数量和长度 
		ll sum=n+m;
		m-=x*h;
		n-=x;
		for(int i=a;i<=b;i++){
			if(i<=st){//i属于前面 
				if(i%(h+1)==0)putchar('B');
				else putchar('A');
				continue;
			}
			if(i-st>=sum-len+1){//i属于后面 
				if((sum-i+st+1)%(h+1)==0)putchar('A');
				else putchar('B');
			}
			else{//i属于中间 
				if(i-st<=n)putchar('A');
				else putchar('B');
			}
		}
		putchar('\n');
	}
	return 0;
}

我场切紫了？这里我没有想到要用二分，直接来了一个数学解法，比 tjh 少一个 $\log$。

首先做这道题你得把最长连续字符子串的长度 $len$ 求出来吧。最坏情况是 $AA...ABA...ABA...AA$。这种情况那就是 $max(\lceil \frac{b}{a+1} \rceil,\lceil \frac{a}{b+1} \rceil)$。

手玩了一会样例，发现整个字符串其实是以这种形式构造的：$A_1...A_1SB_1...B_1$，其中 $A_1$ 是由 $len$ 个 $A$ 和一个 $B$ 拼接而成，$B_1$ 是由一个 $A$ 和 $len$ 个 $B$ 拼接而成的。$S$ 则是剩下的 $A$ 和 $B$ 依次拼接而成，而且你要保证 $A$ 和 $B$ 的数量不能超过 $len$。这样才能保证整个字符串的字典序最小。

很明显，我们必须尽可能多产生 $A_1$ 串。但是如果用贪心的话容易导致 $S$ 内 $A,B$ 失衡。所以我们需要均衡考虑。

考虑使用 $x$ 个 $A_1$，$y$ 个 $B_1$，则可以得到方程组：

$$\begin{cases} len \times x+y=A \\ x+len \times y=B \end{cases}$$

则解二元一次方程得：

$$\begin{cases} x=\frac{\frac{A+B}{len+1}+\frac{A-B}{len-1}}{2} \\ y=\frac{\frac{A+B}{len+1}-\frac{A-B}{len-1}}{2} \end{cases}$$

但由于 $x$ 和 $y$ 都不一定是整数，故都对其向下取整。此时 $S$ 内的 $A$ 和 $B$ 都一定是均衡的（因为都不超过 $len$），而且你也无法再添加哪怕一个 $A_1$。

剩下的求 $C$ 到 $D$ 判断位置所处的块分讨即可，长度不超过 $100$ 直接暴力。

但是注意：当 $len=1$ 时，原二元一次方程无法在程序内解。所以我们单独对 $len=1$ 进行分讨。易发现 $|A-B| \le 1$，构造也绝对是 $ABABA...$ 这种，判断奇偶性即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
void solve()
{
	int a,b,l,r;cin>>a>>b>>l>>r;
	int len=max(ceil(1.0*b/(a+1)),ceil(1.0*a/(b+1)));
	if(len==1)
	{
		if(b==a+1)
		{
			for(int i=l;i<=r;i++)
				if(i&1)cout<<"B";
				else cout<<"A";
		}
		else
		{
			for(int i=l;i<=r;i++)
				if(i&1)cout<<"A";
				else cout<<"B";
		}
		cout<<'\n';
		return ;
	}
	double pp1=(1.0*(a+b)/(len+1)+1.0*(a-b)/(len-1))/2;
	double pp2=(1.0*(a+b)/(len+1)-1.0*(a-b)/(len-1))/2;
	int sum1=pp1,sum2=pp2;
	int p1=a-sum1*len-sum2,p2=b-sum1-sum2*len;
	for(int i=l;i<=r;i++)
	{
		if(i<=sum1*(len+1))
		{
			if(i%(len+1)==0)cout<<"B";
			else cout<<"A";
		}
		else if(i<=sum1*(len+1)+p1+p2)
		{
			if(i-sum1*(len+1)<=p1)cout<<"A";
			else cout<<"B";
		}
		else 
		{
			if((i-(sum1*(len+1)+p1+p2))%(len+1)==1)cout<<"A";
			else cout<<"B";
		}
	}
	cout<<'\n';
}
signed main()
{
	int t;cin>>t;
	while(t--)solve();
	return 0;
}

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 |$

是分成两部分的。

• 前一部分贪心的填A，但是不能打破k的限制

• 后一部分不得已就填B

我们二分这个边界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;
    }
}

首先，解题一定要用简单的方式，所以我们应该设计最简单的形式，则可以设记状态为

$$AA...AABAA...AAB...A|BB...BBABB...BBA...$$

然后，计算出理论最短连续字符串长度

$$k=max(⌈\frac{A}{B+1}⌉,⌈\frac{B}{A+1}⌉)$$

接着二分出设计的形式的分界线。

最后输出答案就行了

完结撒花！！！

#代码

#include<bits/stdc++.h>
#define int long long
#define get(p) (a=A-p/(k+1)*k-p%(k+1),b=B-p/(k+1)) 
using namespace std;
int A,B,C,D,k;
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int T;
	cin>>T;
	while(T--){
		cin>>A>>B>>C>>D;
		k=max(ceil(A*1.0/(B+1)),ceil(B*1.0/(A+1)));//计算最短连续字串长度
		int a,b,L=0,R=A+B;
		while(L<R){//二分边界 
			int M=(L+R)>>1;
			get(M);
			if(b<=a*k)L=M+1;
			else R=M;
		}
		get(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<<"\n";
	}
    return 0;
}

zhengziye和admin题解的注释版，要先读完题解才能看懂：

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t,a,b,c,d;scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d%d%d",&a,&b,&c,&d);
		int k=max(ceil(A*1.0/(B+1)),ceil(B*1.0/(A+1))),x,y,l=0,r=a+b;
		//k为A和B的最短连续长度 
		while(l<r)
		{
			int mid=(l+r)/2;
			x=a-mid/(k+1)*k-mid%(k+1);
			y=b-mid/(k+1);
			if(y<=1ll*x*k)l=mid+1;
            //小细节：x*k最大为(2e8)^2往上，会爆int，要么*1ll，要么就把它们开成long long
			else r=mid;
		}//二分一段一段找l，为分段的那一个字母下标 ，看最贪能贪填A到哪里 
		x=a-l/(k+1)*k-l%(k+1);
		y=b-l/(k+1);//l刚算好，x和y又要重新赋值才是最终的结果
		r=l+1+y-x*k;//r用来分第二段，看前面从哪里开始填B的
		for(int i=c;i<=d;i++)
		{
			if(i<=l)
			{
				if(i%(k+1)!=0)printf("A");//第一段贪心全填A 
				else printf("B");//避免打破k的条件限制 
			}
			else
			{
				if((i-r)%(k+1)!=0)printf("B");
				else printf("A");//同上，第二段只能填B，也不要打破k的限制
			}
		}
		puts("");
	}
	return 0;
}