description

analysis

• 可以先用前缀和把原串不调整的方案数先求出来

• 对于一种翻转，肯定是把\([i..a[i]]\)或\([a[i]..i]\)这段区间翻转

• 也可以看做是以\({i+a[i]}\over 2\)这个点为翻转中心来翻转区间

• 于是把所有\(n\)个翻转中心搞出来，用\(vector\)存下翻转长度

• 对于每个翻转中心点，把翻转长度排一下序，从小到大做

• 由于当前长度翻转只会影响一个点从不合法点变成合法点，所以每次方案递增

• 左右端点\([l,r]\)，每次\(l\)变小\(r\)变大，方案数递增，然后加上该区间以外的方案来更新答案

• 可以说是比较巧妙的思路了

code

#pragma GCC optimize("O3")
#pragma G++ optimize("O3")
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#define MAXN 100005
#define INF 1000000007 
#define ll long long
#define reg register ll
#define fo(i,a,b) for (reg i=a;i<=b;++i)
#define fd(i,a,b) for (reg i=a;i>=b;--i)

using namespace std;

ll a[MAXN],sum[MAXN],pos[MAXN];
vector<ll>v[MAXN<<1];
ll n,ans;

inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while (ch<'0' || '9'<ch){if (ch=='-')f=-1;ch=getchar();}
    while ('0'<=ch && ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
inline ll get(ll x,ll y){return sum[y]-sum[x-1];}
int main()
{
    freopen("rotate.in","r",stdin);
    freopen("rotate.out","w",stdout);
    n=read();
    fo(i,1,n)pos[a[i]=read()]=i,sum[i]=sum[i-1]+(a[i]==i);
    fo(i,1,n)v[i+pos[i]].push_back(abs(i-pos[i])+1);
    ans=sum[n];
    fo(i,1,n<<1)
    {
        if (v[i].size()==0)continue;
        ll mid=i/2,cnt=0;
        sort(v[i].begin(),v[i].end());
        fo(j,0,v[i].size()-1)
        {
            ll len=v[i][j],l,r;
            if (i%2==0)l=mid-len/2,r=mid+len/2;
            else l=mid-len/2+1,r=mid+len/2;
            ++cnt;
            ans=max(ans,get(1,l-1)+cnt+get(r+1,n));
        }
    }
    printf("%lld\n",ans);
    return 0;
}

【JZOJ6288】旋转子段

原文：https://www.cnblogs.com/horizonwd/p/11329642.html