poj 3274 Gold Balanced Lineup (抽屉原理？错题？)
题意：给出n个数和k，每个数不超过k位二进制。现在问最长的一段区间，满足该区间中所有数相加，k个位置上的数相等。
思路：k个位置上的数都相等的话。。。那这个和应该是(k<<1)-1的整数倍。。。
于是抽屉原理搞了一发。。一直wa..
正解是数字hash。。。
不过我拍了一下。。。如果不是我理解错了题意的话。。。我是把一份ac代码 hack掉了。。。。。
用来对拍的ac代码：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define MAX 100005
#define mod 1000000 //此处mod定义为99997时，运行时间1000多MS
int hash[MAX*10];//hash表储存下标
int sum[MAX][35];//第 1 头牛到第 i 头的对应属性的和
int c[MAX][35];//存放每头牛属性 j与第一个属性的差
int n,k;
int Hash_key(int *cc)
{
int j,key=0;
for(j=1;j<k;j++)
key=key%mod+cc[j]<<2;//此处用 * 乘超时
key=abs(key)%mod;//此处得到的key可能会是负数，所以取绝对值
return key;
}
int main()
{
int i,j,x,maxlen=0;//maxlen为最大长度
scanf("%d%d",&n,&k);
int l,r;
memset(hash,-1,sizeof(hash));//初始化哈希表
hash[0]=0;//hash表首位初始化
for(i=1;i<=n;i++)
{
scanf("%d",&x);
for(j=0;j<k;j++)
{
sum[i][j]=sum[i-1][j]+x%2;
c[i][j]=sum[i][j]-sum[i][0];
x>>=1;
}
int key=Hash_key(c[i]);
while(hash[key]!=-1)//处理关键字冲突
{
for(j=0;j<k;j++)//当前牛的属性与其关键字相同的进行比较
if( c[i][j]!=c[ hash[key] ][j] )
break;
if(j==k && maxlen<(i-hash[key]))//若j==k，说明两头牛的属性个数相同
{
maxlen=i-hash[key];
l = i ;
r = hash[key];
break;
}
key++;//往后继续移动处理冲突
}
if(hash[key]==-1)
hash[key]=i; //将下标存放在hash中
}
if (l>r) swap(l,r);
printf("%d %d\n",l,r);
printf("%d\n",maxlen);
return 0;
}
我的代码：
/* ***********************************************
Author :111qqz
Created Time :2016年11月30日 星期三 14时44分41秒
File Name :code/poj/3274.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int N=1E5+7;
const int inf = 0x3f3f3f3f;
int n,k;
int mod;
int a[N];
int sum[N];
map<int,int>mp;
int main()
{
#ifndef ONLINE_JUDGE
// freopen("code/in.txt","r",stdin);
#endif
scanf("%d%d",&n,&k);
mod = (1<<k)-1;
// cout<<"mod:"<<mod<<endl;
sum[0] = 0;
for ( int i = 1 ; i <= n ; i++)
{
scanf("%d",&a[i]);
sum[i] = (sum[i-1] + a[i] ) % mod;
}
// for ( int i = 1; i <= n ; i++) printf("%d:%d \n",i,sum[i]);
int p = -1;
for ( int i = n ; i >= 1 ; i--)
{
if (sum[i]==0)
{
p = i ;
break;
}
}
int l,r;
int ans = 0 ;
if (p!=-1)
{
ans = max(ans,p);
l = 1;
r = p;
}
for ( int i = n ; i >= 1 ; i--)
{
if (mp[sum[i]])
{
// ans = max(ans,abs(mp[sum[i]]-i));
if (abs(mp[sum[i]]-i)>ans)
{
l = i ;
r = mp[sum[i]];
ans = abs(l-r);
}
}else mp[sum[i]] = i;
}
/*
for ( int i = n ; i >= 1 ; i--)
if (!mp[sum[i]]) mp[sum[i]] = i ;
for ( int i = 1; i <= n ; i++)
{
if (mp[sum[i]]!=i)
{
int x = mp[sum[i]];
int y = i;
if (x<y) x++;
else y++;
// cout<<"x:"<<x<<" y:"<<y<<endl;
ans = max(ans,abs(x-y)+1);
}
}
*/
if (l>r) swap(l,r);
printf("%d %d\n",l,r);
printf("%d\n",ans);
#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}
数据生成器：
/* ***********************************************
Author :111qqz
Created Time :2016年11月30日 星期三 15时18分00秒
File Name :data.cpp
************************************************ */
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair
using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
int main()
{
#ifndef ONLINE_JUDGE
// freopen("code/in.txt","r",stdin);
#endif
srand(time(0));
int n = 15;
printf("%d ",n);
int k = rand()%6 + 1;
printf("%d\n",k);
int mx = 1<<k;
mx--;
for ( int i = 1; i <= n ; i++)
{
int x;
x = rand()%mx+1;
printf("%d\n",x);
}
#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}
出错的输入：
15 6
50
34
11
63
63
59
36
9
49
25
1
26
38
6
2
我的输出：
2 10
8
ac代码的输出：
3 5
2
a[i]: 34 11 63 63 59 36 9 49 25
sum[i]: 34 45 108 171 230 266 275 324 349
sum[i]%mx: 34 45 45 45 41 14 23 9 34