A. 旋转子段

很容易想到$n^2$的做法，

枚举断点然后模拟拓展区间就好了。

最后$WA65$。

丑陋的代码：

#include
#include
#include<string>
#include
#define Maxn 100050
#define Reg register
#define INF 0x7ffffff
#define max(x,y) ((x)>(y)?(x):(y))
using namespace std;
int n,sum,maxx,num[Maxn];
int main()
{
    scanf("%d",&n);
    for(Reg int i=1;i<=n;++i)
    {
        scanf("%d",&num[i]);
        if(num[i]==i) ++sum;
    }
    if(n<=10000)
    {
        maxx=sum;
        for(Reg int i=1;i<=n;++i)
        {
            int l=i,r=i,p=sum,ans=0;
            while(l>1&&r<n)
            {
                --l,++r;
                if(num[l]==l) --p;
                if(num[r]==r) --p;
                if(num[l]==r) ++ans;
                if(num[r]==l) ++ans;
                maxx=max(maxx,ans+p);
            }
        }
        for(Reg int i=1;ii)
        {
            int l=i,r=i+1,p=sum,ans=0;
            if(num[l]==l) --p;
            if(num[r]==r) --p;
            if(num[l]==r) ++ans;
            if(num[r]==l) ++ans;
            while(l>1&&r<n)
            {
                --l,++r;
                if(num[l]==l) --p;
                if(num[r]==r) --p;
                if(num[l]==r) ++ans;
                if(num[r]==l) ++ans;
                maxx=max(maxx,ans+p);
            }
        }
    }
    else
    {
        int st=clock();
        maxx=sum;
        for(Reg int i=1;i<=n;++i)
        {
            int l=i,r=i,p=sum,ans=0;
            while(l>1&&r<n)
            {
                --l,++r;
                if(num[l]==l) --p;
                if(num[r]==r) --p;
                if(num[l]==r) ++ans;
                if(num[r]==l) ++ans;
                maxx=max(maxx,ans+p);
                if(clock()-st>=900000)
                {
                    printf("%d",maxx);
                    return 0;
                }
            }
        }
        for(Reg int i=1;ii)
        {
            int l=i,r=i+1,p=sum,ans=0;
            if(num[l]==l) --p;
            if(num[r]==r) --p;
            if(num[l]==r) ++ans;
            if(num[r]==l) ++ans;
            while(l>1&&r<n)
            {
                --l,++r;
                if(num[l]==l) --p;
                if(num[r]==r) --p;
                if(num[l]==r) ++ans;
                if(num[r]==l) ++ans;
                maxx=max(maxx,ans+p);
                if(clock()-st>=900000)
                {
                    printf("%d",maxx);
                    return 0;
                }
            }
        }
    }
    printf("%d",maxx);
    return 0;
}

正解：

找到每个点的旋转轴，把它们分类存放，可以存到一个$vector$中。

然后也是枚举中点，依然拓展区间。

丑陋的代码：

#include
#include
#include
#include<string>
#include
#include
#define Maxn 1000050
#define Reg register
#define INF 0x7ffffff
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
using namespace std;
int n,ans,sum[Maxn],num[Maxn];
struct Node {int l,r,mid,k;} Q[Maxn];
vector > vac(Maxn),vbc(Maxn);
bool comp(Node *a,Node *b) {return a->l>b->l;}
int main()
{
    scanf("%d",&n);
    for(Reg int i=1;i<=n;++i)
    {
        scanf("%d",&num[i]);
        sum[i]=sum[i-1];
        if(num[i]==i) ++sum[i];
        Q[i].l=min(i,num[i]);
        Q[i].r=max(i,num[i]);
        if((i+num[i])&1)
        {
            Q[i].k=2,Q[i].mid=(Q[i].l+Q[i].r)>>1;
            vbc[Q[i].mid].push_back(&Q[i]);
        }
        else
        {
            Q[i].k=1,Q[i].mid=(Q[i].l+Q[i].r)>>1;
            vac[Q[i].mid].push_back(&Q[i]);
        }
    }
    for(Reg int i=1;i<=n;++i)
    {
        sort(vac[i].begin(),vac[i].end(),comp);
        sort(vbc[i].begin(),vbc[i].end(),comp);
    }
    for(Reg int i=1,len,su;i<=n;++i)
    {
        len=vac[i].size(),su=0;
        for(Reg int j=0,l,r;jj)
        {
            l=vac[i][j]->l,r=vac[i][j]->r;
            ++su;
            ans=max(ans,(su+sum[l-1]+sum[n]-sum[r]));
        }
    }
    for(Reg int i=1,len,su;i<=n;++i)
    {
        len=vbc[i].size(),su=0;
        for(Reg int j=0,l,r;jj)
        {
            l=vbc[i][j]->l,r=vbc[i][j]->r;
            ++su;
            ans=max(ans,(su+sum[l-1]+sum[n]-sum[r]));
        }
    }
    printf("%d",ans);
    return 0;
}

