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

Posted by 111qqz on Wednesday, November 30, 2016

TOC

poj 3274 题目链接

题意:给出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  

「真诚赞赏,手留余香」

111qqz的小窝

真诚赞赏,手留余香

使用微信扫描二维码完成支付