2019-8-7 考试总结

水深无声 2021-11-01 09:50 150阅读 0赞

# A. 旋转子段 #

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

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

最后$WA65$。

丑陋的代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstring>
    #include<string>
    #include<cstdio>
    #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;i<n;++i)
            {
                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;i<n;++i)
            {
                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$中。

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

丑陋的代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<cstdio>
    #include<vector>
    #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<vector<Node*> > 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;j<len;++j)
            {
                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;j<len;++j)
            {
                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$分。

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

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

会少考虑一种情况。

正解:

有两种移动方式。

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

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

然后建边跑最短路。

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

丑陋的代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<iostream>
    #include<cstring>
    #include<string>
    #include<cstdio>
    #include<queue>
    #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;j<s.size();++j)
            {
                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$博客 [传送门][Link 1]。

丑陋的代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<algorithm>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<cstdlib>
    #include<cstdio>
    #include<cmath>
    #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$。

没什么水平。。。

转载于:https://www.cnblogs.com/Milk-Feng/p/11318865.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211101/c20a7285029442fbb6d7eaf3de045df3.png
[Link 1]: https://www.cnblogs.com/skyh/p/11318855.html