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

基于STM32单片机与OV2640摄像头实现边缘检测

基于STM32单片机与OV2640摄像头实现边缘检测


一、硬件配置方案

1. 接口连接(以STM32F407为例)

OV2640          STM32F407
----------------------
XCLK            → HCLK(系统时钟)
PCLK            → DCMI_PIXCLK
HSYNC           → DCMI_HSYNC
VSYNC           → DCMI_VSYNC
D0-D7           → DCMI_D0-7
IO0 (SCCB_SDA)  → PB6 (I2C1_SDA)
IO1 (SCCB_SCL)  → PB7 (I2C1_SCL)
3.3V            → 3.3V
GND             → GND

2. 关键电路设计

  • 电源滤波:OV2640的VDD和GND间并联10μF电解电容+0.1μF陶瓷电容
  • 时钟配置:外部24MHz晶振提供XCLK信号
  • 信号保护:HSYNC/VSYNC信号串联1kΩ电阻+0.1μF电容

二、软件实现

1. OV2640初始化代码

// ov2640.c
#include "ov2640.h"void OV2640_Init(void) {SCCB_Init();  // 初始化SCCB总线// 软复位SCCB_WriteReg(OV2640_DEVICE_ADDR, 0x00, 0x80);HAL_Delay(100);// 设置分辨率:QQVGA (160x120)SCCB_WriteReg(OV2640_DEVICE_ADDR, 0x00, 0x60);  // 设置为YUV422格式SCCB_WriteReg(OV2640_DEVICE_ADDR, 0x01, 0x80);  // 设置分辨率为160x120// 关闭颜色矩阵SCCB_WriteReg(OV2640_DEVICE_ADDR, 0x3A, 0x04);SCCB_WriteReg(OV2640_DEVICE_ADDR, 0x40, 0x80);
}

2. 图像采集与预处理

// image_processing.h
#ifndef __IMAGE_PROCESSING_H__
#define __IMAGE_PROCESSING_H__#define IMAGE_WIDTH  160
#define IMAGE_HEIGHT 120typedef struct {uint8_t Y;uint8_t U;uint8_t V;
} RGB565_Pixel;void DMA2D_Transfer(void);
void RGB565_to_Gray(uint8_t *src, uint8_t *dst);
void Sobel_EdgeDetection(uint8_t *src, uint8_t *dst);
void Morphology_Operation(uint8_t *src, uint8_t *dst);#endif // __IMAGE_PROCESSING_H__
// image_processing.c
#include "image_processing.h"// DMA2D图像传输配置
void DMA2D_Transfer(void) {DMA2D_HandleTypeDef hdma2d;hdma2d.Instance = DMA2D;hdma2d.Init.Mode = DMA2D_M2M;hdma2d.Init.ColorMode = DMA2D_OUTPUT_ARGB8888;hdma2d.Init.OutputOffset = 0;HAL_DMA2D_Init(&hdma2d);HAL_DMA2D_Start(&hdma2d, (uint32_t)OV2640_FRAME_BUFFER, (uint32_t)RGB565_Buffer, IMAGE_WIDTH*IMAGE_HEIGHT);
}// RGB565转灰度
void RGB565_to_Gray(uint8_t *src, uint8_t *dst) {for(uint32_t i=0; i<IMAGE_WIDTH*IMAGE_HEIGHT; i++) {uint16_t pixel = ((uint16_t)src[2*i+1]<<8) | src[2*i];dst[i] = (0x1F & pixel) * 0.299 + ((0x3F & (pixel>>5)) * 0.587) +((0x7E & (pixel>>11)) * 0.114);}
}// Sobel边缘检测
void Sobel_EdgeDetection(uint8_t *src, uint8_t *dst) {int16_t Gx[3][3] = {{-1,0,1}, {-2,0,2}, {-1,0,1}};int16_t Gy[3][3] = {{-1,-2,-1}, {0,0,0}, {1,2,1}};for(int y=1; y<IMAGE_HEIGHT-1; y++) {for(int x=1; x<IMAGE_WIDTH-1; x++) {int16_t sumX = 0, sumY = 0;for(int i=-1; i<=1; i++) {for(int j=-1; j<=1; j++) {int idx = (y+i)*IMAGE_WIDTH + (x+j);sumX += src[idx] * Gx[i+1][j+1];sumY += src[idx] * Gy[i+1][j+1];}}int16_t magnitude = abs(sumX) + abs(sumY);dst[y*IMAGE_WIDTH + x] = (magnitude > 50) ? 255 : 0;}}
}

