第七届蓝桥杯决赛JavaC组真题——详细答案对照(完整版)-2

简介: 第七届蓝桥杯决赛JavaC组真题——详细答案对照(完整版)

赢球票

某机构举办球票大奖赛。获奖选手有机会赢得若干张球票。


主持人拿出 N 张卡片(上面写着 1~N 的数字),打乱顺序,排成一个圆圈。

你可以从任意一张卡片开始顺时针数数: 1,2,3.....

如果数到的数字刚好和卡片上的数字相同,则把该卡片收入囊中,从下一个卡片重新数数。

直到再无法收获任何卡片,游戏结束。囊中卡片数字的和就是赢得球票的张数。


比如:

卡片排列是:1 2 3

我们从1号卡开始数,就把1号卡拿走。再从2号卡开始,但数的数字无法与卡片对上,

很快数字越来越大,不可能再拿走卡片了。因此这次我们只赢得了1张球票。


还不算太坏!如果我们开始就傻傻地从2或3号卡片数起,那就一张卡片都拿不到了。


如果运气好,卡片排列是 2 1 3

那我们可以顺利拿到所有的卡片!


本题的目标就是:已知顺时针卡片序列。

随便你从哪里开始数,求最多能赢多少张球票(就是收入囊中的卡片数字之和)


输入数据:

第一行一个整数N(N<100),表示卡片数目

第二行 N 个整数,表示顺时针排列的卡片


输出数据:

一行,一个整数,表示最好情况下能赢得多少张球票


比如:

用户输入:

3

1 2 3


程序应该输出:

1


比如:

用户输入:

3

2 1 3


程序应该输出:

6



资源约定:

峰值内存消耗 < 256M

CPU消耗  < 1000ms


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


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

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

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


package action;
import java.util.Scanner;
public class demo {
  public static int n;
  public static int max = 0;
  public static int[] value;
  public static void getResult() {
  for (int i = 0; i < n; i++) {
    int[] temp = new int[n];
    for (int k = 0; k < n; k++)
    temp[k] = value[k];
    int sum = 0;
    int count = 1;
    int start = i;
    while (true) {
    boolean judge = true;
    for (int k = 0; k < n; k++)
      if (temp[k] >= count) {
      judge = false;
      break;
      }
    if (judge)
      break;
    int j = start % n;
    if (temp[j] == count) {
      sum = sum + count;
      temp[j] = -1;
      count = 1;
    } else if (temp[j] != -1)
      count++;
    start++;
    }
    max = Math.max(max, sum);
  }
  System.out.println(max);
  }
  public static void main(String[] args) {
  Scanner in = new Scanner(System.in);
  n = in.nextInt();
  value = new int[n];
  for (int i = 0; i < n; i++)
    value[i] = in.nextInt();
  getResult();
  }
}



image.png


E、路径之谜

小明冒充X星球的骑士,进入了一个奇怪的城堡。

城堡里边什么都没有,只有方形石头铺成的地面。


假设城堡地面是 n x n 个方格。【如图1.png】所示。


按习俗,骑士要从西北角走到东南角。

可以横向或纵向移动,但不能斜着走,也不能跳跃。

每走到一个新方格,就要向正北方和正西方各射一箭。

(城堡的西墙和北墙内各有 n 个靶子)



同一个方格只允许经过一次。但不必做完所有的方格。


如果只给出靶子上箭的数目,你能推断出骑士的行走路线吗?


有时是可以的,比如图1.png中的例子。


本题的要求就是已知箭靶数字,求骑士的行走路径(测试数据保证路径唯一)


输入:

第一行一个整数N(0<N<20),表示地面有 N x N 个方格

第二行N个整数,空格分开,表示北边的箭靶上的数字(自西向东)

第三行N个整数,空格分开,表示西边的箭靶上的数字(自北向南)


输出:

一行若干个整数,表示骑士路径。


为了方便表示,我们约定每个小格子用一个数字代表,从西北角开始编号: 0,1,2,3....

比如,图1.png中的方块编号为:


0  1  2  3

4  5  6  7

8  9  10 11

12 13 14 15



示例:

用户输入:

4

2 4 3 4

4 3 3 3


程序应该输出:

0 4 5 1 2 3 7 11 10 9 13 14 15


资源约定:

峰值内存消耗 < 256M

CPU消耗  < 1000ms



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


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

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

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


image.png



碱基

生物学家正在对n个物种进行研究。

其中第i个物种的DNA序列为s[i],其中的第j个碱基为s[i][j],碱基一定是A、T、G、C之一。

生物学家想找到这些生物中一部分生物的一些共性,他们现在关注那些至少在m个生物中出现的长度为k的连续碱基序列。准确的说,科学家关心的序列用2m元组(i1,p1,i2,p2....im,pm)表示,

满足:

1<=i1<i2<....<im<=n;

且对于所有q(0<=q<k), s[i1][p1+q]=s[i2][p2+q]=....=s[im][pm+q]。


