编辑

【省赛A组】2018年第九届蓝桥杯(解法通用)

2019-11-29 2019-11-29 83 2 ● 蓝桥杯 PAN先森

友情提示

#001 分式

1/1 + 1/2 + 1/4 + 1/8 + 1/16 + .... 每项是前一项的一半,如果一共有20项,求这个和是多少,结果用分数表示出来。 类似:3/2当然,这只是加了前2项而已。分子分母要求互质。注意:需要提交的是已经约分过的分数,中间任何位置不能含有空格。

..

#002 星期一

整个20世纪(1901年1月1日至2000年12月31日之间),一共有多少个星期一?(不要告诉我你不知道今天是星期几)

..

#003 复数幂

与我整理的B组题目相同:https://www.hoji.site/blog/73


#004 方格计数

与我整理的B组题目相同:https://www.hoji.site/blog/73


#005 打印图形

..

#006 航班时间

【问题背景】小h前往美国参加了蓝桥杯国际赛。小h的女朋友发现小h上午十点出发,上午十二点到达美国,于是感叹到“现在飞机飞得真快,两小时就能到美国了”。小h对超音速飞行感到十分恐惧。仔细观察后发现飞机的起降时间都是当地时间。由于北京和美国东部有12小时时差,故飞机总共需要14小时的飞行时间。不久后小h的女朋友去中东交换。小h并不知道中东与北京的时差。但是小h得到了女朋友来回航班的起降时间。小h想知道女朋友的航班飞行时间是多少。
【问题描述】对于一个可能跨时区的航班,给定来回程的起降时间。假设飞机来回飞行时间相同,求飞机的飞行时间。
【输入格式】从标准输入读入数据。一个输入包含多组数据。输入第一行为一个正整数T,表示输入数据组数。每组数据包含两行,第一行为去程的 起降 时间,第二行为回程的 起降 时间。

起降时间的格式如下h1:m1:s1 h2:m2:s2h1:m1:s1 h3:m3:s3 (+1)h1:m1:s1 h4:m4:s4 (+2),表示该航班在当地时间h1时m1分s1秒起飞

  • 第一种格式表示在当地时间 当日 h2时m2分s2秒降落
  • 第二种格式表示在当地时间 次日 h3时m3分s3秒降落
  • 第三种格式表示在当地时间 第三天 h4时m4分s4秒降落
  • 对于此题目中的所有以 h:m:s 形式给出的时间, 保证 ( 0<=h<=23, 0<=m,s<=59 ).
【输出格式】输出到标准输出。对于每一组数据输出一行一个时间hh:mm:ss,表示飞行时间为hh小时mm分ss秒。

注意,当时间为一位数时,要补齐前导零。如三小时四分五秒应写为03:04:05。

【样例输入】
317:48:19 21:57:2411:05:18 15:14:2317:21:07 00:31:46 (+1)
23:02:41 16:13:20 (+1)
10:19:19 20:41:2422:19:04 16:41:09 (+1)

【样例输出】04:09:0512:10:3914:22:05【限制与约定】保证输入时间合法,飞行时间不超过24小时。
资源约定:峰值内存消耗(含虚拟机) < 256MCPU消耗  < 1000ms
..

#007 三体攻击

【题目描述】

三体人将对地球发起攻击。为了抵御攻击,地球人派出了 A × B × C 艘战舰,在太空中排成一个 A 层 B 行 C 列的立方体。其中,第 i 层第 j 行第 k 列的战舰(记为战舰 (i, j, k))的生命值为 d(i, j, k)。
三体人将会对地球发起 m 轮“立方体攻击”,每次攻击会对一个小立方体中的所有战舰都造成相同的伤害。具体地,第 t 轮攻击用 7 个参数 lat, rat, lbt, rbt, lct, rct, ht 描述;
所有满足 i ∈ [lat, rat],j ∈ [lbt, rbt],k ∈ [lct, rct] 的战舰 (i, j, k) 会受到 ht 的伤害。如果一个战舰累计受到的总伤害超过其防御力,那么这个战舰会爆炸。
地球指挥官希望你能告诉他,第一艘爆炸的战舰是在哪一轮攻击后爆炸的。

【输入格式】

第一行包括 4 个正整数 A, B, C, m; 第二行包含 A × B × C 个整数,其中第 ((i − 1)×B + (j − 1)) × C + (k − 1)+1 个数为 d(i, j, k); 第 3 到第 m + 2 行中,第 (t − 2) 行包含 7 个正整数 lat, rat, lbt, rbt, lct, rct, ht。

【输出格式】

输出到标准输出。 输出第一个爆炸的战舰是在哪一轮攻击后爆炸的。保证一定存在这样的战舰。

【样例输入】
2 2 2 3
1 1 1 1 1 1 1 1
1 2 1 2 1 1 1
1 1 1 2 1 2 1
1 1 1 1 1 1 2

【样例输出】
2

【样例解释】
在第 2 轮攻击后,战舰 (1,1,1) 总共受到了 2 点伤害,超出其防御力导致爆炸。


【数据约定】
对于 10% 的数据,B = C = 1;
对于 20% 的数据,C = 1;
对于 40% 的数据,A × B × C, m ≤ 10, 000;
对于 70% 的数据,A, B, C ≤ 200;
对于所有数据,A × B × C ≤ 10^6, m ≤ 10^6, 0 ≤ d(i, j, k), ht ≤ 10^9。


资源约定:CPU消耗  < 3000ms
待更...

#008 全球变暖

你有一张某海域NxN像素的照片,"."表示海洋、"#"表示陆地,如下所示:

.......
.##....
.##....
....##.
..####.
...###.
.......

