NOIP2012普及组复赛解题报告c++版本

信息学奥赛NOIP2012普及组解题报告（c++版本）第一题质因数分解,题目已知正整数n是两个不同的质数的乘积,试求出较大的那个质数,没什么技术含量,直接开个根号搜一遍就好了.另外不开根号会TLE导致得60分.1#includestdio.h2#includemath.h3intmain()4{5intn;6scanf(%d,&n);7for(inti=2,k=sqrt(n)+1;ik;++i)8if(n%i==0)9{10printf(%d\n,n/i);11break;12}13return0;14}第二题寻宝[题目]传说很遥远的藏宝楼顶层藏着诱人的宝藏。小明历尽千辛万苦终于找到传说中的这个藏宝楼，藏宝楼的门口竖着一个木板，上面写有几个大字：寻宝说明书。说明书的内容如下：藏宝楼共有N+1层，最上面一层是顶层，顶层有一个房间里面藏着宝藏。除了顶层外，藏宝楼另有N层，每层M个房间，这M个房间围成一圈并按逆时针方向依次编号为0，…，M-1。其中一些房间有通往上一层的楼梯，每层楼的楼梯设计可能不同。每个房间里有一个指示牌，指示牌上有一个数字x，表示从这个房间开始按逆时针方向选择第x个有楼梯的房间（假定该房间的编号为k），从该房间上楼，上楼后到达上一层的k号房间。比如当前房间的指示牌上写着2，则按逆时针方向开始尝试，找到第2个有楼梯的房间，从该房间上楼。如果当前房间本身就有楼梯通向上层，该房间作为第一个有楼梯的房间。寻宝说明书的最后用红色大号字体写着：“寻宝须知：帮助你找到每层上楼房间的指示牌上的数字（即每层第一个进入的房间内指示牌上的数字）总和为打开宝箱的密钥”。请帮助小明算出这个打开宝箱的密钥。这个题是个简单的模拟,但是出乎意料的恶心,当年做这个题的时候爆零,钛蒻了,总感觉这个比第三题难.1#includestdio.h2intx[10003][103],fjx[103];3boolk[10003][103];4intmain()5{6intn,m,s,t,key=0,turn;7scanf(%d%d,&n,&m);8for(inti=0,j;in;++i)9for(j=0;jm;++j)10scanf(%d%d,&k[i][j],&x[i][j]);11scanf(%d,&s);12key=0;13for(inti=0,j=s,h=0,fj=0;in;++i)14{15key=(key+x[i][s])%20123;16while(hm)17{18if(k[i][j]==1)19fjx[fj++]=j;20++h;21++j;22if(j==m)23j=0;24}25t=(x[i][s]-1)%fj;26s=fjx[t];27}28printf(%d\n,key);29return0;30}第三题摆花[题目]小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共m盆。通过调查顾客的喜好，小明列出了顾客最喜欢的n种花，从1到n标号。为了在门口展出更多种花，规定第i种花不能超过ai盆，摆花时同一种花放在一起，且不同种类的花需按标号的从小到大的顺序依次摆列。试编程计算，一共有多少种不同的摆花方案。据说是个多重背包...但是我直接写的DP...#includestdio.hinta[102],f[102];intmain(){intn,m,sum=0;scanf(%d%d,&n,&m);for(inti=1;i=n;++i)scanf(%d,&a[i]);f[0]=1;for(inti=1,j,k;i=n;sum=0,++i){for(j=m,sum=0;ja[i];f[j]=sum,sum=0,--j)for(k=j-a[i];k=j;sum%=1000007,++k)sum+=f[k];for(j=a[i],sum=0;j-1;f[j]=sum,sum=0,--j)for(k=0;k=j;sum%=1000007,++k)sum+=f[k];}printf(%d\n,f[m]);return0;}第四题文化之旅[题目]有一位使者要游历各国，他每到一个国家，都能学到一种文化，但他不愿意学习任何一种文化超过一次（即如果他学习了某种文化，则他就不能到达其他有这种文化的国家）。不同的国家可能有相同的文化。不同文化的国家对其他文化的看法不同，有些文化会排斥外来文化（即如果他学习了某种文化，则他不能到达排斥这种文化的其他国家）。现给定各个国家间的地理关系，各个国家的文化，每种文化对其他文化的看法，以及这位使者游历的起点和终点（在起点和终点也会学习当地的文化），国家间的道路距离，试求从起点到终点最少需走多少路。吵了很长时间的一道题,很多人说Floyd可以直接秒杀,DFS不行.但是有人构造出了卡死Floyd的数据,所以保险DFS比较好.另外要从终点开始搜,从原点会得60(TLE).另外CCF的数据太弱了,不考虑文化差异能得90...总之,这道题的数据比较弱,floyd可以过.但是真正完全AC的是深度优先搜索.1#includestdio.h2#includestdlib.h3intn,k,m,s,t,distance[101][101],culture[101],fight[101][101],search[101],p=0;4boolfound=false;5intmin(inta,intb)6{7return(ab?b:a);8}9voidDFS(inttarget)10{11boolCanInqueue=true;12intqueue[101]={0},tail=0;13search[++p]=target;14if(target==t)15{16found=true;17return;18}19for(inti=1,j;i=n;++i)20{21for(j=1;j=p;++j)22{23if(search[j]==i||culture[search[j]]==culture[i]||fight[culture[i]][culture[search[j]]]==1)24{25CanInqueue=false;26break;27}28}29if(distance[target][i]==1001)30CanInqueue=false;31if(CanInqueue)32queue[++tail]=i;33else34CanInqueue=true;35}36for(inti=1;i=tail;++i)37distance[s][queue[i]]=min(distance[s][queue[i]],distance[s][target]+distance[target][queue[i]]);38for(inti=1;i=tail;++i)39DFS(queue[i]);40return;41}42intmain()43{44for(inti=1,j;i101;++i)45for(j=1;j101;++j)46distance[i][j]=1001;47scanf(%d%d%d%d%d,&n,&k,&m,&s,&t);48for(inti=1;i=n;++i)49scanf(%d,&culture[i]);50for(inti=1,j;i=k;++i)51for(j=1;j=k;++j)52scanf(%d,&fight[i][j]);53for(inti=0,y,z,c;im;++i,distance[z][y]c?distance[y][z]=distance[z][y]=c:c=2147483646)54scanf(%d%d%d,&y,&z,&c);55DFS(s);56if(found)57printf(%d\n,distance[s][t]);58else59printf(-1\n);60return0;61}