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