[数据结构与算法]第九届蓝桥杯B组Java试题答案(初赛)

试题A：第几天

2000年的1?1?，是那?年的第1天。那么，2000年的5?4?，是那?年的第?天？

31+29+31+30+4 = 125

答案：125

标题B：方格计数

如图下图所?，在?维平?上有?数个1x1的??格。

我们以某个??格的?个顶点为圆?画?个半径为1000的圆。
你能计算出这个圆?有多少个完整的??格吗？

数学
只需要考虑第一象限的1/4圆，最后结果乘4
在第一象限中，找出小方格右上角坐标x*x+y*y<=1000*1000的点即可，1<=x,y<=1000

答案：?3137548

public class Main {
	public static void main(String[] args) {
		int count = 0;
		for (int x = 1; x <= 1000; x++) {
			for (int y = 1; y <= 1000; y++) {
				if (x * x + y * y <= 1000 * 1000) {
					count++;
				}
			}
		}
		System.out.println(4 * count);
	}
}

试题C：复数幂

设i为虚数单位。对于任意正整数n，(2+3i)^n 的实部和虚部都是整数。
求 (2+3i)^123456 等于多少？ 即(2+3i)的123456次幂，这个数字很?，要求精确表?。
答案写成 "实部±虚部i" 的形式，实部和虚部都是整数（不能?科学计数法表?），中间任何地?都不加空格，实部为正时前?不加正号。
(2+3i)^2 写成: -5+12i，
(2+3i)^5 的写成: 122-597i

答案：很长，这里就不显示了

BigInteger类

import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintStream;
import java.math.BigInteger;

public class Main {
	public static void main(String[] args) throws FileNotFoundException {
		// 改变输出流，输出到work.txt文件
		PrintStream ps = new PrintStream(new FileOutputStream("D:\\work.txt"));
		System.setOut(ps); // 文件输出 用System.out.println()即可将内容输出到文件中
		BigInteger a = new BigInteger("2");
		BigInteger b = new BigInteger("3");
		BigInteger x = new BigInteger("2");
		BigInteger y = new BigInteger("3");
		for (int i = 0; i < 123455; i++) {
			BigInteger tmp = x;
			x = x.multiply(a).subtract(y.multiply(b)); // x存储实部
			y = tmp.multiply(b).add(y.multiply(a)); // y存储虚部
		}
		System.out.println(x + "" + ((y.compareTo(BigInteger.ZERO) > 0) ? "+" : "") + y + "i");
	}
}

试题F：递增三元组

给定三个整数数组
A = [A1, A2, ... AN],
B = [B1, B2, ... BN],
C = [C1, C2, ... CN]，
请你统计有多少个三元组(i, j, k) 满?：
1. 1 <= i, j, k <= N
2. Ai < Bj < Ck
【输?格式】
第??包含?个整数N。
第??包含N个整数A1, A2, ... AN。
第三?包含N个整数B1, B2, ... BN。
第四?包含N个整数C1, C2, ... CN。
对于30%的数据，1 <= N <= 100
对于60%的数据，1 <= N <= 1000
对于100%的数据，1 <= N <= 100000 0 <= Ai, Bi, Ci <= 100000
【输出格式】
?个整数表?答案
【输?样例】
3
1 1 1
2 2 2
3 3 3
【输出样例】
27

双指针

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];
		int[] b = new int[n];
		int[] c = new int[n];
		for (int i = 0; i < n; i++) a[i] = sc.nextInt();
		for (int i = 0; i < n; i++) b[i] = sc.nextInt();
		for (int i = 0; i < n; i++) c[i] = sc.nextInt();
		Arrays.sort(a);
		Arrays.sort(b);
		Arrays.sort(c);
		long res = 0;
		int p = 0, q = 0;
		for (int i = 0; i < n; i++) {
			while (p < n && a[p] < b[i]) {
				p++;
			}
			while (q < n && c[q] <= b[i]) {
				q++;
			}
			res += 1L * p * (n - q);
		}
		System.out.println(res);
		sc.close();
	}
}

试题G：螺旋折线

如图p1.pgn所?的螺旋折线经过平?上所有整点恰好?次。

对于整点(X, Y)，我们定义它到原点的距离dis(X, Y)是从原点到(X, Y)的螺旋折线段的长度。
例如dis(0, 1)=3, dis(-2, -1)=9
给出整点坐标(X, Y)，你能计算出dis(X, Y)吗？
【输?格式】
X和Y
对于40%的数据，-1000 <= X, Y <= 1000
对于70%的数据，-100000 <= X， Y <= 100000
对于100%的数据, -1000000000 <= X, Y <= 1000000000
【输出格式】
输出dis(X, Y)
【输?样例】
0 1
【输出样例】
3

找规律?

把图都当做若干个正方形嵌套。
max(abs(a),abs(b))为第n个正方形，周长为 8*n。
总长等于内嵌的所有正方形的周长总和，再加上该点在此正方形的长度之和，通过分类四条边来计算其值，注意正方形左下角的点归于第四条边。?

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt();
		int y = sc.nextInt();
		if (x == 0 && y == 0) {
			System.out.println(0);
			return;
		}
		long n = Math.max(Math.abs(x), Math.abs(y));// 点(x,y)在第几圈
		long sum = 4 * n * (n - 1); // 里面所有正方形的周长之和：1*8+2*8+...(n-1)*8
		if (x == -n && y != -n) {
			sum += (y + n); // 正方形左下角的点归于第四条边
		} else if (y == n) {
			sum += 2 * n + (x + n);
		} else if (x == n) {
			sum += 4 * n + (n - y);
		} else {
			sum += 6 * n + (n - x);
		}
		System.out.println(sum);
		sc.close();
	}
}

