《蓝桥杯2013决赛java本科b组试题》由会员分享，可在线阅读，更多相关《蓝桥杯2013决赛java本科b组试题（11页珍藏版）》请在金锄头文库上搜索。
1、试题一：公式求值问题描述输入 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
2、 100；对于 70%的数据，n10100，k200；对于 80%的数据，n10500，k 500；对于 100%的数据，n 在十进制下不超过 1000 位，即 1nn) return 1;13. if(n=m| m=0) return 1;14. if(mn-m) m=n-m;15. long tmpi=1,tmpn=1,s1=1,s2=1,ans=1;16. for (int i = 1; i=1;32. x=(x *x)%999101;33. 34. 35. long result = x%999101;36. n=1;37. while (n!=0) 38. x=(x *x)%9991
3、01;39. if (n & 1)!=0)40. result =result*x%999101;41. n=1;42. 43. return result;44. 45. public static void main(String args) 46. Scanner sc = new Scanner(System.in);47. BigInteger n = new BigInteger(sc.nextLine();48. BigInteger m = new BigInteger(sc.nextLine();49. int k = Integer.parseInt(sc.nextLine
4、();50. long start = System.currentTimeMillis();51. BigInteger md = new BigInteger(999101);52. long Cnm=lucas(n, m,md).longValue()%999101;53. long sum = 0;54. if(Cnm!=0)55. int a = new intkk;56. int h = 1;57. for (int i = 0; i = h)60. aij =0;61. else 62. if (j = 0 | j = h - 1)63. aij = 1;64. else 65.
5、 aij = (ai - 1j - 1*(h - j)+ai - 1j)%999101;66. 67. 68. 69. h+;70. 71. long m1 = 1,n1 =1;72. long x=n.subtract(new BigInteger(k+).mod(md.subtract(BigInteger.ONE).longValue();73. long n3 = pow1(2,x);74. for (int i = k - 1; i = 0; i-) 75. n1=n3*pow1(2,i)%999101;76. m1 = m1*(n.subtract(new BigInteger(k
6、 - 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. long end = System.currentTimeMillis();83. 84.85.86. 试题二：九宫重排如下面第一个图的九宫格中，放着 18 的数字卡片，还有一个格子空着。与空格子相邻的格子中的卡片可以移动到空格中。经过若干次移动，可以形成第二个图所示的局面。我们把第一个图的局面记为：1234567
7、8.把第二个图的局面记为：123.46758显然是按从上到下，从左到右的顺序记录数字，空格记为句点。本题目的任务是已知九宫的初态和终态，求最少经过多少步的移动可以到达。如果无论多少步都无法到达，则输出-1。输入格式输入第一行包含九宫的初态，第二行包含九宫的终态。输出格式输出最少的步数，如果不存在方案，则输出-1。样例输入12345678.123.46758样例输出3样例输入13524678.46758123.样例输出22比较经典的搜索题，可以直接搜索或者使用双向搜索优化。1. import java.io.*;2. import java.util.*;3. public class Main
8、4. static Map hm1=new HashMap();5. static Map hm2=new HashMap();6. public static void main(String args) throws IOException7. BufferedReader bf=new BufferedReader(new InputStreamReader(System.in);8. String start=bf.readLine();9. String end=bf.readLine();10. char a=new char33;11. char b=new char33;12.
9、 int c=0,x1=0,y1=0,x2=0,y2=0;13. for(int i=0;i qnode1=new LinkedList();32. Queue qnode2=new LinkedList();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. public static int bfs(Queue q1,Queue
10、q2)41. while(!q1.isEmpty()|!q2.isEmpty()42. 43. if(!q1.isEmpty()44. Node node=q1.poll();45. 46. int x=node.getX();47. int y=node.getY();48. if(hm2.containsKey(node.gettu()49. return node.getSum()+hm2.get(node.gettu();50. 51. if(x0)52. char c=node.getCopy();53. cxy=cx-1y;54. cx-1y=.;55. Node node2=ne
11、w Node(node.sum+1,x-1,y,c);56. String s=node2.gettu();57. if(hm2.containsKey(s)58. return node2.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. char c=node.getCopy();81. cxy=cxy-1;82. cxy-1=.;83. Node node2=new Node(no
12、de.sum+1,x,y-1,c);84. String s=node2.gettu();85. if(hm2.containsKey(s)86. return node2.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. char c=node.getCopy();117. cxy=cx-1y;118. cx-1y=.;119. Node node2=new Node(node.sum+1,x-1,y,c);120. String s=node2.gettu();121. if(hm1.containsKey(s)122. return node2.getSum()+hm1.get(s);123. 124. if(!h
