【模拟7.25】寿司

事实上我不知道该把这道题放在那一块........

此题用了1部分二分的思想，还有函数思想，sdfz大佬用的三分思想orz.......

40分暴力：

将环搞成2len的序列，然后与处理出

sumlb[i]表示从1-i的B移动到左段的总步数 blcnt[i]表示从1-i的b的个数，其余相似。。。

然后分n个区间枚举断点，有一点：

kx=(sum_lb[k]-sum_lb[l-1])+(sum_rb[k+1]-sum_rb[r+1]);

kxl=rlcnt[l-1]*(blcnt[k]-blcnt[l-1]);
kxr=rrcnt[r+1]*(brcnt[k+1]-brcnt[r+1]);

return kx-kxl-kxr

这里我们不能单纯加kx因为数组表示从1-i而此时区间l-r则不是

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<string>
  5 #include<algorithm>
  6 #include<cmath>
  7 #include<stack>
  8 #include<map>
  9 #include<queue>
 10 #define ps push_back
 11 #define MAXN 105101
 12 #define ll long long
 13 using namespace std;
 14 int T;
 15 int n;
 16 char c[MAXN];
 17 int a[MAXN];
 18 int len;
 19 int minn;
 20 int sum1,sum2;
 21 int sum_lb[MAXN],sum_rb[MAXN];
 22 int blcnt[MAXN],brcnt[MAXN],rrcnt[MAXN],rlcnt[MAXN];
 23 int getsum(int l,int k,int r)
 24 {
 25    //printf("sum_rb[%d]=%d s[%d]=%d
",k+1,sum_rb[k+1],r+1,sum_rb[r+1]);
 26    int kx1=(sum_lb[k]-sum_lb[l-1])+(sum_rb[k+1]-sum_rb[r+1]);
 27    int kxl=rlcnt[l-1]*(blcnt[k]-blcnt[l-1]);
 28    int kxr=rrcnt[r+1]*(brcnt[k+1]-brcnt[r+1]);
 29    //printf("kx1=%d lxl=%d kxr=%d
",kx1,kxl,kxr);
 30    return (kx1-kxl-kxr);
 31 }
 32 void work(int l,int r)
 33 {
 34     //printf("l=%d r=%d
",l,r);
 35     int ans=0;
 36     for(int i=l;i<=r;++i)
 37     {
 38         ans=getsum(l,i,r);
 39         //printf("1===i=%d ans=%d
",i,ans);
 40         minn=min(ans,minn);
 41     }
 42 }
 43 
 44 int main()
 45 {
 46     //freopen("text.in","r",stdin);
 47     //freopen("wa.out","w",stdout);
 48     scanf("%d",&T);
 49     while(T--)
 50     {
 51         memset(sum_lb,0,sizeof(sum_lb));
 52         memset(sum_rb,0,sizeof(sum_rb));
 53         memset(blcnt,0,sizeof(blcnt));
 54         memset(brcnt,0,sizeof(brcnt));
 55         memset(rlcnt,0,sizeof(rlcnt));
 56         memset(rrcnt,0,sizeof(rrcnt));
 57         memset(a,0,sizeof(a));
 58         minn=1000000000;
 59         //sum1=0;sum2=0;
 60         scanf("%s",c+1);
 61         int len=strlen(c+1);
 62         if(len==1){printf("0
");continue;}
 63         for(int i=1;i<=len;++i)
 64         {
 65             if(c[i]=='B')a[i]=1;
 66             else c[i]=2;
 67             a[len+i]=a[i];
 68         }
 69         int lr=0;
 70         for(int i=1;i<=2*len;++i)
 71         {
 72             sum_lb[i]=sum_lb[i-1];
 73             blcnt[i]=blcnt[i-1];rlcnt[i]=rlcnt[i-1];
 74             if(a[i]==1)
 75             {
 76                  sum_lb[i]+=lr;
 77                  blcnt[i]++;
 78                  //printf("sum_lb[%d]=%d
",i,sum_lb[i]);
 79             }
 80             else
 81             {
 82                  lr++;
 83                  rlcnt[i]++;
 84             }
 85             //printf("bl=%d rl=%d
",blcnt[i],rlcnt[i]);
 86         }
 87         int rr=0;
 88         for(int i=2*len;i>=1;--i)
 89         {
 90             sum_rb[i]=sum_rb[i+1];
 91             rrcnt[i]=rrcnt[i+1];brcnt[i]=brcnt[i+1];
 92             if(a[i]==1)
 93             {
 94                sum_rb[i]+=rr;
 95                brcnt[i]++;
 96                //printf("sum_rb[%d]=%d
",i,sum_rb[i]);
 97             }
 98             else 
 99             {
100                rr++;
101                rrcnt[i]++;
102             }
103         }
104         for(int i=1;i<=len-1;++i)
105         {
106             work(i,len+i-1);
107         }
108         printf("%d
",minn);
109     }
110 }
111 /*
112 9
113 BRRRBRRRBBRBBR
114 RRRRRBRRRRRBBRR
115 */

View Code

100分代码

满足性质区间向右移最优断点向右移或不变

看过znn的博客受到启发

然后O(n)枚举区间，指针移动最优断点即可

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<string>
  5 #include<algorithm>
  6 #include<cmath>
  7 #include<stack>
  8 #include<map>
  9 #include<queue>
 10 #define ps push_back
 11 #define MAXN 2005101
 12 #define ll long long
 13 using namespace std;
 14 ll T;
 15 char c[MAXN];
 16 ll a[MAXN];
 17 ll len;
 18 ll minn;ll zh;
 19 ll sum1,sum2;
 20 ll sum_lb[MAXN],sum_rb[MAXN];
 21 ll blcnt[MAXN],brcnt[MAXN],rrcnt[MAXN],rlcnt[MAXN];
 22 ll getsum(ll l,ll k,ll r)
 23 {
 24    ll kx1=(sum_lb[k]-sum_lb[l-1])+(sum_rb[k+1]-sum_rb[r+1]);
 25    ll kxl=rlcnt[l-1]*(blcnt[k]-blcnt[l-1]);
 26    ll kxr=rrcnt[r+1]*(brcnt[k+1]-brcnt[r+1]);
 27    return (kx1-kxl-kxr);
 28 }
 29 int main()
 30 {
 31     scanf("%lld",&T);
 32     while(T--)
 33     {
 34         memset(sum_lb,0,sizeof(sum_lb));
 35         memset(sum_rb,0,sizeof(sum_rb));
 36         memset(blcnt,0,sizeof(blcnt));
 37         memset(brcnt,0,sizeof(brcnt));
 38         memset(rlcnt,0,sizeof(rlcnt));
 39         memset(rrcnt,0,sizeof(rrcnt));
 40         memset(a,0,sizeof(a));
 41         minn=0x7fffffffffffffff;
 42         //printf("%lld
",minn);
 43         scanf("%s",c+1);
 44         ll len=strlen(c+1);
 45         if(len==1){printf("0
");continue;}
 46         for(ll i=1;i<=len;++i)
 47         {
 48             if(c[i]=='B')a[i]=1;
 49             else a[i]=2;
 50             a[len+i]=a[i];
 51         }
 52         ll lr=0;
 53         for(ll i=1;i<=2*len;++i)
 54         {
 55             sum_lb[i]=sum_lb[i-1];
 56             blcnt[i]=blcnt[i-1];rlcnt[i]=rlcnt[i-1];
 57             if(a[i]==1)
 58             {
 59                  sum_lb[i]+=lr;
 60                  blcnt[i]++;
 61             }
 62             else
 63             {
 64                  lr++;
 65                  rlcnt[i]++;
 66             }
 67         }
 68         ll rr=0;
 69         for(ll i=2*len;i>=1;--i)
 70         {
 71             sum_rb[i]=sum_rb[i+1];
 72             rrcnt[i]=rrcnt[i+1];brcnt[i]=brcnt[i+1];
 73             if(a[i]==1)
 74             {
 75                sum_rb[i]+=rr;
 76                brcnt[i]++;
 77             }
 78             else 
 79             {
 80                rr++;
 81                rrcnt[i]++;
 82             }
 83         }
 84         ll ans=0;
 85         zh=(rlcnt[len]+1)/2;
 86         for(ll i=1;i<=len;++i)
 87         {
 88             if(rlcnt[i]==zh)
 89             {
 90                 zh=i;
 91                 break;
 92             }
 93         }
 94         ans=getsum(1,zh,len);
 95         //printf("aa%lld %lld
",getsum(1,zh,len),zh);
 96         ans=min(ans,minn);
 97         for(ll i=1;i<=len;++i)
 98         {
 99              ll hh=i;
100              ll tail=i+len-1;
101              if(a[i]==2)
102              {
103                  ans-=blcnt[zh]-blcnt[hh-1];
104                  ans+=brcnt[zh]-brcnt[tail+1];
105                  while(a[++zh]==1)
106                  {
107                       ans-=rrcnt[zh]-rrcnt[tail+2];
108                       ans+=rlcnt[zh]-rlcnt[hh];
109                  }
110                  //printf("ans=%lld
",ans);  
111              }           
112              minn=min(ans,minn);
113         }
114         //printf("%lld
",minn);
115         printf("%lld
",minn);
116     }
117 }
118 /*
119 9
120 BRRRBRRRBBRBBR
121 RRRRRBRRRRRBBRR
122 */

View Code