Day14

第一题

第四届2013年蓝桥杯省赛

带分数

一道dfs全排列的题，题解在这篇文章的最后一题：蓝桥杯AcWing学习笔记 1-1递归的学习

第二题

走迷宫

bfs

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

public class Main {	
	
	static final int N = 110;
	static int[][] g = new int[N][N]; // 迷宫
	static boolean[][] st = new boolean[N][N]; // 状态 true表示已走过 
	static int n, m, x1, y1, x2, y2;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		m = sc.nextInt();
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				g[i][j] = sc.nextInt();

		x1 = sc.nextInt();
		y1 = sc.nextInt();
		x2 = sc.nextInt();
		y2 = sc.nextInt();
		
		System.out.println(bfs());
	}
	
	private static int bfs() {
		Queue<PII> q = new LinkedList<>();
		q.offer(new PII(x1, y1, 0));
		
		int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
		while (!q.isEmpty()) {
			PII t = q.poll();
				
			if (t.x == x2 && t.y == y2) return t.step;
				
			for (int i = 0; i < 4; i++) {
				int x = t.x + dx[i], y = t.y + dy[i];
				if (x < 1 || x > n || y < 1 || y > m) continue; // 越界
				if (st[x][y]) continue; // 已遍历过
				if (g[x][y] == 0) continue;
					
				q.offer(new PII(x, y, t.step + 1));
				st[x][y] = true;
			}
		}
		return -1;
	}
	
	static class PII {
		int x;
		int y;
		int step;
		
		public PII(int x, int y, int step) {
			this.x = x;
			this.y = y;
			this.step = step;
		}
	}
}

第三题

蓝桥幼儿园

并查集

并查集不是很会，直接给大家贴蓝oj平台的代码了。

import java.util.Scanner;

public class Main {
    
    static int[] s;
    static int n;
    static int m;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        s = new int[n + 1];
        for (int i = 1; i < n + 1; i++) s[i] = i;
        while (m-- > 0) {
            int op = sc.nextInt();
            int x = sc.nextInt();
            int y = sc.nextInt();
            if (op == 1) mre(x, y);
            if (op == 2) {
                if (find(x) == find(y)) System.out.println("YES");
                else System.out.println("NO");
            }
        }
    }

    private static int find(int x) {
        if (x != s[x]) {
            s[x] = find(s[x]);
        }
        return s[x];
    }
    
    private static void mre(int x, int y) {
        x = find(x);
        y = find(y);
        if (x != y) s[x] = s[y];
    }
}

第四题

NOIP2015提高组

跳石头

贪心+二分

import java.util.Scanner;

public class Main {

    static final int N = 50010;
    static int L, n, m;
    static int[] d = new int[N];

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        L = sc.nextInt();
        n = sc.nextInt();
        m = sc.nextInt();
        for (int i = 1; i <= n; i++) d[i] = sc.nextInt();
        d[n + 1] = L; // 终点 这里换为 d[++n] = L 就不用加输入的if else了 没搞懂

        int l = 1, r = (int) 1e9;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (check(mid)) l = mid;
            else r = mid - 1;
        }
        if (n == 0 || n == m) System.out.println(L);
        else System.out.println(r);
    }

    private static boolean check(int mid) {
        int last = 0, cnt = 0; // last标记上一块石头的位置 cnt计数
        for (int i = 1; i <= n; i++)
            if (d[i] - last < mid) cnt++ ; // 当前石头和上一块石头的距离小于mid，则将当前石头拿走
            else last = d[i]; // 否则将上一块石头更新成当前这块石头
        return cnt <= m;
    }
}