HZOJ 旋转子段
作者的正解：
?
算法一：對于30%的數(shù)據(jù)：?直接枚舉區(qū)間直接模擬，時間復雜度O(N3)。
算法二：對于60%的數(shù)據(jù)：枚舉旋轉(zhuǎn)中心點,然后再枚舉旋轉(zhuǎn)的端點,?我們可以用O(n)的預處理求前綴和記錄固定點，總時間復雜度O（N2）。
算法三：對于100%的數(shù)據(jù)：假設有最優(yōu)解為[i,j](i,j皆為下標，A[i],A[j]才是題目所要輸出的答案）。if(A[i]!=j&&A[j]!=i)，就是A[i]和A[j]經(jīng)過旋轉(zhuǎn)之后都沒有成為不動點，那么[i+1,j-1]也是一個最優(yōu)解(如果i+1>j-1，那么[1,1]也是最優(yōu)解）。兩端旋轉(zhuǎn)之后如果都沒成為不動點我們可以去掉兩端，不停地去掉后得到最優(yōu)解為[x,y]則有A[x]=y或者A[y]=x,或者x=y=1（ [1,1]可以不參與討論).
因此最優(yōu)解一定是[min(i,A[i]),max(i,A[i])](i=1,2,3......,n)。
只需要枚舉n個值就能找到最優(yōu)解，由此找最優(yōu)解問題變成了查詢問題。假設i<=A[i],要查詢的區(qū)間變成了三段[1,i-1] ??[i, A[i] ] ??[ A[i+1] ,n]，固定點個數(shù)O(1)的時間查詢。中間這一段 [i, A[i] ]經(jīng)過了一次旋轉(zhuǎn)，對于旋轉(zhuǎn)后的固定點j有A[j]+j=A[i]+i且,而[j,A[j]]也是我們要考慮成為最優(yōu)解的一個旋轉(zhuǎn)，我們事先將這n種旋轉(zhuǎn)按照軸心不同分類，每一類由旋轉(zhuǎn)區(qū)間長度短到長排序。以上算法因為要排序所以復雜度為O（N log N）。
?
然而數(shù)據(jù)很水我們可以直接錯解碾標算。
對于60的數(shù)據(jù)：
對于一個旋轉(zhuǎn)中心，他的至少一個端點反轉(zhuǎn)后是固定點，即滿足（a[i]+i=mid*2）。于是我們可以枚舉這個端點，然后就可以算出旋轉(zhuǎn)中心進而On統(tǒng)計答案。
然后說一下我的錯解（其實很接近正解了）：
根據(jù)以上算法可以發(fā)現(xiàn)求得就是對于一個旋轉(zhuǎn)中心的旋轉(zhuǎn)段總（a[i]+i=mid*2）的點數(shù)以及旋轉(zhuǎn)段外本來就是固定點的個數(shù)，前者可以用桶處理，后者可以用前綴和處理。總復雜度O（n）。
對于旋轉(zhuǎn)段端點的處理，更新桶時處理最后保證對稱即可。
1 for(int i=1;i<=n;i++) 2 { 3 sum[i+a[i]]++; 4 l[i+a[i]]=min(l[i+a[i]],i); 5 r[i+a[i]]=max(r[i+a[i]],i); 6 } 7 for(int i=1;i<=n*2;i++) 8 { 9 int tl=l[i],tr=r[i]; 10 l[i]=min(l[i],i-tr); 11 r[i]=max(r[i],i-tl); 12 }?所以到現(xiàn)在你發(fā)現(xiàn)這個算法錯誤的地方嗎？沒錯上面只是處理的對于每個旋轉(zhuǎn)中心最大的旋轉(zhuǎn)段，但是這不一定是最優(yōu)的（然而數(shù)據(jù)中好像都是最優(yōu)的……），提供一組hack數(shù)據(jù)：
15
14 2 8 9 10 11 1 15 6 5 4 3 13 7 12
正確答案是7，而以上算法出的是6。錯誤就在于這里最大的旋轉(zhuǎn)區(qū)間并不是最優(yōu)的。
為了解決這個問題，就需要將最大區(qū)間不斷收縮尋找最優(yōu)解。
但是這樣就又成$n^2$的了，怎么辦呢？
其實可以發(fā)現(xiàn)一步一步收縮的話有很多步數(shù)是沒有意義的，我們可以考慮對每個旋轉(zhuǎn)中心開一個vector存a[i]+i=mid的點的位置，按照離旋轉(zhuǎn)中心的距離排序，這樣收縮的時候只需枚舉vector，以上算法因為要排序所以復雜度為O（N log N）。
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<cmath> 5 #include<ctime> 6 #define MAXN 500010 7 #define LL long long 8 #define ma(x,y) memset(x,y,sizeof(x)) 9 using namespace std; 10 int n,a[MAXN]; 11 int sum[MAXN*2],l[MAXN*2],r[MAXN*2]; 12 int pre[MAXN]; 13 inline int read(); 14 signed main() 15 { 16 // freopen("in.txt","r",stdin); 17 // freopen("tem","r",stdin); 18 // freopen("1.out","w",stdout); 19 20 double sst=clock(); 21 n=read(); 22 for(int i=1;i<=n;i++)a[i]=read(); 23 /* if(n<=500) 24 { 25 int ans=0,res=0; 26 for(int i=1;i<=n;i++) 27 for(int j=i;j<=n;j++) 28 { 29 for(int k=0;i+k<=j-k;k++) 30 { 31 if(a[i+k]==j-k)res++; 32 if(a[j-k]==i+k)res++; 33 if((i+k==j-k)&&a[j-k]==i+k)res--; 34 } 35 for(int k=1;k<i;k++) 36 if(a[k]==k)res++; 37 for(int k=j+1;k<=n;k++) 38 if(a[k]==k)res++; 39 ans=max(ans,res);res=0; 40 } 41 printf("%d\n",ans); 42 return 0; 43 } 44 if(n<=5000) 45 { 46 int ans=0,res=0; 47 for(int i=1;i<=n;i++) 48 { 49 res=0; 50 double mid=1.0*(i+a[i])/2; 51 int st=min(a[i],i),en=max(a[i],i); 52 for(int j=st;j<=en;j++) 53 if(1.0*(double)(j+a[j])/2==mid)res++; 54 for(int j=1;j<st;j++) 55 if(j==a[j])res++; 56 for(int j=en+1;j<=n;j++) 57 if(j==a[j])res++; 58 ans=max(ans,res); 59 } 60 printf("%d\n",ans); 61 return 0; 62 } 63 else*/ 64 { 65 for(int i=1;i<=n;i++) 66 { 67 pre[i]=pre[i-1]; 68 if(a[i]==i)pre[i]++; 69 } 70 ma(l,0x7f);ma(r,0); 71 for(int i=1;i<=n;i++) 72 { 73 sum[i+a[i]]++; 74 l[i+a[i]]=min(l[i+a[i]],i); 75 r[i+a[i]]=max(r[i+a[i]],i); 76 } 77 for(int i=1;i<=n*2;i++) 78 { 79 int tl=l[i],tr=r[i]; 80 l[i]=min(l[i],i-tr); 81 r[i]=max(r[i],i-tl); 82 } 83 int ans=0; 84 for(int i=1;i<=n*2;i++) 85 if(sum[i]) 86 { 87 ans=max(ans,sum[i]+pre[l[i]-1]+pre[n]-pre[r[i]]); 88 /* for(int j=1;j&&l[i]<r[i];j++) 89 { 90 double st=clock(); 91 if(l[i]+a[l[i]]==i)sum[i]--; 92 if(r[i]+a[r[i]]==i)sum[i]--; 93 l[i]++,r[i]--; 94 ans=max(ans,sum[i]+pre[l[i]-1]+pre[n]-pre[r[i]]); 95 double en=clock(); 96 if((en-st)/1000>5)break; 97 if((en-sst)/1000>550)break; 98 }*/ 99 } 100 printf("%d\n",ans); 101 return 0; 102 } 103 } 104 inline int read() 105 { 106 int s=0,f=1;char a=getchar(); 107 while(a<'0'||a>'9'){if(a=='-')f=-1;a=getchar();} 108 while(a>='0'&&a<='9'){s=s*10+a-'0';a=getchar();} 109 return s*f; 110 } 所以我并沒有正解的代碼?
轉(zhuǎn)載于:https://www.cnblogs.com/Al-Ca/p/11318849.html
總結(jié)
