Offer收割赛51题目简要分析

4
4

A. 灯光控制

出题人原意是只有以下两条"射线"上的灯会被点亮：

(X, Y), (X+A, Y+B), (X+2A, Y+2B) ...
(X, Y), (X+C, Y+D), (X+2C, Y+2D)...

我们将(A, B)和(C, D)看作两个向量，如果它们方向不同，我们就可以单独计算每条射线上的亮灯，最后相加再减1就是答案。

如果它们方向相同，我们需要用容斥原理，减去被重复计算的灯。会被重复计算的灯一定也都在某个向量(E, F)上，(E, F)是(A, B)和(C, D)的"最小公倍"。例如(3, 6)和(4, 8)的最小公倍是(12, 24)。

另外在单独计算一条射线上的亮灯时需要讨论A和B是正、负还是0。

B. 相似字符串

对于任意字符串S，与S相似的字符串有26种。我们把其中首字符是A的当作S的代表。

显然相似字符串的代表都是相同的，例如"ABC", "DEF", "ZAB"的代表都是"ABC"。

所以我们求出每个字符串的代表，并且把代表扔进一个set里，最后输出集合的大小即可。

C. 等差子数列

首先我们可以用O(N)的预处理求出从每个位置开始，向右最长能扩展的等差数列的长度。不妨记作S数组。

例如对于A = [1, 2, 3, 5, 7, 9]，对应的S = [3, 2, 4, 3, 2, 1]。

当我们面临查询L, R时，我们可以找出S[L], S[L+1], ... S[R]中最大的值，这是一个经典的RMQ问题，有O(NlogN)的预处理+O(logN)每次查询的解法。

不妨设最大值是S[x]。这时我们要比较x+S[x]-1同R的大小关系，如果x+S[x]-1<=R，那么S[x]就是答案。

否则，意味着由于R的限制，从x开始等差数列只有R-x+1项。这时我们再查询S[L], S[L+1], ... S[x-1]的最大值，仍是一个RMQ问题，不妨设最大值是S[y]。

S[y]和R-x+1中较大的值就是答案。

D. 评论框排版

首先可以发现一点是，一旦两个评论框位置连在一起，就再也不会分开了。只可能整体被向后推。

所以我们可以将连在一起的评论框合并成一个"大区间"，例如三个评论框位置分别是[5, 10], [11, 13], [14, 20]就可以合并成一个大区间[5, 20]。

我们可以用并查集来处理评论框和大区间的合并，这样可以快速查找一个评论框属于哪个大区间，以及一个评论框与大区间的相对位置。

把评论框合并成大区间之后，大区间两两之间是相离的。所以我们可以把大区间都放在一个平衡树(map)里，key是大区间的左边界，这样可以

1) 当要插入一个评论框时，O(logN)找到空行位置

2) O(logN)进行大区间的插入、删除

当我们插入一个新的评论框时，可能会"推挤"后面的大区间。一个大区间被推挤意味着这个大区间会被合并到新插入的评论框所在的大区间，使得大区间总数-1。所以依次处理每个被推挤的大区间均摊时间复杂度是O(1)的。

2 answer(s)

0

有没有人帮忙查查错的，感觉就是依据这个思路，老是过不了 public class Main {

public static void main(String[] args){
    Scanner scanner = new Scanner(System.in);

    int n = scanner.nextInt();
    int m = scanner.nextInt();
    int x = scanner.nextInt();
    int y = scanner.nextInt();
    int a = scanner.nextInt();
    int b = scanner.nextInt();
    int c = scanner.nextInt();
    int d = scanner.nextInt();

    int num = 0;
    int abs_a = Math.abs(a);
    int abs_b = Math.abs(b);
    int abs_c = Math.abs(c);
    int abs_d = Math.abs(d);

    int max_ax = (b > 0 ? (m - y) : (y - 1));
    if(abs_a != 0){
        max_ax = (a > 0 ? (n - x) : (x - 1))/ abs_a;
    }
    int max_by = (a > 0 ? (n - x) : (x - 1));
    if(abs_b != 0){
        max_by = (b > 0 ? (m - y) : (y - 1))/ abs_b;
    }
    int max_cx = (d > 0 ? (m - y) : (y - 1));
    if(abs_c != 0){
        max_cx = (c > 0 ? (n - x) : (x - 1))/ abs_c;
    }
    int max_dy = (c > 0 ? (n - x) : (x - 1));
    if(abs_d != 0){
        max_dy = (d > 0 ? (m - y) : (y - 1))/ abs_d;
    }

    int repeat = 0;
    //在同一象限
    if(a * c > 0 && b * d > 0){
        int abs_ac = abs_a > abs_c ? abs_a % abs_c: abs_c % abs_a;
        int abs_bd = abs_b > abs_d ? abs_b % abs_d: abs_d % abs_b;
        if(abs_ac == 0 && abs_bd == 0){
            if(abs_a >= abs_c && abs_b >= abs_d){
                repeat = Math.min(max_ax, max_by);
            }else if(abs_a <= abs_c && abs_b <= abs_d){
                repeat = Math.min(max_cx, max_dy);
            }
        }
    }else if(a == 0 && c == 0 && b * d >= 0) {
        if(b == 0){
            repeat += Math.min(max_ax, max_by);
        }
        if (d == 0){
            repeat += Math.min(max_cx, max_dy);
        }
        if(b * d > 0){
            int abs_bd = abs_b > abs_d ? abs_b % abs_d: abs_d % abs_b;
            if(abs_bd == 0){
                if(abs_b >= abs_d){
                    repeat = Math.min(max_ax, max_by);
                }else if(abs_b < abs_d){
                    repeat = Math.min(max_cx, max_dy);
                }
            }
        }

    }else if(b == 0 && d == 0 && a * c >= 0){
        if(a == 0){
            repeat += Math.min(max_ax, max_by);
        }
        if(c == 0){
            repeat += Math.min(max_cx, max_dy);
        }
        if(a * c > 0){
            int abs_ac = abs_a > abs_c ? abs_a % abs_c: abs_c % abs_a;
            if(abs_ac == 0){
                if(abs_a >= abs_c){
                    repeat = Math.min(max_ax, max_by);
                }else if(abs_a < abs_c){
                    repeat = Math.min(max_cx, max_dy);
                }
            }
        }
    }

    num = Math.min(max_ax, max_by) + Math.min(max_cx, max_dy) + 1 - repeat;
    System.out.println(num);
}

}

  • 没仔细看，不过你没循环也没递归，最小公倍数怎么求的？正常来说求最小公倍数不是用两数相乘再除以最大公约数么

  • 添加评论
  • ✖reply
0

亮代码

write answer 切换为英文 切换为中文

转发分享

▲