试题H：日志统计

小明维护着?个程序员论坛。现在他收集了?份"点赞"?志，?志共有N?。其中每??的格式是：ts id 表?在ts时刻编号id的帖?收到?个"赞"。
现在?明想统计有哪些帖?曾经是"热帖"。如果?个帖?曾在任意?个长度为D的时间段内收到不少于K个赞，?明就认为这个帖?曾是"热帖"。具体来说，如果存在某个时刻T满?该帖在[T, T+D)这段时间内(注意是左闭右开区间)收到不少于K个赞，该帖就曾是"热帖"。
给定?志，请你帮助?明统计出所有曾是"热帖"的帖?编号。
【输?格式】
第??包含三个整数N、D和K。
以下N?每??条?志，包含两个整数ts和id。
对于50%的数据，1 <= K <= N <= 1000
对于100%的数据，1 <= K <= N <= 100000 0 <= ts <= 100000 0 <= id <= 100000
【输出格式】
按从?到?的顺序输出热帖id。每个id??。
【输?样例】
7 10 2
0 1
0 10
10 10
10 1
9 1
100 3
100 3
【输出样例】
1
3

双指针(尺取法)
思路：先统计每个帖子的点赞日志的时间戳，并排序，再根据尺取法分析哪个帖子是热帖

import java.util.*;

public class Main {
	static int n, d, k;
	static int[][] data;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		d = sc.nextInt();
		k = sc.nextInt();
		data = new int[n][2]; // 存储日志
		Map<Integer, ArrayList<Integer>> map = new TreeMap<>(); //自动根据key排序,这样后面就不用对结果排序了
		for (int i = 0; i < n; i++) {
			data[i][0] = sc.nextInt();
			data[i][1] = sc.nextInt();
			map.put(data[i][1], new ArrayList<>());
		}
		for (int i = 0; i < n; i++) {
			map.get(data[i][1]).add(data[i][0]); // 统计每个帖子点赞日志的时间戳
		}
		List<Integer> ans = new ArrayList<Integer>();
		for (int id : map.keySet()) {
			if (isHot(id, map.get(id))) {
				ans.add(id);
			}
		}
		for (int id : ans) {
			System.out.println(id);
		}
		sc.close();
	}

	private static boolean isHot(int id, ArrayList<Integer> ts) {
		Collections.sort(ts); // 排序
		int l = 0, r = 0, num = 0;
		while (true) {
			// 右指针向右移(k-1)个单位
			while (r < ts.size() && num < k) {
				num++;
				r++;
			}
			if (num < k) {
				return false; // 连k个时间戳,也就是k个赞都没有,自然不满足条件
			} else {
				if (ts.get(r - 1) < ts.get(l) + d) {
					return true;
				} else {
					l++;
					num--;
				}
			}
		}
	}
}

试题I：全球变暖

你有?张某海域NxN像素的照?，"."表?海洋、"#"表?陆地，如下所?：
.......
.##....
.##....
....##.
..####.
...###.
.......
其中"上下左右"四个?向上连在?起的??陆地组成?座岛屿。例如上图就有2座岛屿。
由于全球变暖导致了海?上升，科学家预测未来??年，岛屿边缘?个像素的范围会被海?淹没。具体来说如果?块陆地像素与海洋相邻(上下左右四个相邻像素中有海洋)，它就会被淹没。
例如上图中的海域未来会变成如下样?：
.......
.......
.......
.......
....#..
.......
.......
.......
请你计算：依照科学家的预测，照?中有多少岛屿会被完全淹没。
【输?格式】
第??包含?个整数N。 (1 <= N <= 1000)
以下N?N列代表?张海域照?。
照?保证第1?、第1列、第N?、第N列的像素都是海洋。
【输出格式】
?个整数表?答案。
【输?样例】
7
.......
.##....
.##....
....##.
..####.
...###.
.......
【输出样例】
1

BFS

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int[] dx = { -1, 1, 0, 0 }; // 四个方向
	static int[] dy = { 0, 0, -1, 1 };
	private static int n; // 问题规模
	private static char[][] map; // 地图数据
	private static boolean[][] vis; // 标记每个格子是否被访问
	private static int ans = 0;

	private static class Point {
		int x, y;

		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		sc.nextLine(); // 读取换行符
		map = new char[n][n];
		vis = new boolean[n][n];
		for (int i = 0; i < n; i++) {
			map[i] = sc.nextLine().toCharArray();
		}
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (map[i][j] == '#' && !vis[i][j]) {
					bfs(i, j);
				}
			}
		}
		System.out.println(ans);
		sc.close();
	}

	private static void bfs(int x, int y) {
		vis[x][y] = true; // 标记格子为已访问
		int cntOfLand = 0; // 记录陆地的数量
		int cntOfDrowned = 0; // 距离被淹没的陆地数量
		Queue<Point> queue = new LinkedList<Point>();
		queue.add(new Point(x, y));
		while (!queue.isEmpty()) {
			Point head = queue.poll();
			cntOfLand++;
			boolean nearSea = false;
			// 探测四周
			for (int d = 0; d < 4; d++) {
				int nx = head.x + dx[d];
				int ny = head.y + dy[d];
				if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
					if (map[nx][ny] == '.') {
						nearSea = true; // 该陆地被淹没
					}
					if (map[nx][ny] == '#' && !vis[nx][ny]) {
						queue.add(new Point(nx, ny)); // 周边有没有被访问的陆地，就入队
						vis[nx][ny] = true;
					}
				}
			}
			if (nearSea) {
				cntOfDrowned++;
			}
		}
		if (cntOfLand == cntOfDrowned) {
			ans++; // 一个岛屿的区域被遍历完之后，看看有没有被全部淹没
		}
	}
}