蓝桥杯2024年真题javaB组【H.拼十字】

蓝桥杯2024年真题java B组 【H.拼十字】

原题链接：拼十字 思路：

使用树状数组或线段树解决。

先将输入的信息存入到一个n行3列的数组中，将信息排序，按照长度小到大，长相同时，宽度小到大 排序。 建立三个树状数组，维护三种颜色对应的信息，树状数组的索引就是数据的宽度，值就是有几个这样宽度的数据。 遍历数组每组数据： 当颜色为0时，假设该组数据为6 3 0，则要求的就是其他两个颜色中宽度比当前宽度大的（因为长度已经从小到大排过序），也就是去1,2树状数组中找宽度比当前3的宽度大的，就是下标大于3的（就是宽度大于三的），就是1,2树状数组中的4到无穷大（就是到N）的和。 将该组数据加到对应的树状数组0中去，就是tree0.add(arr[i][1],1)

其他两种情况同理。 该过程中的树状数组中的很多空间是无效的，但还是通过了。

code：

import java.io.*; import java.util.Arrays; public class Main { static int N = 100005; static int MOD = 1000000007; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StreamTokenizer in = new StreamTokenizer(br); PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); in.nextToken(); int n = (int) in.nval; //数据信息，一行存储一个数据项 int[][] arr = new int[n + 1][3]; Tree tree0 = new Tree(N); Tree tree1 = new Tree(N); Tree tree2 = new Tree(N); for (int i = 1; i <= n; i++) { in.nextToken(); arr[i][0] = (int) in.nval; in.nextToken(); arr[i][1] = (int) in.nval; in.nextToken(); arr[i][2] = (int) in.nval; } long res = 0; //排序，先按照长度升序排序，在按照宽度进行升序排序 Arrays.sort(arr, (a, b) -> { if (a[0] != b[0]) { return Integer pare(a[0], b[0]); // 按 arr[i][0] 升序 } return Integer pare(a[1], b[1]); // 如果 arr[i][0] 相同，按 arr[i][1] 升序 }); for (int i = 1; i <= n; i++) { //将当前的节点加入线段树中 //先求和 res %= MOD; if (arr[i][2] == 0){ res += tree1.sum(arr[i][1]); res += tree2.sum(arr[i][1]); tree0.add(arr[i][1],1); } else if (arr[i][2] == 1) { res += tree0.sum(arr[i][1]); res += tree2.sum(arr[i][1]); tree1.add(arr[i][1],1); }else{ res += tree0.sum(arr[i][1]); res += tree1.sum(arr[i][1]); tree2.add(arr[i][1],1); } } out.print(res); out.flush(); out.close(); br.close(); } } class Tree{ long[] tree; int N; public Tree(int N){ this.N = N; tree = new long[N + 1]; } //获取最右边的1 public long lowBit(int i) { return i & -i; } public void add(int i,long val) { while (i <= N) { tree[i] += val; i += lowBit(i); } } //计算的是原数组中的 1-i 对应的和 public long query(int i) { long res = 0; while (i > 0) { res += tree[i]; i -= lowBit(i); } return res; } public long sum(int i){ return query(N) - query(i); } }