制作网站的发展前景,手机网站 手机app,专业网站建设效果,全自动网页制作系统源码蓝桥杯2024年真题java B组 【H.拼十字】
原题链接#xff1a;拼十字 思路#xff1a;
使用树状数组或线段树解决。
先将输入的信息存入到一个n行3列的数组中#xff0c;将信息排序#xff0c;按照长度小到大#xff0c;长相同时#xff0c;宽度小到大 排序。 建立三个…蓝桥杯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.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) {//将当前的节点加入线段树中//先求和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);}}//计算的是原数组中的 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);}
}
