(新版)SJTU-OJ-1008. LSZ的雪地脚印

2023-10-28 18:10
文章标签 新版 oj 1008 脚印 sjtu lsz 雪地

本文主要是介绍(新版)SJTU-OJ-1008. LSZ的雪地脚印,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

2006年冬的某一天上午下了一场大雪,TSYZ教学楼下的排球场上覆盖了一层雪。

下课了,很多人来到这里,留下了很多脚印。

排球场可以看作是由N×M的方格组成的一个矩形, 其中某些方格已经有脚印了,而剩下的则是完好的。

lsz想在上面写下自己的名字,也就是"lsz"三个字母,为了美观,要求这三个字母必须占据一个2:1(横向的,不能是1:2)的完好矩形,

也就是说,在这个2:1的矩形内不得有脚印。

现在给你场地的脚印情况,lsz想知道自己的名字最大可以占据多大面积。

输入格式

第一行为空格分隔的两个正整数,N和M,表示场地的大小。

下面有N行,每行M个字符,每个字符要么是-(减号),表示该方格完好,要么是X(大写的x),表示该方格有脚印。

输出格式

一个正整数,表示"lsz"最大可以占据多大面积。

样例输入

4 6
X--XXX
----X-
------
-X--X-

样例输出

8

数据范围

40%的数据满足N,M<123

100%的数据满足0<N,M<1234

题目吐槽

        首先,这年代有点久远了,不知道是老题目还是就蹭着那句歌词玩玩

        然后,TSYZ教学楼是什么啊,和交大有关系吗,我也不是很知道,希望有人能解答

        lsz应该是个人名吧,不认识也不需要介意这个

        突然想起来好像有听说(或者是见到emmm不记得了应该是听说吧)利用什么在雪地上写字表白的emmm就很神奇,不过emmm估计就写到这里吧,不能再BB了

        这家伙占地盘可还行,还要我帮忙算能占多少地盘,hhh

        上面是关于题面的吐槽,接着,下面是!

        这题太难了呜呜呜,刚刚去百度了一波,没有找到一样的题目,看来是新题

        这个有点厉害真的真的真的,一般的最容易想到的基本上肯定过不了,能过的都是nb

        在一位公开了代码的同学帮助下还是顺利完成了好耶!

        感谢一波(虽然可能也不认识)

题目解答

        老套路,毕竟是初学c++,最先想到的基本上都不对过不了,哪怕是对的往往也是卡在时间的节点上,不过嘛既然是学习那还是慢慢来,先看最容易想到的暴力枚举方法吧

        读数据就不用说了,没有什么特别的,定义一个字符串的矩阵,然后一个一个读取就可以了。然后判断什么的用字符串的比较就可以。

        这里强调一下比较的方法是

char ch;cin >> ch;
if (ch == 'X')    //正确
if (ch == "X")    //错误

         看来程序员都有一个共性就是几天前写的代码都忘记什么了2333

        刚刚看了一下记录,下面这段代码可以拿60分hhhh

