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}
我的代码：
1/* ***********************************************
2Author :111qqz
3Created Time :2016年11月30日 星期三 14时44分41秒
4File Name :code/poj/3274.cpp
5 ************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int N=1E5+7;
33const int inf = 0x3f3f3f3f;
34int n,k;
35int mod;
36int a[N];
37int sum[N];
38map<int,int>mp;
39int main()
40{
41#ifndef ONLINE_JUDGE
42// freopen("code/in.txt","r",stdin);
43#endif
44 scanf("%d%d",&n,&k);
45 mod = (1<<k)-1;
46 // cout<<"mod:"<<mod<<endl;
47 sum[0] = 0;
48 for ( int i = 1 ; i <= n ; i++)
49 {
50 scanf("%d",&a[i]);
51 sum[i] = (sum[i-1] + a[i] ) % mod;
52 }
53
54 // for ( int i = 1; i <= n ; i++) printf("%d:%d \n",i,sum[i]);
55 int p = -1;
56 for ( int i = n ; i >= 1 ; i--)
57 {
58 if (sum[i]==0)
59 {
60 p = i ;
61 break;
62 }
63 }
64 int l,r;
65 int ans = 0 ;
66 if (p!=-1)
67 {
68 ans = max(ans,p);
69 l = 1;
70 r = p;
71 }
72 for ( int i = n ; i >= 1 ; i--)
73 {
74 if (mp[sum[i]])
75 {
76// ans = max(ans,abs(mp[sum[i]]-i));
77 if (abs(mp[sum[i]]-i)>ans)
78 {
79 l = i ;
80 r = mp[sum[i]];
81 ans = abs(l-r);
82 }
83 }else mp[sum[i]] = i;
84 }
85
86 /*
87 for ( int i = n ; i >= 1 ; i--)
88 if (!mp[sum[i]]) mp[sum[i]] = i ;
89 for ( int i = 1; i <= n ; i++)
90 {
91 if (mp[sum[i]]!=i)
92 {
93 int x = mp[sum[i]];
94 int y = i;
95 if (x<y) x++;
96 else y++;
97 // cout<<"x:"<<x<<" y:"<<y<<endl;
98 ans = max(ans,abs(x-y)+1);
99 }
100 }
101 */
102 if (l>r) swap(l,r);
103 printf("%d %d\n",l,r);
104 printf("%d\n",ans);
105
106#ifndef ONLINE_JUDGE
107 fclose(stdin);
108#endif
109 return 0;
110}
数据生成器：
1/* ***********************************************
2Author :111qqz
3Created Time :2016年11月30日 星期三 15时18分00秒
4File Name :data.cpp
5************************************************ */
6
7#include <cstdio>
8#include <cstring>
9#include <iostream>
10#include <algorithm>
11#include <vector>
12#include <queue>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <ctime>
19#define fst first
20#define sec second
21#define lson l,m,rt<<1
22#define rson m+1,r,rt<<1|1
23#define ms(a,x) memset(a,x,sizeof(a))
24typedef long long LL;
25#define pi pair < int ,int >
26#define MP make_pair
27
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33int main()
34{
35 #ifndef ONLINE_JUDGE
36// freopen("code/in.txt","r",stdin);
37 #endif
38 srand(time(0));
39 int n = 15;
40 printf("%d ",n);
41 int k = rand()%6 + 1;
42 printf("%d\n",k);
43 int mx = 1<<k;
44 mx--;
45 for ( int i = 1; i <= n ; i++)
46 {
47 int x;
48 x = rand()%mx+1;
49 printf("%d\n",x);
50 }
51
52 #ifndef ONLINE_JUDGE
53 fclose(stdin);
54 #endif
55 return 0;
56}
出错的输入：
15 6
50
34
11
63
63
59
36
9
49
25
1
26
38
6
2
我的输出：
2 10
8
ac代码的输出：
3 5
2
1a[i]: 34 11 63 63 59 36 9 49 25
2sum[i]: 34 45 108 171 230 266 275 324 349
3sum[i]%mx: 34 45 45 45 41 14 23 9 34