noip2014普及组解题报告

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

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

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

3、(){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分Problem2比例简化这道题目是说，给定A和B，求解一组A’和B’，满足以下条件：A′B′−AB≥0 0

5、证的复杂度为O(k)，则总的算法的复杂度为O(kL2) ，其中L2是104，所以我们只要保证k的大小在100以内就一定没有问题。 现在要求两个分数的差值，该怎么办呢？高精除！很多人一下就想到了，当时我在赛场上就是这么想的，但是又仔细一考虑。。。。。首先，高精除有风险，而且如果我是出题者的话，我一定会卡高精除，第二，高精除的编程复杂度很高，很容易出错而且耗时间 于是我重新读题，找寻一些特殊的切入点，终于看到了这个东西：1≤A,B≤106，我的脑袋里瞬间就萌生出一种想法：模拟手动比较分数——就是说如果你要比较两个分数，就先把他们通分，然后比较分子的大小，如ab和cd比较，先把它们

6、化成adbd和bcbd的形式，然后比较ad和bc的大小，而在整个枚举的过程中，你最大的情况只需要比较A′B′和AB的大小，而且他们分母的乘积最大是108，到此，问题就完美地解决了！贴上代码：#include#includeusingnamespacestd;longA,B,a,b,L,besta,bestb;longlongcha_zi,cha_mu,best_cha_zi,best_cha_mu=-1,t1,t2;voidMinus(longlongz1,longlongm1,longlongz2,longlongm2,longlong&

7、cz,longlong&cm){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=2;i*i<=max;i++){if(x%i==0&&y%i==0)returnfalse;}returntrue;}intmain(){freopen("ratio.in","r",stdin);freopen("ratio.out","w",stdout);ci