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

【算法】【蓝桥23国A软件C】四版代码思路分析与逐步优化

news 来源：原创 2025/9/16 16:16:46

题目来源：第十四届蓝桥杯大赛软件赛国赛C/C++ 大学 A 组

题目描述：

问题描述

给定一个 W×H 的长方形，两边长度均为整数。小蓝想把它切割为很多个边长为整数的小正方形。假设切割没有任何损耗，正方形的边长至少为 2，不允许出现余料，要求所有正方形的大小相等，请问最多能切割出多少个?

输入格式

输入一行，包含两个整数 W, H，用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。如果不存在满足要求的方案，输出 0。

【测试用例及其规模见文末】

题目解析：

方法一：暴力求解（无关数论）（得分：7/10）

#include <iostream>
using namespace std;
#define ll long long
int main()
{ll w,h;cin>>w>>h;ll a=min(w,h);ll b=max(w,h);  // 取较小的边为 a，较大为 bll ans=0;// 枚举 a 的约数（通过 a/i 形式间接枚举，a/i >= 2 保证正方形边长 ≥2）for(ll i=1; a/i >= 2; i++){if(a % i != 0) continue;   // i 不是 a 的约数，跳过ll cur = a / i;            // cur 是一个候选的正方形边长if(b % cur == 0)           // 如果 b 也能整除 cur，说明 w 和 h 都能被 cur 整除ans = cur;             // 更新当前满足条件的最大正方形边长}// 计算可以切多少个边长为 ans 的正方形ans = (a / ans) * (b / ans);cout << ans;return 0;
}

问题之一：粗心：没有判断找不到的情况，即输出ans=0的情况

思路分析：

目标是找一个最大的正方形边长 d（d ≥ 2），使得 w % d == 0 && h % d == 0，即正方形能完全铺满矩形；
枚举的是 i，通过 cur = a / i，我们得到了 a 的一个因数 cur；
如果 b % cur == 0，那说明 cur 也整除 b，即 cur 同时整除 w 和 h；
记录这个满足条件的最大 cur（实际上随着 i 增加，cur 减小，所以最后 ans 是最大满足条件的正方形边长）；
用这个 ans 去计算：一共能切 (w / ans) * (h / ans) 个正方形。

方法二：暴力求解（优化方法一）（得分：8/10）

#include <iostream>
using namespace std;
#define ll long long
int main()
{ll w,h;cin>>w>>h;ll a=min(w,h);ll b=max(w,h);ll ans=0;for(ll i=1;a/i>=2;i++){if(a%i!=0)continue;ll cur=a/i;if(b%cur==0)ans=cur;}if(ans!=0)ans=(a/ans)*(b/ans);cout<<ans;return 0;
}

优化了ans可能为0的情况

问题：该方法时间复杂度极高，因此有两组测试用例没有通过在 W, H ≤ 10^9 的范围下会超时，尤其在最坏情况（比如 W=10^9, H=10^9-1）下要跑上亿次循环。

假设 a = 10^9，那么最坏情况下你会从 i = 1 枚举到 i ≈ 5×10^8，也就是5亿次循环，这肯定爆了

方法三：暴力求解（优化方法二）（得分：10/10）

#include <iostream>
using namespace std;
#define ll long long
int main()
{ll w,h;cin>>w>>h;ll a=min(w,h);ll b=max(w,h);ll ans=0;for(ll i=a/2;i>=1;i--){if(a%i!=0)continue;ll cur=a/i;if(b%cur==0){ans=cur;break;}}if(ans!=0)ans=(a/ans)*(b/ans);cout<<ans;return 0;
}

为什么它能过所有测试？

从 a/2 开始倒序找 a 的因数，最早遇到的符合条件的就是最大可行边长；
一旦找到了合法边长就 break，省下后续判断；
a/2 → 1 最多只跑 5e8 次（极限），但实际用例中基本很快找到；

方法四：数论方法——最大公因数（得分：10/10）

