蓝桥杯2013决赛JAVA本科B组试题.doc

试题一：公式求值问题描述输入n, m, k，输出下面公式的值。其中C_nm是组合数，表示在n个人的集合中选出m个人组成一个集合的方案数。组合数的计算公式如下。输入格式输入的第一行包含一个整数n；第二行包含一个整数m，第三行包含一个整数k。输出格式计算上面公式的值，由于答案非常大，请输出这个值除以999101的余数。样例输入313样例输出162样例输入201010样例输出359316数据规模和约定对于10%的数据，n10，k3；对于20%的数据，n20，k3；对于30%的数据，n1000，k5；对于40%的数据，n107，k10；对于60%的数据，n1015，k 100；对于70%的数据，n10100，k200；对于80%的数据，n10500，k 500；对于100%的数据，n在十进制下不超过1000位，即1nn)return1;13. if(n=m|m=0)return1;14. if(mn-m)m=n-m;15. longtmpi=1,tmpn=1,s1=1,s2=1,ans=1;16. for(inti=1;i=1;32. x=(x*x)%999101;33. 34. 35. longresult=x%999101;36. n=1;37. while(n!=0)38. x=(x*x)%999101;39. if(n&1)!=0)40. result=result*x%999101;41. n=1;42. 43. returnresult;44. 45. publicstaticvoidmain(Stringargs)46. Scannersc=newScanner(System.in);47. BigIntegern=newBigInteger(sc.nextLine();48. BigIntegerm=newBigInteger(sc.nextLine();49. intk=Integer.parseInt(sc.nextLine();50. longstart=System.currentTimeMillis();51. BigIntegermd=newBigInteger(999101);52. longCnm=lucas(n,m,md).longValue()%999101;53. longsum=0;54. if(Cnm!=0)55. inta=newintkk;56. inth=1;57. for(inti=0;ik;i+)58. for(intj=0;j=h)60. aij=0;61. else62. if(j=0|j=h-1)63. aij=1;64. else65. aij=(ai-1j-1*(h-j)+ai-1j)%999101;66. 67. 68. 69. h+;70. 71. longm1=1,n1=1;72. longx=n.subtract(newBigInteger(k+).mod(md.subtract(BigInteger.ONE).longValue();73. longn3=pow1(2,x);74. for(inti=k-1;i=0;i-)75. n1=n3*pow1(2,i)%999101;76. m1=m1*(n.subtract(newBigInteger(k-1-i)+).mod(md).longValue()%999101;77. sum=(sum+m1*ak-1i*n1)%999101;78. 79. sum=sum*Cnm%999101;80. 81. System.out.println(sum);82. longend=System.currentTimeMillis();83. 84.85.86. 试题二：九宫重排如下面第一个图的九宫格中，放着 18 的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动，可以形成第二个图所示的局面。我们把第一个图的局面记为：12345678.把第二个图的局面记为：123.46758显然是按从上到下，从左到右的顺序记录数字，空格记为句点。本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。输入格式输入第一行包含九宫的初态，第二行包含九宫的终态。输出格式输出最少的步数，如果不存在方案，则输出-1。样例输入12345678.123.46758样例输出3样例输入13524678.46758123.样例输出22比较经典的搜索题，可以直接搜索或者使用双向搜索优化。1. importjava.io.*;2. importjava.util.*;3. publicclassMain4. staticMaphm1=newHashMap();5. staticMaphm2=newHashMap();6. publicstaticvoidmain(Stringargs)throwsIOException7. BufferedReaderbf=newBufferedReader(newInputStreamReader(System.in);8. Stringstart=bf.readLine();9. Stringend=bf.readLine();10. chara=newchar33;11. charb=newchar33;12. intc=0,x1=0,y1=0,x2=0,y2=0;13. for(inti=0;i3;i+)14. for(intj=0;j3;j+)15. aij=start.charAt(c);16. bij=end.charAt(c);17. c+;18. if(aij=.)19. x1=i;20. y1=j;21. 22. if(bij=.)23. x2=i;24. y2=j;25. 26. 27. 28. Nodenode1=newNode(0,x1,y1,a);29. Nodenode2=newNode(0,x2,y2,b);30. 31. Queueqnode1=newLinkedList();32. Queueqnode2=newLinkedList();33. qnode1.add(node1);34. qnode2.add(node2);35. hm1.put(node1.gettu(),0);36. hm2.put(node2.gettu(),0);37. 38. System.out.println(bfs(qnode1,qnode2);39. 40. publicstaticintbfs(Queueq1,Queueq2)41. while(!q1.isEmpty()|!q2.isEmpty()42. 43. if(!q1.isEmpty()44. Nodenode=q1.poll();45. 46. intx=node.getX();47. inty=node.getY();48. if(hm2.containsKey(node.gettu()49. returnnode.getSum()+hm2.get(node.gettu();50. 51. if(x0)52. charc=node.getCopy();53. cxy=cx-1y;54. cx-1y=.;55. Nodenode2=newNode(node.sum+1,x-1,y,c);56. Strings=node2.gettu();57. if(hm2.containsKey(s)58. returnnode2.getSum()+hm2.get(node2.gettu();59. 60. if(!hm1.containsKey(s)61. hm1.put(s,node2.getSum();62. q1.add(node2);63. 64. 65. if(x0)80. charc=node.getCopy();81. cxy=cxy-1;82. cxy-1=.;83. Nodenode2=newNode(node.sum+1,x,y-1,c);84. Strings=node2.gettu();85. if(hm2.containsKey(s)86. returnnode2.getSum()+hm2.get(s);87. 88. if(!hm1.containsKey(s)89. hm1.put(s,node2.getSum();90. q1.add(node2);91. 92. 93. if(y0)116. charc=node.getCopy();117. cxy=cx-1y;118. cx-1y=.;119. Nodenode2=newNode(node.sum+1,x-1,y,c);120. Strings=node2.gettu();121. if(hm1.containsKey(s)122. returnnode2.getSum()+hm1.get(s);123. 124. if(!hm2.containsKey(s)125. hm2.put(s,node2.getSum();126. q2.add(node2);127. 128. 129. if(x0)145. charc=node.getCopy();146. cxy=cxy-1;147. cxy-1=.;148. Nodenode2=newNode(node.sum+1,x,y-1,c);149. Strings=node2.gettu();150. if(hm1.containsKey(s)151. returnnode2.getSum()+hm1.get(s);152. 153. if(!hm2.containsKey(s)154. hm2.put(s,node2.getSum();155. q2.add(node2);156. 157. 158. if(y2)159. charc=node.getCopy();160. cxy=cxy+1;161. cxy+1=.;162. Nodenode2=newNode(node.sum+1,x,y+1,c);163. Strings=node2.gettu();164. if(hm1.containsKey(s)165. returnnode2.getSum()+hm1.get(s);166. 167. if(!hm2.containsKey(s)168. hm2.put(s,node2.getSum();169. q2.add(node2);170. 171. 172. 173. 174. 175. 176. return-1;177. 178. 179. classNode180. intsum,x,y;181. charc=null;182. publicchargetCopy()183. charcopy=newchar33;184. 185. for(inti=0;i3;i+)186. for(intj=0;j3;j+)187. copyij=cij;188. 189. 190. returncopy;191. 192. publicStringgettu()193. StringBuffers=newStringBuffer();194. for(inti=0;i3;i+)195. for(intj=0;j3;j+)196. s.append(cij);197. 198. 199. returns.toString();200. 201. publicNode(intsum,intx,inty,charc)202. super();203. this.sum=sum;204. this.x=x;205. this.y=y;206. this.c=c;207. 208.