poj1840 五项式等于0(哈希)

题目传送门

题意很好懂,注意一下xi不能等于0

思路:智商检测题,一开始想着五重for暴力。。。Orz,后来移向(把a4a5移到右边)了发现减了1e8数量级的复杂度,再次Orz,所以直接三重循环,记录每一次答案,存到哈希表中(多次出现的要++,而且哈希值可能是负的,所以要加上一个比较大的数字),然后再两重循环,ans+=hash【e】就可以了。

然而!这样子开的数组会很大,直接int hash[maxn]会mle。网上看到一个骚操作是short[maxn],这个真的Orz,感觉以前好多mle的题目都是可以改的。(short的范围是2的16次,三万多,而这道题中hash表里存的数量肯定不到三万)

#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<sstream>
#include<cstring>
#include<bitset>
#include<cstdio>
#include<string>
#include<deque>
#include<stack>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define INF 0x3f3f3f3f
#define CLR(x,y) memset(x,y,sizeof(x))
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
const double PI=acos(-1.0);
int fact[10]= {1,1,2,6,24,120,720,5040,40320,362880};
const int maxn = 6250000;
int n,k;
int c[3000];
short hash[maxn*6+10];
int a[6];
int main(){
	for(int i=1;i<=5;i++)cin>>a[i];
	for(int i=-50,j=1;i<=50;i++,j++){
		if(i==0){
		j--;
		continue;}
		c[j]=i*i*i;
	}
	 for(int i=1;i<=100;i++){
	 	for(int j=1;j<=100;j++){
	 		for(int k=1;k<=100;k++){
	 			int e=a[1]*c[i]+a[2]*c[j]+a[3]*c[k]+3*maxn;
	 			hash[e]++;
			 }
		 }
	 }
	 int ans=0;
	 for(int i=1;i<=100;i++){
	 	for(int j=1;j<=100;j++){
	 			int e=-a[4]*c[i]-a[5]*c[j]+3*maxn;
	 			if(hash[e])ans+=hash[e];
			 
		 }
	 }
	 cout<<ans<<endl;
}

原文地址:https://www.cnblogs.com/mountaink/p/9536722.html