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

每日c/c++题 备战蓝桥杯(P2241 统计方形(数据加强版))

洛谷P2241 统计方形(数据加强版)题解

题目描述

给定一个 n × m n \times m n×m 的方格棋盘,要求统计其中包含的正方形数量和长方形数量(不包含正方形)。输入为两个正整数 n n n m m m,输出两个整数分别表示正方形和长方形的数量。

输入输出样例

输入

2 3

输出

8 10

解题思路

方法一:枚举右下角坐标

核心思想:固定右下角坐标 ( i , j ) (i,j) (i,j),统计以该点为右下角的正方形和矩形数量。

  1. 正方形数量

    • ( i , j ) (i,j) (i,j) 为右下角的正方形边长最大为 min ⁡ ( i , j ) \min(i,j) min(i,j)
    • 例如,当 i = 2 , j = 3 i=2, j=3 i=2,j=3 时,最大边长为 2 2 2,可形成 2 2 2 个正方形(边长为 1 1 1 2 2 2)。
  2. 矩形数量

    • ( i , j ) (i,j) (i,j) 为右下角的矩形数量为 i × j i \times j i×j(长为 i i i,宽为 j j j 的矩形)。
  3. 累加结果

    • 遍历所有右下角坐标 ( i , j ) (i,j) (i,j),累加正方形和矩形数量。
    • 长方形数量 = 矩形总数 - 正方形总数。

代码实现

