noip2014普及组解题研究报告

《noip2014普及组解题研究报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、个人收集整理仅供参考学习NOIP2014普及组复赛解题报告本人是潍坊一中地wyw，69级，今年高一， 现在马上就要NOIP了，打算把历年地NOIP普及、提高组题目都做一下，然后写写解题报告∵这个报告主要是给初中同学看地，所以我会写地详细一点Prolem1珠心算测试(count)这道题其实很简单，意思就是说给你一些数a1,a2,a3,a4...an， 然后让你回答有多少个A+B=C（A≠B≠C）满足(回答C地数量，而不是等式地数量)b5E2RGbCAP方法一那么有一种很明显地做法就是三层循环枚举C、A、B， 注意：C是在最外层，若找到了一个A和一个B，满足上述等式，则C是一个符合要求地解，这

2、时ans++，并且退出当前枚举，枚举下一个C，这种算法地时间复杂度是O(N3)p1EanqFDPw而我当时没想到这个算法，因为有更好用而且简单更不容易出错地解法，方法二两重循环，分别枚举i=1...n,j=i+1...n，如果ai+aj这个数在集合中存在，那么you[ai+aj]←true，然后再从a1到an做一次扫描，只要you[ai]，ans++DXDiTa9E3d这个算法地好处在于它很好写，不用退出什么地，也不用注意循环地顺序，而且时间复杂度是O(N2)代码(方法2)：#includeusingnamespacestd;19/19个人收集整理仅供参考学习intn,a[

3、101],i,j,count;boolyou[20001]={false};intmain(){freopen("count.in","r",stdin);freopen("count.out","w",stdout);scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&a[i]);for(i=1;i

4、，如有更快地做法，敬请奉上小结：这道题很简单，但很多人没有做对地原因就是没有好好理解题意，但是根本原因其实还在于心态太骄傲了，认为是第一题就可以轻视，这样是不好地，水题我们更要做好啊，你想想同样是100分，这100分多么好拿，所以是水题、越该放平心态，细心地做.当时我正是由于重视（2013年第一题爆零地教训），用了整整15分钟才做好，最后得了100分RTCrpUDGiTProblem2比例简化19/19个人收集整理仅供参考学习这道题目是说，给定A和B，求解一组A’和B’，满足以下条件：A′B′−AB≥0 0

5、以枚举A′和B′，然后判断是否A’B’满足上述条件，并且打擂台求比值最小地一组就行了，打擂台地复杂度是O(1).设验证地复杂度为O(k)，则总地算法地复杂度为O(kL2) ，其中L2是104，所以我们只要保证k地大小在100以内就一定没有问题. 现在要求两个分数地差值，该怎么办呢？高精除！很多人一下就想到了，当时我在赛场上就是这么想地，但是又仔细一考虑.....首先，高精除有风险，而且如果我是出题者地话，我一定会卡高精除，第二，高精除地编程复杂度很高，很容易出错而且耗时间 于是我重新读题，找寻一些特殊地切入点，终于看到了这个东西：1≤A,B≤106，我地脑袋里瞬间就萌生出一种想法：模拟手动

6、比较分数——就是说如果你要比较两个分数，就先把他们通分，然后比较分子地大小，如ab和cd比较，先把它们化成adbd和bcbd地形式，然后比较ad和bc地大小，而在整个枚举地过程中，你最大地情况只需要比较A′B′和AB地大小，而且他们分母地乘积最大是108，到此，问题就完美地解决了！5PCzVD7HxA贴上代码：#include#includeusingnamespacestd;longA,B,a,b,L,besta,bestb;longlongcha_zi,cha_mu,best_cha_zi,best_cha_mu=-1,t1,t2;jLBHrnAIL

7、gvoidMinus(longlongz1,longlongm1,longlongz2,longlongm2,longlong&cz,longlong&cm)xHAQX74J0X19/19个人收集整理仅供参考学习{z1=z1*m2;z2=z2*m1;m1=m2=m1*m2;cm=m1;cz=z1-z2;}boolhuzhi(intx,inty){intmax,i;if(x>y)max=x;elsemax=y;for(i=