Co2y's Blog

hihocoder-Offer收割编程练习赛8

发表于 | 分类于 |

2017-03-05 hihocoder[Offer收割]编程练习赛8题解

A

根据题意，如果nd<kl<nd+f，则为”NO”，所以需要f>kl-nd，其中k,n是最接近的两个，而kl-nd是循环的，所以我下面写的是发现循环节且全都满足了就break并打印”YES”。实际上只需要f>gcd(l,d)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.util.Scanner;
public class A {
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        int T;
        T = scanner.nextInt();
        for (int i = 0; i < T; ++i) {
            long l, f, d;
            l = scanner.nextLong();
            f = scanner.nextLong();
            d = scanner.nextLong();
            if (f > l) {
                System.out.println("NO");
                continue;
            }
            if (f == l) {
                if (d % l == 0) System.out.println("YES");
                else System.out.println("NO");
                continue;
            }
            d = d % l;
            long temp = d;
            boolean flag = true;
            for (long j = 1; j <= l; ++j) {
                if (j != 1 && temp == j*d%l) break;
                if ((j * d) / l == (j * d + f) / l)
                    continue;
                System.out.println("NO");
                flag = false;
                break;
            }
            if (flag)
                System.out.println("YES");
        }
    }
}

B

普通的搜索，注意输出时只输出当前部分为’1’的，其余用’0’填充

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class B {
    private static int n, m;
    public static void main(String args[]) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        boolean[][] used = new boolean[n][m];
        char[][] word = new char[n][m];
        for (int i = 0; i < n; i++) {
            String line = scanner.next();
            for (int j = 0; j < m; j++) {
                word[i][j] = line.charAt(j);
            }
        }
        ArrayList<Point> aaa = new ArrayList<>();
        for (int j = 0; j < m; j++) {
            for (int i = 0; i < n; i++) {
                if (word[i][j] == '1' && used[i][j] == false) {
                    dfs(word, i, j, used, aaa);
                    myprint(word, aaa);
                    aaa.clear();
                }
            }
        }
    }
    private static void myprint(char[][] word, ArrayList<Point> aaa) {
        int left = 600, right = -1, up = 600, down = -1;
        for (Point p : aaa) {
            if (p.x < up) up = p.x;
            if (p.x > down) down = p.x;
            if (p.y < left) left = p.y;
            if (p.y > right) right = p.y;
        }
        int x = down - up;
        int y = right - left;
        char[][] pp = new char[x + 1][y + 1];
        for (int i = 0; i <= x; ++i) {
            for (int j = 0; j <= y; ++j) {
                pp[i][j] = '0';
            }
        }
        for (Point p : aaa) {
            pp[p.x - up][p.y - left] = '1';
        }
        System.out.println((x+1) + " " + (y+1));
        for (int i = 0; i <= x; ++i) {
            for (int j = 0; j <= y; ++j) {
                System.out.print(pp[i][j]);
            }
            System.out.println();
        }
    }
    static class Point {
        public int x;
        public int y;
        Point(int a, int b) {
            x = a;
            y = b;
        }
    }
    private static void dfs(char[][] word, int i, int j, boolean[][] used, ArrayList aaa) {
        if (i >= n || j >= m || i < 0 || j < 0) return;
        if (used[i][j] == false && word[i][j] == '1') {
            used[i][j] = true;
            aaa.add(new Point(i, j));
            dfs(word, i + 1, j, used, aaa);
            dfs(word, i - 1, j, used, aaa);
            dfs(word, i, j + 1, used, aaa);
            dfs(word, i, j - 1, used, aaa);
        }
    }
}

C

只理解了O(n^2)的DP，假设DP[k]表示前k个数的分割方法，对于k+1来说，DP[k+1]=DP[k]+…+DP[i]+…+DP[1]其中[i,k+1]的和不为0，这可以用前缀和计算。

D

容斥原理，用总矩形个数减去包含1个黑色矩形的，加上包含2个黑色矩形的…………。重点在于如何计算包含某个矩形的个数，设该矩形上下左右分别距边界a,b,c,d。则结果为(a+1)(b+1)(c+1)(d+1)。想法是，上下左右的点必然落在对应的线段上，而每条线段分别有a+1,b+1,c+1,d+1个点，根据组合数学，从中各取一点的总取法就是乘积。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.Scanner;
public class D {
    public static void main(String[] args) {
        int n, m, k;
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        k = scanner.nextInt();
        int[][] a = new int[k][2];
        for (int i = 0; i < k; ++i) {
            a[i][0] = scanner.nextInt();
            a[i][1] = scanner.nextInt();
        }
        long ans = (long) (n + 1) * n * (m + 1) * m / 4;
        for (int code = 1; code < (1 << k); ++code) {
            int l = m, r = 0, u = n, d = 0, cnt = 0;
            for (int i = 0; i < k; ++i) {
                if ((code & (1 << i)) != 0) {
                    l = Math.min(l, a[i][1]);
                    r = Math.max(r, a[i][1]);
                    u = Math.min(u, a[i][0]);
                    d = Math.max(d, a[i][0]);
                    cnt++;
                }
            }
            if (cnt % 2 == 0) ans += (long) l * u * (m - r + 1) * (n - d + 1);
            else ans -= (long) l * u * (m - r + 1) * (n - d + 1);
        }
        System.out.println(ans);
    }
}