#include <bits/stdc++.h>
using namespace std;int main() {long long n, m;cin >> n >> m;long long square = 0, rectangle = 0;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {square += min(i, j);          // 累加正方形rectangle += i * j;           // 累加矩形}}cout << square << " " << rectangle - square << endl;return 0;
}

方法二:数学公式法

核心思想:通过数学公式直接计算正方形和矩形总数。

  1. 正方形总数

    • 边长为 k k k 的正方形数量为 ( n − k + 1 ) × ( m − k + 1 ) (n-k+1) \times (m-k+1) (nk+1)×(mk+1)
    • 遍历 k k k 1 1 1 min ⁡ ( n , m ) \min(n,m) min(n,m),累加所有可能边长的正方形数量:
      square_total = ∑ k = 1 min ⁡ ( n , m ) ( n − k + 1 ) ( m − k + 1 ) \text{square\_total} = \sum_{k=1}^{\min(n,m)} (n-k+1)(m-k+1) square_total=k=1min(n,m)(nk+1)(mk+1)
  2. 矩形总数

    • n + 1 n+1 n+1 条横线中选 2 2 2 条,从 m + 1 m+1 m+1 条竖线中选 2 2 2 条,组合数为:
      rectangle_total = n ( n + 1 ) 2 × m ( m + 1 ) 2 \text{rectangle\_total} = \frac{n(n+1)}{2} \times \frac{m(m+1)}{2} rectangle_total=2n(n+1)×2m(m+1)
  3. 长方形数量

    • 长方形数量 = 矩形总数 - 正方形总数。

代码实现

#include <bits/stdc++.h>
using namespace std;int main() {long long n, m;cin >> n >> m;long long square_total = 0, rectangle_total;// 计算正方形总数for (long long k = 1; k <= min(n, m); ++k) {square_total += (n - k + 1) * (m - k + 1);}// 计算矩形总数rectangle_total = (n * (n + 1) / 2) * (m * (m + 1) / 2);cout << square_total << " " << rectangle_total - square_total << endl;return 0;
}

复杂度分析

  • 枚举法:时间复杂度为 O ( n × m ) O(n \times m) O(n×m),适用于 n , m ≤ 5000 n,m \leq 5000 n,m5000 的数据范围。
  • 数学公式法:时间复杂度为 O ( min ⁡ ( n , m ) ) O(\min(n,m)) O(min(n,m)),效率更高,适合处理更大规模的数据。

注意事项

  1. 数据类型:由于结果可能非常大,需使用 long long 类型防止溢出。
  2. 输入范围:题目中 n n n m m m 的范围为 1 ≤ n , m ≤ 5000 1 \leq n,m \leq 5000 1n,m5000,需确保代码能处理大数运算。

总结

本题可通过枚举法或数学公式法解决。枚举法直观易懂,适合初学者;数学公式法效率更高,适合处理大规模数据。实际编码中可根据需求选择合适的方法。

相关文章:

每日c/c++题 备战蓝桥杯(P2241 统计方形(数据加强版))

洛谷P2241 统计方形&#xff08;数据加强版&#xff09;题解 题目描述 给定一个 n m n \times m nm 的方格棋盘&#xff0c;要求统计其中包含的正方形数量和长方形数量&#xff08;不包含正方形&#xff09;。输入为两个正整数 n n n 和 m m m&#xff0c;输出两个整数分…...

LLaVA:开源多模态大语言模型深度解析

一、基本介绍 1.1 项目背景与定位 LLaVA(Large Language and Vision Assistant)是由Haotian Liu等人开发的开源多模态大语言模型,旨在实现GPT-4级别的视觉-语言交互能力。该项目通过视觉指令微调技术,将预训练的视觉编码器与语言模型深度融合,在多个多模态基准测试中达到…...

基于Spring Boot + Vue的母婴商城系统( 前后端分离)

一、项目背景介绍 随着母婴行业在互联网平台的快速发展&#xff0c;越来越多的家庭倾向于在线选购母婴产品。为了提高商品管理效率和用户购物体验&#xff0c;本项目开发了一个基于 Spring Boot Vue 技术栈的母婴商城系统&#xff0c;实现了商品分类、商品浏览、资讯展示、评…...

HNUST湖南科技大学-软件测试期中复习考点(保命版)

使用说明&#xff1a;本复习考点仅用于及格保命。软件测试和其他专业课不太一样&#xff0c;记忆的太多了&#xff0c;只能说考试的时候&#xff0c;想到啥就写啥&#xff0c;多写一点&#xff01;多写一点&#xff01;多写一点&#xff01;&#xff08;重要事情说三遍&#xf…...

【AI智能推荐系统】第七篇:跨领域推荐系统的技术突破与应用场景

第七篇:跨领域推荐系统的技术突破与应用场景 提示语:🔥 “打破数据孤岛,实现1+1>2的推荐效果!深度解析美团、亚马逊如何用跨领域推荐技术实现业务协同,知识迁移核心技术全公开!” 目录 跨领域推荐的商业价值跨领域推荐技术体系 2.1 基于共享表征的学习2.2 迁移学习…...

【现代深度学习技术】注意力机制04:Bahdanau注意力

【作者主页】Francek Chen 【专栏介绍】 ⌈ ⌈ ⌈PyTorch深度学习 ⌋ ⌋ ⌋ 深度学习 (DL, Deep Learning) 特指基于深层神经网络模型和方法的机器学习。它是在统计机器学习、人工神经网络等算法模型基础上&#xff0c;结合当代大数据和大算力的发展而发展出来的。深度学习最重…...

使用FastAPI和React以及MongoDB构建全栈Web应用01 概述

Are you ready to craft digital experiences that captivate and convert? 您准备好打造令人着迷并能带来转变的数字体验了吗&#xff1f; In a world driven by innovation, the demand for robust and scalable web applications has never been higher. Whether you’re…...

Flutter - UIKit开发相关指南 - 概览

环境 Flutter 3.29 macOS Sequoia 15.4.1 Xcode 16.3 概览 UIView与Widgets的比较 在UIKit使用UIView类的对象进行页面开发,布局也是UIView类的对象,在Flutter中使用的是Widget,在概念上Widget可以理解成UIView。 差异&#xff1a; 有效期: Widgets是不可变的,它的生存期只…...

扩容 QCOW2 磁盘镜像文件

&#x1f308; 个人主页&#xff1a;Zfox_ 目录 ✅ 一、扩展 QCOW2 文件大小✅ 二、启动虚拟机后扩展分区和文件系统方式一&#xff1a;如果使用的是标准分区&#xff08;如 /dev/vda1&#xff09;方式二&#xff1a;使用 gparted&#xff08;图形工具&#xff09; ✅ 总结 &am…...

【ts】for in对象时,ts如何正确获取对应的属性值

第一种&#xff1a;for…in keyof&#xff1a;适合需要遍历对象属性键并动态访问值的场景。 keyof typeof obj是ts的类型操作符&#xff0c;用于获取对象obj的所有属性键的联合类型&#xff08;“name” | “age” | “city”&#xff09;通过obj[key keyof typeof obj]&…...

软考 系统架构设计师系列知识点之杂项集萃(55)

接前一篇文章&#xff1a;软考 系统架构设计师系列知识点之杂项集萃&#xff08;54&#xff09; 第89题 某软件公司欲开发一个Windows平台上的公告板系统。在明确用户需求后&#xff0c;该公司的架构师决定采用Command模式实现该系统的界面显示部分&#xff0c;并设计UML类图如…...

绑定 SSH key(macos)

在 macOS 上绑定 Gitee 或 GitHub 的 SSH Key&#xff0c;通常分为以下几步操作&#xff0c;包括生成 SSH key、添加到 ssh-agent&#xff0c;并配置到 Gitee 或 GitHub 平台。 1. 检查是否已有 SSH Key ls -al ~/.ssh 看看是否已有 id_rsa 或 id_ed25519 等文件。如果没有就…...

PyTorch API 6 - 编译、fft、fx、函数转换、调试、符号追踪

文章目录 torch.compiler延伸阅读 torch.fft快速傅里叶变换辅助函数 torch.func什么是可组合的函数变换&#xff1f;为什么需要可组合的函数变换&#xff1f;延伸阅读 torch.futurestorch.fx概述编写转换函数图结构快速入门图操作直接操作计算图使用 replace_pattern() 进行子图…...

Unreal 从入门到精通之VR常用操作

文章目录 前言1.如何设置VRPawn视角的位置。2.如何播放视频3.如何播放VR全景视频。4.如何打开和关闭VR模式。前言 我们使用Unreal5 开发VR 项目的时候,会遇到很多常见问题。 比如: 1.如何设置VRPawn视角的位置。 2.如何播放视频。 3.如何播放VR全景视频。 4.如何打开和关闭V…...

Dify使用总结

最近完成了一个Dify的项目简单进行总结下搭建服务按照官方文档操作就行就不写了。 进入首页之后由以下组成&#xff1a; 探索、工作室、知识库、工具 探索&#xff1a; 可以展示自己创建的所有应用&#xff0c;一个应用就是一个APP&#xff0c;可以进行测试使用 工作室包含…...

事务连接池

一、事务概述 &#xff08;一&#xff09;事务的定义 事务是数据库提供的一种特性&#xff0c;用于确保数据操作的完整性和一致性。事务将多个数据操作组合成一个逻辑单元&#xff0c;这些操作要么全部成功&#xff0c;要么全部失败。 &#xff08;二&#xff09;事务的特性…...

如何用AWS Lambda构建无服务器解决方案:实战经验与场景解析

一、为什么开发者都在关注Serverless&#xff1f; 一、为什么开发者都在关注Serverless&#xff1f; 在云计算高速发展的今天&#xff0c;“无服务器架构”正成为技术新宠。根据Gartner预测&#xff0c;到2025年全球将有50%企业采用Serverless技术。而作为无服务器领域的领头…...

Android Compose 框架物理动画之捕捉动画深入剖析(29)

Android Compose 框架物理动画之捕捉动画深入剖析 一、引言 在 Android 应用开发中&#xff0c;动画是提升用户体验的关键元素之一。它能够让界面更加生动、交互更加自然。Android Compose 作为新一代的声明式 UI 框架&#xff0c;为开发者提供了强大且灵活的动画能力。其中&…...

Jmeter中的Json提取器如何使用?

在JMeter中使用JSON提取器可以方便地从JSON格式的响应数据中提取特定字段的值。以下是详细步骤和示例&#xff1a; 1. 添加JSON提取器 右击目标HTTP请求 -> 选择 添加 -> 后置处理器 -> JSON提取器。 2. 配置JSON提取器参数 变量名称&#xff08;Names of created…...

STM32中断

STM32 GPIO外部中断简图 中断向量表 定义一块固定的内存&#xff0c;以4字节对齐&#xff0c;存放各个中断服务函数程序的首地址 中断向量表定义在启动文件&#xff0c;当发生中断&#xff0c;CPU会自动执行对应的中断服务函数 中断向量表以及中断函数 NVIC嵌套向量中断控制…...

navicat 如何导出数据库表 的这些信息 字段名 类型 描述

navicat 如何导出数据库表 的这些信息 字段名 类型 描述 数据库名字 springbootmt74k 表名字 address SELECT COLUMN_NAME AS 字段名,COLUMN_TYPE AS 类型,COLUMN_COMMENT AS 描述 FROM information_schema.COLUMNS WHERE TABLE_SCHEMA springbootmt74k AND TABLE_NAME a…...

LangGraph(三)——添加记忆

目录 1. 创建MemorySaver检查指针2. 构建并编译Graph3. 与聊天机器人互动4. 问一个后续问题5. 检查State参考 1. 创建MemorySaver检查指针 创建MemorySaver检查指针&#xff1a; from langgraph.checkpoint.memory import MemorySavermemory MemorySaver()这是位于内存中的检…...

数仓-可累计,半累加,不可累加指标,是什么,举例说明及解决方案

目录 1. 可累计指标定义&#xff1a;举例&#xff1a;解决方案&#xff1a; 2. 半累加指标定义&#xff1a;举例&#xff1a;解决方案&#xff1a; 3. 不可累加指标定义&#xff1a;举例&#xff1a;解决方案&#xff1a; 4. 总结对比5. 实际场景中的注意事项 这是数据仓库设计…...

Java ClassLoader双亲委派机制

Java ClassLoader双亲委派机制 1 什么是双亲委派模型 “类加载体系”及ClassLoader双亲委派机制。java程序中的 .java文件编译完会生成 .class文件&#xff0c;而 .class文件就是通过被称为类加载器的ClassLoader加载的&#xff0c;而ClassLoder在加载过程中会使用“双亲委派…...

upload-labs靶场通关详解:第四关

一、分析源代码 可以看出这一关仍然是黑名单验证&#xff0c;但是它禁止了更多的后缀。像php3&#xff0c;php4这类后缀也被加入了黑名单&#xff0c;第三关的方法在这里显然就失效了。那么我们想一想&#xff0c;既然配置文件中存在将php3当作php来执行的功能&#xff0c;那么…...

Webug4.0通关笔记25- 第30关SSRF

目录 一、SSRF简介 1.SSRF原理 2.渗透方法 二、第30关SSRF渗透实战 1.打开靶场 2.渗透实战 &#xff08;1&#xff09;Windows靶场修复 &#xff08;2&#xff09;Docker靶场修复 &#xff08;3&#xff09;获取敏感文件信息 &#xff08;4&#xff09;内网端口与服务…...

【 Redis | 实战篇 缓存 】

目录 前言&#xff1a; 1.认识缓存 2.添加Redis缓存 2.1.根据id查询商铺缓存 2.2.优化根据id查询商铺缓存 3.缓存更新策略 3.1.三种策略 3.2.策略选择 3.3.主动更新的方案 3.4. Cache Aside的模式选择 3.5.最佳实践方案 4.缓存三大问题 4.1.缓存穿透 4.1.1.介绍 …...

数字果园管理系统的设计与实现(Tensorflow的害虫识别结合高德API的害虫定位与Websocket的在线聊天室)

文章目录 技术栈主要功能害虫识别与定位害虫识别的实现训练与测试评估代码模型转化为TFLite预测脚本PredictController预测控制器害虫识别过程展示 害虫定位实现害虫定位代码害虫定位过程展示 专家咨询功能在线咨询聊天室主要前端代码如下主要后端代码如下 技术栈 Spring Boot…...

信息检索(包含源码)

实验目的 掌握逻辑回归模型在二分类问题中的应用方法熟悉机器学习模型评估指标PR曲线&#xff08;精确率-召回率曲线&#xff09;和ROC曲线&#xff08;受试者工作特征曲线&#xff09;的绘制与分析学习使用Python的scikit-learn库进行数据预处理、模型训练与评估理解特征选择…...

【金仓数据库征文】金仓数据库KingbaseES: 技术优势与实践指南(包含安装)

目录 前言 引言 一 : 关于KingbaseES,他有那些优势呢? 核心特性 典型应用场景 政务信息化 金融核心系统&#xff1a; 能源通信行业&#xff1a; 企业级信息系统&#xff1a; 二: 下载安装KingbaseES 三:目录一览表: 四:常用SQL语句 创建表&#xff1a; 修改表结构…...

Java数据结构——二叉树

二叉树 树的概念二叉树满二叉树和完全二叉树二叉树的性质二叉树的遍历 题目练习前序遍历中序遍历后序遍历 前言 已经知道了数据结构中的线性结构&#xff0c;那有没有非线性结构呢&#xff1f; 当然有就像我们文件夹&#xff0c;一个文件夹中有有另一个文件夹&#xff0c;这就是…...

用go从零构建写一个RPC(仿gRPC,tRPC)--- 版本2

在版本1中&#xff0c;虽然系统能够满足基本需求&#xff0c;但随着连接数的增加和处理请求的复杂度上升&#xff0c;性能瓶颈逐渐显现。为了进一步提升系统的稳定性、并发处理能力以及资源的高效利用&#xff0c;版本2引入了三个重要功能&#xff1a;客户端连接池、服务器长连…...

drf 使用jwt

安装jwt pip install pyJwt 添加登录url path("jwt/login",views.JwtLoginView.as_view(),namejwt-login),path("jwt/order",views.JwtOrderView.as_view(),namejwt-order), 创建视图 from django.contrib.auth import authenticateimport jwt from jw…...

202536 | KafKa生产者分区写入策略+消费者分区分配策略

KafKa生产者分区写入策略 1. 轮询分区策略&#xff08;Round-Robin Partitioning&#xff09; 轮询分区策略 是 Kafka 默认的分配策略&#xff0c;当消息没有指定 key 时&#xff0c;Kafka 会采用轮询的方式将消息均匀地分配到各个分区。 工作原理&#xff1a; 每次生产者发…...

《自动驾驶封闭测试场地建设技术要求》 GB/T 43119-2023——解读

目录 一、标准框架与核心内容 二、重点技术要求 三、实施要点与建议 四、实施时间与参考依据 原文链接&#xff1a;国家标准|GB/T 43119-2023 &#xff08;发布&#xff1a;2023-09-07&#xff1b;实施&#xff1a;2024-01-01&#xff09; 一、标准框架与核心内容 适用范围…...

【C++ Qt】容器类(GroupBox、TabWidget)内附思维导图 通俗易懂

每日激励&#xff1a;“不设限和自我肯定的心态&#xff1a;I can do all things。 — Stephen Curry” ✍️绪论​&#xff1a; 本章主要介绍了 Qt 中 QGroupBox 与 QTabWidget 控件。QGroupBox 是带标题的分组框&#xff0c;能容纳其他控件&#xff0c;有标题、对齐方式、是否…...

【SpringBoot】从环境准备到创建SpringBoot项目的全面解析.

本篇博客给大家带来的是SpringBoot的知识点, 包括Idea的干净卸载… &#x1f40e;文章专栏: JavaEE初阶 &#x1f680;若有问题 评论区见 ❤ 欢迎大家点赞 评论 收藏 分享 如果你不知道分享给谁,那就分享给薯条. 你们的支持是我不断创作的动力 . 王子,公主请阅&#x1f680; 要…...

基于ESP32控制的机器人摄像头车

DIY Wi-Fi 控制的机器人摄像头车&#xff1a;从零开始的智能探索之旅 在当今科技飞速发展的时代&#xff0c;机器人技术已经逐渐走进了我们的生活。今天&#xff0c;我将带你一起探索如何制作一个 Wi-Fi 控制的机器人摄像头车&#xff0c;它不仅可以远程操控&#xff0c;还能通…...

Excel图表 vs 专业可视化工具:差距有多大?内容摘要

你是不是还在用 Excel 做图表&#xff0c;觉得它已经够用了&#xff1f;但你知道吗&#xff0c;Excel 和专业的可视化工具之间其实有着巨大的差距&#xff01;Excel 是办公必备&#xff0c;但它的图表功能真的能满足复杂的数据展示需求吗&#xff1f;而那些听起来高大上的专业可…...

Nacos源码—7.Nacos升级gRPC分析三

大纲 5.服务变动时如何通知订阅的客户端 6.微服务实例信息如何同步集群节点 5.服务变动时如何通知订阅的客户端 (1)服务注册和服务订阅时发布的客户端注册和订阅事件的处理 (2)延迟任务的执行引擎源码 (3)处理客户端注册和订阅事件时发布的服务变动和服务订阅事件的处理 (…...

量化学习DAY2-开始批量提交alpha!

量化学习第二天笔记 一、World Quant平台的Alpha概念 在World Quant平台中&#xff0c;alpha本质上是一个数学公式&#xff0c;它是**operator&#xff08;操作&#xff09;与Data&#xff08;数据&#xff09;**的组合。 &#xff08;一&#xff09;Data相关 Data&#xf…...

【Qwen3_ 4b lora xinli 】 task完成实践记录

task 我需要 基于llamafactory框架选取基本上相同的数据集用lora微调Qwen3_ 4b两次并保存lora参数然后分别合并这两个lora参数到基座模型。再换个数据集上接着进行微调。并且保存新的lora参数&#xff0c;然后我们匹配这里面的特征值和特征向量&#xff0c;如果这两个新的lora…...

文旅田园康养小镇规划设计方案PPT(85页)

1. 项目背景与定位 背景&#xff1a;位于长三角经济圈&#xff0c;依托安吉丰富的自然与文化资源&#xff0c;旨在打造集康养、度假、文化体验于一体的综合小镇。 定位&#xff1a;成为浙北地区知名的康养旅游目的地&#xff0c;融合“一溪两岸”规划理念&#xff0c;实现全面…...

[Windows] 能同时打开多个图片的图像游览器JWSEE v2.0

[Windows] 能同时打开多个图片的图像游览器JWSEE 链接&#xff1a;https://pan.xunlei.com/s/VOPpO86Hu3dalYLaZ1ivcTGIA1?pwdhckf# 十多年前收藏的能同时打开多个图片的图像游览器JWSEE v2.0&#xff0c;官网已没有下载资源。 JWSEE v2.0是乌鲁木齐金维图文信息科技有限公司…...

低成本自动化改造技术锚点深度解析

执行摘要 本文旨在深入剖析四项关键的低成本自动化技术&#xff0c;这些技术为工业转型提供了显著的运营和经济效益。文章将提供实用且深入的指导&#xff0c;涵盖老旧设备联网、AGV车队优化、空压机系统智能能耗管控以及此类项目投资回报率&#xff08;ROI&#xff09;的严谨…...

23盘古石决赛

一&#xff0c;流量分析 1. 计算流量包文件的SHA256值是&#xff1f;[答案&#xff1a;字母小写][★☆☆☆☆] 答案&#xff1a;2d689add281b477c82b18af8ab857ef5be6badf253db1c1923528dd73b3d61a9 解压出来流量包计算 2. 流量包长度在“640 - 1279”之间的的数据包总共有多少…...

C语言—指针3

1. 数组名的理解 观察以下代码 可以观察到pa指向的地址与数组首元素地址相同&#xff0c;那么可以说明数组就是首元素地址吗&#xff1f; 这种说法是不严谨的&#xff0c;观察以下代码&#xff1a; 程序输出的结果为16&#xff0c;此时的arr表示的是整个数组的大小。 观察以…...

操作系统 第2章节 进程,线程和作业

一:多道程序设计 1-多道程设计的目的 for:提高吞吐量(作业道数/处理时间),我们可以从提高资源的利用率出发 2-单道程序设计缺点: 设备的利用率低,内存的利用率低,处理机的利用率低 比如CPU去访问内存,CPU空转.内存等待CPU访问也是没有任何操作的.要是有多个东西要去访问不冲…...

数字化转型-4A架构之数据架构

系列文章 数字化转型-4A架构&#xff08;业务架构、应用架构、数据架构、技术架构&#xff09; 数字化转型-4A架构之业务架构 数字化转型-4A架构之应用架构 数据架构 Data Architecture&#xff08;DA&#xff09; 1. 定义 数据架构&#xff0c;是组织管理数据资产的科学之…...

Java中的反射

目录 什么是反射 反射的核心作用 反射的核心类 反射的基本使用 获取Class对象 创建对象 操作字段&#xff08;Field&#xff09; 调用方法&#xff08;Method&#xff09; 反射的应用场景 反射的优缺点 优点 缺点 示例&#xff1a;完整反射操作 总结 什么是反射 …...