题目描述
$ZYL$有$N$张牌编号分别为$1,2,...,N$。他把这$N$张牌打乱排成一排，然后他要做一次旋转使得旋转后固定点尽可能多。如果第$i$个位置的牌的编号为$i$，我们就称之为固定点。旋转可以被认为是将其中的一个子段旋转$180$度，这意味着子段的第一张牌和最后一张牌交换位置，以及第二张牌和倒数第二张牌交换位置，等等。写一个程序，找到旋转子段（子段长度可以为$1$）。
输入格式
第一行包含一个整数$N$。
第二行有$N$个数，第$i$个数表示旋转之前第$i$个位置的牌的编号。
输出格式
找到固定点最多的旋转所选的子段，输出旋转之后固定点的个数。
样例
样例输入1：
4
3 2 1 4
样例输出1：
4
样例输入2：
2
1 2
样例输出2：
2
数据范围与提示
样例解释：
在样例$1$中，只需要旋转的子段$[3,2,1]$，将排列变成$1\ 2\ 3\ 4$，旋转后所有的牌都为固定点。答案为$4$。
在样例$2$中，所有的牌已经在固定点，旋转子段$[1]$或者子段$[2]$，答案为$2$。
数据范围：
$30\%$的数据满足：$N\leqslant 500$；
$60\%$的数据满足：$N\leqslant 5,000$；
$100\%$的数据满足：$1\leqslant N\leqslant 500,000$。
题解
$30\%$算法：
裸的暴力，直接搞就行了。
可以用$reverse$卡常，但是没什么用。
注意可以不旋转。
时间复杂度：$\Theta(n^3)$。
期望得分：$30$分。
实际得分：$35$分。
$60\%$算法：
枚举旋转中心和旋转半径，思想类似莫队。
时间复杂度：$\Theta(n^2)$。
期望得分：$60$分。
实际得分：$60$分。
$100\%$算法：
先来利用反证法来证明一个问题：如果最优翻转区间是$[l,r]$，那么如果$a[l]\neq r\&\&a[r]\neq l$，则翻转这个区间$a[l]$和$a[r]$一定都不能成为不动点，对答案一定不能做出贡献，选择区间$[l+1,r-1]$一定不劣。
所以，我们要找的区间一定满足$a[l]=r||a[r]=l$，也就是说，翻转之后一定有一个点成为不动点。
根据上面的出的结论，我们还可以知道，答案一定在所有的$[\min(a[i],i),\max(a[i],i)]$中产生。
显然仅仅是这样我们还是会超时，那么考虑如何进行优化。
依次枚举$n$必不可少，我们考虑从查询中入手。
我们还可以知道，一个点在翻转之后成为不动点，在翻转之前一定满足$a[i]+i=a[j]+j$（式中$i,j$分别表示旋转之前的位置和旋转之后的位置）。
可以使用$vector$优化空间复杂度。
时间复杂度：$\Theta(n\log n)$。
期望得分：$100$分。
实际得分：$100$分。
代码时刻
$30\%$算法：
#include<bits/stdc++.h>
using namespace std;
int a[500001];
int ans;
int main()
{
int n;
scanf("%d",&n);
for(register int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]==i)ans++;
}
for(register int i=1;i<n;i++)
for(register int j=i+1;j<=n;j++)
{
register int sum=0;
reverse(a+i,a+j+1);
for(register int k=1;k<=n;k++)
if(a[k]==k)sum++;
reverse(a+i,a+j+1);
ans=max(ans,sum);
}
printf("%d",ans);
return 0;
}
$60\%$算法：
#include<bits/stdc++.h>
using namespace std;
int n,ans,now,res,a[500001];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]==i)res++;
}
ans=res;
for(int i=1;i<=n;i++)
{
now=res;
for(int j=1;j<=n;j++)
{
int l=i-j,r=i+j;
if(l<=0||r>=n)break;
if(a[l]==r)now++;
if(a[r]==l)now++;
if(a[l]==l)now--;
if(a[r]==r)now--;
ans=max(ans,now);
}
now=res;
for(int j=1;j<=n;j++)
{
int l=i-j+1,r=i+j;
if(l<=0||r>=n)break;
if(a[l]==r)now++;
if(a[r]==l)now++;
if(a[l]==l)now--;
if(a[r]==r)now--;
ans=max(ans,now);
}
}
printf("%d\n",ans);
return 0;
}
$100\%$算法：
#include<bits/stdc++.h>
using namespace std;
int n;
int a[2000000],sum1[2000000],sum2[2000000];
int flag,ans;
vector<int> g[2000000];
bool cmp(int x,int y){return abs((x<<1)-flag)<abs((y<<1)-flag);}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
g[a[i]+i].push_back(i);
if(a[i]==i)sum1[i]=sum2[i]=1;
sum1[i]+=sum1[i-1];
}
for(int i=n;i;i--)sum2[i]+=sum2[i+1];
for(int i=2;i<=(n<<1);i++)
if(!g[i].empty())
{
flag=i;
sort(g[i].begin(),g[i].end(),cmp);
for(int j=0;j<g[i].size();j++)
{
int l=g[i][j];
int r=i-g[i][j];
if(l>r)swap(l,r);
ans=max(ans,sum1[l-1]+sum2[r+1]+j+1);
}
}
cout<<ans<<endl;
return 0;
}
rp++