题目链接:http://nyoj.top/problem/1368

  • 内存限制:64MB 时间限制:1000ms

题目描述

Gene mutation is the sudden and inheritable mutation of genomic DNA molecules. From the molecular level, gene mutation refers to the change of the composition or sequence of base pairs in the structure of a gene. Although the gene is very stable, it can reproduce itself accurately when the cell divides. Under certain conditions, the gene can also suddenly change from its original existence to another new form of existence.

A genome sequence might provide answers to major questions about the biology and evolutionary history of an organism. A 2010 study found a gene sequence in the skin of cuttlefish similar to those in the eye’s retina. If the gene matches, it can be used to treat certain diseases of the eye.

A gene sequence in the skin of cuttlefish is specified by a sequence of distinct integers (Y1,Y2, …Yc). it may be mutated. Even if these integers are transposed ( increased or decreased by a common amount ) , or re-ordered , it is still a gene sequence of cuttlefish. For example, if "4 6 7" is a gene sequence of cuttlefish, then "3 5 6" (-1), "6 8 9" ( +2), "6 4 7" (re-ordered), and "5 3 6" (transposed and re-ordered) are also ruminant a gene sequence of cuttlefish.

Your task is to determine that there are several matching points at most in a gene sequence of the eye’s retina (X1,X2, …, Xn)

输入描述

The first line of the input contains one integer T, which is the number of  test cases (1<=T<=5).  Each test case specifies:
* Line 1: n (1 ≤ n ≤ 20,000)
* Line 2: X1  X2… Xn (1 ≤ Xi ≤ 100  i=1…n)
* Line 3: c (1 ≤ c ≤ 10)
* Line 4: Y1  Y2… Yc (1 ≤ Yi ≤ 100  i=1…c)

输出描述

For each test case generate a single line:  a single integer that there are several matching points. The matching gene sequence can be partially overlapped.

样例输入

1
6
1 8 5 7 9 10
3
4 6 7

样例输出

2

解题思路

题意:给了两组数，然后问第一组数中有多少个子数组加任意数或减任意数再任意排序得到第二组数。
思路:直接暴力寻找枚举每一个m长的子串，判断就行了。

#include <bits/stdc++.h>
using namespace std;
int n, m;
int pre[20005], ans[15], cnt[15];
int Check(int l, int r) {
    for (int i = l; i <= r; i++)
        cnt[i - l] = pre[i];
    sort(cnt, cnt + m);
    int flag = cnt[0] - ans[0];
    for (int i = 0; i < m; i++) {
        if (ans[i] + flag != cnt[i])
            return 0;
    }
    return 1;
}
int main() {
    int t, num;
    scanf("%d", &t);
    while (t--) {
        num = 0;
        scanf("%d", &n);
        for (int i = 0; i < n; i++)
            scanf("%d", &pre[i]);
        scanf("%d", &m);
        for (int i = 0; i < m; i++)
            scanf("%d", &ans[i]);
        sort(ans, ans + m);
        for (int i = 0; i <= n - m; i++)
            if (Check(i, i + m - 1))
                num++;
        printf("%d\n", num);
    }
    return 0;
}