其中"上下左右"四个方向上连在一起的一片陆地组成一座岛屿。例如上图就有2座岛屿。  

由于全球变暖导致了海面上升,科学家预测未来几十年,岛屿边缘一个像素的范围会被海水淹没。具体来说如果一块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋),它就会被淹没。  

例如上图中的海域未来会变成如下样子:

.......
.......
.......
.......
....#..
.......
.......

请你计算:依照科学家的预测,照片中有多少岛屿会被完全淹没。

【输入格式】
第一行包含一个整数N。  (1 <= N <= 1000)  
以下N行N列代表一张海域照片。  

照片保证第1行、第1列、第N行、第N列的像素都是海洋。  

【输出格式】
一个整数表示答案。

【输入样例】
7 
.......
.##....
.##....
....##.
..####.
...###.
.......  

【输出样例】1  

资源约定:CPU消耗  < 1000ms

大致思路:

  • 初始化迷宫(maze),如果maze[i][j]'#',并且没被访问过,才从这个点(i,j)深搜
  • mark[]数组:记录下标为count的岛屿(count其实是记录岛屿的总数量),mark[]则是记录不被淹没的岛屿,将其标记为非0.
  • count什么时候回自增?count的自增时机是一次dfs回来以后,也就是统计岛屿数量,这题的样例就是count==2,但不被淹没的mark[1]就是非0
  • dfs 就是找到一个四周都是'#'的陆地,并按一个方向继续搜索下去直到搜到'.'为止,然后换一个方向继续上半句逻辑
  • 最后就是遍历mark[]数组,如果在count个岛屿中有没被标记过的岛屿(没被标记过的岛屿即要被淹没的岛屿),那么++ans,最后打印ans
import java.util.Scanner;
/**
 * @Author: Hoji(PAN先森)
 * @Date: 11/28/2019 4:18 PM
 * @个人博客:https://www.hoji.site
 */
public class Main {
  private static String[][] maze = null;
  private static boolean visited[][] = null;
  private static int[] mark=new int[100];
  /**
   * 初始化迷宫(maze)
   * @param maze
   * @param N
   */
  private static viod init(int N) {
    maze = new String[N][N];
    visited[][] = new boolean[N][N];
    for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
      maze[i][j] = s.next();
  }
  /**
   * 深搜
   * @param x
   * @param y
   * @param k
   */
  private static void dfs(int x, int y, int k, int N) {
    if(maze[x][y].equals(".")  || visited[x][y])
      return;
    visited[x][y]=true;
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        //在范围内、是岛屿、没访问过i>0 && i<N && j>0 && j<N && maze[x][y]=="#" && !visited[x][y]
        //如果上下左右都是陆地,那么标记该点(以及后续遍历到的"#")为不会被淹没
        if(maze[x-1][y].equals("#") && maze[x+1][y].equals("#") && maze[x][y-1].equals("#") && maze[x][y+1].equals("#"))
          mark[k]++;
        dfs(x-1,y,k);
        dfs(x+1,y,k);
        dfs(x,y-1,k);
        dfs(x,y+1,k);
      }
    }
  }

  public static void main(String[] args) {
    int N;
    Scanner s = new Scanner(System.in);
    N=s.nextInt();
    init(N);    //初始化
    int count=0, ans=0;
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        if(maze[i][j].equals("#") && !visited[i][j]) {
          dfs(i,j,count,N);
          ++count;
        }
      }
    }
    //找到count个岛屿,mark标记着不会被淹没的岛屿的数量,
    //如果mark[i]==0(没被标记),那么证明它是被淹没的.
    for(int i = 0; i < count; i++)
    if(mark[i]==0)
      ++ans;
    System.out.println(ans);
  }
}

#009 倍数问题

众所周知,小葱同学擅长计算,尤其擅长计算一个数是否是另外一个数的倍数。但小葱只擅长两个数的情况,当有很多个数之后就会比较苦恼。现在小葱给了你 n 个数,希望你从这 n 个数中找到三个数,使得这三个数的和是 K 的倍数,且这个和最大。数据保证一定有解

【输入格式】
从标准输入读入数据。
第一行包括 2 个正整数 n, K。
第二行 n 个正整数,代表给定的 n 个数。

【输出格式】
输出到标准输出。
输出一行一个整数代表所求的和。

【样例输入】
4 3
1 2 3 4

【样例输出】
9

【样例解释】
选择2、3、4。

【数据约定】
对于 30% 的数据,n <= 100。
对于 60% 的数据,n <= 1000。
对于另外 20% 的数据,K <= 10。
对于 100% 的数据,1 <= n <= 10^5, 1 <= K <= 10^3,给定的 n 个数均不超过 10^8。


资源约定:CPU消耗  < 1000ms
待更

#010 付账问题

待更...

倘若小文于你有益,欢迎
  • 如果您的提问博主没能及时回复,通过分享文章获得援助,何尝不是一种查缺补漏的好做法
  • 版权声明:本文为博主原创文章,遵循CC 4.0 BY版权协议
  • 文章转载:请在文末添加原文章地址,这也是尊重他人劳动成果的一点体现,谢谢您的配合!
  • 评论信息 (注:评论收到回复后,会以邮箱的方式提醒您;您的邮箱不会显示到页面中)

    验证码信息 看不清?点击图片进行切换!
    精彩随处可见 更多精彩内容
    作者: 浏览 61 评论 1 赞 1 2020-01-15
    作者: 浏览 62 评论 1 赞 1 2019-11-29
    作者: 浏览 83 评论 1 赞 1 2019-11-29
    作者: 浏览 54 评论 1 赞 1 2019-11-29
    作者: 浏览 52 评论 1 赞 1 2019-11-29
    目录