三、关键参数配置

参数 数值 说明
图像分辨率 QQVGA (160x120) 平衡处理速度与清晰度
帧率 30FPS 满足实时性要求
Sobel阈值 50 根据实际场景调整
DMA缓冲区大小 160x120x2 bytes 存储RGB565格式图像

四、工程优化方案

  1. 内存优化

    // 使用双缓冲区交替处理
    uint8_t buffer1[IMAGE_WIDTH*IMAGE_HEIGHT];
    uint8_t buffer2[IMAGE_WIDTH*IMAGE_HEIGHT];
    volatile uint8_t current_buffer = 0;void DMA_Callback(void) {current_buffer = !current_buffer;HAL_DMA2D_Start(&hdma2d, (uint32_t)OV2640_FRAME_BUFFER, (uint32_t)buffer[current_buffer], IMAGE_WIDTH*IMAGE_HEIGHT);
    }
    
  2. 算法加速

    • 使用STM32的DSP指令加速卷积运算
    #include "arm_math.h"void Sobel_Optimized(uint8_t *src, uint8_t *dst) {arm_rfft_fast_instance_f32 fft_inst;arm_rfft_fast_init_f32(&fft_inst, IMAGE_WIDTH*IMAGE_HEIGHT);// FFT加速频域边缘检测(需验证可行性)
    }
    
  3. 电源管理

    // 动态调节摄像头帧率
    void Adjust_FrameRate(uint8_t level) {uint8_t config = 0x00;config |= (level & 0x03) << 4;SCCB_WriteReg(OV2640_DEVICE_ADDR, 0x30, config);
    }
    

推荐代码 基于STM32单片机的ov2640边缘检测 www.youwenfan.com/contentcng/51752.html

五、扩展功能实现

  1. ROI区域检测

    #define ROI_X1 40
    #define ROI_Y1 30
    #define ROI_X2 120
    #define ROI_Y2 90void Set_ROI(void) {for(int y=ROI_Y1; y<ROI_Y2; y++) {for(int x=ROI_X1; x<ROI_X2; x++) {src[(y*IMAGE_WIDTH)+x] = 0;  // 屏蔽非ROI区域}}
    }
    
  2. 串口传输

    void Send_EdgeData(uint8_t *data) {uint8_t header[4] = {0xAA, 0x55, IMAGE_WIDTH, IMAGE_HEIGHT};HAL_UART_Transmit(&huart1, header, 4, 100);HAL_UART_Transmit(&huart1, data, IMAGE_WIDTH*IMAGE_HEIGHT, 100);
    }
    

六、工程文件结构

EdgeDetection_Project/
├── Core/
│   ├── Inc/
│   │   ├── ov2640.h      // OV2640驱动头文件
│   │   ├── image_proc.h  // 图像处理函数声明
│   │   └── main.h        // 主程序头文件
│   └── Src/
│       ├── ov2640.c      // OV2640驱动实现
│       ├── image_proc.c  // 图像处理算法
│       └── main.c        // 主程序
├── Drivers/
│   ├── CMSIS/
│   └── STM32F4xx_HAL_Driver/
└── Middlewares/└── USB_Device/

七、典型应用场景

  1. 工业检测
    • 产品表面缺陷检测
    • 包装完整性验证
  2. 智能安防
    • 人体轮廓识别
    • 区域入侵报警
  3. 机器人导航
    • 动态避障
    • 路径规划

