Codeforces Round #269 Div 2（D MUH and Cube Walls（KMP））

来源：网络整理时间:2016-03-12 关键词:

本篇文章主要介绍了"Codeforces Round #269 Div 2（D MUH and Cube Walls（KMP））"，主要涉及到方面的内容，对于其他编程jrs看球网直播吧_低调看直播体育app软件下载_低调看体育直播感兴趣的同学可以参考一下：题目链接：点击打开链接题意：给你一个长度为n的序列，让你找其中有几个长度为m的序列的形状（即高低差距）思路：将数组预处理成相邻两数的差的形式，然后KMP即可...

题目链接：点击打开链接

题意：给你一个长度为n的序列，让你找其中有几个长度为m的序列的形状（即高低差距）

思路：将数组预处理成相邻两数的差的形式，然后KMP即可。 KMP的精华在于状态转移图的构造，有点DP的思想，也就是预处理失配之后能转移到代价尽量小的地方。

这里附上一篇KMP详解：点击打开链接

细节参见代码：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef long long ll;
typedef long double ld;
const ld eps = 1e-9, PI = 3.1415926535897932384626433832795;
const int mod = 1000000000 + 7;
const int INF = 0x3f3f3f3f;
// & 0x7FFFFFFF
const int seed = 131;
const ll INF64 = ll(1e18);
const int maxn = 200000 + 10;
int n,m,ans=0,f[maxn],T[maxn],p[maxn],a[maxn];
void getfail() {
    f[0] = 0; f[1] = 0;
    for(int i=1;i= m) ++ans, j = f[j];
    }
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=0;i 0) T[i] = a[i] - a[i-1];
        else T[i] = INF;
    }
    for(int i=0;i

以上就介绍了Codeforces Round #269 Div 2（D MUH and Cube Walls（KMP）），包括了方面的内容，希望对其他编程jrs看球网直播吧_低调看直播体育app软件下载_低调看体育直播有兴趣的朋友有所帮助。

本文网址链接：http://www.codes51.com/article/detail_421272.html

上一篇：tiny_cnn代码详解（4）——convolutional_layer类结构信息之成员变量与构造函数 下一篇：直线拟合算法

Codeforces Round #269 Div 2（D MUH and Cube Walls（KMP））

相关图片

相关文章