1 好好学习

汤姆跟爷爷来中国旅游。一天，他帮助中国的小朋友贴标语。他负责贴的标语是分别写在四块红纸上的四个大字：“好、好、学、习”。但是汤姆不认识汉字，他就想胡乱地贴成一行。

    请你替小汤姆算一下，他这样乱贴，恰好贴对的概率是多少？

    答案是一个分数，请表示为两个整数比值的形式。例如：1/3 或 2/15 等。

如果能够约分，请输出约分后的结果。

    注意：不要书写多余的空格。

    请严格按照格式，通过浏览器提交答案。

注意：只提交这个比值，不要写其它附加内容，比如：说明性的文字。

1 / 12

2 埃及分数

古埃及曾经创造出灿烂的人类文明，他们的分数表示却很令人不解。古埃及喜欢把一个分数分解为类似： 1/a + 1/b 的格式。

    这里，a 和 b 必须是不同的两个整数，分子必须为 1

    比如，2/15 一共有 4 种不同的分解法（姑且称为埃及分解法）：

1/8 + 1/120

1/9 + 1/45

1/10 + 1/30

1/12 + 1/20

    那么， 2/45 一共有多少个不同的埃及分解呢（满足加法交换律的算同种分解）？ 请直接提交该整数（千万不要提交详细的分解式！）。

    请严格按照要求，通过浏览器提交答案。

    注意：只提交分解的种类数，不要写其它附加内容，比如：说明性的文字

7

 public class Main {

     public static void main(String[] args) {

         int count = 0;

         for(int a = 1;a < 2000;a++) {

             for(int b = 1;b < 2000;b++) {

                 if(45 * (a + b) == 2 * a * b) {

                     count++;

                     System.out.println("a = "+a+", b = "+b);

                 }

             }

         }

         System.out.println("count = "+count / 2);

     }

 }

3 金蝉素数

 考古发现某古墓石碑上刻着一个数字：13597，后研究发现：

    这是一个素数！

    并且，去掉首尾数字仍是素数！

    并且，最中间的数字也是素数！

    这样特征的数字还有哪些呢？通过以下程序的帮助可以轻松解决。请仔细阅读代码，并填写划线部分缺失的代码。

public class A

{

    static boolean isPrime(int n)

    {

        if(n<=1) return false;

        for(int i=2; i*i<=n; i++){

            if(n%i==0) return false;

        }

        return true;

    }

    static void f(int[] x, int k)

    {

        if(_____________________________){  // 填空位置

            if(isPrime(x[0]*10000 + x[1]*1000 + x[2]*100 + x[3]*10 + x[4]) &&

                isPrime(x[1]*100 + x[2]*10 + x[3]) &&

                isPrime(x[2]))

                System.out.println(""+x[0]+x[1]+x[2]+x[3]+x[4]);

            return;

        }

        for(int i=k; i<x.length; i++){

            {int tmp=x[k]; x[k]=x[i]; x[i]=tmp; }

            f(x,k+1);

            {int tmp=x[k]; x[k]=x[i]; x[i]=tmp; }

        }

    }

    static void test()

    {

        int[] x = {1,3,5,7,9};

        f(x,0);

    }

    public static void main(String[] args)

    {

        test();

    }

}

    请分析代码逻辑，并推测划线处的代码，通过网页提交。

    注意：仅把缺少的代码作为答案，千万不要填写多余的代码、符号或说明文字！！

k == x.length

4 横向打印二叉树

二叉树可以用于排序。其原理很简单：对于一个排序二叉树添加新节点时，先与根节点比较，若小则交给左子树继续处理，否则交给右子树。

    当遇到空子树时，则把该节点放入那个位置。

    比如，10 8 5 7 12 4 的输入顺序，应该建成二叉树如图1所示。

    本题目要求：根据已知的数字，建立排序二叉树，并在标准输出中横向打印该二叉树。

    输入数据为一行空格分开的N个整数。 N<100，每个数字不超过10000。

    输入数据中没有重复的数字。

    输出该排序二叉树的横向表示。 对应上例中的数据，应输出：

   |-12

10-|

   |-8-|

       |   |-7

       |-5-|

           |-4

    为了便于评卷程序比对空格的数目，请把空格用句点代替：

...|-12

10-|

...|-8-|

.......|...|-7

.......|-5-|

...........|-4

例如：

用户输入：

10 5 20

则程序输出：

...|-20

10-|

...|-5

再例如：

用户输入：

5 10 20 8 4 7

则程序输出：

.......|-20

..|-10-|

..|....|-8-|

..|........|-7

5-|

..|-4

资源约定：

峰值内存消耗（含虚拟机） < 64M

CPU消耗  < 1000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。

注意：不要使用package语句。不要使用jdk1.6及以上版本的特性。