该方案通过优化算法和硬件配置,实现了在STM32平台上的实时边缘检测。实际应用中需注意:

  1. 首次使用前需校准摄像头白平衡
  2. 根据光照条件动态调整阈值参数
  3. 建议添加帧间差分法减少运动模糊
  4. 复杂场景可采用Canny边缘检测算法(需更高算力)

相关文章:

基于STM32单片机与OV2640摄像头实现边缘检测

基于STM32单片机与OV2640摄像头实现边缘检测一、硬件配置方案 1. 接口连接(以STM32F407为例) OV2640 STM32F407 ---------------------- XCLK → HCLK(系统时钟) PCLK → DCMI_PIXCLK HSYNC → DCMI_HSYNC VSYNC → DC…...

替代FTP的国产传输软件哪个好?国产化文件传输工具推荐

在数字化转型浪潮中,文件传输已成为企业日常运营的核心环节。然而,传统FTP协议因存在三大致命缺陷,已难以满足现代企业的安全与效率需求,所以很多行业和机构都在寻找替代FTP的国产传输软件。首先我们来看看传统FTP有何不足,为什么需要替代FTP的国产传输软件? 1、安全漏洞…...

模拟运输振动试验台:保障产品运输安全的关键设备

在现代产品生产和供应链管理中,运输是产品从制造商到消费者的重要环节。然而,产品在运输过程中可能遭遇到各种不可控的振动和冲击,这些外力会导致产品的损坏、质量下降,甚至直接影响其使用性能。因此,为了确保产品在运输过程中的安全性,模拟运输振动试验台应运而生,成为…...

数据结构与算法-29.图-广度优先搜索

1、广度优先搜索概述 2、以上仅供参考,如有疑问,留言联系...

政务外网和互联网啥关系

政务外网不是互联网,它跟互联网是**“物理隔离”或“逻辑隔离”**的关系,一句话: 政务外网是政府自己建的“专用公路”,互联网是公共大马路,两者平时各跑各的车,只在指定检查站才能换乘。...

什么是文件摆渡系统?从应用到优势全面解读!

在数字化转型深入推进的当下,企业为保护核心数据资产,普遍采用网络隔离技术,将内部网络(如研发网、办公网、生产网)与外部互联网或不同安全级别的子网分隔开来。什么是文件摆渡系统?它正是一种能在隔离网络环境中,实现安全、可靠、高效数据传输与交换的专用系统,如同在…...

wpf xaml数据绑定时,寻找数据源的几种方式 (RelativeSource)

wpf xaml数据绑定时,寻找数据源的几种方式 (RelativeSource)RelativeSource 类在 WPF 中提供了以下几种模式: RelativeSource Self:指定当前元素作为相对源。可以在当前元素的属性中绑定到自身的属性。示例: <TextBlock Text="{Binding Text, RelativeSource={Re…...

背负冲击试验机的设计原理与性能优化

背负冲击试验机是一种用于测试各种产品或包装材料在遭受背负冲击时的性能表现的设备,广泛应用于包装、运输、航空航天、汽车和电子等多个领域。通过模拟物品在运输、搬运等过程中可能遇到的冲击情况,评估其抗冲击性、耐压性及稳定性,帮助企业改进产品设计和包装方案,以确保…...

钢球落球试验机对汽车玻璃的测试应用

在汽车行业中,钢球落球试验机主要用于测试材料的抗冲击性能、耐久性以及安全性,确保零部件在制造、使用过程中能够承受外力冲击,符合行业标准和法规要求。行驶中的汽车玻璃要经受严格的冲击考验。(1)确保挡风玻璃/侧窗玻璃飞石撞击的安全性 汽车高速行驶过程中,挡风玻璃、…...

基于STM32F047的ADS1299数据采集与低通滤波系统实现