现在给定所有生物的DNA序列,请告诉科学家有多少的2m元组是需要关注的。如果两个2m元组有任何一个位置不同,则认为是不同的元组。


【输入格式】

输入的第一行包含三个整数n、m、k,两个整数之间用一个空格分隔,意义如题目所述。

接下来n行,每行一个字符串表示一种生物的DNA序列。

DNA序列从1至n编号,每个序列中的碱基从1开始依次编号,不同的生物的DNA序列长度可能不同。


【输出格式】

输出一个整数,表示关注的元组个数。

答案可能很大,你需要输出答案除以1000000007的余数。


【样例输入】

3 2 2

ATC

TCG

ACG


【样例输出】

2


再例如:

【样例输入】

4 3 3

AAA

AAAA

AAA

AAA


【样例输出】

7



【数据规模与约定】

对于20%的数据,k<=5,所有字符串总长L满足L <=100

对于30%的数据,L<=10000

对于60%的数据,L<=30000

对于100%的数据,n<=5,m<=5,1<=k<=L<=100000

保证所有DNA序列不为空且只会包含’A’ ’G’ ’C’ ’T’四种字母


资源约定:

峰值内存消耗 < 256M

CPU消耗  < 1000ms


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


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

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

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


package action;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Scanner;
public class demo {
  public static int n, m, k;
  public static String[] S;
  public static String[] num;
  public static int[] start;
  public static long MOD = 1000000007;
  public static long count = 0;
  public static HashSet<String> result = new HashSet<String>();
  public static void dfs(int step, int sum) {
    if (step == n || sum >= m) {
      if (sum >= m) {
        ArrayList<String> set = new ArrayList<String>();
        StringBuffer[] s = new StringBuffer[sum];
        for (int i = 0; i < sum; i++)
          s[i] = new StringBuffer("");
        for (int i = 0; i < n; i++) {
          if (!num[i].equals("-")) {
            if (!set.contains(num[i])) {
              set.add(num[i]);
              s[set.size() - 1].append(i);
              s[set.size() - 1].append(start[i]);
            } else {
              int j = set.indexOf(num[i]);
              s[j].append(i);
              s[j].append(start[i]);
            }
          }
        }
        if (set.size() == sum - m + 1) {
          for (int i = 0; i < sum; i++) {
            if (s[i].toString().length() == k * 2) {
              if (!result.contains(s[i].toString()))
                count = (count + 1) % MOD;
              result.add(s[i].toString());
              break;
            }
          }
        }
      }
      return;
    } else {
      for (int i = 0; i < S[step].length(); i++) {
        if (i + k <= S[step].length()) {
          num[step] = S[step].substring(i, i + k);
          start[step] = i;
          dfs(step + 1, sum + 1);
          num[step] = "-";
        }
        dfs(step + 1, sum);
      }
    }
  }
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    n = in.nextInt();
    m = in.nextInt();
    k = in.nextInt();
    S = new String[n];
    for (int i = 0; i < n; i++)
      S[i] = in.next();
    num = new String[n + 1];
    start = new int[n + 1];
    for (int i = 0; i <= n; i++)
      num[i] = "-";
    dfs(0, 0);
    System.out.println(count);
  }
}
相关文章
|
2月前
第十四届蓝桥杯集训——JavaC组第十三篇——for循环
第十四届蓝桥杯集训——JavaC组第十三篇——for循环
44 0
|
2月前
|
算法
第十四届蓝桥杯集训——JavaC组第十二篇——while循环(循环四要素)
第十四届蓝桥杯集训——JavaC组第十二篇——while循环(循环四要素)
49 0
|
2月前
|
算法 Java C语言
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-试题 基础练习 数列排序(四种语言对照)
第十四届蓝桥杯集训——练习解题阶段(无序阶段)-试题 基础练习 数列排序(四种语言对照)
32 0
|
2月前
|
Java C语言
第十四届蓝桥杯集训——JavaC组第十四篇——嵌套循环
第十四届蓝桥杯集训——JavaC组第十四篇——嵌套循环
42 0
|
2月前
|
C语言
第十四届蓝桥杯集训——JavaC组第十一篇——switch
第十四届蓝桥杯集训——JavaC组第十一篇——switch
40 0
|
2月前
第十四届蓝桥杯集训——JavaC组第十篇——分支语句
第十四届蓝桥杯集训——JavaC组第十篇——分支语句
39 0
|
2月前
|
算法
第十四届蓝桥杯集训——JavaC组第九篇——三元运算符
第十四届蓝桥杯集训——JavaC组第九篇——三元运算符
36 0
|
2月前
第十四届蓝桥杯集训——JavaC组第九篇——位运算符
第十四届蓝桥杯集训——JavaC组第九篇——位运算符
27 0
|
2月前
第十四届蓝桥杯集训——JavaC组第八篇——进制转换
第十四届蓝桥杯集训——JavaC组第八篇——进制转换
41 0
|
2月前
|
Java 测试技术 C++
第十四届蓝桥杯集训——JavaC组——运算符练习题
第十四届蓝桥杯集训——JavaC组——运算符练习题
50 0