B. 走格子

又是一个模拟。

伪正解：

$BFS$，每次有$8$种移动方式。

如果上下左右有墙，那么它可以像移动到四面第一个墙的位置。

但是它错了。。。但是可以水到$85$分。

这个传送门是有时间差的。

就是说可以先放一个传送门，走到墙边再放一个传送门，然后传送。

会少考虑一种情况。

正解:

有两种移动方式。

第一种是向上下左右移动一个格子。

另一种是使用传送门，这时可以找到最近的一面墙，它可以从最近的一面墙移动到四个方向上的墙旁边。

然后建边跑最短路。

听说这跟那个叫华容道的题差不多，但我是水过去的。。

丑陋的代码：

#include
#include
#include<string>
#include
#include
#define int long long
#define Maxn 550
#define Reg register
#define INF 0x7ffffff
#define get(x,y) (((x)-1)*m+(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
using namespace std;
bool vis[Maxn*Maxn];
int n,m,sx,sy,ex,ey,tot,ans=INF,fir[Maxn*Maxn],num[Maxn][Maxn],dis[Maxn*Maxn];
string s;
struct Tu {int st,ed,next,val;} lian[Maxn*Maxn*5];
void add(int x,int y,int z)
{
    if(x==y||!x||!y) return;
    lian[++tot].st=x;
    lian[tot].ed=y;
    lian[tot].val=z;
    lian[tot].next=fir[x];
    fir[x]=tot;
    return;
}
void bfs()
{
    for(Reg int i=1;i<=n;++i)
    {
        for(Reg int j=1;j<=m;++j)
        {
            if(num[i][j]) continue;
            int Lix[4]={0},Liy[4]={0},Dis[4]={INF,INF,INF,INF};
            for(Reg int k=i-1;k>=1;--k)
                if(num[k][j]) {Lix[0]=k,Liy[0]=j,Dis[0]=i-k; break;}
            for(Reg int k=i+1;k<=n;++k)
                if(num[k][j]) {Lix[1]=k,Liy[1]=j,Dis[1]=k-i; break;}
            for(Reg int k=j-1;k>=1;--k)
                if(num[i][k]) {Lix[2]=i,Liy[2]=k,Dis[2]=j-k; break;}
            for(Reg int k=j+1;k<=m;++k)
                if(num[i][k]) {Lix[3]=i,Liy[3]=k,Dis[3]=k-j; break;}
            int Min=min(Dis[0],min(Dis[1],min(Dis[2],Dis[3])));
            for(Reg int x=0;x<4;++x)
            {
                if(Dis[x]!=Min) continue;
                for(Reg int y=0;y<4;++y)
                {
                    if(y==0) add(get(i,j),get(Lix[y]+1,Liy[y]),Min);
                    else if(y==1) add(get(i,j),get(Lix[y]-1,Liy[y]),Min);
                    else if(y==2) add(get(i,j),get(Lix[y],Liy[y]+1),Min);
                    else if(y==3) add(get(i,j),get(Lix[y],Liy[y]-1),Min);
                }
            }
            if(!num[i+1][j]) add(get(i,j),get(i+1,j),1);
            if(!num[i-1][j]) add(get(i,j),get(i-1,j),1);
            if(!num[i][j+1]) add(get(i,j),get(i,j+1),1);
            if(!num[i][j-1]) add(get(i,j),get(i,j-1),1);
        }
    }
    return;
}
void spfa(int x)
{
    queue<int> q;
    memset(dis,0x7f,sizeof(dis));
    dis[x]=0,vis[x]=1;
    q.push(x);
    while(!q.empty())
    {
        int x=q.front(); q.pop(); vis[x]=0;
        for(Reg int i=fir[x];i;i=lian[i].next)
        {
            if(dis[lian[i].ed]>dis[x]+lian[i].val)
            {
                dis[lian[i].ed]=dis[x]+lian[i].val;
                if(!vis[lian[i].ed])
                {
                    q.push(lian[i].ed);
                    vis[lian[i].ed]=1;
                }
            }
        }
    }
    return;
}
signed main()
{
    scanf("%lld%lld",&n,&m);
    for(Reg int i=1;i<=n;++i)
    {
        cin>>s;
        for(Reg int j=0;jj)
        {
            if(s[j]=='#') num[i][j+1]=1;
            else if(s[j]=='.') num[i][j+1]=0;
            else if(s[j]=='C') num[i][j+1]=0,sx=i,sy=j+1;
            else num[i][j+1]=0,ex=i,ey=j+1;
        }
    }
    bfs(); spfa(get(sx,sy));
    if(dis[get(ex,ey)]!=INF) printf("%lld",dis[get(ex,ey)]);
    else printf("no");
    return 0;
}