#include<iostream>
using namespace std;
int gcd(long long a,long long b) {return b==0?a:gcd(b,a%b);//辗转相除法计算最大公约数
}signed main() {int w, h;cin >> w >> h;int up = gcd(w, h);if (up == 1) {cout << 0 << endl;return 0;}int ans = 0;for (int i = 2; i * i <= up; i++) {if (up % i == 0) {ans = i;break;}}if (!ans)ans = up;ans = (w * h) / (ans * ans);cout << ans << endl;return 0;
}

利用辗转相除法计算最大公约数（gcd函数）

方法：

把大数变成小数（用模 %）
交换位置继续递归

直到余数为 0，此时的另一个数就是答案。

测试用例：

样例输入1

10 20

样例输出1

样例说明：切割成 5×10=505×10=50 个边长为 22 的正方形。

样例输入2

6 9

样例输出2

样例输入3

8 13

样例输出3

评测用例规模与约定

对于 30%30% 的评测用例，1≤W,H≤10001≤W,H≤1000;

对于 60%60% 的评测用例，1≤W,H≤1061≤W,H≤106;

对于所有评测用例，1≤W,H≤1091≤W,H≤109。

【算法】【蓝桥23国A软件C】四版代码思路分析与逐步优化

题目来源：第十四届蓝桥杯大赛软件赛国赛C/C 大学 A 组题目描述： 问题描述给定一个 WH 的长方形，两边长度均为整数。小蓝想把它切割为很多个边长为整数的小正方形。假设切割没有任何损耗，正方形的边长至少为 2，不允…...

编程日记 2025/9/16 16:16:46

程序设计竞赛1

题目1 2025年春节期间，DeepSeek作为“AI界的天降紫微星”成为新晋效率神器，热度席卷全球，其团队主创成员也迅速引起了大家的关注。 DeepSeek之所以能在短时间内取得如此不凡成绩，与其团队成员的背景密不可分。团队汇聚了来自清华…...

编程日记 2025/9/15 18:41:37

android studio 2022打开了v1 签名但是生成的apk没有v1签名问题

我使用了Android Studio Flamingo | 2022.2.1 Patch 2版本的IDE编译了一个apk，但是apksigner查看apk的签名信息时，发现只有v2签名，没有v1签名。 apksigner verify -v app-debug.apk Verifies Verified using v1 scheme (JAR signing): false Verified usin…...

编程日记 2025/9/13 21:18:23

EPGAN：融合高效注意力的生成对抗网络图像修复算法

简介简介：利用掩码设计来遮掉输入图像的一部分，将这类图像输入给生成器。生成器结合ECA注意力机制架构，利用感知损失、对抗损失和均方误差损失的加权和来作为生成器的损失计算。鉴别器分别对应掩码和整张图做损失计算。论文题目：融合高效注意力的生成对抗网络图像修复算…...

编程日记 2025/9/16 9:12:41

使用模板报错：_G.unicode.len(orgline.text_stripped:gsub(“ “,““))