注意：主类的名字必须是：Main，否则按无效代码处理。

 import java.util.Scanner;

 public class Main {

     public static int begin;

     static class Tree {

         public int value;

         public int left;

         public int right;

         public Tree(int value, int left, int right) {

             this.value = value;

             this.left = left;

             this.right = right;

         }

     }

     public void dfs(int start, Tree[] tree, String s1, String s2, int n) {

         if(start == begin)

             s1 = s1 + tree[start].value;

         else {

             s1 = s1 + "-|-";

             s1 = s1 + tree[start].value;

         }

         if(tree[start].right != -1)  {

             s2 = s2 + "1";

             dfs(tree[start].right, tree, s1, s2, n + 1);

             s2 = s2.substring(0, s2.length() - 1);

         }

         int t = 0;

         for(int i = 0;i < s1.length();i++) {

             if(s1.charAt(i) == '|') {

                 if(s2.length() <= t + 1 || s2.charAt(t) != s2.charAt(t + 1))

                     System.out.print("|");

                 else

                     System.out.print(".");

                 t++;

             } else if(t < n) {

                 System.out.print(".");

             } else

                 System.out.print(s1.charAt(i));

         }

         if(tree[start].left != -1 || tree[start].right != -1)

             System.out.print("-|");

         System.out.println();

         if(tree[start].left != -1) {

             s2 = s2 + "0";

             dfs(tree[start].left, tree, s1, s2, n + 1);

             s2 = s2.substring(0, s2.length() - 1);

         }

     }

     public static void main(String[] args) {

         Main test = new Main();

         Scanner in = new Scanner(System.in);

         String A = in.nextLine();

         String[] arrayA = A.split(" ");

         Tree[] tree = new Tree[10005];

         for(int i = 0;i < arrayA.length;i++) {

             int v = Integer.valueOf(arrayA[i]);

             tree[v] = new Tree(v, -1, -1);

         }

         int start = Integer.valueOf(arrayA[0]);

         begin = start;

         for(int i = 1;i < arrayA.length;i++) {

             int v = Integer.valueOf(arrayA[i]);

             int temp = start;

             while(true) {

                 if(v > temp) {

                     if(tree[temp].right == -1) {

                         tree[temp].right = v;

                         break;

                     } else

                         temp = tree[temp].right;

                 } else {

                     if(tree[temp].left == -1) {

                         tree[temp].left = v;

                         break;

                     } else

                         temp = tree[temp].left;

                 }

             }

         }

         String s1 = "";

         String s2 = "";

         test.dfs(start, tree, s1, s2, 0);

     }

 }

5 危险系数

抗日战争时期，冀中平原的地道战曾发挥重要作用。

    地道的多个站点间有通道连接，形成了庞大的网络。但也有隐患，当敌人发现了某个站点后，其它站点间可能因此会失去联系。

    我们来定义一个危险系数DF(x,y)：

    对于两个站点x和y (x != y), 如果能找到一个站点z，当z被敌人破坏后，x和y不连通，那么我们称z为关于x,y的关键点。相应的，对于任意一对站点x和y，危险系数DF(x,y)就表示为这两点之间的关键点个数。

本题的任务是：已知网络结构，求两站点之间的危险系数。

    输入数据第一行包含2个整数n(2 <= n <= 1000), m(0 <= m <= 2000),分别代表站点数，通道数；

    接下来m行，每行两个整数 u,v (1 <= u, v <= n; u != v)代表一条通道；

    最后1行，两个数u,v，代表询问两点之间的危险系数DF(u, v)。

    输出：一个整数，如果询问的两点不连通则输出-1.

例如：

用户输入：

7 6

1 3

2 3

3 4

3 5

4 5

5 6

1 6

则程序应该输出：

2

资源约定：

峰值内存消耗（含虚拟机） < 64M

CPU消耗  < 2000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。

注意：不要使用package语句。不要使用jdk1.6及以上版本的特性。

