NOIP2014复赛普及组第一题题解
更新时间:2024-06-30 12:34:01 阅读量: 综合文库 文档下载
活动园地
NOIP2014复赛普及组第一题题解
原题
一、 题目简化:求N个正数中有多少个数是这些数中其它两个数的和。
3<=N<=100; 每个正整数M:1<=M<=10000;
二、 过程分析:试题显然可以分成三个步骤求解:1、先求出N个数中每两个数的
和;2、判断这些和中有没有重复,重复的数只留下一个;3、N个数中的每一个数都与这些和比较,若相等些记下,比较完成,即得其解。
三、 算法与策略:三个步骤都采用一一列举所有可能的方法,是典型的枚举。 四、 程序设计思路:1、一维数组A存放N个数,一维数组B存放两两相加的和;
求和、判断重复、比较两数是否相等,都采用两重循环,i 控制外循环,j 控制内循环,k表示数组B的下标变化,ans表示题目答案。
数组a最多100个元素,考虑到用循环,为防止下标越界,可适当把数组开大一些,a[0..101];数组b中元素数是N个数两个数两两相加的和的个数,由于N最大是100,所以和的个数最多是1+2+3+……99=4950个,则b[0..5000] 五、程序设计: program count; var
a:array[0..101] of longint; b:array[0..5000] of longint; n,ans,i,j,k:longint; begin
assign(input,'count.in'); reset(input);
assign(output,'count.out'); rewrite(output); readln(n); for i:=1 to n do
read(a[i]); fillchar(b,sizeof(b),0);
**下面开始步骤1:a中的数两两相加放在b中** k:=1;
for i:=1 to n-1 do for j:=i+1 to n do begin
b[k]:=a[i]+a[j]; inc(k); end;
**下面开始步骤2:筛掉b中的重
复数据:**
for i:= 1 to (k-1)-1 do for j:=i+1 to k-1 do begin if b[i]:=b[j] then b[j]:=0; end;
**下面开始步骤3:比较a数组中有多少个数与b数组中的数相等:** ans:=0; for i:=1 to n do
for j:=1 to k-1 do begin if (a[i]=b[j]) then inc(ans); end;
**比较结束,结果已得出,下面输出结果,关闭文件,结束程序** write(ans); close(input) close(output); end.
n?1i?1六、时间复杂度分析:三个步骤采用了三个双重循环,每个双重循环运行约N·?i 次,若N=100,则整个程序运行约150万次操作,T(N)=0(N3)理论上讲,还可以忍受。
第二步的任务是排除B中的重复数值,以免第三步统计时重复计算,使结果不正确。从原题提供的数据来看,N个正整数中每个都不超过10000,这就是说,B中的最大数值就是20000,开一个[1..20000]的数组,A中两个数的和等于几,就把这个数放在B中的第几个位置上,即:让B数组的下标跟A中这两个数的和相同。写到这里,如果你还不明白,那,那算我没说明白,举个粟子捋一捋:3+5=8,则B[8]:=8;1500+1000=2500 则这个结果放在B[2500]中,即:B[2500]:=2500;问:如果有2+6=8,这个结果放在哪里?这样处理,B数组中还有重复数据吗?答案是:肯定有,那些重复的都是些啥?答:0
这样,上面的第二步骤就省去了…… 优化后的程序:
输入数据运行一下验证程序:
如果你还有更好的算法,请你告诉我,以及,其它人……
正在阅读:
NOIP2014复赛普及组第一题题解06-30
高等钢结构试卷2013A09-21
管理会计习题集1(本科)06-07
第五章 工程造价各阶段计价与控制04-23
桩基监理交底记录07-18
江苏省徐州市2019年中考化学复习 题型突破(四)物质的转化与推断练习05-26
综采队设备使用管理制度 wps11-10
- 小学生造句大全
- 增压泵投资项目可行性研究报告(模板)
- 高中语文人教版粤教版必修1-5全部文言文知识点归纳
- 两学一做专题民主生活会组织生活会批评与自我批评环节个人发言提
- 管理处环境保洁工作操作标准作业指导书
- 2012六一儿童节活动议程 - 图文
- 移树申请报告
- 《贵州省市政工程计价定额》2016定额说明及计算规则
- 计算机长期没有向WSUS报告状态
- 汉语拼音教学策略研究
- 发展西部领先的航空货运枢纽
- 司法所上半年工作总结4篇
- 如何提高银行服务水平
- 发电厂各级人员岗位职责
- 丰田汽车的外部环境分析
- 2017—2018年最新冀教版四年级数学下册《混合运算》教案精品优质
- 中建八局样板策划 - 图文
- 戚安邦《项目管理学》电子书
- 2015年高级项目经理笔记
- 弯桥的设计要点
- 题解
- 复赛
- 普及
- NOIP2014
- 对口单招机械基础期末试卷
- 公共政策试题
- 食品购销合同
- 谢桥矿2013年-2015年典型事故案例
- 医学伦理学案例
- 民法教学同步练习题
- 陈玉琴大师教你认清人体真相--做自己的良医 - 图文
- 七年级生物上册期中考试卷及答案集
- 2012河北省政法干警职位目录 - 图文
- 大跨钢结构动力特性
- 2018届四川省双流中学高三上学期9月月考历史试题
- 矿大毕业设计-单曲柄往复式给煤机设计
- 2011-2013年福建省及全国印染布季度产量数据统计报告
- 申请备案产品的说明书和生产加工工艺资料;企业原辅料、食品添加
- 室外燃气管道工程设计、施工及验收标准
- 财务分析各章习题集答案
- 个人所得税算方法
- 年度安全生产目标管理责任书
- 2010年高考数学(山东卷)(文)
- 利用计算机引发小学生习作兴趣论文