《蓝桥杯分类模拟题》由会员分享，可在线阅读，更多相关《蓝桥杯分类模拟题（51页珍藏版）》请在金锄头文库上搜索。
1、-# 本资料非原创，为了方便大家复习，特此整理。在此感谢提供试题的作者专题一：动态规划1.结点选择问题描述有一棵 n 个节点的树，树上每个节点都有一个正整数权值。如果一个点被选择了，则在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少？解题思路：这题模型是树形动态规划入门题目，dpi0表示该节点不被选择，dpi1表示该结点被选择。转移方程为:dpu1+=dpv0;/选择了u结点，则与它邻接的结点不选；dpu0+=ma*(dpv0，dpv1);不选择u结点，则与它邻接的结点选择结果最大的；应该特别注意：该题结点数量较大，应该选用邻接表存储边的关系1. #include2. #inclu
2、de3. #definema*(a,b)(a)(b)?(a):(b)4. #definema*n1000105. boolvisma*n;6. intdpma*n2;7. intfatherma*n;8. intheadma*n;9. intn;10. intt;11. structEdge12. 13. intto,ne*t;14. edge2*ma*n;15. voidadd(intu,intv)16. 17. edget.to=v;18. edget.ne*t=headu;19. headu=t+;20. 21. voidtreedp(intu)22. 23. visu=1;24. fo
3、r(inti=headu;i!=-1;i=edgei.ne*t)25. 26. intv=edgei.to;27. if(!visv)28. 29. treedp(v);30. dpu1+=dpv0;31. dpu0+=ma*(dpv1,dpv0);32. 33. 34. 35. voidinit()36. 37. t=0;38. memset(dp,0,sizeof(dp);39. memset(father,0,sizeof(father);40. memset(vis,0,sizeof(vis);41. memset(head,-1,sizeof(head);42. 43. intmai
4、n()44. 45. init();46. scanf(%d,&n);47. for(inti=1;i=n;i+)48. scanf(%d,&dpi1);49. introot=0;50. intbegin=1;51. for(inti=0;in-1;i+)52. 53. inta,b;54. scanf(%d%d,&a,&b);55. add(a,b);56. add(b,a);57. fatherb=a;58. if(root=b|begin)59. 60. root=a;61. 62. 63. while(fatherroot)64. root=fatherroot;65. treedp
5、(root);66. intans;67. ans=ma*(dproot0,dproot1);68. printf(%dn,ans);69. 2.K好数问题描述如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字，则我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4，L = 2的时候，所有K好数为11、13、20、22、30、31、33 共7个。由于这个数目很大，请你输出它对1000000007取模后的值。解题思路：dpij表示第i位为j的时候的个I好数个数；因此有转移方程：dpij=dpi-1m+dpij;m为上一位的值，满足的条件应为m-j的绝对值不为1.即不相
6、邻；应当注意的是：最后在求和的时候不能简单的统计dplm 0=mk;因为首位如果是0的话，其实不足L位了，所以0mk,也许有人会疑问这是不统计L位的0，不是第一位呀。其实仔细想想，是等效的。1. #include2. #include3. #definemod10000000074. #defineabs(a,b)(a)(b)?(a-b):(b-a)5. intdp110110;6. intmain()7. 8. intk,l;9. memset(dp,0,sizeof(dp);10. scanf(%d%d,&k,&l);11. for(inti=0;ik;i+)12. dp1i=1;13.
7、for(inti=2;i=l;i+)14. 15. for(intj=0;jk;j+)16. 17. for(intm=0;mk;m+)18. 19. if(abs(m,j)!=1)20. dpij=(dpij%mod+dpi-1m%mod)%mod;21. 22. 23. 24. intans=0;25. for(inti=1;ik;i+)26. ans=(ans%mod+dpli%mod)%mod;27. printf(%dn,ans);28. 3. 导弹拦截-动态规划问题描述*国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意
8、的高度，但是以后每一发炮弹都不能高于前一发的高度。*天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。解题思路：因为要求后面每一发炮弹都不能高于前一发，故问题就转化成了求最长不下降子序列，用n2算法即可。对于第二问，遇到高于前一项的，便要准备另外一套系统，而且要全部拦截，故求严格的最长上升子序列。dpi表示以i位置结束的最长不下降子序列；dpsi表示以i位置结束的最长上升子序列；注意初始化
9、问题，对于每一个dpi，最少也会包括自身，所以都要初始化为1；cppview plaincopy1. #include2. #include3. #include4. #definema*(a,b)(a)(b)?(a):(b)5. usingnamespacestd;6. intmain()7. 8. intdp10010;9. intdps10010;10. memset(dp,0,sizeof(dp);11. memset(dps,0,sizeof(dps);12. intn=0;13. intnum10010;14. int*;15. while(scanf(%d,&*)16. num+
10、n=*;17. for(inti=1;i=n;i+)18. dpi=dpsi=1;19. for(inti=1;i=n;i+)20. 21. for(intj=1;ji;j+)22. 23. if(numinumj)28. 29. dpsi=ma*(dpsi,dpsj+1);30. 31. 32. 33. intans1=0,ans2=0;34. for(inti=1;i=n;i+)35. 36. ans1=ma*(ans1,dpi);37. ans2=ma*(ans2,dpsi);38. 39. printf(%dn,ans1);40. printf(%dn,ans2);41. 4. 乘积最
11、大问题描述今年是国际数学联盟确定的“2000世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰90周年。在华罗庚先生的家乡*金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友*Z也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：设有一个长度为N的数字串，要求选手使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1个部分的乘积能够为最大。同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：有一个数字串：312，当N=3，K=1时会有以下两种分法：3*12=3631*2=62这时，符合题目要求的结果是：31*2=62现在，请你帮助你的好朋友*Z设计一个
12、程序，求得正确的答案。输入格式程序的输入共有两行：第一行共有2个自然数N，K（6N40，1K6）第二行是一个长度为N的数字串。解题思路：动态规划的经典题目。i从0开始；ansij表示长度为i+1的数字串插入j个*号能够获得的最大的乘积；ansi0显然是长度为i+1的数字串所对应的数字；状态转移方程：利用最优子结构的性质，如果在k个字符后插入第j个*取得最大值，则anskj-1也是最大，因此只需要在确定i,j的情况下，只需要枚举最后一个*号的位置即可ansij=ma*(ansij,anskj-1*(k+1个位置起，i-k个长度字符串所对应的数字)；0=ki;1=j=min(i,*最大的个数)；c
13、ppview plaincopy1. #include2. #include3. #include4. #include5. #include6. usingnamespacestd;7. intchange(stringa)8. 9. intans=a0-0;10. intlen=a.length();11. for(inti=1;imn;21. strings;22. cins;23. longlongans457;24. memset(ans,0,sizeof(ans);25. for(inti=1;i=m;i+)26. ansi-10=change(s.substr(0,i);27. for(inti=0;im;i+)28. 29. intt=min(i,n)