使用aegisub制作歌词特效，白嫖大佬的自动化模板时，经常会遇到如下报错： Runtime error in template code: Expected 1 arguments, got 2 Code producing error: ci {0,0}; cn _G.unicode.len(orgline.text_stripped:gsub(" ",&q…...

编程日记 2025/9/11 8:38:28

linux入门六：Linux Shell 编程

一、Shell 概述 1. 什么是 Shell？ Shell 是 Linux 系统中用户与内核之间的桥梁，作为命令解析器，它负责将用户输入的文本命令转换为计算机可执行的机器指令。本质：Shell 是一个程序（如常见的 Bash、Zsh&#xff09…...

编程日记 2025/9/11 3:03:29

Franka 机器人x Dexterity Gen引领遥操作精细任务新时代

教授机器人工具灵活操作难题在教授机器人灵活使用工具方面，目前主要有两种策略：一是人类遥控（用于模仿学习），二是模拟到现实的强化学习。然而，这两种方法均存在明显的局限性。 1、人类遥控（用…...

编程日记 2025/9/11 16:37:16

网络通讯协议UDP转发TCP工具_UdpToTcpRelay_双向版

UDP/TCP网络转发器程序说明书 1. 程序概述本程序是一个高性能网络数据转发工具，支持UDP和TCP协议之间的双向数据转发，并具备以下核心功能： 协议转换：实现UDP↔TCP协议转换数据转换：支持十六进制/ASCII格式的数据转…...

编程日记 2025/9/12 17:57:54

深入理解 RxSwift 中的 Driver：用法与实践

目录前言一、什么是Driver 1.不会发出错误 2.主线程保证 3.可重放 4.易于绑定二、Driver vs Observable 三、使用场景 1.绑定数据到UI控件 2.响应用户交互 3.需要线程安全的逻辑 4.如何使用Driver？ 1.绑定文本输入到Label 2.处理按钮点击事件 3…...

编程日记 2025/9/10 12:10:37

【XML基础-3】深入理解XML Schema：XML的强大语义约束机制

XML（可扩展标记语言）作为数据交换的标准格式，在当今信息技术领域扮演着重要角色。然而，仅有基本的XML语法规则往往不足以满足复杂的数据验证需求。这正是XML Schema发挥作用的地方——它为XML文档提供了强大的语义约束能力。本文将…...

编程日记 2025/9/8 18:26:12

神经网络语言模型与统计语言模型的比较

神经网络语言模型（Neural Language Models, NLMs）与统计语言模型（Statistical Language Models, SLMs）是自然语言处理（NLP）中两类核心的语言建模方法，其核心差异体现在建模方式、表示能力、数据…...

编程日记 2025/9/9 3:03:31

大模型论文：CRAMMING TRAINING A LANGUAGE MODEL ON ASINGLE GPU IN ONE DAY(效率提升)-final

大模型论文：CRAMMING: TRAINING A LANGUAGE MODEL ON ASINGLE GPU IN ONE DAY(效率提升) 文章地址：https://arxiv.org/abs/2212.14034 摘要近年来，语言建模的研究趋势集中在通过大规模扩展来提升性能，导致训练语言模型的成本变…...

编程日记 2025/9/8 20:06:23

构建AI应用（持续更新）

常用的框架： dify、coze：低代码模块化编程 langchain：面向程序人员常规的应用： 语音转文字ASR，文字转语音TTS，下一步问题建议， 旅游计划，买点提取，情感陪聊&#x…...

编程日记 2025/9/15 15:22:23

【JAVA】JVM 堆内存“缓冲空间”的压缩机制及调整方法

1. 缓冲空间是否可压缩？ 是的，JVM 会在满足条件时自动收缩堆内存，将未使用的缓冲空间释放回操作系统。但需满足以下条件： GC 触发堆收缩：某些垃圾回收器（如 G1、Serial、Parallel）在 Full GC …...

编程日记 2025/9/2 11:38:47

NLP高频面试题（三十八）——什么是LLM的灾难性遗忘？如何避免灾难性遗忘？

近年来，大语言模型在人工智能领域取得了显著进展。然而，随着模型的不断更新和新任务的引入，出现了一个重要的问题，即灾难性遗忘（Catastrophic Forgetting）。灾难性遗忘指的是大模型在连续学习新知识或新任务时，先前掌握的旧知识会迅速被覆盖或遗忘，从而导致模型在旧任务…...

编程日记 2025/9/15 17:21:32

Keepalived+LVS高可用集群实战：从原理到落地

在分布式系统架构中，服务的高可用性和负载均衡是保障业务连续性的核心要素。本文通过一次实验，深入探索了基于KeepalivedLVS的高可用负载均衡集群方案，带您从零开始理解原理、动手实践配置，并验证其可靠性。一、实验目标本次实…...

编程日记 2025/9/10 11:01:32

【JVM】JVM调优实战

😀大家好，我是白晨，一个不是很能熬夜😫，但是也想日更的人✈。如果喜欢这篇文章，点个赞👍，关注一下👀白晨吧！你的支持就是我最大的动力！&#x1f4…...

编程日记 2025/9/12 17:18:36

Linux系统安全-开发中注意哪些操作系统安全

Hey小伙伴们~👋 在Linux开发中，确保操作系统的安全真的太太太重要啦！🛡️ 今天就来和大家聊聊几个超关键的注意事项，记得拿小本本记下来哦！📝 1️⃣ ‌用户管理与权限控制‌👥 合理…...

编程日记 2025/9/16 1:31:36

Qt问题之告别软件因系统默认中文输入法导致错误退出的烦恼

1. 问题使用Qt进行研发时，遇到一个问题，当在系统默认输入法中文（英文输入法或者搜狗就不会触发闪退）的情况下，选中QTableWidget控件（QTableWidgetItem有焦点，但是不双击）&#xff…...

编程日记 2025/9/16 1:57:38

2025 年“认证杯”数学中国数学建模网络挑战赛 D题无人机送货规划

在快递和外卖等短途递送小件货物的业务中，无人机或许大有可为。现有一个城市的快递仓库准备使用若干无人机进行派件，设有若干架无人机从仓库出发，分别装载了若干快递包裹。每架无人机装载的包裹的收货地点会被排列为一个目的地列表&#x…...

编程日记 2025/9/14 0:43:28

【2025年认证杯数学中国数学建模网络挑战赛】A题解题思路与模型代码

【2025年认证杯数学建模挑战赛】A题该题为典型的空间几何建模轨道动力学建模预测问题。 ⚙ 问题一：利用多个天文台的同步观测，确定小行星与地球的相对距离问题分析已知若干地面天文台的观测数据：方位角 (Azimuth) 和高度角 (Altitude)&…...

编程日记 2025/9/10 6:57:42

Redhat红帽 RHCE8.0认证体系课程

课程大小：7.7G 课程下载：https://download.csdn.net/download/m0_66047725/90546064 更多资源下载：关注我红帽企业 Linux 系统的管理技能已经成为现代数据中心的核心竞争力。 Linux 在支持混合云、跨物理服务器、虚机、私有云和公共云计…...

编程日记 2025/9/10 0:38:36

Python 实现的运筹优化系统数学建模详解(最大最小化模型)

一、引言在数学建模的实际应用里，最大最小化模型是一种极为关键的优化模型。它的核心目标是找出一组决策变量，让多个目标函数值里的最大值尽可能小。该模型在诸多领域，如资源分配、选址规划等，都有广泛的应用。本文将深入剖析最大…...

编程日记 2025/8/31 6:37:43

MySQL快速入门

MySQL快速入门 SQL语句 SQL语句概述 1.SQL 是用于访问和处理数据库的标准的计算机语言。 2.SQL指结构化查询语言，全称是 Structured Query Language。 3.SQL 可以访问和处理数据库。 4.SQL 是一种 ANSI（American National Standards Institute 美国…...

编程日记 2025/9/10 1:04:37

离线安装 nvidia-docker2(nvidia-container-toolkit)

很多时候大家都有用docker使用gpu的需求，但是因为网络等原因不是那么好用，这里留了一个给ubuntu的安装包，网络好的话也提供了在线安装方式安装 nvidia-docker2 1 离线安装 （推荐） unzip解压后进入目录 dpkg -i *.d…...

编程日记 2025/9/9 1:32:13

【自然语言处理】深度学习中文本分类实现

文本分类是NLP中最基础也是应用最广泛的任务之一，从无用的邮件过滤到情感分析，从新闻分类到智能客服，都离不开高效准确的文本分类技术。本文将带您全面了解文本分类的技术演进，从传统机器学习到深度学习，手把手实现一套…...

编程日记 2025/9/16 4:50:22

云原生运维在 2025 年的发展蓝图

随着云计算技术的不断发展和普及，云原生已经成为了现代应用开发和运维的主流趋势。云原生运维是指在云原生环境下，对应用进行部署、监控、管理和优化的过程。在 2025 年，云原生运维将迎来更加广阔的发展前景，同时也将面临着一系列…...

编程日记 2025/9/12 4:29:02

Windows系统Python多版本运行解决TensorFlow安装问题（附详细图文）

Windows系统Python多版本运行解决TensorFlow安装问题（附详细图文） 摘要 TensorFlow 无法安装？Python版本太高是元凶！ 本文针对Windows系统中因Python版本过高导致TensorFlow安装失败的问题，提供三种降级解决方案&…...

编程日记 2025/9/12 13:31:35

银行业务知识序言

银行业务知识体系全景解析第一章金融创新浪潮下的银行业务知识革命 1.1 数字化转型驱动金融业态重构在区块链、人工智能、物联网等技术的叠加作用下，全球银行业正经历着"服务无形化、流程智能化、风控穿透化"的深刻变革。根据麦肯锡《2023全球银行业…...

编程日记 2025/9/3 19:46:37

《深度剖析分布式软总线：软时钟与时间同步机制探秘》

在分布式系统不断发展的进程中，设备间的协同合作变得愈发紧密和复杂。为了确保各个设备在协同工作时能够有条不紊地进行，就像一场精准的交响乐演出，每个乐器都要在正确的时间奏响音符，分布式软总线中的软时钟与时间同步机制应运而…...

编程日记 2025/9/10 22:32:48

RK3588 android12 适配 ilitek i2c接口TP

一，Ilitek 触摸屏简介 Ilitek 提供多种型号的触控屏控制器，如 ILI6480、ILI9341 等，采用 I2C 接口。这些控制器能够支持多点触控，并具有优秀的灵敏度和响应速度。 Ilitek 的触摸屏控制器监测屏幕上的触摸事件。当触摸发生时&a…...

编程日记 2025/9/11 17:04:22

pgsql:关联查询union(并集)、except(差集)、intersect(交集)

pgsql:关联查询union(并集)、except(差集)、intersect(交集)_pgsql except-CSDN博客...

编程日记 2025/9/7 0:46:27

模型材质共享导致的问题

问题：当我选中其中某个网格模型并设置color的时候，相同种类的颜色都被改变，但是打印我选中的网格模型数据其实只有一个。导致问题的原因： 加载Blender模型修改材质颜色 Blender创建一个模型对象，设置颜色&#xff0…...

编程日记 2025/9/10 5:40:58

ThinkpPHP生成二维码

导入依赖 composer require endroid/qr-code 封装成函数，传入二维码包含的值，存储路径，二维码大小，二维码边距 private function getCode($content, $directory, $size 300, $margin 10){// 创建二维码对象// $content: 二…...

编程日记 2025/9/10 17:24:19

FLINK框架：流式处理框架Flink简介

在大数据时代，数据的价值不言而喻，谁能利用好数据，谁就掌握了整个行业的先机。面对海量的数据，如何处理数据成为了一个难题。除了海量数据外，实时性也是一个重要的课题，所以流式数据处理便登上了技术舞台&a…...

编程日记 2025/9/15 3:34:24

使用Python从零开始构建生成型TransformerLM并训练

在人工智能的浩瀚宇宙中，有一种神奇的生物，它拥有着强大的语言魔法，能够生成各种各样的文本，仿佛拥有无尽的创造力。它就是——Transformer 模型！Transformer 模型的出现，为人工智能领域带来了一场“语言魔…...

编程日记 2025/9/11 22:35:30

xtrabackup备份

安装： https://downloads.percona.com/downloads/Percona-XtraBackup-8.0/Percona-XtraBackup-8.0.35-30/binary/tarball/percona-xtrabackup-8.0.35-30-Linux-x86_64.glibc2.17.tar.gz?_gl1*1ud2oby*_gcl_au*MTMyODM4NTk1NS4xNzM3MjUwNjQ2https://downloads.perc…...

编程日记 2025/9/11 10:21:31

2.3 Spark运行架构与流程

Spark运行架构与流程包括几个核心概念：Driver负责提交应用并初始化作业，Executor在工作节点上执行任务，作业是一系列计算任务，任务是作业的基本执行单元，阶段是一组并行任务。Spark支持多种运行模式，包括单…...

编程日记 2025/9/13 17:17:01

【Pandas】pandas DataFrame head

Pandas2.2 DataFrame Indexing, iteration 方法描述DataFrame.head([n])用于返回 DataFrame 的前几行 pandas.DataFrame.head pandas.DataFrame.head 是一个方法，用于返回 DataFrame 的前几行。这个方法非常有用，特别是在需要快速查看 DataFrame 的前…...

编程日记 2025/9/11 3:50:13

从递归入手一维动态规划

从递归入手一维动态规划 1. 509. 斐波那契数 1.1 思路递归 F(i) F(i-1) F(i-2) 每个点都往下展开两个分支，时间复杂度为 O(2n) 。在上图中我们可以看到 F(6) F(5) F(4)。计算 F(6) 的时候已经展开计算过 F(5)了。而在计算 F(7)的时候，还需要…...

编程日记 2025/9/13 1:33:35

鸿蒙HarmonyOS埋点SDK，ClkLog适配鸿蒙埋点分析

ClkLog埋点分析系统，是一种全新的、开源的洞察方案，它能够帮助您捕捉每一个关键数据点，确保您的决策基于最准确的用户行为分析。技术人员可快速搭建私有的分析系统。 ClkLog鸿蒙埋点SDK通过手动埋点的方式实现HarmonyOS 原生应用的前端数据采…...

编程日记 2025/9/13 21:40:58

HarmonyOS：HMPermission权限请求框架

前段时间利用空余时间写了一个权限请求库：HMPermission。一，简介 HMPermission 是鸿蒙系统上的一款权限请求框架，封装了权限请求逻辑，采用链式调用的方式请求权限，简化了权限请求的代码。二，使用方法 …...

编程日记 2025/9/5 14:43:14

【书籍】DeepSeek谈《持续交付2.0》

目录一、深入理解1. 核心理念升级：从"自动化"到"双环模型"2. 数字化转型的五大核心能力3. 关键实践与案例4. 组织与文化变革5. 与其它框架的关系6. 实际应用建议二、对于开发实习生的帮助1. 立刻提升你的代码交付质量（技术验证环实…...

编程日记 2025/9/12 16:10:25

Spring AOP 扫盲

🧑 博主简介：CSDN博客专家，历代文学网（PC端可以访问：https://literature.sinhy.com/#/literature?__c1000，移动端可微信小程序搜索“历代文学”）总架构师，15年工作经验，…...

编程日记 2025/9/7 11:45:22

银河麒麟v10（arm架构）部署Embedding模型bge-m3【简单版本】

硬件服务器配置：鲲鹏2 * 920（32c） 4 * Atlas300I duo卡参考文章 https://www.hiascend.com/developer/ascendhub/detail/07a016975cc341f3a5ae131f2b52399d 鲲鹏昇腾Atlas300Iduo部署Embedding模型和Rerank模型并连接Dify（自…...

编程日记 2025/9/7 19:35:14

如何通过流程管理优化企业运营？

流程管理的本质是“用确定性的规则应对不确定性的业务”。那么，具体该如何通过流程管理来优化企业的运作呢？以下是一些关键步骤和思路，或许能给到一些启发。 1. 从流程梳理开始：摸清现状，找准问题想要管理好企业的…...

编程日记 2025/9/10 14:04:19

ZYNQ笔记（四）：AXI GPIO

版本：Vivado2020.2（Vitis） 任务：使用 AXI GPIO IP 核实现按键 KEY 控制 LED 亮灭（两个都在PL端） 一、介绍 AXI GPIO (Advanced eXtensible Interface General Purpose Input/Output) 是 Xilinx 提供的一个可…...

编程日记 2025/9/9 22:42:33

Java学习手册：JVM、JRE和JDK的关系

在Java生态系统中，JVM（Java虚拟机）、JRE（Java运行时环境）和JDK（Java开发工具包）是三个核心概念。它们共同构成了Java语言运行和开发的基础。理解它们之间的关系对于Java开发者来说至关重要。本文…...

编程日记 2025/9/15 16:37:41

Java 并发-newFixedThreadPool

前言为什么选择使用多线程？一种场景是在数据和业务处理能力出现瓶颈时，而服务器性能又有空闲，通常是cpu空闲，这时使用多线程就能很好的解决问题，而又无需加硬件，实际使用中，线程池又是最为常用…...

编程日记 2025/9/15 10:52:12

C# task任务异步编程提高UI的响应性

方式1：async/await模式 private async void button1_Click(object sender, EventArgs e){try{var result await Task.Run(() > CalculateResult());label1.Text result.ToString();}catch (Exception ex){label1.Text $"Error: {ex.Message}";}}pri…...

编程日记 2025/9/12 3:57:42