注意：主类的名字必须是：Main，否则按无效代码处理。

 import java.util.ArrayList;

 import java.util.Scanner;

 public class Main {

     public static int n, m, start, end;

     public static ArrayList<Integer>[] map;

     public static int count, root;

     public static int[] DFN;

     public static int[] Low;

     public static int[] Parent;

     public ArrayList<Integer> point;

     public void init() {

         count = 0;

         root = 1;

         DFN = new int[n + 1];

         Low = new int[n + 1];

         Parent = new int[n + 1];

         point = new ArrayList<Integer>();

         for(int i = 1;i <= n;i++) {

             DFN[i] = -1;

             Low[i] = -1;

             Parent[i] = -1;

         }

     }

     public void TarJan(int begin, int parent) {

         DFN[begin] = ++count;

         Low[begin] = DFN[begin];

         Parent[begin] = parent;

         int Childern = 0;

         for(int i = 0;i < map[begin].size();i++) {

             int j = map[begin].get(i);

             if(DFN[j] == -1) {

                 Childern++;

                 TarJan(j, begin);

                 Low[begin] = Math.min(Low[begin], Low[j]);

                 if(begin == root && Childern > 1) {

                     if(!point.contains(begin))

                         point.add(begin);

                 } else if(begin != root && Low[j] >= DFN[begin]) {

                     if(!point.contains(begin))

                         point.add(begin);

                 }

             } else if(j != Parent[begin]) {

                 Low[begin] = Math.min(Low[begin], DFN[j]);

             }

         }

     } 

     public void dfs(int begin, boolean[] visited) {

         visited[begin] = true;

         for(int i = 0;i < map[begin].size();i++) {

             int j = map[begin].get(i);

             if(visited[j] == false)

                 dfs(j, visited);

         }

     }

     public void getResult() {

         boolean[] visited = new boolean[n + 1];

         dfs(start, visited);

         if(visited[end] == false) {

             System.out.println("-1");

             return;

         }

         init();

         TarJan(1, 0);

         int count = 0;

         for(int i = 0;i < point.size();i++) {

             int j = point.get(i);

             if(j != start && j != end) {

                 visited = new boolean[n + 1];

                 visited[j] = true;

                 dfs(start, visited);

                 if(visited[end] == false)

                     count++;

             }

         }

         System.out.println(count);

     }

     @SuppressWarnings("unchecked")

     public static void main(String[] args) {

         Main test = new Main();

         Scanner in = new Scanner(System.in);

         n = in.nextInt();

         m = in.nextInt();

         map = new ArrayList[n + 1];

         for(int i = 1;i <= n;i++)

             map[i] = new ArrayList<Integer>();

         for(int i = 1;i <= m;i++) {

             int u = in.nextInt();

             int v = in.nextInt();

             map[u].add(v);

             map[v].add(u);

         }

         start = in.nextInt();

         end = in.nextInt();

         test.getResult();

     }

 }

6 公式求值

6、标题：公式求值

    输入n, m, k，输出图1所示的公式的值。其中C_n^m是组合数，表示在n个人的集合中选出m个人组成一个集合的方案数。组合数的计算公式如图2所示。

    输入的第一行包含一个整数n；第二行包含一个整数m，第三行包含一个整数k。

    计算图1所示的公式的值，由于答案非常大，请输出这个值除以999101的余数。

【样例输入1】

3

1

3

【样例输出1】

162

【样例输入2】

20

10

10

【样例输出2】

359316

【数据规模与约定】

对于10%的数据，n≤10，k≤3；

对于20%的数据，n≤20，k≤3；

对于30%的数据，n≤1000，k≤5；

对于40%的数据，n≤10^7，k≤10；

对于60%的数据，n≤10^15，k ≤100；

对于70%的数据，n≤10^100，k≤200；

对于80%的数据，n≤10^500，k ≤500；

对于100%的数据，n在十进制下不超过1000位，即1≤n<10^1000，1≤k≤1000，同时0≤m≤n，k≤n。

【提示】

999101是一个质数；

当n位数比较多时，绝大多数情况下答案都是0，但评测的时候会选取一些答案不是0的数据；

资源约定：

峰值内存消耗（含虚拟机） < 128M

CPU消耗  < 2000ms

请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。

所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。

注意：不要使用package语句。不要使用jdk1.6及以上版本的特性。

注意：主类的名字必须是：Main，否则按无效代码处理。

完整解答请参见：公式求值解题报告

下面是楼主自己使用蛮力法求解，只过蓝桥练习系统中3组数据>~<。

 import java.math.BigInteger;

 import java.util.Scanner;

 public class Main {

     public BigInteger getCnm(long n, long m) {

         BigInteger A = BigInteger.ONE;

         BigInteger B = BigInteger.ONE;

         long c = m;

         if(n-m > m)

             c = n - m;

         for(long i = c + 1;i <= n;i++)

             A = A.multiply(new BigInteger(""+i));

         for(long i = 1;i <= n - c;i++)

             B = B.multiply(new BigInteger(""+i));

         return A.divide(B);

     }

     public BigInteger getXk(long a, long b) {

         BigInteger temp = new BigInteger(""+a);

         BigInteger result = BigInteger.ONE;

         while(b != 0) {

             if((b&1) == 1)

                 result = result.multiply(temp);

             temp = temp.multiply(temp);

             b >>= 1;

         }

         return result;

     }

     public void getReuslt(long n, long m, int k) {

         BigInteger result = getCnm(n, m);

         BigInteger sum = BigInteger.ZERO;

         for(long i = 0;i <= n;i++)

             sum = sum.add(getCnm(n, i).multiply(getXk(i, k)));

         result = result.multiply(sum).mod(new BigInteger("999101"));

         System.out.println(result);

     }

     public static void main(String[] args) {

         Main test = new Main();

         Scanner in = new Scanner(System.in);

         long n = in.nextLong();

         long m = in.nextLong();

         int k = in.nextInt();

         test.getReuslt(n, m, k);

     }

 }

巴特西

算法笔记_204:第四届蓝桥杯软件类决赛真题(Java语言C组)

1 好好学习

2 埃及分数

3 金蝉素数

4 横向打印二叉树

5 危险系数

6 公式求值

最新文章

热门文章