NOIP普与组解题报告

1、wordNOIP2014普与组复赛解题报告本人是潍坊一中的wyw，69级，今年高一，现在马上就要NOIP了， 打算把历年的NOIP普与、提高组题目都做一下， 然后写写解题报告这个报告主要是给初中同学看的，所以我会写的详细一点Prolem 1 珠心算测试(count)这道题其实很简单， 意思就是说给你一些数a1,a2,a3,a4.an，然后让你回答有多少个A+B=CA B C满足(回答C的数量，而不是等式的数量)方法一那么有一种很明显的做法就是三层循环枚举C、A、B，注意：C是在最外层，假设找到了一个A和一个B，满足上述等式，如此C是一个符合要求的解，这时ans+，并且退出当前枚举，枚举下一个C，这种算法的时间复杂度是O(N3)而我当时没想到这个算法，因为有更好用而且简单更不容易出错的解法，方法二两重循环，分别枚举i=1.n,j=i+1.n，如果ai+aj这个数在集合中存在，那么youai+ajtrue，然后再从a1到an做一次扫描，只要youai，ans+这个算法的好处在于它很好写，不用退出什么的，也不用注意循环的顺序，而且时间复杂度是O(N2)代码(方法2)：#includeusin

2、g namespace std;int n, a101, i, j, count;bool you20001=false;int main() freopen(count.in,r,stdin); freopen(count.out,w,stdout); scanf(%d,&n); for(i=1;i=n;i+)scanf(%d,&ai); for(i=1;in;i+) for(j=i+1;j=n;j+) you ai+aj =true; count=0; for(i=1;i=n;i+) count += you ai ; printf(%dn,count); return 0;在此征求一下大神的意见，如有更快的做法，敬请奉上小结：这道题很简单，但很多人没有做对的原因就是没有好好理解题意，但是根本原因其实还在于心态太骄傲了，认为是第一题就可以轻视，这样是不好的，水题我们更要做好啊，你想想同样是100分，这100分多么好拿，所以是水题、越该放平心态，细心地做。当时我正是由于重视2013年第一题爆零的教训，用了整整15分钟才做好，最后得了100分Problem 2 比例简化这道题目是说，给

3、定A和B，求解一组A和B，满足以下条件：ABAB00A,BLA和B互质首先，想一个总体的框架：我们发现L100，因此可以枚举A和B，然后判断是否AB满足上述条件，并且打擂台求比值最小的一组就行了，打擂台的复杂度是O(1)。设验证的复杂度为O(k)，如此总的算法的复杂度为O(kL2)，其中L2是104，所以我们只要保证k的大小在100以就一定没有问题。现在要求两个分数的差值，该怎么办呢？高精除！很多人一下就想到了，当时我在赛场上就是这么想的，但是又仔细一考虑。首先，高精除有风险，而且如果我是出题者的话，我一定会卡高精除，第二，高精除的编程复杂度很高，很容易出错而且耗时间于是我重新读题，找寻一些特殊的切入点，终于看到了这个东西：1A,B106，我的脑袋里瞬间就萌生出一种想法：模拟手动比拟分数就是说如果你要比拟两个分数，就先把他们通分，然后比拟分子的大小，如ab和cd比拟，先把它们化成adbd和bcbd的形式，然后比拟ad和bc的大小，而在整个枚举的过程中，你最大的情况只需要比拟AB和AB的大小，而且他们分母的乘积最大是108，到此，问题就完美地解决了！贴上代码：#include#inclu

4、deusing namespace std;long A,B,a,b,L,besta,bestb;long long cha_zi, cha_mu, best_cha_zi, best_cha_mu=-1, t1, t2;void Minus(long long z1, long long m1, long long z2, long long m2, long long &cz, long long &cm) z1=z1*m2; z2=z2*m1; m1=m2=m1*m2; cm=m1; cz=z1-z2;bool huzhi(int x, int y) int max, i; if(xy)max=x; else max=y; for(i=2; i*i A B L; for(a=1;a=L;a+) for(b=1;b=0) Minus(best_cha_zi,best_cha_mu,cha_zi,cha_mu,t1,t2); if(t10 | best_cha_mu=-1) best_cha_zi=cha_zi; best_cha_mu=cha_mu; besta=a; bestb=

5、b; cout besta bestb endl; return 0;这段代码是我初中时写的，有不足之处还请见谅。小结此道题放在第二个挺适宜，特点是代码好写，但方法不是特别好想(与历年相比)，只要按部就班一步一步地来，这道题还是很容易的，我的分数是100分Problem 3 螺旋矩阵当我看到这道题的时候，有一种很熟悉的感觉。然后我就想：NOIP怎么会考这么简单的题目？然后。就用了模拟的方法，调了很长时间，但是结果很惨，爆零了(因为直接开了30000*30000的数组)，到现在我也不明白当时为什么那么傻。好了回归正题，这道题是有技巧的观察这个矩阵123412 13 14511 16 15610987想想我们模拟的时候是1 2 3 4，然后转弯5 6 7，然后转弯8, 9, 10以此类推，其实我们走了很多不必要的路，比如从1到4，我们可以直接加3，然而怎样知道应该加上几呢？试一试：1+3=44+3=77+3=1010+2=1212+1=1313+1=1414+1=1515+1=1616+0=0咦？有规律！对于每个“圈，比如说从1到12，这里面的规律是可以找到的，从1开始，依次加3、3、3、

6、2，而从一个圈到下一个圈的时候，横坐标要+1，然后是+1、+1、+1、+0，规律很容易看出，从这个“圈的左上角开始，依次加k、k、k、k-1(要搞明白横纵坐标)，然而k就是上一个“圈的k-2得到的，到此问题就解决了代码：#include#includeusing namespace std;int n,I,J,i,j,k,t,clk;long x;int main() freopen(matrix.in,r,stdin); freopen(matrix.out,w,stdout); scanf(%d%d%d,&n,&I,&J); x=0; i=1; j=0; for(k=0;kn/2+n%2;k+) if(i!=I) j=j+(n-2*k); x=x+(n-2*k); else x=x+(J-j); break; if(j!=J) i=i+(n-2*k-1); x=x+(n-2*k-1); else x=x+(I-i); break; if(i!=I) j=j-(n-2*k-1); x=x+(n-2*k-1); else x=x+(j-J); break; if(j!=J) i=i-(n-2*k-2); x=x+(n-2*k-2); else x=x+(i-I); break; return 0;小结说白了，这道题还是在模拟，只不过换了种方式来模拟，参加了一些小小的优化，我觉得这道题的坑度等级还是很高的，它让人看了有种很想当然的感觉，会情不自禁地认为：“这道题我会，结果很多人都爆零了，真是惨痛的教训啊！另外，从这道题中我学会了一种方法，那就是像这种数字大规模出现的题目应该手动写写，找找规律，这样有助于解决问题Problem 4 子矩阵这道题要好好说说给出如下定义：子矩阵：从一个矩阵当中选取某些行和某些列交叉位置所组成的新矩阵保持行与列的相对顺序被称为原矩阵的一个子矩阵。例如，下面左图中选取第 2、4 行和第 2、4、

《NOIP普与组解题报告》由会员re****.1分享，可在线阅读，更多相关《NOIP普与组解题报告》请在金锄头文库上搜索。