蓝桥杯真题3

迷南。 2024-03-24 10:58 51阅读 0赞

## \[蓝桥杯 2015 省 B\] 移动距离 ##

### 题目描述 ###

X 星球居民小区的楼房全是一样的，并且按矩阵样式排列。其楼房的编号为 $1,2,3, \\cdots $ 。

当排满一行时，从下一行相邻的楼往反方向排号。

比如：当小区排号宽度为  6 6 6 时，开始情形如下：

1  2  3  4  5  6
    12 11 10 9  8  7
    13 14 15 .....

我们的问题是：已知了两个楼号  m m m 和  n n n，需要求出它们之间的最短移动距离。（不能斜线方向移动）

### 输入格式 ###

输入为  3 3 3 个整数 wmn，空格分开，都在  1 1 1 到  10000 10000 10000 范围内。

w w w 为排号宽度， m , n m,n m,n 为待计算的楼号。

### 输出格式 ###

要求输出一个整数，表示  m m m 与  n n n 两楼间最短移动距离。

### 样例 \#1 ###

#### 样例输入 \#1 ####

6 8 2

#### 样例输出 \#1 ####

### 样例 \#2 ###

#### 样例输入 \#2 ####

4 7 20

#### 样例输出 \#2 ####

### 提示 ###

时限 1 秒, 256M。

蓝桥杯 2015 年省赛 B 组 H 题。

### 分析 ###

这道题有点类似于高中数学学的二维坐标系的距离问题，即哈密顿距离 |x1-x2|+|y1-y1|,因此我们只需要知道所求两个点的横纵坐标既可以求出最短距离。`x = n/W,y = n % w`;关键就在于他的列号排列不像正常的坐标系去从左向右排列，而是蛇形排列的。我们不妨把这个楼层的行列也设为数组的行列排序，即从0开始，我们发现只要是奇数行即（n%w == 1)的行，他的列号是要颠倒的，如何实现颠倒列号呢，很简单`y = w - 1 - n % w`;就是高中时学的数轴找对称点。

### 代码实现 ###

import java.util.*;
    public class Main{
        
        public static void main(String[] args){
        
            Scanner scan = new Scanner(System.in);
            int w = scan.nextInt();
            int m = scan.nextInt();
            int n = scan.nextInt();
            m--;n--;//将其转化为数组下标也即是从0开始。
            int x1 = m / w,x2 = n / w;
            int y1 = m % w,y2 = n % w;
            if(x1 % 2 == 1) y1 = w - 1 - m % w;
            if(x2 % 2 == 1) y2 = w - 1 - n % w;
            System.out.println(Math.abs(x1-x2)+Math.abs(y1-y2));
        }
    }

## \[蓝桥杯 2017 省 B\] 日期问题 ##

### 题目描述 ###

小明正在整理一批历史文献。这些历史文献中出现了很多日期。小明知道这些日期都在 1960 年 1 月 1 日至 2059 年 12 月 31 日。令小明头疼的是，这些日期采用的格式非常不统一，有采用`年/月/日`的，有采用`月/日/年`的，还有采用`日/月/年`的。更加麻烦的是，年份也都省略了前两位，使得文献上的一个日期，存在很多可能的日期与其对应。

比如 `02/03/04`，可能是 2002 年 03 月 04 日、2004 年 02 月 03 日或 2004 年 03 月 02 日。

给出一个文献上的日期，你能帮助小明判断有哪些可能的日期对其对应吗？

### 输入格式 ###

一个日期，格式是 `AA/BB/CC`。( 0 ≤ A , B , C ≤ 9 0\\le A, B, C\\le 9 0≤A,B,C≤9)

### 输出格式 ###

输出若干个不相同的日期，每个日期一行，格式是 `yyyy-MM-dd`。多个日期按从早到晚排列。

### 样例 \#1 ###

#### 样例输入 \#1 ####

02/03/04

#### 样例输出 \#1 ####

2002-03-04  
    2004-02-03  
    2004-03-02

### 分析 ###

本来我看这道题的思路是，枚举三种位置组成的所有日期，然后再去检验是否合法，但当真正去写的时候发现有个很大的问题，太过繁琐麻烦，你不仅需要去判断是19··年还是20··年，还有闰年什么的情况，再加上判断日子等等,最后还需要排序输出。所以我们换一种思路，枚举所有960 年 1 月 1 日至 2059 年 12 月 31 日之间的日子，判断日期是否合法，同时判断这个日期是否可以由三种构成方法中的任一种组成，这样无疑会简单许多。

### 代码实现 ###

import java.util.*;
    public class Main{
        
        static int[] Months = {
        0,31,28,31,30,31,30,31,31,30,31,30,31};
        public static void main(String[] args){
        
            Scanner scan = new Scanner(System.in);
            String date = scan.next();
            String[] s = date.split("/");
            int a = Integer.parseInt(s[0]);
            int b = Integer.parseInt(s[1]);
            int c = Integer.parseInt(s[2]);
            for(int i = 19600101;i <= 20591231;i++){
        
            int y = i / 10000;
            int m = i % 10000 / 100;
            int d = i % 100;
                if(checkYear(i)){
        
                    if(y % 100 == a && m==b && d ==c||
                    y % 100 == c && m == b && d == a||
                    y % 100 == c&&  m == a && d == b){
        
                        System.out.print(y+"-");
                        if(m<10)System.out.print("0");
                        System.out.print(m+"-");
                        if(d<10)System.out.print("0");
                        System.out.println(d);
                    }
                }
            }
        }
        public static boolean checkYear(int i){
        
            int y = i / 10000;
            int m = i % 10000 / 100;
            int d = i % 100;
            if(m == 0 || m > 12) return false;
            if(d == 0) return false;
            if(m != 2){
        
                if(d > Months[m]) return false;
            }else{
        
                int leap = 0;
                if(y % 100 != 0 && y % 4 == 0 || y % 400 == 0){
        
                    leap = 1;
                }
                if(d > Months[2]+leap){
        
                    return false;
                }
            }
            return true;
        }
    }

### 早先思路代码实现 ###

import java.io.*;
    import java.util.TreeSet;
    
    public class Main {
        
        static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        static TreeSet<String> ans = new TreeSet<>();
        static int []normalYear = {
        0,31,28,31,30,31,30,31,31,30,31,30,31};
        static int []leapYear = {
        0,31,29,31,30,31,30,31,31,30,31,30,31};
        static String []num = {
        "19","20"};
        static String maxDate = "2059-12-31",minDate = "1960-01-01";
    
        static boolean isLeapYear(String year){
        
            int numYear = Integer.parseInt(year);
            return numYear % 4 == 0 && numYear % 100 != 0 || numYear % 400 == 0;
        }
    
        static void add(String a,String b,String c){
        
            String res;
            int month = Integer.parseInt(b);
            if (month == 0 || month > 12)return;
            int maxDay;
            if (isLeapYear(a))maxDay = leapYear[month];
            else maxDay = normalYear[month];
            int day = Integer.parseInt(c);
            if (day == 0 || day > maxDay)return;
            res = a + "-" + b + "-" + c;
            if (res.compareTo(maxDate) <= 0 && res.compareTo(minDate) >= 0)ans.add(res);
        }
    
        public static void main(String[] args) throws IOException {
        
            String []all = br.readLine().split("/");
            for(int i = 0 ; i < 2 ; i ++){
        
                add(num[i] + all[0],all[1],all[2]);
                add(num[i] + all[2],all[0],all[1]);
                add(num[i] + all[2],all[1],all[0]);
            }
            for(String i :ans) System.out.println(i);
        }
    }