acm1496 求电脑高手在线解答解答

1508人阅读
ACM算法总结(13)
递归算法就是在函数或子过程的内部,直接或者间接地调用自己的算法,在ACM中它是一个入门级的算法,题目一般非常简单。它一般解决三类问题:
(1) 数据的定义是按递归定义的。(Fibonacci函数)
(2) 问题解法按递归算法实现。(回溯)
(3) 数据的结构形式是按递归定义的。(树的遍历,图的搜索)
递归算法解决问题的特点:
(1) 递归就是在过程或函数里调用自身。
(2) 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口。
(3) 递归算法解题通常显得很简洁,但递归算法解题的运行效率较低,并且在递归调用的过程当中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。所以一般不提倡用递归算法设计程序
递归是非常工具性的算法,常用于其他算法的实现,例如递归常与分治算法一同出现,也在深搜,递归建树,树的递归遍历等等地方使用,在很多的模拟题中也有很大的作用,往往使得代码变得十分清晰和精短。
& & 同时ACM中递归的题目也相对简单以下是我做过的一些简单题的总结。
& 下面HDOJ 2044 到 HDOJ 2050是很好的入门级别的递归练习,当然,有的题还是很有难度。&
HDOJ 2044&
& & & & &解题思路:1)每到一个点的路径数肯定等于它左边和左下方(左上方)的路径之和。
&&&&&&&&&&&&&&2)设从a走到b之间一共走n步,则有:
&&&&&&&&&&&&&&&&&&dp[n]=dp[n-1]+dp[n-2]; dp[n-1]=dp[n-2]+dp[n-3]..............
贴下代码:
#include &iostream&
#include &cstdio&
#include &cmath&
long long a[55];
int T,n,m;
int main()
for (int i=3; i&=50; i++)
a[i]=a[i-1]+a[i-2];
while (T--)
cin && n &&
cout && a[m-n] &&
HDOJ 47/差不多都是一样的思想,大家就慢慢推理吧。
& & & &重点说说 & HDOJ2050:
& & & 这题当初我也是CP的,大家可以参考: & && &&, 这里讲的很不错,当大家看明白这篇文章时,我想A掉2050就变得很简单了。
解题思路:主要是用到递推即可。递推过程:首先分析直线分平面最多多少份:
f(1)=2;f(2)=4;f(3)=7;f(4)=11……可知f(n)=f(n-1)+n且f(1)=2.可知f(n)=(1+n)*n/2+1; 同理,可将每个折线看成是两条直线,但是少了一半。因此每一条折线比两条直线分割的面的部分少2。因此n条折线比2n条直线分割平面形成的部分少2n。 所以f(n)=2*n^2-n+1;CP的代码:#include&iostream&
int main()
int sum=2*m*m-m+1;
cout&&sum&&
参考知识库
* 以上用户言论只代表其个人观点,不代表CSDN网站的观点或立场
访问:37153次
排名:千里之外
原创:15篇
转载:18篇
评论:13条
(4)(12)(17)Time Limit:
MS (Java/Others)&&&&Memory Limit:
K (Java/Others)Total Submission(s): 3978&&&&Accepted Submission(s): 1602
Problem Description
Consider equations having the following form:&a*x1^2+b*x2^2+c*x3^2+d*x4^2=0a, b, c, d are integers from the interval [-50,50] and any of them cannot be 0.It is consider a solution a system ( x1,x2,x3,x4 ) that verifies the equation, xi is an integer from [-100,100] and xi != 0, any i &{1,2,3,4}.Determine how many solutions satisfy the given equation.
The input consists of several test cases. Each test case consists of a single line containing the 4 coefficients a, b, c, d, separated by one or more blanks.End of file.
For each test case, output a single line containing the number of the solutions.
Sample Input
Sample Output
解题思路:暴力+hash,主要是想练练hash,一直认为hash是高端黑,用线性探测再散列处理冲突,记得不知道谁说过处理余数的数一般用上素数,不要忘了最后乘上16,因为四个数有可能是正负
1 #include&stdio.h&
2 #include&string.h&
3 #define MAXN 50001
4 int num[MAXN], store[MAXN];
6 int hash(int cur)
int temp = cur%MAXN;
if(temp & 0) temp += MAXN;
while(num[temp] != 0 && store[temp] != cur)
temp = (temp+1)%MAXN;
17 int main()
freopen("input.txt", "r", stdin);
int rate[101], a, b, c, d, i, j, sum, temp,
for(i=0; i&101; ++i) rate[i] = i*i;
while(scanf("%d%d%d%d", &a, &b, &c, &d) != EOF)
if((a&0&&b&0&&c&0&&d&0) || (a&0&&b&0&&c&0&&d&0))
printf("0\n");
memset(num, 0, sizeof(num));
for(i=1; i&101; ++i)
for(j=1; j&101; ++j)
temp = a*rate[i]+b*rate[j];
res = hash(temp);
store[res] =
num[res]++;
for(i=1; i&101; ++i)
for(j=1; j&101; ++j)
temp = -(c*rate[i]+d*rate[j]);
res = hash(temp);
sum += num[res];
printf("%d\n", sum*2*2*2*2);
阅读(...) 评论()杭电oj 1496 提交说超时 感觉实在是跟别人给出的AC代码差不多 求大神帮我看看 谢谢!!_百度知道
杭电oj 1496 提交说超时 感觉实在是跟别人给出的AC代码差不多 求大神帮我看看 谢谢!!
2;=100,j++)
ans[a*i*i+b*j*j+1000000]++.Determine how many solutions satisfy the given equation, b,50] and any of them cannot be 0!= 0, d,c;0&&b&;i&lt.Sample Input1 2 3 -41 1 1 1Sample Output390880#include&&0&i&j&lt, separated by one or more blanks.It is consider a solution a system ( x1,0) {cout&0&&d&gt. OutputFor each test case,x2;i++)
for(int j=1;0&&c&iostream&&&lt,4},&c,x3;
memset(ans,100]0&&b&
while(scanf(&quot,b,sizeof(ans)),&a,x4 ) that verifies the equation,&d))
count=0,0;j++)
count+=ans[1000000-c*i*i-d*j*j];&quot,d;continue, xi is an integer from [-100;int ans[2000002];&&}
for(int i=1;=100;int main(){
int a, any i ∈{1. Each test case consists of a single line containing the 4 coefficients a,=100Problem DescriptionConsider equations havin0&&c&gt, output a single line containing the number of the solutions,
return 0,&b, d are integers from the interval [-50.InputThe input consists o16*count&=100;
for(int i=1;
cout&lt,3;j&lt: a*x1^2+b*x2^2+c*x3^2+d*x4^2=0a;0&&d&0||a&%d %d %d %d&i++)
for(int j=1
提问者采纳
count&=&&d)==4) {
count&d&c;=&1;j&&iostream&0&j&=&&namespace&j&;int&0;100;+&
cout&-&0&0&
//&nbsp,&&i&& } return&c;c&&&a&1;
if&cout&&&&int&(int&& while&
for&nbsp,&1;b;(a&(int&&main(){ int&j++)
ans[a*i*i&0&&用map来代替数组还更快一点;j&nbsp,&&&&}
for&&&&&0&&=&&b&{&(scanf(&&d*j*j];c&&i&d&&&&&#include&+&0&b;&100;c*i*i&&%d&&%d&&&=&count&a;(int&&%d&&endl,&100;0&map&d;a;*&&-&1000000]++;16&&+=&&i++)
for&&using&0,&&&=&&nbsp,&||&&=&nbsp,&ans[1000000&std,&&&nbspmemset&0&1;0)&nbsp,但是不用初始化200万的数组
map&lt,虽然查找慢了;&&amp,&=&=&&&i++)
for&i&%d&b*j*j&一个200万的数组很慢的#include&100;b&i&(int&nbsp
可是我不会用map 我之后会去看看的 谢谢!能不能帮我看看这段代码?这是网上别人写的 跟我的基本差不多 但是他把结果分成正数负数两个数组来存 memset了两个100万的数组 耗时不是应该一样么?麻烦了!放代码超字数只好截图 可能看的时候比较麻烦 不好意思啊……
他是scanf printf你是cin cout,可能是这个原因吧
试了下 不是 真的好困惑啊啊啊啊
哦我忘了告诉你读取的时候要写成while&(scanf(&%d&%d&%d&%d&,&&a,&&b,&&c,&&d)==4)或者while&(scanf(&%d&%d&%d&%d&,&&a,&&b,&&c,&&d)&!=&EOF)while&(scanf(&%d&%d&%d&%d&,&&a,&&b,&&c,&&d))写成这样是错的
提问者评价
来自团队:
为您推荐:
其他2条回答
&&d&0&c&lt。;&0&0&&&&&&0&&0&&b&&&&&&&&&&&0&}楼主你确定这句没问题?;&nbsp, 加个括号;endl,确保剪枝正确;&&((a&&&&&(a&&0)&&&&{&0&&&c&0&&&&&&a&&&&&||&0&&&0)){&c&&&c&&&&d&&&&&0&nbsp。if&&&&b&&d&gt&&&0)&0&nbsp。;(a&||&&&&&&if&d&cout&&&&0&0&0&&0&&&&cout&b&gt?如下;b&lt
应该不是这个问题 或的优先级比与高 所以没关系还是谢谢了! 还能看出别的问题么?
这吧搞acm的不多,你问也白问
等待您来回答
下载知道APP
随时随地咨询
出门在外也不愁二分(17)
Problem Description
Sample Input
Sample Output
题目很简单,只贴代码:
#include &stdio.h&
#include &string.h&
#include &iostream&
#include &algorithm&
typedef long long LL;
LL sum[400007];
void erfen(LL t)
int l=0,r=k;
while(l&=r)
mid=(l+r)/2;
if(sum[mid]==t)
//printf(&%d\n&,ans);
for(int x=mid-1; x&=1&&sum[x]==t; x--)
if(sum[x]==t)
for(int x=mid+1; x&k&&sum[x]==t; x++)
if(sum[x]==t)
else if(sum[mid]&t)
int main()
int a,b,c,d;
while(~scanf(&%d%d%d%d&,&a,&b,&c,&d))
if(a&0&&b&0&&c&0&&d&0)
printf(&0\n&);
for(int i=1; i&=100; i++)
for(int j=1; j&=100; j++)
sum[k++]=a*i*i+b*j*j;
sort(sum,sum+k);
for(int i=1; i&=100; i++)
for(int j=1; j&=100; j++)
LL t=-(c*i*i+d*j*j);
printf(&%I64d\n&,ans*16);
#include &stdio.h&
#include &iostream&
#include &string.h&
const int maxn=1000005;
int vis[2000005];
int main()
int a,b,c,d;
while(~scanf(&%d%d%d%d&,&a,&b,&c,&d))
if(a&0&&b&0&&c&0&&d&0)
printf(&0\n&);
int ans=0;
memset(vis,0,sizeof(vis));
for(int i=1;i&=100;i++)
for(int j=1;j&=100;j++)
vis[i*i*a+b*j*j+maxn]++;
for(int i=1;i&=100;i++)
for(int j=1;j&=100;j++)
ans+=vis[-(c*i*i+d*j*j)+maxn];
printf(&%d\n&,ans*16);
参考知识库
* 以上用户言论只代表其个人观点,不代表CSDN网站的观点或立场
访问:237490次
积分:9420
积分:9420
排名:第1233名
原创:746篇
转载:10篇
评论:49条
(1)(5)(4)(4)(3)(4)(4)(8)(8)(22)(21)(9)(23)(30)(38)(40)(30)(28)(28)(33)(30)(57)(43)(66)(62)(47)(59)(45)(2)MC1496DG中文资料_图文_百度文库
两大类热门资源免费畅读
续费一年阅读会员,立省24元!
MC1496DG中文资料
||暂无简介
电子元器件行业,实体市场,全程保障|
总评分0.0|
阅读已结束,如果下载本文需要使用2下载券
想免费下载本文?
下载文档到电脑,查找使用更方便
还剩11页未读,继续阅读
你可能喜欢}

我要回帖

更多关于 求一黑客高手 的文章

更多推荐

版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。

点击添加站长微信