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

题目描述

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

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

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

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

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

输入格式

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

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

输出格式

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

样例 #1

样例输入 #1

6 8 2

样例输出 #1

4

样例 #2

样例输入 #2

4 7 20

样例输出 #2

5

提示

时限 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\le A,B,C\le 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);}
}