#include <iostream>
using namespace std;int n,m;
char array[1240][1240];                          //养成好习惯,空间一次性开满
bool IfAvailable(int line, int colony, int scale);//这个函数判断已知左上角和规模是否可行
bool PositionFocus(int scale);                   //这个函数用来定位每一个左上角//其实后面两个函数是紧密关联的//第二个函数可以调用第一个函数
int main()
{cin >> n >> m;for (int i = 0; i < n; i++){for (int j = 0; j < m; j++){cin >> array[i][j];}                                        //读数据呗}                                            int ans;//这里还是要多说几句,因为m,n大小也不知道,所以最大的规模k能多少也不知道
//那么我们知道,情况一 m>= 2*k 且 n>=k
//             情况二 m>= k   且 n>= 2*k
//所以,最大的k = max(min(m, n / 2), min(n, m / 2))
//其实这里有两个思路一个是k从1开始往上爬
//另外一个是k从最大的开始递减hhh,后来发现递减的分数拿的比递增的分数高 nice虽然都没有过for (int k = max(min(m, n / 2), min(n, m / 2)); k >= 1; k--){if (PositionFocus(k) == true){ans = k;break;}}cout << ans * ans * 2;system("pause");return 0;
}//小结一下,主函数还是蛮简洁的个人觉得

         这个代码看着我都头大,还是费力爬上去写完了注释。

        似乎分开来看更合适,

        考虑到不同规模的情况下,左上角的横纵坐标的范围不同,所以用这个函数根据scale规模来确定位置

.

.....

.

.

.

        上图中:粉色的为定位点,黄色的是预备检测的区域。那么可以根据定位点以及规模确定整个区域啦,上图就是2*4规模的写字区域

        我们定义左上角的坐标为(1,1)那么当规模为2(即为2\times 4)时候的定位点的可行区域是绿色部分

.

.....

.

.

.

        所以说白了就是emmm下面这个函数用来扫描这个绿色的区域,让定位点依次经过上面绿色部分的每一个地方

        只要找到规模为k的任意一个可行的解决方法,函数结束,返回true 可以找到!

//下面这个PositionFocus用于定位,目的就是把所有可以的情况检测一遍
bool PositionFocus(int scale)
{for (int i = 0; i < n + 1 - scale; i++){for (int j = 0; j < m - scale * 2 + 1; j++){if (array[i][j]=='X')continue;else if (IfAvailable(i, j, scale)==true)return true;//找到一个就结束}}return false;
}

        每次确定一个定位点后需要检测这个区域是否可以放下所有的,只要有一个脚印,函数结束返回不可以

bool IfAvailable(int line,int colony,int scale)
{bool tempresult = true;for (int a = line; a <= line + scale - 1; a++){for (int b = colony; b <= colony + 2 * scale - 1; b++){if (array[a][b]=='X'){return false;}}}return tempresult;
}

        评测结果60分。显然不是我们需要的

        所以呢我们要改进方法啦,我们要用数学的方法来解决这种问题,改进时候参考了别人的代码中的思想,但是还是基于自己的代码修改的,修改的仅仅是IfAvailable这个函数,以及输入的部分。

        可以看到,之前的IfAvailable有两个嵌套循环,时间复杂度较大,所以改进如下

bool IfAvailable(int x,int y,int scale)
{if (array[x - 1][y - 1] + array[x + scale - 1][y + 2 * scale - 1] - array[x - 1][y + 2 * scale - 1] - array[x + scale - 1][y - 1] == 0)return true;elsereturn false;
}

        看上去这个代码很长,而且还出现了一个二维数组array,但是简洁明了,用一个数学表达式解决了判断的问题。

        原理是什么呢?

        我们不妨叫做堆叠法吧(我也不知道是不是这个名字)

        先从一维数组开始

        我们高中就学习过数列,知道根据数列的前n项和可以求出每一项a_n,公式如下:

        \begin{equation} a_n=\left\{ \begin{aligned} S_1 \quad \quad \quad n=1\\ S_n-S_{n-1} \quad n\geq 2\\ \end{aligned} \right . \end{equation}

        同理对于数组a_n也可以用类似的方法表示,构造一个前缀数组

        原数组:       

123456……n-1n
a_1a_2a_3a_4a_5a_6a_{n-1}a_n

         新数组:

123456……n-1n
a_1\sum_{i=1}^{2}a_i\sum_{i=1}^{3}a_i\sum_{i=1}^{4}a_i\sum_{i=1}^{5}a_i\sum_{i=1}^{6}a_i\sum_{i=1}^{n-1}a_i\sum_{i=1}^{n}a_i

        类似的,二维数组我们也可以构造前缀和:

        原数组: 

a_{11}a_{12}a_{13}a_{14}.....a_{1j}
a_{21}a_{22}

a_{23}

a_{31}a_{32}
a_{41}
.....a_{i-1,j-1}a_{i-1,j}
a_{i1}a_{i,j-1}

a_{i,j}

         新的数组: 

         

\sum_{j=1}^{1}\sum_{i=1}^{1}a_{ij}\sum_{j=1}^{2}\sum_{i=1}^{1}a_{ij}\sum_{j=1}^{3}\sum_{i=1}^{1}a_{ij}\sum_{j=1}^{4}\sum_{i=1}^{1}a_{ij}      ......      \sum_{j=1}^{n}\sum_{i=1}^{1}a_{ij}
\sum_{j=1}^{1}\sum_{i=1}^{2}a_{ij}\sum_{j=1}^{2}\sum_{i=1}^{2}a_{ij}\sum_{j=1}^{3}\sum_{i=1}^{2}a_{ij}

\sum_{j=1}^{1}\sum_{i=1}^{3}a_{ij}

\sum_{j=1}^{1}\sum_{i=1}^{4}a_{ij}

        .....

\sum_{j=1}^{m-1}\sum_{i=1}^{n-1}a_{ij}\sum_{j=1}^{m}\sum_{i=1}^{n-1}a_{ij}
\sum_{j=1}^{1}\sum_{i=1}^{n}a_{ij}\sum_{j=1}^{m-1}\sum_{i=1}^{n}a_{ij}

\sum_{j=1}^{m}\sum_{i=1}^{n}a_{ij}

        好家伙这个看上去确实很复杂,需要怎样才能构建这个新的数组呢

        首先,原数组的读取就不用多说了,两层for循环就可以搞定,读取数据。

        但是新数组的构建应该如何呢,暴力方法是对于每个坐标(m,n)计算\sum_{j=1}^{m}\sum_{i=1}^{n}a_{ij},确实如此,但是计算方法如果在使用嵌套循环太麻烦了。

        所以,有下面的公式:

\sum_{j=1}^{m}\sum_{i=1}^{n}a_{ij}=\sum_{j=1}^{m}\sum_{i=1}^{n-1}a_{ij}+\sum_{j=1}^{m-1}\sum_{i=1}^{n}a_{ij}-\sum_{j=1}^{m-1}\sum_{i=1}^{n-1}a_{ij}

        把公式翻译成代码就是:

array[m][n] = array[m][n - 1] + array[m - 1][n] - array[m - 1][n - 1];

         如果你觉得不好理解那可以画图验证一下下,减去的那一部分是重复的(黄色部分hhh)

         我们还是看这一表格吧,会好理解一些

a_{11}a_{12}a_{13}a_{14}.....a_{1j}
a_{21}a_{22}

a_{23}

a_{31}a_{32}
a_{41}
.....a_{i-1,j-1}a_{i-1,j}
a_{i1}a_{i,j-1}

a_{i,j}

        在比照一下下面这个东西

\sum_{j=1}^{1}\sum_{i=1}^{1}a_{ij}\sum_{j=1}^{2}\sum_{i=1}^{1}a_{ij}\sum_{j=1}^{3}\sum_{i=1}^{1}a_{ij}\sum_{j=1}^{4}\sum_{i=1}^{1}a_{ij}      ......      \sum_{j=1}^{n}\sum_{i=1}^{1}a_{ij}
\sum_{j=1}^{1}\sum_{i=1}^{2}a_{ij}\sum_{j=1}^{2}\sum_{i=1}^{2}a_{ij}\sum_{j=1}^{3}\sum_{i=1}^{2}a_{ij}

\sum_{j=1}^{1}\sum_{i=1}^{3}a_{ij}

\sum_{j=1}^{1}\sum_{i=1}^{4}a_{ij}

        .....

\sum_{j=1}^{m-1}\sum_{i=1}^{n-1}a_{ij}\sum_{j=1}^{m}\sum_{i=1}^{n-1}a_{ij}
\sum_{j=1}^{1}\sum_{i=1}^{n}a_{ij}\sum_{j=1}^{m-1}\sum_{i=1}^{n}a_{ij}

\sum_{j=1}^{m}\sum_{i=1}^{n}a_{ij}

        所以其实在读取数据的时候就可以完成数据的处理了,用那个公式就可以

        所以,简化算法流程的关键在于,用数学运算来检测X位置

        用一个新的数组(或者就在原数组的基础上面)

       c_{mn}=\sum_{j=1}^{m}\sum_{i=1}^{n}a_{ij}

        表示


        那么下面是代码部分啦!

        

        下面是数据读取的部分代码,X是不可以防止的地方,别的是可以的,所以只要为X就把对应的那个a_{mn}加一,(我这个编译器数组默认是全部为0),这也为后面的操作提供了便利

    cin >> n >> m;    //题目已定义的数据输入for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){char ch;cin >> ch;array[i][j] = array[i][j - 1] + array[i - 1][j] - array[i - 1][j - 1];//注意,这里先完成数据的预处理,再检查是不是Xif (ch == 'X'){ array[i][j]++;      //是X就再加一吧,不是就不用管,顺序关注一下即可}}}

        接下来,我改进了IfAvailable这个函数(这个函数是在已知预检测区域左上角的坐标以及规模的前提下,检测整个区域是否有X)

        那好说啦,检测这个区域有没有X,只需要用这个公式就可以。这个代码有点长

if (array[x-1][y-1]+array[x+scale-1][y+2*scale-1]-array[x-1][y+2*scale-1]-array[x+scale-1][y-1]==0)
// x,y表示左上定位点坐标
// scale表示检测区域的规模,为短边的大小

       换一种解释(可以理解的):

a_{11}a_{12}a_{13}.....a_{1j}
a_{21}a_{22}
a_{31}
a_{x-1,y-1}
.....a_{x,y}

a_{i-1,j-1}

a_{i-1,j}
a_{i1}a_{i,j-1}

a_{i,j}

     

\sum_{j=1}^{1}\sum_{i=1}^{1}a_{ij}\sum_{j=1}^{2}\sum_{i=1}^{1}a_{ij}\sum_{j=1}^{3}\sum_{i=1}^{1}a_{ij}\sum_{j=1}^{4}\sum_{i=1}^{1}a_{ij}      ......      \sum_{j=1}^{n}\sum_{i=1}^{1}a_{ij}\sum_{j=1}^{n}\sum_{i=1}^{1}a_{ij}
\sum_{j=1}^{1}\sum_{i=1}^{2}a_{ij}\sum_{j=1}^{2}\sum_{i=1}^{2}a_{ij}\sum_{j=1}^{3}\sum_{i=1}^{2}a_{ij}

\sum_{j=1}^{1}\sum_{i=1}^{3}a_{ij}

.........................................

     

       ......

      

\sum_{j=1}^{x-1}\sum_{i=1}^{y-1}a_{ij}

        .....

\sum_{j=1}^{x}\sum_{i=1}^{y}a_{ij}.......\sum_{j=1}^{m-1}\sum_{i=1}^{n-1}a_{ij}\sum_{j=1}^{m-1}\sum_{i=1}^{n}a_{ij}
\sum_{j=1}^{1}\sum_{i=1}^{n}a_{ij}......\sum_{j=1}^{m-1}\sum_{i=1}^{n}a_{ij}\sum_{j=1}^{m}\sum_{i=1}^{n-1}a_{ij}\sum_{j=1}^{m}\sum_{i=1}^{n}a_{ij}

         按照上图的解释,检测区域如图,监测区域的定位点为(m,n),a_{i,j}表示该区域X的个数,有为1,没有为0,

        \sum_{j=1}^{m}\sum_{i=1}^{n}a_{ij}表示从(m,n)(1,1)这个矩形的X的个数

         为了保证绿色区域没有任何X,则有下面的等式成立:

\sum_{j=1}^{m}\sum_{i=1}^{n}a_{ij}+\sum_{j=1}^{x-1}\sum_{i=1}^{y-1}a_{ij}= \sum_{j=1}^{m}\sum_{i=1}^{y-1}a_{ij}+\sum_{j=1}^{x-1}\sum_{i=1}^{n}a_{ij}

         公式翻译过来就是:整个(m,n)左上的区域+蓝色区域 =(粉色区域+蓝色区域)+(蓝色区域+白色区域)

         左右去掉一样的,就是绿色区域=0,就是说没有X。好机智的算法

        下面是IfAviarlable函数的改进版,

bool IfAvailable(int x,int y,int scale)
{if (array[x - 1][y - 1] + array[x + scale - 1][y + 2 * scale - 1] - array[x - 1][y + 2 * scale - 1] - array[x + scale - 1][y - 1] == 0)return true;elsereturn false;
}

         最后上以下完整的AC代码,毕竟前面已经解释很清楚啦,就没有单独加注释hhh偷个懒

#include <iostream>
using namespace std;int n,m;
int array[1240][1240];bool PositionFocus(int scale);
bool IfAvailable(int x, int y, int scale);int main()
{cin >> n >> m;for (int i = 1; i <= n; i++){for (int j = 1; j <= m; j++){char ch;cin >> ch;array[i][j] = array[i][j - 1] + array[i - 1][j] - array[i - 1][j - 1];if (ch == 'X'){ array[i][j]++;}}}int ans;for (int k = 1; k <= n; k++){if (PositionFocus(k) == false){ans = k-1;break;}}cout << ans * ans * 2;system("pause");return 0;
}bool PositionFocus(int scale)
{for (int i = 1; i <= n + 1 - scale; i++){for (int j = 1; j <= m - scale * 2 + 1; j++){if (IfAvailable(i, j, scale) == true)return true;//找到一个就结束}}return false;
}bool IfAvailable(int x,int y,int scale)
{if (array[x - 1][y - 1] + array[x + scale - 1][y + 2 * scale - 1] - array[x - 1][y + 2 * scale - 1] - array[x + scale - 1][y - 1] == 0)return true;elsereturn false;
}

这篇关于(新版)SJTU-OJ-1008. LSZ的雪地脚印的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/295010

相关文章

哈理工OJ 2179(深搜)

组合 Time Limit: 1000 MSMemory Limit: 32768 K Total Submit: 7(5 users)Total Accepted: 6(5 users)Rating: Special Judge: No Description 给出一个正整数N,从集合{1,2,3..N} 中找出所有大小为k的子集, 并按照字典序从小到大输出。 Input 第一行是一个整

每日OJ_牛客_求和(递归深搜)

目录 牛客_求和(递归深搜) 解析代码 牛客_求和(递归深搜) 求和_好未来笔试题_牛客网 解析代码         递归中每次累加一个新的数,如果累加和大于等于目标,结束递归。此时如果累加和正好等于目标,则打印组合。向上回退搜索其它组合。此题本身就是一个搜索的过程,找到所有的组合。 #include <iostream>#include <cmath>#in

DevExpress WinForms v24.1新版亮点:功能区、数据编辑器全新升级

DevExpress WinForms拥有180+组件和UI库,能为Windows Forms平台创建具有影响力的业务解决方案。DevExpress WinForms能完美构建流畅、美观且易于使用的应用程序,无论是Office风格的界面,还是分析处理大批量的业务数据,它都能轻松胜任! DevExpress WinForms控件2024年第一个重大版本——v24.1全新发布,此版本对功能区、状态栏

JD 1008:最短路径问题

OJ题目:click here~~ 题目分析:无向图,每条边有长度和花费,求点s到t的最短路径长度和花费。若有相同的最短路径长度,找出最少的花费的那条。 邻接表 + Dijstra + 优先队列 AC_CODE const int maxn = 1008 ;const int inf = 1<<30 ;vector<int> g[maxn] ;int len[maxn][maxn

翻译Houdini官方对UE4新版插件的介绍:Houdini Engine for Unreal - V2

原视频:Houdini For Unreal - YouTube 目录 介绍0. 总览1. 简介HoudiniEngine2. UE4的HoudiniEngine - 第二版为什么要做“第二版” ?What's new? - 核心What's new? - 输出(1)What's new? - 输出(2)What's new? - 输入What's new? - 参数What's new?

Wyn 商业智能V8.0 新版本来袭,解锁“智造”的无限可能

Wyn商业智能V8.0 版本全新发布,聚焦制造业数字化升级痛点,深度赋能制造业数字化转型升级之路,从无缝集成物联网海量数据,到构建可视化实时分析、监控与预警大屏,全面打通生产制造全生命周期的数据脉络,为您开启工业智能新视界,一键解锁数字化工厂无限可能! Wyn商业智能 V8.0 版本亮点功能一览 1、支持MQTT等采集协议,接入物联网设备数据 全新引入”物联网数据”类型,支持MQTT,Web

新版iOS内购(IAP)完整流程

新版iOS内购(IAP)完整流程 苹果内购是用来做什么的?能不能吃? iOS内购(以下简称IAP)是你可以实现一个应用内购买各种物品的功能,最常见的就是游戏中购买的道具,比如钻石。 新版的iOS内购从申请、审核以及代码的书写都充满了恶意,下面来介绍一下IAP的基本流程和我们遇到的问题以及一些解决办法。 1.创建应用和IAP项目 首先进入苹果的iTunesConnection(http

OJ-0905

题目 示例1: 输入:10 10 56 34 99 1 87 8 99 3 255 6 99 5 255 4 99 7 255 2 99 9 255 213 4输出:99 示例2: 输入:10 10 255 34 0 1 255 8 0 3 255 6 0 5 255 4 0 7 255 2 0 9 255 213 5输出:255 import java.util.

每日OJ_牛客_Emacs计算器(逆波兰表达式)

目录 牛客_Emacs计算器(逆波兰表达式) 解析代码 牛客_Emacs计算器(逆波兰表达式) Emacs计算器__牛客网 解析代码 逆波兰表达式(后缀表达式)求值,需要借助栈,思路: 循环输入,获取逆波兰表达式,然后进行以下补助,直到测试完所有的测试用例: 遇到数字字符串,将该数字字符串转化为数字然后入栈。遇到操作符时,从栈顶取两个数字,然后进行该运算符所对应运算

WordPress 手动还原到旧版本与新版

WordPress 手动还原到旧版本与新版 WordPress后台一般都可以直接一键升级,但是也存在一些情况导致无法自动升级,比如说权限不足,还有就是一些文件的权限不一样,当然我们可以设置0777权限,但是不够安全。简单说一下 wordpress 手动还原到旧版本 和 WordPress 手动更新到最新版的方法,其实,操作都是一样的,可以说是手动更新到任意版本。