2018西电网安比赛 ppc解题报告


网站搭好没几天被叫来投稿(大雾)

(还有 划线字体莫名不能显示 你们就吧我的括号当做划线字体吧。。。)

这次西电比赛感觉很刺激 打了三道ppc 名次就靠前  (可能是西电的师傅们把其他题都搞得太难了  于是当上了渔翁?) 

进入正题

 

1. BinarySearch Tree

(有一点二叉树知识的都知道) 中序遍历就是一个排序 

c++的话sort一遍就过了  至于其他语言没有排序函数的话就(手写快排也不错)

但是纯碎的模拟建树的话可能会被卡成一条链 复杂度就是O(n^2) 超时了 (平衡树转几圈的话还是能行的)

 

2.BrickBreaker

如果参加过今年的noip的人那么就很得利了(比如我) 

noip2013 积木大赛

noip2018 铺设道路

想想贪心 一个切掉一个山峰所需要的次数就是他的高度  

所以我们从左往右 走一遍爬山 所走的上山的路的长度就是我们需要切的次数  

 

3.维修队列

选自noi2005 维护数列 (连图都是扣的)

但是数据缩小 模拟一下就能过

插入:把post后面的数往后移动tot 空出来的tot用于插入新数

删除:把post+tot~最后 的数往前移动tot 意思是直接覆盖了要删除的tot个数

修改:直接赋值修改。。

反转:利用对称性转换 要是实在没法想通就按顺序放进另一个数组 然后逆序覆盖回来

求和:一个一个加。。

最大子段:dp[i]=max{ dp[i-1]+a[i],a[i] } 然后从dp数组中选取最大值

 

4.MaxMatrixElement

考试的时候就被这题卡住了 (求一个最大子矩阵 我还会)

后来某(chen大佬给我解释了一番 才恍然大悟

首先得会求一个最大子矩阵的方法

int work(int ln,int rn,int lm,int rm)
{
    int maxn=0;
    for(int i=ln;i<=rn;i++)
    {
        memset(c,0,sizeof(c));
        for(int j=i;j<=rn;j++)
        {
            for(intk=lm;k<=rm;k++)
            {
                c[k]+=a[j][k];
            }
           maxn=max(maxn,find(c,lm,rm));
        }
    }
    return maxn;
}

该函数用于求 ln~rn lm~rm的一个矩阵的最大子矩阵

然后就是(SAO事件)  

我们知道两个最大子矩阵的组合图 一定是可以分成两个较小的矩阵(本来就是分开的就也是俩矩阵)

所以我们任选一个点 将原始矩阵分成4矩阵

(如果选到最边上的点 其中有矩阵是空的 也无所谓 他的最大子矩阵就是 0 

然后分别求这四个子矩阵的 最大子矩阵    选择俩最大的求和 就是本次选点求到的两最大子矩阵之和

枚举每个点 不断更新最大值 

枚举点复杂度 O(n^2)  计算work函数(n^2)    一共是 O(n^4)   n最大是100   所以复杂度是O(能过)

贴份c++代码 (我也没有当时做题的网站了 不保证代码的正确性) 代码挂了可以找我一起讨论

#include<bits/stdc++.h>
#define inf 0x3fffffff
using namespace std;
int a[105][105],c[105],n,m;
int find(int *c,int l,int r)
{
    int sum=0,maxx=0;
    for(int i=l;i<=r;i++)
    {
        if(sum>0) sum+=c[i];
        else sum=c[i];
        if(sum>maxx) maxx=sum;
    }
    return maxx;
}
int work(int ln,int rn,int lm,int rm)
{
    int maxn=0;
    for(int i=ln;i<=rn;i++)
    {
        memset(c,0,sizeof(c));
        for(int j=i;j<=rn;j++)
        {
            for(intk=lm;k<=rm;k++)
            {
                c[k]+=a[j][k];
            }
           maxn=max(maxn,find(c,lm,rm));
        }
    }
    return maxn;
}
int main()
{
    cin>>n>>m; intans=-inf,ansi,ansj;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)cin>>a[i][j];
    for(int i=0;i<=n;i++)
    for(int j=0;j<=m;j++)
    {
        int maxn[2]={-inf,-inf},k;
        /*
            (1~i 1~j) (i+1~n 1~j)(1~i j+1~m) (i+1~n j+1~m)
        */
//      printf("%d%d:\n",i,j);
        if(1<=i&&i<=j)
        {
            k=work(1,i,1,j);
            if(k>maxn[0])maxn[1]=maxn[0],maxn[0]=k;
            elseif(k>maxn[1])  maxn[1]=k;
//          printf("    %d %d %d %d : %d\n",1,i,1,j,k);
        }
       if(i+1<=n&&1<=j)
        {
            k=work(i+1,n,1,j);
            if(k>maxn[0])maxn[1]=maxn[0],maxn[0]=k;
            elseif(k>maxn[1])  maxn[1]=k;
//          printf("    %d %d %d %d : %d\n",i+1,n,1,j,k);
        }
       if(1<=i&&j+1<=m)
        {
            k=work(1,i,j+1,m);
            if(k>maxn[0])maxn[1]=maxn[0],maxn[0]=k;
            elseif(k>maxn[1])  maxn[1]=k;
//          printf("    %d %d %d %d : %d\n",1,i,j+1,m,k);
        }
       if(i+1<=n&&j+1<=m)
        {
            k=work(i+1,n,j+1,m);
            if(k>maxn[0])maxn[1]=maxn[0],maxn[0]=k;
            elseif(k>maxn[1])  maxn[1]=k;
//          printf("    %d %d %d %d : %d\n",i+1,n,j+1,m,k);
        }
        if(ans<maxn[0]+maxn[1])
        {
            ans=maxn[0]+maxn[1];
            ansi=i,ansj=j;
        }
       ans=max(ans,maxn[0]+maxn[1]);
    }
    cout<<ans<<endl;
//  cout<<ansi<<""<<ansj<<endl;
    return 0;
}
 
/*
 
Input:
3 3
-1 -1 -2
2 0 1
2 0 -3
 
Output:
5
 
*/

 

5.GrassJelly

(最讨厌暴力打表的题目 )

留坑待补

(可能一辈子也不会补)

  

报告有什么不妥当或者错误的地方 还请dalao们指出修改

最新回复 (0)
返回
发新帖