poj3274 Gold Balanced Lineup
IAmL
posted @ 2009年4月07日 00:33
in 解题报告
with tags
poj3274 Gold Balanced Lineup解题
, 4970 阅读
这题主要考的是对题目的理解。简单说说题意：fj有一些牛，那些牛有k个特点中的一个或者几个。现在要求从第i到j头牛中，满足每个属性的牛的数目都一样。
如果粗暴地枚举，肯定会超时。所以需要对问题进行转化。
题目转化如下：
（转自http://hi.baidu.com/aconly/blog/item/9d1ed1122a29af876538db0b.html）
令C[i][l]=sum[i][l]-sum[i][0] (0<l<k)。
sum[i][k-1]-sum[i][0]==sum[j][k-1]-sum[j][0]
.
.
sum[i][2]-sum[i][0]==sum[j][2]-sum[j][0]
sum[i][1]-sum[i][0]==sum[j][1]-sum[j][0]
最大的i-j
sum[i][0]-sum[j][0]==sum[i][1]-sum[j][1]==.....==sum[i][k-1]-sum[j][k-1] (j<i)
数组sum[i][j]表示从的1到i头cow属性j的和。所以题目要求等价为求满足
所以只需求满足C[i]==C[j] 中最大的i-j。
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝华丽的分割线＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
注：代码如下：由于我是看完解题报告再写代码的，所以代码和解题报告的代码相似性很大……只能怪自己太水，不会做……
#include <iostream>
using namespace std;
#define N 100001
#define Prime 99983
int n, k, flag[N][31], c[N][31], hash[Prime];
inline int hashcode(const int *v)
{
int s = 0;
for(int i = 0; i < k; i++)
s=((s << 2) + (v[i] >> 4)) ^ (v[i] << 10);
s = s % Prime;
s = s < 0 ? s + Prime : s;
return s;
}
int main()
{
int i, j, tmp, maximum = 0;
scanf("%d%d", &n, &k);
memset(flag, 0, sizeof(flag));
memset(c, 0, sizeof(c));
memset(hash, -1, sizeof(hash));
hash[hashcode(c[1])] = 0;
for (i = 1; i <= n; i++)
{
scanf("%d", &tmp);
//input
for (j = 0; j < k; j++)
{
if ((tmp >> j) & 1) flag[i][j] = flag[i - 1][j] + 1;
else flag[i][j] = flag[i - 1][j];
c[i][j] = flag[i][j] - flag[i][0];
}
//solve
//find key
tmp = hashcode(c[i]);
//match
while (hash[tmp] != -1)
{
for (j = 1; j < k; j++)
if (c[i][j] != c[hash[tmp]][j]) break;
if (j >= k)
{
j = i - hash[tmp];
maximum = maximum > j ? maximum : j;
break;
/*如果遇到符合条件的，就跳出。注意，跳出之后不一定能记录i。
但是没所谓，因为我们要求最大的i-j差距，
所以如果这个i能和之前录入的imatch，则之后能和现在的i match的i也一定能和之前录入的i match*/
}
tmp++;
}
if (hash[tmp] == -1) hash[tmp] = i;
}
printf("%d\n", maximum);
return 0;
}
using namespace std;
#define N 100001
#define Prime 99983
int n, k, flag[N][31], c[N][31], hash[Prime];
inline int hashcode(const int *v)
{
int s = 0;
for(int i = 0; i < k; i++)
s=((s << 2) + (v[i] >> 4)) ^ (v[i] << 10);
s = s % Prime;
s = s < 0 ? s + Prime : s;
return s;
}
int main()
{
int i, j, tmp, maximum = 0;
scanf("%d%d", &n, &k);
memset(flag, 0, sizeof(flag));
memset(c, 0, sizeof(c));
memset(hash, -1, sizeof(hash));
hash[hashcode(c[1])] = 0;
for (i = 1; i <= n; i++)
{
scanf("%d", &tmp);
//input
for (j = 0; j < k; j++)
{
if ((tmp >> j) & 1) flag[i][j] = flag[i - 1][j] + 1;
else flag[i][j] = flag[i - 1][j];
c[i][j] = flag[i][j] - flag[i][0];
}
//solve
//find key
tmp = hashcode(c[i]);
//match
while (hash[tmp] != -1)
{
for (j = 1; j < k; j++)
if (c[i][j] != c[hash[tmp]][j]) break;
if (j >= k)
{
j = i - hash[tmp];
maximum = maximum > j ? maximum : j;
break;
/*如果遇到符合条件的，就跳出。注意，跳出之后不一定能记录i。
但是没所谓，因为我们要求最大的i-j差距，
所以如果这个i能和之前录入的imatch，则之后能和现在的i match的i也一定能和之前录入的i match*/
}
tmp++;
}
if (hash[tmp] == -1) hash[tmp] = i;
}
printf("%d\n", maximum);
return 0;
}
评论 (0)