设y=y(x)是由方程cos(x+y)+y=1确定,求dy/dx?

Byteasar 组建了一支舰队!他们现在正在海洋上航行着。海洋可以抽象成一张n×m 的网格图,其中有些位置是“.”,表示这一格是海水,可以通过;有些位置是“#”,表示这一格是礁石,不可以通过;有些位置是“o”,表示这一格目前有一艘舰,且舰离开这一格之后,这一格将变为“.”。这些“o” 表示Byteasar 的舰队,他们每天可以往上下左右中的一个方向移动一格,但不能有任何一艘舰驶出地图。特别地,Byteasar 对阵形有所研究,所以他不希望在航行的过程中改变阵形,即任何时刻任何两艘舰的相对位置都不能发生变化。Byteasar 的舰队可以航行无限长的时间,每当一艘舰经过某个格子的时候,这个格子海底的矿藏都将被Byteasar 获得。请写一个程序,帮助Byteasar 计算他最多可以获得多少个格子海底的矿藏?

很妙……如果没有做过类似的题可能打死也不知道是道FFT题。

首先将最小的包含所有舰队的矩形拿出来,那么先不考虑能否到达,我们只需要将这个小矩形和大矩形匹配,就能知道我们舰队能够放在哪里。

于是想到暴力匹配,但是显然是过不了的。

想到这道题,但是那是一维匹配,而我们要二维匹配。

所以一个想法就是降维,简单点说,就是第一行字符+第二行字符+……

设大矩形为a[],小矩形(需要将大小填充等于大矩形)为b[]。

对于一个合法的匹配位置的左上角下标为p,则有对于所有的位置,都不能存在a[p+i]有礁石,b[i]有舰队这种情况。

接下来考虑,对于所有的左上角,我们并不是都能到达的,所以从小矩阵最开始的左上角搜索找到所有合法的左上角。

最后就是一个点其下标为p,它能到达当其存在一个左上角p-i合法,且b[i]=1,于是令所有合法左上角=1,则f[i]=sigma(a[i-j]*b[j])>0,直接就是一个卷积,FFT求一遍就行了。

+本文作者:luyouqi233。               +

+欢迎访问我的博客:+

我要回帖

更多关于 yy''=1+y'^2 的文章

 

随机推荐