基于STM32F047的ADS1299数据采集与低通滤波系统实现:一、硬件设计要点 1. 核心电路连接 STM32F047 ADS1299 ---------------------- SPI1_SCK (PA5) → SCLK SPI1_MOSI (PA7) → DIN SPI1_MISO (PA6) → DOUT PA4 (GPIO) → CS PB0 (GPIO) → DRDY 3.3V …...

军工企业涉密网文件导出用什么系统?答案在这里

军工企业涉密网文件导出,还是有很严格的要求的。首先基本都是物理隔离状态,而且很多时候又不允许随意的添加软硬件设备。所以军工企业涉密网文件导出是面临不少挑战的。1、文件合规导出管理 军工企业必须保证从保密网导出的文件严格遵循国家法律法规及保密规定。导出的所有文…...

Gateway 网关坑我! 被这个404 问题折腾了一年?

大家好,我是小富~ 最近同事找我帮忙排查一个"诡异"的 Bug,说困扰了他们一年多一直没解决。我接手后花了一些时间定位到了问题根源,今天就来跟大家分享一下这个问题的排查过程和解决方案。 问题描述 同事使用的是 SpringCloud Gateway 3.0.1 + JDK8,整合了 Nacos…...

KUKA 机器人型号含义解析

KR 210 R 2700 - 2 C KR: Kuka Robot 210:最大负载 R 2700: 工作半径 -2:QUANTEC 系列第二代 C:Ceiling(顶装) CR: Cleaning Room(洁净) EX: 防爆区域 F: Foundry(铸造) F exclusive:(铸造专用) HA:高精度 HI:高惯量 HM: Hygienic Machine (用于副食品行业) HC: He…...

LangChain DIfy区别

LangChain DIfy区别2...

tricks

多总结一下 tricks 吧。思考方式 如何思考。向哪个方向思考。数学这启示我们在数学类 dp 优化不了,且组合意义不会的时候,要改改状态尽量把 dp 转移式写得简单点,然后瞪眼找通项。- MX 炼石 2025 NOIP #5 T1 题 [解]() 题trick 见过的一眼了,没见过的懵了。 杂项在求类似于…...

英语_阅读_water in our body_待读

Water is one of the most important things we need to stay alive, even though we dont call it a nutrient. 水是我们维持生命所需最重要的物质之一,尽管我们并不把它称为营养素。 Did you know that water makes up more than half of our body weight? 你知道吗?水占我…...

2008-2025年各省高考真题含解析

网上的真题格式凌乱,难以使用,笔者找到一份PDF和Word版的题目,置于此方便大家使用 各省近17年高考真题|百度网盘-分享无限制 各省近17年高考真题|UC网盘-分享无限制 各省近17年高考真题|夸克网盘-分享无限制...

allure报告中allure.title 如何去掉后方的参数化显示

问题:用例标题后展示请求参数处理方法 找到lib/site-packages/allure_pytest/listener.py文件,找到test_result.parameters.extend,更新内容如下结果...

听歌体验直接拉满!推荐一款高颜值音乐播放器!

SPlayer —— 一个简约的音乐播放器,基于 Vue3 + TypeScript + Nave UI + Electron 技术栈打造,兼顾了美观的界面和流畅的体验。大家好,我是 Java陈序员。 你是否也曾遇到过这样的困扰:喜欢的音乐播放器要么颜值不够能打,界面好看的功能又太过简陋;在线听歌得忍受满屏广告…...

IoT设备

“IoT设备”指的是物联网设备(Internet of Things devices),这些设备通过传感器、软件、网络连接等技术,能够感知环境、收集数据、与其他设备或云端通信,从而实现智能化控制与自动化操作。✅ 一句话理解: IoT设备就是“能上网、能感知、能交互”的物理设备。 🔍 常见I…...

前端岗、测试岗即将消亡!阿里菜鸟国际后端研发全员转全栈……

