算法很简单, 就是记录各个feature的累积和数组, 数组稍作处理, 只要能够比较 [让能够相减得出答案的两个数组] 的”形状”.
比如
111 111 000 110 221<= 110 111 332 110 010 342 120 001 342 120 100 443<= 110 010 453 120
中间一列的221和443的”形状”一样, 也就是相减能得到答案, 所以稍作处理都减去最右边的数即可, 方便比较.
问题是者离散化以后也有100000的数据怎么记录, 好吧我开始用的二叉树后来发现想错了..
无耻的Google以后发现对数组Hash的方法.. 很汗颜 太洋气了.. 跑2xxMS
代码:
1 | #include <stdio.h> |
2 | #include <stdlib.h> |
3 | #include <string.h> |
4 |
5 | int hashcode(int *a, int k) { |
6 | int p = 0; |
7 | for (int i = 0; i < k; i++) |
8 | p = ((p << 2) + (a[i] >> 4)) ^ (a[i] << 10); |
9 | p %= 99983; |
10 | if (p < 0) |
11 | p += 99983; |
12 | return p; |
13 | } |
14 |
15 | int main() { |
16 | int N, K; |
17 | scanf("%d%d", &N, &K); |
18 |
19 | int hash[100000]; |
20 | memset(hash, 0xff, sizeof(hash)); |
21 |
22 | int (*c)[30]; |
23 | c = (int(*)[30]) malloc(sizeof(int) * 30 * 100001); |
24 | memset(c[0], 0x00, sizeof(c[0])); |
25 |
26 | hash[hashcode(c[0],K)]=0; |
27 |
28 | int result = 0; |
29 | for (int i = 1; i <= N; i++) { |
30 | int data; |
31 | scanf("%d", &data); |
32 | for (int j = 0; j < K; j++) { |
33 | c[i][j]=c[i-1][j]; |
34 | c[i][j] += (data >> j) & 1; |
35 | } |
36 | for (int j = K - 1; j >= 0; j--) |
37 | c[i][j] -= c[i][0]; |
38 |
39 | int hc = hashcode(c[i], K); |
40 | for (;; hc++) { |
41 | if (hash[hc] == -1) |
42 | break; |
43 | bool bingo = true; |
44 | for (int j = 0; j < K; j++) |
45 | if (c[i][j] != c[hash[hc]][j]) { |
46 | bingo = false; |
47 | break; |
48 | } |
49 | if (bingo) |
50 | break; |
51 | } |
52 | if (hash[hc] == -1) |
53 | hash[hc] = i; |
54 | else |
55 | result = (i - hash[hc]) > result ? (i - hash[hc]) : result; |
56 | } |
57 | printf("%d\n", result); |
58 | return 0; |
59 | } |
thanks!