Time Limit: 1 second
Memory Limit: 128 MB
【问题描述】
神牛小R在许多方面都有着很强的能力，具体的说，他总共有m种能力，并将这些能力编号为1到m。他的能力是一天一天地提升的，每天都会有一些能力得到一次提升，R对每天的能力提升都用一个数字表示，称之为能力提升数字，比如数字13，转化为二进制为1101，并且从右往左看，表示他的编号为1,3,4的能力分别得到了一次提升。小R把每天表示能力提升的数字的记了下来，如果在连续的一段时间内，小R的每项能力都提升了相同的次数，小R就会称这段时间为一个均衡时期，比如在连续5天内，小R的每种能力都提升了4次，那么这就是一个长度为5的均衡时期。 于是，问题来了，给出 小R n天的能力提升数字，请求出均衡时期的最大长度。【输入格式】
第一行有两个整数n,m，表示有n天，m种能力。接下来有n行，每行有一个整数，分别表示第1到n天的能力提升数字。能力提升数字转化为二进制后，从右到左的每一位表示对应的能力是否在当天得到了一次提升。 n<=100000, m<=30
【输出格式】
输出只有一个整数，表示长度最大的均衡时期的长度。
【数据规模】
对于50%的数据，N <= 1000。
Sample Input1
7 3 7 6 7 2 1 4 2
Sample Output1
4
【样例说明】
每天被提升的能力种类分别为： 第一天:1，2，3 第二天:2，3 第三天:1，2，3 第四天：2 第五天：1 第六天：3 第七天：2 第三天到第六天为长度最长的均衡时期 因为 这四天 每种能力分别提升了 2次
【题解】
设在第i天，所得到的能力值组成的数列为a1,a2,a3..an;
则我们要找之前的一个数列a1-k,a2-k,a3-k..an-k;(尽量靠前找)
这个数列和第i天的数列的差值，就是所需要的均衡时期。
也即所有的能力都提升了相同的值。
我们可以这样做。
在第i天加完之后。把数列中所有的值都减去那个最小值。(每个值减去的数都是一样的,满足均衡发展的题意)；
然后看看之前有没有出现过这个数列(我们存的都是最早出现的)。
如果有出现。则就用这两个数列的天数差作为temp，尝试更新ans.
这里的寻找过程，需要用到hash函数。
随便写一个hash函数，然后取模，用链表来处理冲突就可以了。
这里的hash函数就是每一个数值*ascill码值然后对100007取模
【代码】
#include <cstdio>
struct point
{
int shulie[40], where;//这是链表的结构体。
point *next;
};
int n, m,totn=1,ans = 0;
int st[40];
point *h[100007]; //这是链表的头结点和尾节点。
point *t[100007];
int sear_ch(int a[], int where) //当前这个数列是在第where天找到的。
{
int key = 0;
for (int i = 1; i <= m; i++)//构造出hash函数
key = (key + a[i] * (a[i]+'0'))%100007;//要对100007取模
point *p = h[key]; //取出这个hash值的头结点。
while (p != NULL) //在头结点和尾节点之间寻找这个数列
{
bool find = true;
for (int i = 1;i <= m;i++)
if (p->shulie[i] != a[i])//只要有一个不同，它就不是这个数列
{
find = false;
break;
}
if (find)//如果找到了，就返回它第一次出现的位置。
return p->where;
p = p->next;//否则继续找
}
p = new point;//如果没有找到就创立一个新的节点
p->next = NULL;
for (int i = 1; i <= m; i++)//把这个数列存在这个节点中
p->shulie[i] = a[i];
p->where = where;//记录一下它的天数
t[key]->next = p;//把节点接在尾节点后面。
t[key] = t[key]->next;
return p->where;
}
int main()
{
//freopen("F:\rush.txt", "r", stdin);
//freopen("F:\rush_out.txt", "w", stdout);
for (int i = 0; i <= 100007; i++)
{
h[i] = new point;
h[i]->next = NULL;
h[i]->where = 0; //初始化头结点和尾节点。
t[i] = h[i];
}
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++) //一开始所有的能力值都为0
st[i] = 0;
sear_ch(st, 0);//把这个初始数列加入到hash表中
for (int i = 1; i <= n; i++)
{
int x, now = 0, min = 2100000000;
scanf("%d", &x);
while (x > 0)//先将其转换成二进制
{
now++;
int temp = x % 2;
if (temp == 1) //如果是1就加上1
st[now]++;
x /= 2;
}
for (int j = 1; j <= m; j++)//寻找最小值
if (st[j] < min)
min = st[j];
if (min > 0)
for (int j = 1; j <= m; j++)//把数列的每一个数字减去min
st[j] -= min;
int pre = sear_ch(st, i);//查找之前出现过的下标最小的这个数列的下标
if (i - pre > ans)//看看这个差能不能更新答案。
ans = i - pre;
}
printf("%d", ans);
return 0;
}