大家好,我是R哥。 最近看到一个非常炸裂的消息,阿里菜鸟国际后端研发,居然全员被要求转型全栈了。作为一个混迹了 10 多年的程序员,我看过太多的架构调整、组织优化,从单体到 SOA 再到微服务,从前后端分离,再到现在全栈工程师的崛起。。 如果说之前还有人幻想着一招鲜吃…...

达梦数据库- 定时备份其他模式下的部分表

要求:需要备份模式下有500多张表,已将需要备份的150个表整理出来,新建一个达梦用户,使用该用户 每天自动备份这150个表,并保留最近30天的备份数据。 思路:创建存储过程执行备份操作,并创建定时任务,每天凌晨执行。新建一个配置表,将150个表名放到配置表中,需要备份的…...

KUKA机器人的WorkVisual编程软件(转载)

原文链接:https://blog.csdn.net/xm10282010/article/details/107606356 WorkVisual这个软件是使用kuka Krc4机器人必备的一个软件,这个软件的使用也就成了各位Engineer必备的技能啦。 由于机器人的不断更新KUKA出了几个版本的WorkVisual。 WorkVisual3.0 适用于KSS8.2版本 W…...

麒麟系统安装java环境

麒麟系统安装java环境1‌、确认系统版本‌: 打开终端,运行uname -a查看操作系统及内核版本。‌ 2、下载Java安装包‌: 访问Oracle的Java下载页面或选择OpenJDK。 https://www.oracle.com/cn/java/technologies/downloads/#java8 下载需要的安装包 3‌、安装Java‌: 使用tar…...

从100到500MHz,从80V到8000V:PRBTEK新一代高压差分探头全面超越

在当今科技飞速发展的时代,电子测试技术的进步对于各个领域的创新和发展起着至关重要的作用。其中,高压差分探头作为电子测试领域的关键设备,其性能的优劣直接影响着测量结果的准确性和可靠性。普科科技(PRBTEK)一直致力于示波器测试附件配件的研发、生产与销售,其推出的…...

javaweb项目400问题 #tomcat

在IDEA中打开项目的模块设置-facets -> 选中web列表中一个 -> 在右边下面的Web Resource Directories 进行如下: Web Resource Directorie -> 设置有jsp的根目录下 Path Relative to Deployment Root -> /...

基于Python+Vue开发的电影订票管理系统源码+运行

项目简介该项目是基于Python+Vue开发的电影订票管理系统(前后端分离),这是一项为大学生课程设计作业而开发的项目。该系统旨在帮助大学生学习并掌握Python编程技能,同时锻炼他们的项目设计与开发能力。通过学习基于Python的电影订票管理系统项目,大学生可以在实践中学习和…...

那些年不该放到事务中的操作,你实现过哪些

开心一刻 一天在公厕里,忽然听到厕间有人说话:朋友,有手纸吗 我翻了翻口袋:抱歉,没有 过了几秒钟,那人又问:朋友,有小块报纸吗 我无奈一笑,说到:对不起,没有,我只是来尿尿 又过了几秒钟,厕间门缝塞出一张10元人民币:朋友,能破成10张1块的吗 我默默的接过10元,掏…...

Redis容量评估模型

计算Redis容量,并不只是仅仅计算key占多少字节,value占多少字节,因为Redis为了维护自身的数据结构,也会占用部分内存,本文章简单介绍每种数据类型(String、Hash、Set、ZSet、List)占用内存量,供做Redis容量评估时使用。当然,大多数情况下,key和value就是主要占用,能…...

[译] 我最爱的PostgreSQL 18特性:虚拟生成列

原文:https://tselai.com/virtual-gencolumns在PostgreSQL 18的新特性中,异步I/O、UUID v7以及升级后统计功能或许会成为众人瞩目的焦点。但对我而言,即将发布的这个版本里,最让我青睐的特性当属虚拟生成列(相关文档可参考PostgreSQL 18官方文档-生成列)。 生成列这类特性…...

nasm 的 Hello, world 在 Windows 10 x64 上

