- 浏览: 196820 次
- 性别:
- 来自: 武汉
文章分类
- 全部博客 (137)
- c++ (74)
- c++,算法,回溯 (2)
- DP问题。 (9)
- DP问题,0/1背包问题 (3)
- 数学问题 (6)
- 贪心算法 (10)
- 排序 (16)
- 数据结构 (7)
- 容器 (2)
- 模拟问题 (2)
- 水题 (8)
- 并查集 (3)
- 非技术 (2)
- 素数问题 (1)
- DFS (3)
- 二叉树 (1)
- 递归 (1)
- 图论 (5)
- 最小生成树 (5)
- 最短路径 (6)
- bell_flaod算法 (2)
- hash (3)
- 二分查找 (1)
- 搜索 (5)
- BFS (5)
- STL (3)
- 字符串hash (1)
- 拓扑排序 (1)
- 字典树 (4)
- 哈弗曼树 (1)
- KMP (7)
- 线段树 (9)
- 树状数组 (6)
- 全排列 (2)
- DP问题 (2)
- LCS (1)
- 最长不下降子序列 (2)
- 面试经验 (3)
题意:对于方程:a1x13+ a2x23+ a3x33+ a4x43+ a5x53=0 ,有xi∈[-50,50], xi != 0, any i∈{1,2,3,4,5}. 现在给出a1,a2,a3,a4,a5的值,求出满足上面方程的解有多少个。 思路:hash的应用。暴力枚举的话会达到100^5,明显会超时。所以将方程分成a1x13+ a2x23 和 -(a3x33+a4x43+ a5x53 )两部分,若这两部分相等,则为方程的一个解。 一开始以为hash的优化效果不会很明显,因为觉得代码的大部分时间会消耗在o(100^3)求方程后部分的值上,后来看了别人的解题报告,发现用hash进行优化的效果还是很恐怖的,这么说代码的大部分时间是消耗在前后两部份的排序和匹对求解的个数上,所以干脆用直接寻址表进行了优化,结果运行时间由1329MS 到了 157MS,不是一般的快。
关于hash的解法未完待续……#include <iostream>
using namespace std;
#define mq 100007
int a[100008][10];
int top[100008];
int main()
{
int a1,a2,a3,a4,a5,t,sum=0,p,i;
int x1,x2,x3,x4,x5;
cin>>a1>>a2>>a3>>a4>>a5;
for(x1=-50;x1<=50;x1++)
{
if(!x1)
continue;
for(x2=-50;x2<=50;x2++)
{
if(!x2)
continue;
t=a1*x1*x1*x1+a2*x2*x2*x2;
p=t;
t%=mq;
if(t<0)
t+=mq;
a[t][top[t]++]=p;
}
}
for(x3=-50;x3<=50;x3++)
{
if(!x3)
continue;
for(x4=-50;x4<=50;x4++)
{
if(!x4)
continue;
for(x5=-50;x5<=50;x5++)
{
if(!x5)
continue;
t=-(a3*x3*x3*x3+a4*x4*x4*x4+a5*x5*x5*x5);
p=t;
t%=mq;
if(t<=0)
t+=mq;
for(i=0;i<top[t];i++)
if(a[t][i]==p)
sum++;
}
}
}
cout<<sum<<endl;
return 0;
}
发表评论
-
虚函数、纯虚函数、虚基类、抽象类、虚函数继承、虚继承
2013-08-29 14:34 789虚函数:虚函数是C++中用于实现多态(polymorphis ... -
排序算法总结
2013-05-17 11:00 784选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法, ... -
poj 3122
2012-12-11 19:51 812题意:作者要开一个生日party,他现在拥有n块高度都为1 ... -
poj 3273
2012-12-11 16:49 948题意:给你天数n,和每天需要花的钱,让你把这些天分成m份(每份 ... -
字典树学习材料
2012-05-30 14:29 933字典树,又称单词查找树,Trie树,是一种树形结构,典型应 ... -
poj 1159
2012-05-28 19:08 1398题目大意:给你一段字符串,让你求出在中间最少加入几个字符 ... -
poj 3176
2012-05-28 14:47 977大致题意: 输入一个n层的三角形,第i层有i个数,求从第 ... -
poj 1260
2012-05-28 09:54 1572题意解释: 有n个等级的珠宝,等级依次升高,等级越高价钱越高 ... -
poj 1836
2012-05-28 09:22 2671是POJ2533的扩展题。题意不难,令到原队列 ... -
poj 2533
2012-05-26 15:36 1207在做这道题目之前,首先让我们了解一下什么是LIS算法,LIS俗 ... -
poj 3267
2012-05-26 09:43 776从程序可以看出,第i个位置到L所删除的字符数,总是先取最坏情况 ... -
poj 1276
2012-05-25 16:20 2351题意: 这道题的意思是给你一堆钱,各种面值的都有,比 ... -
poj 1094
2012-05-25 13:54 1062题意:给出字母个数,和有限个有序对(a<b)求出能确定字 ... -
poj 3393
2012-05-23 17:00 1226大致题意: 科普文一篇,文章80%都是无用信息,因为 ... -
poj 3007
2012-05-14 10:21 949大致题意: 给定一个字符串,从任意位置把它切为两半, ... -
poj 3096
2012-05-10 21:09 962题意: 定义D-pairs表示取字符串s中相距为D的两个字母 ... -
poj 1426
2012-04-26 20:11 2116大致题意: 给出一个整数n,(1 <= n <= ... -
poj 1797
2012-04-24 15:05 1590题目大意是就是何处一个图,n个顶点和m条边,每个边都有最大承载 ... -
poj 1338
2012-04-23 10:20 1225题意:题目意思是求由2,3,5的乘积组成的数从大到小排列,从1 ... -
poj 2021
2012-04-19 15:00 894题意:Ted今年100岁,给出n对他家族的关系:“父 ...
相关推荐
北大POJ1840-Eqs 解题报告+AC代码
NULL 博文链接:https://128kj.iteye.com/blog/1754756
这是西北工业大学的POJ试题的答案,欢迎下载!
网上整理的一些poj刷题指南。 poj地址:http://poj.org
LeetCode判断字符串是否循环 :bookmark_tabs:Plan 动态规划 背包问题 动态规划 POJ 3267 POJ 1260 POJ ...1840 POJ 2002 POJ 3432 POJ 2503 Leetcode 33 哈夫曼树、优先队列 POJ 3253 trie树 POJ 251
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
twilight-poj-solutionPOJ () solution by twilight想当年要找一题的分析, 解答实在太难了现在都是开源的时代了, 干脆把Archive放到GitHub上, 供后来人参考.POJ ID: 部分题解: 转载请注明出处~
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
poj 算法题在poj.org上做的一些算法题poj.org 账号:xxfeixiang题目地址:例如,第1001题的地址为:
初学者练题开始------在POJ上(注:是百练) 初学者练题开始------在POJ上(注:是百练) 初学者练题开始------在POJ上(注:是百练)
POJ 1300 Door Man:无向图、欧拉定理、gets、sscanf
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
poj POJ是在线法官。 我想不到一个更好的名字。 它是用Python3和Django编写的。 它使用Docker和Celery进行提交评估。 Docker确保每个提交都在单独的容器中运行,而Celery使其全部异步。 我们在此处用于Celery的...
poj分类poj分类poj分类poj分类
北大POJ1009-Edge Detection 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告