poj 3274 Gold Balanced Lineup (抽屉原理？错题？)

 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#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}

 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}