当前位置: 首页 > news >正文

蓝桥杯2024年真题java B组 【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.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);}
}

相关文章:

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

蓝桥杯2024年真题java B组 【H.拼十字】 原题链接&#xff1a;拼十字 思路&#xff1a; 使用树状数组或线段树解决。 先将输入的信息存入到一个n行3列的数组中&#xff0c;将信息排序&#xff0c;按照长度小到大&#xff0c;长相同时&#xff0c;宽度小到大 排序。 建立三个…...

Spring MVC 程序开发(1)

目录 1、什么是 SpringMVC2、返回数据2.1、返回 JSON 对象2.2、请求转发2.3、请求重定向2.4、自定义返回的内容 1、什么是 SpringMVC 1、Tomcat 和 Servlet 分别是什么&#xff1f;有什么关系&#xff1f; Servlet 是 java 官方定义的 web 开发的标准规范&#xff1b;Tomcat 是…...

PyCharm接入本地部署DeepSeek 实现AI编程!【支持windows与linux】

今天尝试在pycharm上接入了本地部署的deepseek&#xff0c;实现了AI编程&#xff0c;体验还是很棒的。下面详细叙述整个安装过程。 本次搭建的框架组合是 DeepSeek-r1:1.5b/7b Pycharm专业版或者社区版 Proxy AI&#xff08;CodeGPT&#xff09; 首先了解不同版本的deepsee…...

Linux服务升级:Almalinux 升级 DeepSeek-R1

目录 一、实验 1.环境 2.Almalinux 部署 Ollama 3.Almalinux 升级 DeepSeek-R1 4.Almalinux 部署 docker 5. docker 部署 DeepSeek-R1 6.Almalinux 部署 Cpolar (内网穿透) 7.使用cpolar内网穿透 二、问题 1.构建容器失败 一、实验 1.环境 &#xff08;1&#xff09…...

Linux操作系统5- 补充知识(可重入函数,volatile关键字,SIGCHLD信号)

上篇文章&#xff1a;Linux操作系统5-进程信号3&#xff08;信号的捕捉流程&#xff0c;信号集&#xff0c;sigaction&#xff09;-CSDN博客 本篇Gitee仓库&#xff1a;myLerningCode/l26 橘子真甜/Linux操作系统与网络编程学习 - 码云 - 开源中国 (gitee.com) 目录 一. 可重入…...

ctfshow刷题笔记—栈溢出—pwn61~pwn64

目录 前言 一、pwn61&#xff08;输出了什么&#xff1f;&#xff09; 二、pwn62&#xff08;短了一点&#xff09; 三、pwn63(又短了一点) 四、pwn64(有时候开启某种保护并不代表这条路不通) 五、一些shellcode 前言 这几道都是与shellcode有关的题&#xff0c;实在是…...

java23种设计模式-责任链模式

责任链模式(Chain of Responsibility Pattern)学习笔记 编程相关书籍分享:https://blog.csdn.net/weixin_47763579/article/details/145855793 DeepSeek使用技巧pdf资料分享:https://blog.csdn.net/weixin_47763579/article/details/145884039 🌟 模式定义 责任链模式是…...

新一代跨境电商ERP系统:从订单到发货的全流程自动化管理

随着全球电商市场的持续扩张&#xff0c;跨境电商卖家面临着多平台运营、国际物流、税务合规等复杂挑战。如何高效整合订单、库存、物流和财务数据&#xff0c;实现从客户下单到商品交付的无缝衔接&#xff0c;成为企业降本增效的关键。Zoho Books作为一款专为跨境商家设计的智…...

苹果廉价机型 iPhone 16e 影像系统深度解析

【人像拍摄差异】 尽管iPhone 16e支持后期焦点调整功能&#xff0c;但用户无法像iPhone 16系列那样通过点击屏幕实时切换拍摄主体。前置摄像头同样缺失人像深度控制功能&#xff0c;不过TrueTone原彩闪光灯系统在前后摄均有保留。 很多人都高估了 iPhone 的安全性&#xff0c;查…...

hive 面试题

Hive基础概念 1.1 Hive是什么&#xff1f; 基于Hadoop的数据仓库工具&#xff0c;支持类SQL&#xff08;HiveQL&#xff09;查询&#xff0c;底层转换为MapReduce/Tez/Spark任务。 核心功能&#xff1a;数据ETL、查询、分析&#xff1b;定位&#xff1a;OLAP&#xff08;分析…...

VScode在windows10上使用clang-format

用途&#xff1a;自动调整代码格式&#xff0c;如缩进等。 clang-format官方文档&#xff1a;ClangFormat — Clang 21.0.0git documentation 前提&#xff1a;有一个.clang-format文件 下载LLVM&#xff1a;https://github.com/llvm/llvm-project/releases&#xff0c;将可…...

AWS API Gateway灰度验证实现

