藍(lán)橋杯2024年真題java B組 【H.拼十字】

原題鏈接：拼十字
思路：

使用樹狀數(shù)組或線段樹解決。

先將輸入的信息存入到一個(gè)n行3列的數(shù)組中，將信息排序，按照長度小到大，長相同時(shí)，寬度小到大
排序。
建立三個(gè)樹狀數(shù)組，維護(hù)三種顏色對(duì)應(yīng)的信息，樹狀數(shù)組的索引就是數(shù)據(jù)的寬度，值就是有幾個(gè)這樣寬度的數(shù)據(jù)。
遍歷數(shù)組每組數(shù)據(jù)：
當(dāng)顏色為0時(shí)，假設(shè)該組數(shù)據(jù)為6 3 0，則要求的就是其他兩個(gè)顏色中寬度比當(dāng)前寬度大的（因?yàn)殚L度已經(jīng)從小到大排過序），也就是去1,2樹狀數(shù)組中找寬度比當(dāng)前3的寬度大的，就是下標(biāo)大于3的（就是寬度大于三的），就是1,2樹狀數(shù)組中的4到無窮大（就是到N）的和。
將該組數(shù)據(jù)加到對(duì)應(yīng)的樹狀數(shù)組0中去，就是tree0.add(arr[i][1],1)

其他兩種情況同理。
該過程中的樹狀數(shù)組中的很多空間是無效的，但還是通過了。

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;//數(shù)據(jù)信息，一行存儲(chǔ)一個(gè)數(shù)據(jù)項(xiàng)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;//排序，先按照長度升序排序，在按照寬度進(jìn)行升序排序Arrays.sort(arr, (a, b) -> {if (a[0] != b[0]) {return Integer.compare(a[0], b[0]); // 按 arr[i][0] 升序}return Integer.compare(a[1], b[1]); // 如果 arr[i][0] 相同，按 arr[i][1] 升序});for (int i = 1; i <= n; i++) {//將當(dāng)前的節(jié)點(diǎn)加入線段樹中//先求和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];}//獲取最右邊的1public long lowBit(int i) {return i & -i;}public void add(int i,long  val) {while (i <= N) {tree[i] += val;i += lowBit(i);}}//計(jì)算的是原數(shù)組中的 1-i 對(duì)應(yīng)的和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);}
}