tkdsheep-solution-0052

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

题意是给你两组数据，每组数据里面的数字代表一个山峰的高度
现在我要在每组数据里取出k个数，k>=2，并且取的时候必须是连续的k个数，且不能改变他们在组里的原始位置关系
比如第一组数据是（1，2，3，4），当k=3的时候
我可以取（1，2，4）或者（2，3，4）但不能取（1，3，4）也不能取（2，1，4）
其实就可以把两组数据看作两个字符串，然后各取一个长度为k的字符子串
现在要还要保证这两个字符串的rank相同，所谓rank可以见题目描述，实际上就是两个字符串的逆序对要完全一样
比如（1，2）和（3，4）是一样的，（1，4，2）和（2，5，3）是一样的，就是计算一下两个子串中每个数字的逆序对数，如果都相等则rank一样
问有多少种这样的组合～～
标程是kmp，我和zrj在比赛时都用的hash，zrj的hash过了，可惜我没过，赛后听讲题才知道是我hash写错了
hash其实很简单，就是对一组数据，枚举起点和终点，然后计算这个子串的hash值，计算hash的时候，比如我算到枚举子串中的第i个数了
那么要维护一个big[i]和same[i]信息，big[i]表示前i个数中比第i个数小的有多少，same[i]表示等于的有多少，然后把这两个数字当成字符来hash就行了
两组数据的hash都用map维护，最后遍历其中一组hash即可～

题意是给你两组数据，每组数据里面的数字代表一个山峰的高度

现在我要在每组数据里取出k个数，k>=2，并且取的时候必须是连续的k个数，且不能改变他们在组里的原始位置关系

比如第一组数据是（1，2，3，4），当k=3的时候

我可以取（1，2，4）或者（2，3，4）但不能取（1，3，4）也不能取（2，1，4）

其实就可以把两组数据看作两个字符串，然后各取一个长度为k的字符子串

现在要还要保证这两个字符串的rank相同，所谓rank可以见题目描述，实际上就是两个字符串的逆序对要完全一样

比如（1，2）和（3，4）是一样的，（1，4，2）和（2，5，3）是一样的，就是计算一下两个子串中每个数字的逆序对数，如果都相等则rank一样

问有多少种这样的组合～～

标程是kmp，我和zrj在比赛时都用的hash，zrj的hash过了，可惜我没过，赛后听讲题才知道是我hash写错了

hash其实很简单，就是对一组数据，枚举起点和终点，然后计算这个子串的hash值，计算hash的时候，比如我算到枚举子串中的第i个数了

那么要维护一个big[i]和same[i]信息，big[i]表示前i个数中比第i个数小的有多少，same[i]表示等于的有多少，然后把这两个数字当成字符来hash就行了

两组数据的hash都用map维护，最后遍历其中一组hash即可～