NOIP2014普及组复赛解题报告

《NOIP2014普及组复赛解题报告》由会员分享，可在线阅读，更多相关《NOIP2014普及组复赛解题报告（15页珍藏版）》请在装配图网上搜索。

1、Prolem 1珠心算测试（count）这道题其实很简单，意思就是说给你一些数ai，a2,a3,a4.-an，然后让你回答有多少个A+B=C （A丰B丰C）满足（回答C的数量，而不是等式的数 量）方法一那么有一种很明显的做法就是三层循环枚举C、A、B，注意：C是在最外层，若找到了一个A和一个B，满足上述等式，则C是一个符合 要求的解，这时ans+,并且退出当前枚举，枚举下一个C,这种算法的时间复杂度是O（N3）而我当时没想到这个算法，因为有更好用而且简单更不容易出错的解法，方法二两重循环，分别枚举i=1n,j=i+1.n，如果ai+aj这个数在集合中存在，那么you%+ajtrue,然后再从a

2、】到a“做一次扫描，只要youaj，ans+这个算法的好处在于它很好写，不用退出什么的，也不用注意循环的顺序，而且时 间复杂度是O（N2）代码（方法2）：#include using namespace std;int n, a101, i, j, count;bool you20001=false;intmain()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+

3、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比例简化这道题目是说，给定A和B，求解一组A和B，

4、满足以下条件:AB-AB-00A,BWLA和B互质首先，想一个总体的框架：我们发现L100,因此可以枚举A,和B,，然后判断是否AB满足上述条件，并且打擂台求比值最小的一组就行了，打擂台的复杂度是0(1)。设验证的复杂度为O(k)，则总的算法的复杂度为O(kL2)，其中L2是104，所以我们只要保证k的 大小在100以内就一定没有问题。现在要求两个分数的差值，该怎么办呢？高精除！很多人一下就想到了，当时我在 赛场上就是这么想的，但是又仔细一考虑。首先，咼精除有风险，而且如 果我是出题者的话，我一定会卡高精除，第二，高精除的编程复杂度很高，很容易 出错而且耗时间于是我重新读题，找寻一些特殊的切入

5、点，终于看到了这个东西:1A,B106，我 的脑袋里瞬间就萌生出一种想法：模拟手动比较分数一就是说如果你要比较两个 分数，就先把他们通分，然后比较分子的大小，女臥和cd比较，先把它们化成adbd 和bcbd的形式，然后比较ad和bc的大小，而在整个枚举的过程中，你最大的情况 只需要比较AB，和AB的大小，而且他们分母的乘积最大是108，到此，问题就完美 地解决了！贴上代码：#include#includeusing namespace std;long A,B,a,b,L,besta,bestb;long long cha_zi, cha_mu, best_cha_zi, best_cha_m

6、u=4, t1, t2;longlvoid Minus(long long z1, long long m1, long long z2, ong 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)zi,chaMinus(best_cha_zi,best_cha_mu,cha mu,t1

7、,t2);if(t10 | best_cha_mu=-1)best_cha_zi=cha_zi; best_cha_mu=cha_mu;besta=a;bestb=b;这段代码是我初中时写的，有不足之处还请见谅。小结此道题放在第二个挺合适，特点是代码好写，但方法不是特别好想（与历年相比）， 只要按部就班一步一步地来，这道题还是很容易的，我的分数是100分Problem 3螺旋矩阵当我看到这道题的时候，有一种很熟悉的感觉。然后我就想:NOIP怎么会考 这么简单的题目？然后。就用了模拟的方法，调了很长时间，但是结果很惨, 爆零了（因为直接开了 30000*30000的数组），到现在我也不明白当时为

8、什么那么 傻。好了回归正题，这道题是有技巧的观察这个矩阵12 3 412 13 14 511 16 15 610 9 8 7想想我们模拟的时候是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、2，而从一个圈到下一个圈的时候，横坐标要+1，然后是+1、+1、+1、+

9、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()freopenmatrix.in,r,stdin);freopenmatrix.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+(2-k);x=x+(n-2*k);elsex=x+(

10、J-j);break;if(j!=J)i=i+(2-*k-1); x=x+(n-2*k-1);elsex=x+(I-i);break;if(i!=I)j=j-(2-*k-1); x=x+(n-2*k-1);elsex=x+(j-J);break;说白了，这道题还是在模拟，只不过换了种方式来模拟，加入了一些小小的优化， 我觉得这道题的坑度等级还是很高的，它让人看了有种很想当然的感觉，会情不自 禁地认为：“这道题我会”，结果很多人都爆零了，真是惨痛的教训啊！另外，从这道题中我学会了一种方法，那就是像这种数字大规模出现的题目应该手 动写写，找找规律，这样有助于解决问题Problem 4子矩阵这道题要