C. 柱状图

因为没看懂正解

首先，根据××定理，当屋顶位置确定时，屋顶高度为××中位数时代价最小。

当屋顶高度为$H$，位置为$x$时，代价$W=\sum \limits_{i=1}^{n} h[i]-(H-|i-j|)$，

记$d=|i-j|$。

那么$W=\sum \limits_{i=1}^{n} h[i]+d-H$，

那么$h[i]+d$是确定的，当$H$为$h[i]+d$的中位数(中间的那个数)时代价最小。

当$H$为中位数时：

如果$H$变大，那么左侧代价会$+1$，右侧代价会$-1$，

而左侧的元素还多，所以总代价会增大。

如果$H$变小，则同理。

模拟退火是个好东西，实测时间$650ms$。

链接$skyh$博客 。

丑陋的代码：

#include
#include
#include
#include<string>
#include
#include
#include
#define Maxn 1000050
#define Reg register
#define INF 0x7ffffffffffffff
#define int long long
#define min_(x,y) ((x)<(y)?(x):(y))
#define max_(x,y) ((x)>(y)?(x):(y))
#define abs_(x) ((x)<0?(-1*(x)):(x))
using namespace std;
int n,ans,anx=0,mxx,num[Maxn],f[Maxn],lss[Maxn];
const double delta=0.9011;
double t;
int clac(int x)
{
    if(f[x]!=-1) return f[x];
    for(Reg int i=1;i<=n;++i)
        lss[i]=num[i]+abs_(i-x);
    int mid=(1+n)>>1;
    nth_element(lss+1,lss+mid,lss+n+1);
    int h=lss[mid]; f[x]=0;
    for(Reg int i=1;i<=n;++i)
        f[x]+=abs_(num[i]-(h-abs_(i-x)));
    return f[x];
}
void get()
{
    int x=rand()%(n-1)+1,an=INF; t=0.01;
    while(t>1e-14)
    {
        int X=x+(double)((rand()<<1)-RAND_MAX)*t;
        X=min_(n,X),X=max_(1,X);
        int now=clac(X);
        int Delta=now-an;
        if(Delta<0||exp(-Delta/t)*RAND_MAX>rand()) an=now,x=X;
        ans=min(ans,now);
        t*=delta;
    }
    return;
}
signed main()
{
    srand(time(0));
    scanf("%lld",&n);
    for(Reg int i=1;i<=n;++i)
    {
        scanf("%lld",&num[i]);
        mxx=max(mxx,num[i]);
        f[i]=-1;
    }
    ans=INF; get();
    printf("%lld",ans);
    return 0;
}

总结：

感觉还不错，$T1$的$n^2$没花多少时间。

在前$30$分钟打完$T1$的$n^2$，最后又加了一个$clock()$，拿到$65$分。

往下看$T2$，数据范围这么小。

$n^3$级别都能过，然后就打了一个$BFS$，水到$85$分。

$T3$一开始没思路，打了一个$n^3$大暴力，

当时想没什么非常新奇的思路，要么它具有单调性，要么是一种单峰或单谷。

然后就开始打表，突然发现它的那个代价随高度的变化是单谷函数。。

之前外校的郭老师说过一次三分。

然后我考场上三分还是调了很长时间。

最后半个小时发现暴力打错了。

它的屋顶的变化量可以为负数。

然后测试点分治，三分不知道为啥没拿多少分。

最后$65+85+40=190$。

没什么水平。。。