在微服务架构中,灰度发布(金丝雀发布)是验证新版本稳定性的核心手段。通过将小部分流量(如 10%)导向新版本服务,可以在不影响整体系统的情况下快速发现问题。AWS API Gateway 原生支持流量按比例分配功能,无需复杂编码即可实现灰度验证。本文将详细解析其实现方法、最佳…...

【每日八股】MySQL篇(三):索引(上)

目录 MySQL 为什么使用 B 树来做索引&#xff0c;它的优势是什么&#xff1f;特性和定义B 树和 B 树的对比拓展&#xff1a;既然 B 树相较于 B 树优势如此之大&#xff0c;为什么 nosql 的 MongoDB 底层仍采用 B 树而不是 B 树&#xff1f; 使用 B 树做索引的优势补充&#xff…...

在Pycharm中将ui文件修改为py文件

在Pycharm中将ui文件修改为py文件 有些时候&#xff0c;我们需要把QTDesigner生成的.ui文件修改为.py文件 在一些教程中&#xff0c;通常使用cmd打开终端修改&#xff0c;或者是有一些人写了一些脚本来修改 这里我们可以使用pycharm来快速的修改 首先&#xff0c;我们在pyc…...

看视频学习方法总结

以下是提高教学视频吸收率的系统性方法&#xff0c;结合认知科学原理和实际学习场景&#xff0c;帮助您最大化学习效果&#xff1a; 一、观看前的黄金准备阶段 60秒快速扫描法 用1分钟快速浏览视频目录、章节标题和简介&#xff0c;建立知识框架。荷兰伊拉斯姆斯大学实验表明&…...

Matlab 大量接单

分享一个matlab接私活、兼职的平台 1、技术方向满足任一即可 2、技术要求 3、最后 技术方向满足即可 MATLAB&#xff1a;熟练掌握MATLAB编程语言&#xff0c;能够使用MATLAB进行数据处理、机器学习和深度学习等相关工作。 机器学习、深度学习、强化学习、仿真、复现、算法、…...

《深度剖析:生成对抗网络中生成器与判别器的高效协作之道》

在人工智能的前沿领域&#xff0c;生成对抗网络&#xff08;GAN&#xff09;以其独特的对抗学习机制&#xff0c;为数据生成和处理带来了革命性的变革。生成器与判别器作为GAN的核心组件&#xff0c;它们之间的协作效率直接决定了GAN在图像生成、数据增强、风格迁移等众多应用中…...

Android6到Android15版本新增的功能和api

Android6到Android15版本新增的功能和api 文章目录 Android6到Android15版本新增的功能和api一、前言二、Android6 后的版本迭代1、Android 6.0&#xff08;Marshmallow&#xff0c;API 级别 23&#xff09;新增功能重要 API 2、Android 7.0&#xff08;Nougat&#xff0c;API …...

【现代Web布局与动画技术:卡片组件实战分享】

&#x1f4f1; 现代Web布局与动画技术&#xff1a;卡片组件实战分享 &#x1f680; 引言 &#x1f31f; 在过去的开发过程中&#xff0c;我们共同实现了一个功能丰富的卡片组件&#xff0c;它不仅美观&#xff0c;还具有交互性和响应式设计。这篇文章将分享这个组件背后的技术…...

计算机网络之传输层(传输层提供的服务)

一、可靠的数据传输 传输层提供可靠的数据传输服务&#xff0c;确保数据在传输过程中不丢失、不重复、不乱序&#xff0c;并且能够被正确接收。这通常通过面向连接的协议&#xff08;如TCP&#xff09;来实现&#xff0c;TCP通过确认、重传、序号等机制来保证数据传输的可靠性…...

java 实现excel文件转pdf | 无水印 | 无限制

文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...

WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成

厌倦手动写WordPress文章&#xff1f;AI自动生成&#xff0c;效率提升10倍&#xff01; 支持多语言、自动配图、定时发布&#xff0c;让内容创作更轻松&#xff01; AI内容生成 → 不想每天写文章&#xff1f;AI一键生成高质量内容&#xff01;多语言支持 → 跨境电商必备&am…...

ardupilot 开发环境eclipse 中import 缺少C++

目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在 GPU 上对图像执行 均值漂移滤波&#xff08;Mean Shift Filtering&#xff09;&#xff0c;用于图像分割或平滑处理。 该函数将输入图像中的…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中&#xff0c;新增了一个本地验证码接口 /code&#xff0c;使用函数式路由&#xff08;RouterFunction&#xff09;和 Hutool 的 Circle…...

laravel8+vue3.0+element-plus搭建方法

创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

jmeter聚合报告中参数详解

sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample&#xff08;样本数&#xff09; 表示测试中发送的请求数量&#xff0c;即测试执行了多少次请求。 单位&#xff0c;以个或者次数表示。 示例&#xff1a;…...

打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用

一、方案背景​ 在现代生产与生活场景中&#xff0c;如工厂高危作业区、医院手术室、公共场景等&#xff0c;人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式&#xff0c;存在效率低、覆盖面不足、判断主观性强等问题&#xff0c;难以满足对人员打手机行为精…...