魔法少女优化修改

2024-01-09 10:21:29

题目描述:

参照上一篇《魔法少女小Scarlet#洛谷》博客:https://blog.csdn.net/KLSZM/article/details/135405861?spm=1001.2014.3001.5501
这里对于超时的解决方法进行记录


原因分析描述

之前的主要思路就是设置如下的函数:

def work(key,flag,x_value,y_value,size):
    global mapp
    if flag==0:
        key=np.rot90(key,3)
        pass
    else:
        key=np.rot90(key)
        pass
    xx=x_value-size
    yy=y_value-size
    for item in range(2*size+1):
        for jtem in range(2*size+1):
            mapp[item+xx][jtem+yy]=key[item][jtem]

将所记录好的key数组用numpy进行旋转,再通过遍历的方法将原数组的位置进行覆盖。而key数组的创建方式如下:

for p in range(2 * r + 1):
            for q in range(2 * r + 1):
                data[p][q] = mapp[x0 + p][y0 + q]
                pass
            pass

但是这样创建key数组以及,在函数中再遍历进行覆盖就会占用十分多的时间。所以应该思考,如何避免这些循环的套用甚至使用。


解决方案:

使用numpy旋转、二维数组切片、数组的替换

之前做过的题目中,就是博客中一直没有改正的题目中,就是因为循环套用过多而超时。后来考虑了用直接定位来代替搜索的方式,大大减少了时间,然后过了。这里也是一样,但是对于二维数组进行直接定位子数组,并且再进行替换是之前没有接触过的。这里要用到numpy来操作
1、先将之前设置的二维数组惊醒np的转化(其实不转换应该也可以,我没试过):

mapp=np.array(mapp)

2、二维数组切片:

mapp[xx:xx+2*size+1,yy:yy+2*size+1]

这个语句代表了二维数组中xx—xx+2size+1行的区间,以及xx—xx+2size+1列的区间。将这个矩阵旋转后再用key数组进行承接。

key=np.rot90(mapp[xx:xx+2*size+1,yy:yy+2*size+1],3)

rot90()这个函数是numpy里的,在之前的题单中已经用过了,默认的是逆时针方向,所以想要得到顺时针的结果,则要转三次。
3、数组的替换:

mapp[xx:xx + 2 * size + 1, yy:yy + 2 * size + 1]=key

直接用等号大胆进行替换即可

AC代码如下:

import numpy as np


def work(flag,x_value,y_value,size):
    global mapp
    xx = x_value - size
    yy = y_value - size
    if flag==0:
        key=np.rot90(mapp[xx:xx+2*size+1,yy:yy+2*size+1],3)
    else:
        key=np.rot90(mapp[xx:xx+2*size+1,yy:yy+2*size+1])
        pass
    mapp[xx:xx + 2 * size + 1, yy:yy + 2 * size + 1]=key
    # for item in range(2*size+1):
    #     for jtem in range(2*size+1):
    #         mapp[item+xx][jtem+yy]=key[item][jtem]


if __name__=="__main__":
    n, m = map(int, input().split())
    mapp = [[jtem for jtem in range(item * n + 1, item * n + n + 1)] for item in range(n + 1)]
    mapp=np.array(mapp)
    for item in range(m):
        x, y, r, z = map(int, input().split())
        x-=1
        y-=1
        data = [[0] * (2 * r + 1) for _ in range(2 * r + 1)]
        x0 = x - r
        y0 = y - r
        work(z,x,y,r)
        pass
        # print(mapp)
    for item in range(n):
        for jtem in range(n):
            if jtem==n-1:
                print(mapp[item][jtem])
            else:
                print(mapp[item][jtem],end=' ')
            pass

文章来源:https://blog.csdn.net/KLSZM/article/details/135414864
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。