2015年第六届蓝桥杯省赛AB组全部编程题和部分填空题AC代码（仅不包含A组第十题灾后重建）

文章目录

方程整数解星系炸弹牌型总数手链样式饮料换购奖券数目加法变乘法移动距离生命之树打印大X

方程整数解

import java.io.*; import java.util.*; public class Main { private static final Class<int[]> Comparator = null; public static void main(String args[]) { int res = 0; Scanner in = new Scanner(System.in); int n; while(in.hasNext()) { int[][] arr = new int[100][3]; n = in.nextInt(); int f = 0, cnt = 0; for(int c = 1; c <= n/c; c++) { for(int b = 1; b <= c; b++) { int a = n - c*c - b*b; int t = (int) Math.sqrt(a); if(a >= 1 && t*t == a && a <= b*b && a <= c*c) { f = 1; arr[cnt][0] = t; arr[cnt][1] = b; arr[cnt][2] = c; cnt ++; } } } if(f != 1) { System.out.print("No Solution\n"); continue; } Arrays.sort(arr, 0, cnt, new Comparator<int[]>() { // 排序 public int compare(int[] a, int[] b) { if(a[0] != b[0]) return a[0] - b[0]; else if(a[1] != b[1]) return a[1] -b[1]; else if(a[2] != b[2]) return a[2] - b[2]; return 0; } }); for(int i = 0; i < cnt; i++) { for(int j = 0; j < 3; j++) System.out.print(arr[i][j] + " "); System.out.println(); } } } }

星系炸弹

import java.io.*; public class Main{ static BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out)); static int[] arr = {31,28,31,30,31,30,31,31,30,31,30,31}; public static int Int(String s) { return Integer.parseInt(s); } public static boolean IsLeapYear(int n) { if(n % 4 == 0 && n % 100 != 0 || n % 400 == 0) return true; else return false; } public static void main(String[] args) throws IOException { while(in.ready()) { String[] s = in.readLine().split(" "); int y, m, d, t; y = Int(s[0]); m = Int(s[1]); d = Int(s[2]); t = Int(s[3]); if(IsLeapYear(y)) arr[1] = 29; while(t != 0) { if(IsLeapYear(y)) arr[1] = 29; else arr[1] = 28; if(t + d <= arr[m-1]) { d += t; t = 0; } else { t -= arr[m-1] - d + 1; if(m < 12) m++; else{ m = 1; y ++; } d = 1; } //out.write(y + " " + m + " " + d + " " + t + "\n"); } String M = null,D = null; if(m <= 9) M = "0" + Integer.toString(m); else M = Integer.toString(m); if(d <= 9) D = "0" + Integer.toString(d); else D = Integer.toString(d); out.write(y + "-" + M + "-" + D + "\n"); out.flush(); } } }

牌型总数

import java.io.*; import java.util.*; public class Main { static int[] arr = new int[14]; static int ans = 0; public static void dfs(int n, int m) // 枚举每一种牌可以选择几张 { if(n == 13 && m <= 13) { ans ++; return ; } if(m > 13) return; for(int i = 1; i <= 4; i++) { dfs(n+i, m+1); } dfs(n, m+1); } public static void dfs1(int n, int m)// 枚举1~13中的组合 { if(n == 13) { ans ++; //System.out.print("\n"); // if(ans == 20) // System.exit(0); return ; } for(int i = m; i < 13; i++) { if(arr[i] < 4) { // System.out.print(i + " "); arr[i] ++; dfs1(n+1, i); arr[i] --; } } } public static void main(String args[]) { dfs(0, 0); //dfs1(0, 0); System.out.println(ans); } }

手链样式

package 蓝桥杯2015初赛; import java.io.*; import java.util.*; public class T_手链样式 { static TreeSet<String> set = new TreeSet<String>(); static char[] arr = {'a', 'b', 'c'}; static int[] st = new int[3]; static int res = 0; public static void dfs(int n, String s) { if(n == 12) { Iterator it = set.iterator(); int f = 0; while(it.hasNext()) { String t = (String)it.next(); if(t.indexOf(s) != -1) { f = 1; break; } } if(f == 1) return; // 已经有存在的 String ans = s + s; set.add(ans); set.add(new StringBuilder(ans).reverse().toString()); // 为了去重后面出现反转的情况 123 321 res ++; return ; } for(int i = 0; i < 3 ; i++) { if(st[i] < i + 3) { st[i] ++; dfs(n+1, s + arr[i]); st[i] --; } } } public static void main(String args[]) { dfs(0, ""); System.out.print(res); } }

饮料换购

import java.io.*; import java.util.Scanner; public class Main { // static BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out)); static Scanner input = new Scanner(System.in);; public static void main(String[] args) throws IOException { int n; while(input.hasNext()) { n = input.nextInt(); int res = n, num = 0; while(n >= 3) { res += n / 3; num += n % 3; n = n/3 + num; num = 0; } out.write(res + "\n"); out.flush(); } } }

##　垒骰子

import java.util.Arrays; import java.util.Scanner; public class Main{ static final int mod = 1000000000 + 7; public static void Int(long[][] a, long[][] b) { for(int i = 0; i < 6; i++) { Arrays.fill(b[i], 1); a[0][i] = 1; } } public static void mut_mul(long[][] a, long[][] b, long[][] c) // c = a*b { long[][] t = new long[6][6]; for(int i = 0; i < 6; i++) { Arrays.fill(t[i], 0); } for(int i = 0; i < 6; i++) { for(int j = 0; j < 6; j++) { for(int k = 0; k < 6; k++) { t[i][j] = (t[i][j] + (a[i][k] * b[k][j])%mod)%mod; } } } for(int i = 0; i < 6; i++) { c[i] = Arrays.copyOf(t[i], 6); } } public static void mut_qmi(long[][] a, long b, long[][] c) // a = a * c^b { while(b != 0) { if((b&1) == 1) { mut_mul(a, c, a); } mut_mul(c, c, c); b >>= 1; } } public static long qmi(long a, long b) // return a^b { long res = 1; while(b != 0) { if((b&1) == 1) { res = (res * a) % mod; } a = (a * a) % mod; b >>= 1; } return res; } public static void main(String[] args) { long[][] a = new long[6][6]; long[][] b = new long[6][6]; int[] op = {0,4,5,6,1,2,3}; Scanner in = new Scanner(System.in); int n, m; while(in.hasNext()) { Int(a, b); n = in.nextInt(); m = in.nextInt(); while(m --> 0) { int m1,m2; m1 = in.nextInt(); m2 = in.nextInt(); // 不能直接用冲突面处理关系矩阵， 不能让第一个骰子确定朝上面， 然后让第二个骰子确定朝下面 // 因为当骰子数大于3时， 第三个骰子势必要落在第二个骰子的上面，所以如果不确定第二个骰子朝上的面有几种可能，算出的答案就是错的 b[op[m1]-1][m2-1] = 0; // 4 2 b[op[m2]-1][m1-1] = 0; // 5 1 } mut_qmi(a, n-1, b); long res = 0; for(int i = 0; i < 6; i++) res = (res + a[0][i])%mod; res = res * qmi(4, n) % mod; System.out.println(res); } } }

奖券数目

public class Main{ public static void main(String args[]) { int res = 0; for(int i = 10000; i <= 99999; i++) { int t = i, f = 0; while(t != 0) { int r = t%10; t /= 10; if(r == 4) { f = 1; break; } } if(f == 0) res ++; } System.out.print(res); } }

加法变乘法

public class Main { public static void main(String args[]) { int t = 1225; for(int i = 1; i <= 48; i++) { for(int j = i+2; j <= 48; j++) { int n = t - (i+i+1) - (j+j+1); n += i*(i+1) + j*(j+1); if(n == 2015 && i != 10) System.out.print(i+"\n"); } } } }

移动距离

import java.util.Scanner; public class Main{ public static int gety(int n, int w) { int y1 = 0; if(((n-1)/w)%2 != 0) { y1 = w - ((n-1)%w+1); } else { y1 = (n-1)%w; } return y1; } public static void main(String args[]) { Scanner in = new Scanner(System.in); int w, n, m; while(in.hasNext()) { w = in.nextInt(); n = in.nextInt(); m = in.nextInt(); int x1, y1, x2, y2; x1 = (n-1)/w; x2 = (m-1)/w; y1 = gety(n, w); y2 = gety(m, w); System.out.print(Math.abs(x1 - x2) + Math.abs(y1-y2) + "\n"); } } }

生命之树

注意

递归问题：”本题用java写DFS解法则会运行错误，原因是栈溢出，java中递归函数最多递归10000层 而本题中结点数最大为100000，会爆栈 C/C++用此方法则无问题数据问题：本题题干中所描述的是查找最大非空节点集S中所有点的对应整数的最大和，所以对于全为负数的数据结果不应该为0， 但是只有输出0的时候才可以过测试点。

JAVA解法：拓扑序 将DFS转化为BFS，从叶结点开始遍历，以拓扑序的方式搜索整棵树，期间不断更新最大值

import java.io.*; import java.util.*; class DFS { static final int N = 100005, M = N*2; int[] e = new int[M], ne = new int[M], h = new int[N], w = new int[N]; int idx = 1; long res; public void add(int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx++; } public long dfs(int u, int f) { long sum = w[u]; for(int i = h[u]; i != 0; i = ne[i]) { int j = e[i]; if(j == f) continue; long d = dfs(j, u); if(d > 0) { sum += d; } } res = Math.max(res, sum); return sum; } public void slove() { Scanner in = new Scanner(System.in); int n = in.nextInt(); for(int i = 1; i <= n; i++) { w[i] = in.nextInt(); } for(int i = 0; i < n-1; i++) { int a, b; a = in.nextInt(); b = in.nextInt(); add(a, b); add(b, a); } dfs(1,-1); System.out.print(res + "\n"); } } class BFS { static final int N = 100005, M = N*2; int[] e = new int[M], ne = new int[M], h = new int[N], r = new int[N], st = new int[N]; long[] w = new long[N]; int idx = 1; long res = 0; Queue<Integer> q = new LinkedList<Integer>(); public void add(int a, int b) { e[idx] = b; ne[idx] = h[a]; h[a] = idx++; r[b]++; //入度加 1 } public void bfs() { while(!q.isEmpty()) { int f = q.poll(); st[f] = 1; for(int i = h[f]; i != 0; i = ne[i]) { int j = e[i]; if(st[j] == 0) { if(w[f] > 0) w[j] += w[f]; r[j] --; if(r[j] == 0) { q.add(j); } } } res = Math.max(res, w[f]); } } public void slove() { Scanner in = new Scanner(System.in); int n = in.nextInt(); for(int i = 1; i <= n; i++) { w[i] = in.nextLong(); } for(int i = 0; i < n-1; i++) { int a, b; a = in.nextInt(); b = in.nextInt(); if(a > b) add(a, b); else add(b, a); } for(int i = 1; i <= n; i++) { if(r[i] == 0) { q.add(i); } } bfs(); System.out.print(res + "\n"); } } public class Main { public static void main(String args[]) throws Exception { // DFS dfs1 = new DFS(); // dfs1.slove(); BFS bfs1 = new BFS(); bfs1.slove(); } }

打印大X

import java.util.Scanner; public class Main{ public static void main(String args[]) { Scanner in = new Scanner(System.in); while(in.hasNext()) { int m = in.nextInt(); // 笔的宽度 int n = in.nextInt(); // X的高度 int[][] arr = new int[1005][1005]; for(int i = 0; i < n; i++) { for(int j = i; j < i + m; j++) { arr[i][j] = 1; arr[i][n+m-j-2] = 1; } } for(int i = 0; i < n; i++) { for(int j = 0; j < n + m-1; j++) { if(arr[i][j] == 1) System.out.print("*"); else System.out.print("."); } System.out.print("\n"); } } } }