noip2014普及组复赛题解

《noip2014普及组复赛题解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、余姚中学罗方炜1.珠心算测验注意看清题意：其中有多少个数，恰好等于集合中另外两个(不同的)数之和。这样的题意加上100的规模，建议暴力3个for:#include#include#include#includeusingnamespacestd;intn;inta[105];intmain(){freopen("count.in","r",stdin);freopen("count.out","w",stdout);scanf("%d"

2、,&n);for(inti=1;i<=n;i++){scanf("%d",&a[i]);}sort(a+1,a+n+1);intres=0;for(inti=1;i<=n;i++){intok=0;for(intj=1;j<=n&&!ok;j++)if(j!=i){for(intk=1;k<=n&&!ok;k++)if(a[k]!=a[j]){if(a[j]+a[k]==a[i])ok=1;}}res+=ok;}printf("%d",res);return0;}2.比例简化L很小，还是枚举，然后比较的话建

3、议用乘法比较，避免精度问题：#include#include#includeusingnamespacestd;intA,B,L;intgcd(inta,intb){if(b==0)returna;returngcd(b,a%b);}intmain(){freopen("ratio.in","r",stdin);freopen("ratio.out","w",stdout);scanf("%d%d%d",&A,&B,&L);intba=1000000,bb=

4、1;for(inti=1;i<=L;i++){for(intj=1;j<=L;j++){if(gcd(i,j)==1&&i*B>=j*A){4余姚中学罗方炜if(ba*j>=bb*i){ba=i,bb=j;}}}}printf("%d%d",ba,bb);return0;}1.螺旋矩阵没一圈的数量有规律的，最外面一圈(n-1)*4，然后每往里n-2，直到后要么只有一个点，要么4个点。所以可以先确定是在哪圈里，然后暴力走一圈就行：#include#include#includ

5、eusingnamespacestd;intn,x,y;intsolve(){scanf("%d%d%d",&n,&x,&y);intceng=min(x,n+1-x);ceng=min(ceng,min(y,n+1-y));intnum=0,len=n-1;for(inti=1;i

6、rnnum;for(inti=1;i<=len;i++){ny++;num++;if(nx==x&&ny==y)returnnum;}for(inti=1;i<=len;i++){nx++;num++;if(nx==x&&ny==y)returnnum;}for(inti=1;i<=len;i++){ny--;num++;if(nx==x&&ny==y)returnnum;}for(inti=1;i

7、}intmain(){4余姚中学罗方炜freopen("matrix.in","r",stdin);freopen("matrix.out","w",stdout);intres=solve();printf("%d",res);return0;}1.子矩阵可以用二进制状态枚举取了哪些列，然后对于行的选取，可以DP,预处理每一行的代价，任意两行之间的代价，那么dp[j][i]=min(dp[j][i],dp[k][i-1]+val[k][j]+dp[j][1]);代码写的不是很顺，为了调试写了很多输出注释语

8、句：#include#include#include#includeusingnamespacestd;intg[25][25],f[25][25],dp[25][25],val[25][25];intn,m,x,y,res;intcount(intv){intret=0;while(v){if(v&1)ret++