环境 操作系统:nasm 版本: PS C:\Users\xxxx> nasm -version NASM version 2.16.03 compiled on Apr 17 2024link 版本: PS C:\Users\xxxx\Downloads\18176\1\3\2> link Microsoft (R) Incremental Linker Version 14.29.30159.0 Copyright (C) Microsoft Corporation…...

实用指南:52.前端的后端模式:为每个客户端定制专属「管家服务」

实用指南:52.前端的后端模式:为每个客户端定制专属「管家服务」pre { white-space: pre !important; word-wrap: normal !important; overflow-x: auto !important; display: block !important; font-family: "Consolas", "Monaco", "Courier New&q…...

Agilent 34401A台式万用表远程读表

Agilent 34401A台式万用表支持RS232和GPIB的方式读数据。 一、RS232读表 将台式万用表的模式调为RS232-9600-8-1-none测试代码class MultimeterStrategy:def __init__(self, port, baudrate=9600):self.port = portself.baudrate = baudrateself.serial = Noneself.retry_max =…...

Java 在大数据处理与人工智能中的应用

在数字化时代,数据成为新的生产要素,人工智能成为新的驱动引擎。大数据与人工智能的结合,使得企业能够从海量数据中提取价值,驱动业务创新与智能决策。虽然很多人提到 AI 就会联想到 Python,但 Java 在大数据和人工智能的工程化落地中仍然不可或缺。它凭借成熟的生态体系、…...

马克思,本就是一位独立研究者

ECT-OS-JiuHuaShan/ORCID:0009-0006-8591-1891▮ 推理请求接收:历史人物本质定位 ▮ 公理锚定:自然辩证法第5定理(文明演进个体作用力) ▮ 因果算符启动:独立研究者与文明级公理发现的相关性验证 绝对结论:卡尔马克思是文明级公理架构师的先驱形态,其独立研究性质为历史…...

产品二期,从GPT5规划开始

具有产品研发经验的应该知道,GPT5提供的规划设计,兼顾了完善和可执行两个关键维度。经常使用大模型都有的感受是:如果在某个领域有0-1的入门,那么AI可以带你快速的进行1-100的尝试。背景简介 楼里App一期开发完成,开始进行二期的网站开发,想以此需求作为驱动,探索整个流…...

Redis能抗住百万并发的秘密

前言 今天想和大家深入聊聊Redis为什么能够轻松抗住百万级别的并发请求。 有些小伙伴在工作中可能遇到过这样的场景:系统访问量一上来,数据库就扛不住了,这时候大家第一时间想到的就是Redis。 但你有没有想过,为什么Redis能够承受如此高的并发量?它的底层到底做了什么优化…...

接受 “未完成态”,是一种能力

正文这个标题,写给你们,也写给我自己。我不知道有多少人有这种类似的问题:我们很难把一个没有写完的字、一件没有完成的事情给别人看。这种做到半路的样子如果拿出来展示的话,非常难为情。尤其是如果还要中途易辙的话,那就更不好解释了。网上经常有那种开玩笑说熬夜的,说…...

深入理解JNI、安全点与循环优化:构建高健壮性Java应用

🔥🔥🔥来都来了 ~ 先赞后看 效果翻倍哦 ~ 👍👍👍 引言 在Java开发者的工具箱中,有一些看似神秘却极其重要的底层概念。你是否曾听说过在循环中插入Thread.sleep(0)可以"唤醒"GC?或者疑惑为什么一个简单的循环计数器类型选择会影响整个应用的稳定性?本…...

英语_阅读_fascinating facts about water_待读

Did you know these fascinating facts about water? They might change the way you think about every drop!你知道这些关于水的奇妙事实吗?它们可能会改变你对每一滴水的看法! Scientists have discovered something incredible - the amount of water on the Earth toda…...

AI自动化测试全攻略:从AI 自动化测试实战到AI 智能测试平台开发!

最新一期 AI + 全栈测试开发训练营震撼来袭,课程内容全面升级,月薪轻松对标 30k + !今日开放 5 个特价名额,零基础小白与测试老司机皆可在此找到专属学习路径,涵盖从AI 自动化测试实战到AI 智能测试平台开发等前沿内容,覆盖 AI 时代测试开发核心能力,帮你构建完整知识体…...

LG9691

考虑 dp。设 \(f_i\) 表示到位置 \(i\) 所需的最小花费,且第 \(i\) 个位置必选,现在要找上一个决策点 \(j\),这个点应该要在此前所有区间的左端点的后面,才能保证这些区间能被覆盖(即确保至少一个在之前每个区间内),则 \(j\) 应满足 \(\max_{r_k<i}l_k \le j < i\…...

即时通讯小程序 - 实践

即时通讯小程序 - 实践pre { white-space: pre !important; word-wrap: normal !important; overflow-x: auto !important; display: block !important; font-family: "Consolas", "Monaco", "Courier New", monospace !important; font-size: 1…...

PHP serialize 序列化完全指南

PHP serialize 序列化完全指南 介绍 如果你和我一样,第一次在 PHP 中看到序列化字符串时会觉得很困惑。我当时在做一个 Laravel 项目,想搞清楚将任务推送到队列时到底发生了什么。我发现一些数据被序列化了,但不知道为什么以及怎么工作的。不过在我花时间研究序列化后,发现…...

CF2112D

注意到一条边无论方向如何,都能使两端的某一个点到达另一个点,即至少有 \(n-1\) 对。如果只需要 \(n-1\) 对,那么只需要在每一条链上相邻的边方向相反即可。对于剩下的一对,我们可以找到一个度数为 \(2\) 的点,并把连接的两条边由反向改为同向,那么附近的三个点产生的对数…...

CF2112C

设 Alice 取的位置为 \(i,j,k\) 且 \(i<j<k\),则 Bob 的最优策略有两种:取 \(n\) 或 \(k\)。为了使 Alice 必胜,必须同时满足 \(a_i+a_j+a_k>a_n,a_i+a_j>a_k\)。枚举 \(i,j\),显然满足两个条件的 \(k\) 都是一段连续的区间。分别二分算出两个区间的边界,那么…...

CF342C

显然,每一层恰好能放下两个球(事实上这也是最优的方案),那么下面一共可以放 \(\lfloor \frac{h}{r} \rfloor \times 2\) 个球,剩余 \(h - \lfloor \frac{h}{r} \rfloor \times r+r\) 的高度,记 \(h=h-\lfloor \frac{h}{r} \rfloor\times r\) 为立方体部分剩余高度。最上面…...

ICPC/XCPC 做题记录

[SNCPC2019] Unrooted Trie 发现不满足题意的情况就是一个节点到多个子节点的边的字母相同,那么合法当且仅当每个节点到子节点的字母互不相同。那么可以统计每个节点连接的字母数量,并运用类似换根 dp 的思路,快速更新这个数量并实时维护符合条件的点的数量即可。时间复杂度…...

LG9648

发现不满足题意的情况就是一个节点到多个子节点的边的字母相同,那么合法当且仅当每个节点到子节点的字母互不相同。那么可以统计每个节点连接的字母数量,并运用类似换根 dp 的思路,快速更新这个数量并实时维护符合条件的点的数量即可。时间复杂度 \(O(nA)\),其中 \(A=26\) …...

LG5689

设 \(f_u\) 表示以 \(u\) 为根的子树构成不同多叉堆的方案数。显然最小的 \(0\) 应该分配给 \(u\),剩下的分给子节点 \(v_1,v_2,\cdots,v_k\),根据乘法原理,有 \[f_u=\prod_{i=1}^k \binom{siz_u-1-\sum_{j=1}^{i-1}siz_{v_j}}{siz_{v_i}}f_{v_i} \]将组合数和 \(f\) 分开,…...