HZOJ 旋转子段

作者的正解：

算法一：对于30%的数据： 直接枚举区间直接模拟，时间复杂度O(N³)。

算法二：对于60%的数据：枚举旋转中心点,然后再枚举旋转的端点, 我们可以用O(n)的预处理求前缀和记录固定点，总时间复杂度O（N²）。

算法三：对于100%的数据：假设有最优解为[i,j](i,j皆为下标，A[i],A[j]才是题目所要输出的答案）。if(A[i]!=j&&A[j]!=i)，就是A[i]和A[j]经过旋转之后都没有成为不动点，那么[i+1,j-1]也是一个最优解(如果i+1>j-1，那么[1,1]也是最优解）。两端旋转之后如果都没成为不动点我们可以去掉两端，不停地去掉后得到最优解为[x,y]则有A[x]=y或者A[y]=x,或者x=y=1（ [1,1]可以不参与讨论).

因此最优解一定是[min(i,A[i]),max(i,A[i])](i=1,2,3......,n)。

只需要枚举n个值就能找到最优解，由此找最优解问题变成了查询问题。假设i<=A[i],要查询的区间变成了三段[1,i-1] [i, A[i] ] [ A[i+1] ,n]，固定点个数O(1)的时间查询。中间这一段 [i, A[i] ]经过了一次旋转，对于旋转后的固定点j有A[j]+j=A[i]+i且,而[j,A[j]]也是我们要考虑成为最优解的一个旋转，我们事先将这n种旋转按照轴心不同分类，每一类由旋转区间长度短到长排序。以上算法因为要排序所以复杂度为O（N log N）。

然而数据很水我们可以直接错解碾标算。

对于60的数据：

对于一个旋转中心，他的至少一个端点反转后是固定点，即满足（a[i]+i=mid*2）。于是我们可以枚举这个端点，然后就可以算出旋转中心进而On统计答案。

然后说一下我的错解（其实很接近正解了）：

根据以上算法可以发现求得就是对于一个旋转中心的旋转段总（a[i]+i=mid*2）的点数以及旋转段外本来就是固定点的个数，前者可以用桶处理，后者可以用前缀和处理。总复杂度O（n）。

对于旋转段端点的处理，更新桶时处理最后保证对称即可。

         for(int i=;i<=n;i++)

         {

             sum[i+a[i]]++;

             l[i+a[i]]=min(l[i+a[i]],i);

             r[i+a[i]]=max(r[i+a[i]],i);

         }

         for(int i=;i<=n*;i++)

         {

             int tl=l[i],tr=r[i];

             l[i]=min(l[i],i-tr);

             r[i]=max(r[i],i-tl);

         }

所以到现在你发现这个算法错误的地方吗？没错上面只是处理的对于每个旋转中心最大的旋转段，但是这不一定是最优的（然而数据中好像都是最优的……），提供一组hack数据：

15

14 2 8 9 10 11 1 15 6 5 4 3 13 7 12

正确答案是7，而以上算法出的是6。错误就在于这里最大的旋转区间并不是最优的。

为了解决这个问题，就需要将最大区间不断收缩寻找最优解。

但是这样就又成$n^2$的了，怎么办呢？

其实可以发现一步一步收缩的话有很多步数是没有意义的，我们可以考虑对每个旋转中心开一个vector存a[i]+i=mid的点的位置，按照离旋转中心的距离排序，这样收缩的时候只需枚举vector，以上算法因为要排序所以复杂度为O（N log N）。

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #include<ctime>

 #define MAXN 500010

 #define LL long long

 #define ma(x,y) memset(x,y,sizeof(x))

 using namespace std;

 int n,a[MAXN];

 int sum[MAXN*],l[MAXN*],r[MAXN*];

 int pre[MAXN];

 inline int read();

 signed main()

 {

 //    freopen("in.txt","r",stdin);

 //    freopen("tem","r",stdin);

 //    freopen("1.out","w",stdout);

     double sst=clock();

     n=read();

     for(int i=;i<=n;i++)a[i]=read();

 /*    if(n<=500)

     {

         int ans=0,res=0;

         for(int i=1;i<=n;i++)

             for(int j=i;j<=n;j++)

             {

                 for(int k=0;i+k<=j-k;k++)

                 {

                     if(a[i+k]==j-k)res++;

                     if(a[j-k]==i+k)res++;

                     if((i+k==j-k)&&a[j-k]==i+k)res--;

                 }

                 for(int k=1;k<i;k++)

                 if(a[k]==k)res++;

                 for(int k=j+1;k<=n;k++)

                 if(a[k]==k)res++;

                 ans=max(ans,res);res=0;

             }

         printf("%d\n",ans);

         return 0;

     }

     if(n<=5000)

     {

         int ans=0,res=0;

         for(int i=1;i<=n;i++)

         {

             res=0;

             double mid=1.0*(i+a[i])/2;

             int st=min(a[i],i),en=max(a[i],i);

             for(int j=st;j<=en;j++)

                 if(1.0*(double)(j+a[j])/2==mid)res++;

             for(int j=1;j<st;j++)

                 if(j==a[j])res++;

             for(int j=en+1;j<=n;j++)

                 if(j==a[j])res++;

             ans=max(ans,res);

         }

         printf("%d\n",ans);

         return 0;

     }

     else*/

     {

         for(int i=;i<=n;i++)

         {

             pre[i]=pre[i-];

             if(a[i]==i)pre[i]++;

         }

         ma(l,0x7f);ma(r,);

         for(int i=;i<=n;i++)

         {

             sum[i+a[i]]++;

             l[i+a[i]]=min(l[i+a[i]],i);

             r[i+a[i]]=max(r[i+a[i]],i);

         }

         for(int i=;i<=n*;i++)

         {

             int tl=l[i],tr=r[i];

             l[i]=min(l[i],i-tr);

             r[i]=max(r[i],i-tl);

         }

         int ans=;

         for(int i=;i<=n*;i++)

         if(sum[i])

         {

             ans=max(ans,sum[i]+pre[l[i]-]+pre[n]-pre[r[i]]);

 /*            for(int j=1;j&&l[i]<r[i];j++)

             {

                 double st=clock();

                 if(l[i]+a[l[i]]==i)sum[i]--;

                 if(r[i]+a[r[i]]==i)sum[i]--;

                 l[i]++,r[i]--;

                 ans=max(ans,sum[i]+pre[l[i]-1]+pre[n]-pre[r[i]]);

                 double en=clock();

                 if((en-st)/1000>5)break;

                 if((en-sst)/1000>550)break;

             }*/

         }

         printf("%d\n",ans);

         return ;

     }

 }

 inline int read()

 {

     int s=,f=;char a=getchar();

     while(a<''||a>''){if(a=='-')f=-;a=getchar();}

     while(a>=''&&a<=''){s=s*+a-'';a=getchar();}

     return s*f;

 }

所以我并没有正解的代码

巴特西

HZOJ 旋转子段

最新文章

热门文章