AtCoder Grand Contest 020 D - Min Max Repetition

q<=1000个询问，每次问a,b,c,d：f(a,b)表示含a个A，b个B的字符串中，连续A或连续B最小的串中，字典序最小的一个串，输出这个串的c到d位。a,b<=5e8，d-c+1<=100。

首先可以确定这个“连续A或连续B的最小值”是：$\left \lceil \frac{p}{q+1} \right \rceil$

然后就尽可能在前面放A，如果放A导致后面不满足这个“连续A或连续B的最小值”，就放B，这样是O(n)的。

打几个表发现：串实际上是前面：AA……ABAA……ABAA……ABAA……这样的，后面是BABB……BABB……BABB，这样的，那二分一下这个分界的位置，判断按前缀那样放A，B之后后缀能否满足“连续A或连续B的最小值”。然后根据c，d在这个位置前后分下类输出答案即可。

 #include<string.h>

 #include<stdlib.h>

 #include<stdio.h>

 #include<math.h>

 //#include<assert.h>

 #include<algorithm>

 //#include<iostream>

 //#include<bitset>

 using namespace std;

 int q,a,b,c,d,len;

 int calc(int a,int b)

 {

     if (!a || !b) return a^b;

     if (a<b) a^=b,b^=a,a^=b;

     return (a-)/(b+)+;

 }

 bool check(int x)

 {

     int cnta=x/(len+)*len+x%(len+),cntb=x/(len+)-(x%(len+)==);

     if (cnta>a) return ;

     return calc(a-cnta,b-cntb)<=len;

 }

 void workleft(int left,int right)

 {

     for (int i=left;i<=right;i++)

     {

         if (i%(len+)==) putchar('B');

         else putchar('A');

     }

 }

 void workright(int left,int right)

 {

     for (int i=left;i<=right;i++)

     {

         if ((a+b-i+)%(len+)==) putchar('A');

         else putchar('B');

     }

 }

 int main()

 {

     scanf("%d",&q);

     while (q--)

     {

         scanf("%d%d%d%d",&a,&b,&c,&d);

         len=calc(a,b);

         int L=,R=a+b;

         while (L<R)

         {

             int mid=(L+R+)>>;

             if (check(mid)) L=mid;

             else R=mid-;

         }

         int pos=L;

         if (d<=pos) workleft(c,d);

         else if (c>pos) workright(c,d);

         else workleft(c,pos),workright(pos+,d);

         puts("");

     }

     return ;

 }

巴特西

AtCoder Grand Contest 020 D - Min Max Repetition

最新文章

热门文章