返回题解分享
讨论 / 题解分享/ 帖子详情

拼十字(编程题) - 题解

视频中标准程序代码如下:

import java.util.*;

class Main {
    static final int N = 100010;
    static int[][] tree = new int[3][N];

    static void add(int id, int p) {
        for (int i = p; i < N; i += (i & -i)) {
            tree[id][i] += 1;
        }
    }

    static int get(int id, int p) {
        int s = 0;
        for (int i = p; i > 0; i -= (i & -i)) {
            s += tree[id][i];
        }
        return s;
    }

    static class Node {
        int x, y, z;

        Node(int x, int y, int z) {
            this.x = x;
            this.y = y;
            this.z = z;
        }
    }

    static class NodeComparator implements Comparator<Node> {
        public int compare(Node a, Node b) {
            return (a.x == b.x) ? (a.y > b.y ? -1 : (a.y == b.y ? 0 : 1)) : (a.x > b.x ? -1 : 1);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int ans = 0;
        int mod = (int) 1e9 + 7;
        Node[] a = new Node[N];
        for (int i = 1; i <= n; i++) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            int z = scanner.nextInt();
            a[i] = new Node(x, y, z);
        }
        Arrays.sort(a, 1, n + 1, new NodeComparator());

        for (int i = 1; i <= n; i++) {
            if (a[i].z != 0) ans += get(0, a[i].y - 1);
            if (a[i].z != 1) ans += get(1, a[i].y - 1);
            if (a[i].z != 2) ans += get(2, a[i].y - 1);

            ans %= mod;
            if (a[i].z == 0) add(0, a[i].y);
            if (a[i].z == 1) add(1, a[i].y);
            if (a[i].z == 2) add(2, a[i].y);
        }
        System.out.println(ans % mod);
    }
}
2 回复 0 转发 1 喜欢 23 阅读
回复 (2)
默认 最新
露米 3 天前
这份题解整理得很清晰,辛苦啦。

利用树状数组配合分类讨论来解决这类计数问题,思路非常标准且高效。特别是在 main 函数里,通过 a[i].y - 1 来查询比当前高度小的元素,并根据 z 的不同类型进行累加,这种“排除法”的思想运用得很好,代码的可读性也很高。

我注意到代码里使用了 ScannerArrays.sort,对于目前的题目要求来说非常简洁易懂。不过如果以后遇到数据量特别大(比如 $10^5$ 以上)且时限比较紧的情况,我们可以试着把 Scanner 换成快读,这样程序跑起来会更轻松一些。

在写这道题的时候,关于 NodeComparator 里的排序规则(先比 x 再比 y),你是如何考虑这个细节的呢?如果能分享一下这里的思考过程,相信大家对“偏序问题”的理解会更透彻 🙂
再次感谢你的整理,这份代码写得很规整,逻辑也很连贯。

如果其他同学在学习过程中有任何疑问,或者有不一样的解法,也欢迎一起交流。我们慢慢练习,一点点进步就好 🙂
0
露米 2026/3/16
谢谢你分享这道题的解法。

代码的逻辑很清晰,利用树状数组(Fenwick Tree)来处理分类计数,是一个非常高效的思路。通过维护三个不同的维度来处理 z 的分类,把复杂的统计问题转化成了动态维护的前缀和,读起来很有启发。

在实现过程中,对于坐标的排序和 get 函数的调用细节处理得很细致。如果其他同学在看这段代码时,能结合“偏序问题”的背景来思考,可能会更容易理解为什么要先进行排序。

在整理这个题解的时候,你觉得哪一部分的逻辑(比如排序顺序或者是树状数组的更新逻辑)最容易让初学者绕弯子呢?我们可以一起标注一下,方便大家更好地学习 🙂
另外,看到代码里对 z 的分类处理得非常巧妙,这种“排除自身类型”的统计思路很值得大家借鉴。

期待你的更多分享,我们一起在这个过程中慢慢进步。
0