8
26
2012
1

怕超时?哈希一下:Arithmetic Progressions

我们将所有能写成 p2+q(p,q>=0)的数字成为bisquare数,在bisquare集合中有多少长度为N(3<=N<=25)的等差序列?我们规定p,q的取值区间为[0,M](1<=M<=250),且等差序列的公差大于0。

我们很容易想到枚举序列中的前两项(或者首项和尾项,这正是我用的方法,这样便于剪枝)来确定整个序列并检验其余项是否是bisquare,但注意当M=250的时候bisquare集合中有20000多个数字,所以算法的复杂度要控制在o(n2)以内,这样检验是否是bisquare的步骤要用常数时间才行,这时候哈希表就派上用场了。

点击查看我的源代码:

 

/*
ID: *******
LANG: C
TASK: ariprog
*/
#include<stdio.h>
#include<stdlib.h>

int N,M;
FILE *fin,*fout;
typedef struct{
    int first;
    int diff;
}R;
R seq[10001];
int tailSeq;
int bisq[32000];
int tailBisq;
int hash[125001];

int cmpint(const void *a, const void *b){
	return(*(int *)a-*(int *)b); //升序 
}

int cmpR(const void *a, const void *b){//先按公差比较,再按首项比较 
	R aa=*(R*)a;
	R bb=*(R*)b;
	if(aa.diff==bb.diff){
		return aa.first-bb.first;
	}
	return aa.diff-bb.diff;
}

int main(){
    fin=fopen("ariprog.in","r");
    fout=fopen("ariprog.out","w");
    fscanf(fin,"%d %d",&N,&M);
    int i,j;
    for(i=0;i<125001;i++)hash[i]=0;
    tailBisq=-1;
    for(i=0;i<=M;i++){
		for(j=i;j<=M;j++){
			bisq[++tailBisq]=i*i+j*j;
			hash[bisq[tailBisq]]=1;//哈希表记录某数字是否在bisquare数字集合中 
		}
    }
    qsort(bisq,tailBisq+1,sizeof(int),cmpint);
    int count=0;
    int pre=-1;
    for(i=0;i<=tailBisq;i++){//排序后去重 
		if(bisq[i]!=pre){
			bisq[count]=bisq[i];
			count++;
			pre=bisq[i];
		}
	}
	tailBisq=count-1;

    tailSeq=-1;
    int first,last;
    for(first=0;first<=tailBisq;first++){
		for(last=first+N-1;last<=tailBisq;last++){//枚举首项和尾项 
			int diff=bisq[last]-bisq[first];
			if(diff==0)continue;
			if(diff%(N-1)!=0)continue;//剪枝
			diff=diff/(N-1);
			for(i=1;i<=N-2;i++)//查看中间项是否是bisquare数 
				if(hash[bisq[first]+diff*i]==0)
					break;
			if(i>N-2){//记录符合条件的等差序列 
				R r;
				r.first=bisq[first];
				r.diff=diff;
				seq[++tailSeq]=r;
			}
		}
	}
	qsort(seq,tailSeq+1,sizeof(R),cmpR);
	for(i=0;i<=tailSeq;i++){
		fprintf(fout,"%d %d\n",seq[i].first,seq[i].diff);
	}
	if(tailSeq==-1)fprintf(fout,"NONE\n");
    return 0;
}
Category: USACO | Tags: usaco | Read Count: 874
hire writers 说:
2020年6月05日 16:30

The people with programming skills can grab here the useful update and get help by experts about coding as well. I admire your excellent help online and must recommend others to avail stuff while having it here. Thumbs up and keep going to bring useful material.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com