11、好好说说给出如下定义：子矩阵：从一个矩阵当中选取某些行和某些列交叉位置所组成的新矩阵（保持行与 列的相对顺序）被称为原矩阵的一个子矩阵。例如，下面左图中选取第2、4行和第2、4、5列交叉位置的元素得到一个2*3的 子矩阵如右图所示。相邻的元素：矩阵中的某个元素与其上下左右四个元素（如果存在的话）是相邻的。 矩阵的分值：矩阵中每一对相邻元素之差的绝对值之和。本题任务：给定一个n行m列的正整数矩阵，请你从这个矩阵中选出一个r行c 列的子矩阵，使得这个子矩阵的分值最小，并输出这个分值。93J33Id948741m4EH685697nRn的其中个2*3对于50%的数据，1 n 12,1 m 12,矩阵

12、中的每个元素1 aij 20；对于100%的数据，1 n 16,1 m 16,矩阵中的每个元素1 aij 1000,1 r n, 1 c m这道题乍一眼看来就是爆搜，然而爆搜要枚举行和列，枚举的次数最大约是8! 8! =403202=1625702400,很明显超时，但是我们发现只枚举一层为8!=40320还是很小的，因此可以先枚举一 层，另一层再考虑别的方法想一想，如果选择哪些行已经确定了，那现在问题就变为在矩阵上选择一些列，使 得分值最大假如枚举上图所示的行，那么矩阵变成948746856922现在选一些列，使得分值最大，如果我选择了某一列，那么代价就是这列的纵向的 分值的差的绝对值之和，

13、加上它和上一个选择的列的横向对应的权值的绝对值之和, 那么现在这个问题就完全变成一个一维的问题了，我们把选择某一列付出的纵向的 代价叫做纵差(zci)，选择第i列和第j列所付出的横向的代价叫做hcij(ij),现在把它看成一个一维的数列，选择一个数，要付出的代价就是zci+hclasti, last表示上一个选择的数，而这一个是否具有子结构最优性质呢？设计状态fiU表示已经选择了 i个数，并且最后一个的编号为j所付出的最小代 价，那么有状态转移方程：fij=min(fi-1k+hckj)+zcj)(1iN,1jj,1kj)枚举的复杂度是O(N2)!，而DP的时间复杂度是O(N3),总的是 O(

14、N2)! N3)至此，问题解决了代码奉上#include#include#define oo 2000000000using namespace std;int N, M, R, C, zc17, hc1717, a1717;long ans, maxz;int abs(int n)if(n0)n=-n;return n;long min(long a, long b)if(a0)count+=z2;z=z1;return count;void qiu_zchc(long z)int i,j,k,num17,size,x;x1;size 0;while(z0)if(z%2=1)num+size

15、=x;x+;z=z1;memset(zc,0,sizeof(zc);for(i=1;i=M;i+)for(j=1;jsize;j+)zcia+b=s( a numj i - a numj1memset(hc,0,sizeof(hc);for(i=1;i=M;i+)for(j=i;j=M;j+)for(k=1;k=size;k+)hcji a+b=s( a numk i - a j);i );numk long DP(long z)qiu_zchc(z);long f1717, Min=oo, min;int i,j,k;for(i=1;i=M;i+)f1i=zci;for(i=2;i=C;i+

16、)for(j=1;j=M;j+)min=oo;for(k=1;kj;k+)if( fi-1k+hcjk min)min=fi-1k+h cjk;fij = min + zcj;for(j=1;j=M;j+)if(fCjMin)Min=fCj;return Min;int main()freopen submatrix.in,r,stdin);freopen submatrix.out,w,stdout);int i,j;long t, z;scanf(%d%d%d%d,&N,&M,&R,&C);for(i=1;i=N;i+)for(j=1;j=M;j+)scanf(”d,&aij);maxz 1;for(i=1;i=N;i+)maxz=maxz*2;maxz=maxz 1;ans=oo;for(z=1;z=maxz;z+)if(geshu(z)=R)t=DP(z);if(tans)ans=t;printf(%ldn,ans);return 0;