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

二进制、数位dp:0912T3

考虑题目转化,二进制下满足 i ⊆ j , ( i + x ) ⊆ ( j + y ) i\subseteq j,(i+x)\subseteq (j+y) ij,(i+x)(j+y)

这显然是个数位dp形式

考虑枚举每一位与进位, d p k , p 1 , p 2 dp_{k,p_1,p_2} dpk,p1,p2 表示第 k − 1 k-1 k1 位向第 k k k 位,分别进位 p 1 , p 2 p_1,p_2 p1,p2 的方案数

考虑当前 ( i , j ) (i,j) (i,j) 二进制下分别为 q 1 , q 2 q_1,q_2 q1,q2,则 ( i + x , j + y ) = ( p 1 + q 1 + x i , p 2 + q 2 + y i ) = ( n 1 , n 2 ) (i+x,j+y)=(p_1+q_1+x_i,p_2+q_2+y_i)=(n_1,n_2) (i+x,j+y)=(p1+q1+xi,p2+q2+yi)=(n1,n2)

必须满足 q 1 ⊆ q 2 , n 1 & 1 ⊆ n 2 & 1 q1\subseteq q2,n1\&1\subseteq n2\&1 q1q2,n1&1n2&1,由 d p ( i + 1 , n 1 2 , n 2 2 ) dp(i+1,\frac{n_1}2,\frac{n_2}2) dp(i+1,2n1,2n2) 转移过来

综上:
d p ( k , i , j ) = ∑ q 1 ⊆ q 2 , n 1 = p 1 + q 1 + x i , n 2 = p 2 + q 2 + y i [ n 1 & 1 ⊆ n 2 & 1 ] d p ( i + 1 , n 1 2 , n 2 2 ) \Large dp(k,i,j)=\sum_{q1\subseteq q2,n1=p1+q1+x_i,n2=p2+q2+y_i}[n1\&1\subseteq n2\&1]dp(i+1,\frac{n_1}2,\frac{n_2}2) dp(k,i,j)=q1q2,n1=p1+q1+xi,n2=p2+q2+yi[n1&1n2&1]dp(i+1,2n1,2n2)

dp[n][0][0].a[1]=1; 
for(i=n-1; i>=0; --i) {for(p1=0; p1<=1; ++p1) for(p2=0; p2<=1; ++p2) {for(q1=0; q1<=1; ++q1) for(q2=q1; q2<=1; ++q2) {n1=p1+q1+x[i]; n2=p2+q2+y[i]; if(n1%2>n2%2) continue; dp[i][p1][p2]=dp[i][p1][p2]+dp[i+1][n1/2][n2/2]; }}}
dp[0][0][0].print(); 

相关文章:

二进制、数位dp:0912T3

考虑题目转化&#xff0c;二进制下满足 i ⊆ j , ( i x ) ⊆ ( j y ) i\subseteq j,(ix)\subseteq (jy) i⊆j,(ix)⊆(jy) 这显然是个数位dp形式 考虑枚举每一位与进位&#xff0c; d p k , p 1 , p 2 dp_{k,p_1,p_2} dpk,p1​,p2​​ 表示第 k − 1 k-1 k−1 位向第 k k…...

Java基于SpringBoot+Vue的 4S店车辆管理系统

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝30W,Csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 文章目录 1 简介2 技术栈3 功能总览4 系统设计4.1 系统设计主要功能4.2 数据库设计4.2.1 数据库设计规范4.2…...

助力智能化公路养护,基于YOLOv5s集成SPD-BIFPN-SE开发构建公路开裂检测识别系统

在前文中我们尝试构建了在隧道、涵洞尝尽下的自动智能化养护巡查相关的模型&#xff0c;进行了实地测试评估&#xff0c;感兴趣的话可以自行移步阅读即可&#xff1a; 《基于轻量级YOLOv5s开发构建隧道基建裂痕、脱落等缺陷问题检测系统》 本文的想法是相近的&#xff0c;核心…...

C++--day5

实现一个图形类&#xff08;Shape&#xff09;&#xff0c;包含受保护成员属性&#xff1a;周长、面积&#xff0c; 公共成员函数&#xff1a;特殊成员函数书写 定义一个圆形类&#xff08;Circle&#xff09;&#xff0c;继承自图形类&#xff0c;包含私有属性&#xff1a;半…...

Django应用部署实战:从开发到生产,全程解析

部署架构图 版本说明 Centos 7.4 Python 3.6.4 Django 2.0.2 Channels 2.0.0 MySql 5.7 uWSGI Nginx 1.12.2 部署前 1、更新系统环境 yum install epel-release 2、安装所有的开发工具包 yum groupinstall -y “Development tools” 一、安装python 3.6.4 1、下载 cd /usr/…...

群晖NAS如何在内网部署HTTPS服务让浏览器信任证书

前言 最近在折腾内部部署Web服务。通过Vue实现一个H5的内部的管理服务。但在实际部署过程中由于种种原因&#xff0c;必须部署成Https服务。但在部署成Https服务后&#xff0c;由于没有HTTPS证书&#xff0c;每次进入页面都会被浏览器拦截。使用起来非常不便。于是开始各种Goo…...

crAPI靶场学习记录

靶场搭建 [靶场下载地址](我fork了一份) docker安装&#xff0c;笔者是用的wsldocker. [lab0:**初始账户 **] 注册一个账户&#xff0c;邮箱为[APIqq.com]&#xff0c;密码为Admin123 登陆后访问对应IP的8025端口&#xff0c;接收邮件获取车辆信息。 [lab1:**访问其它用户车…...

知识图谱实战应用28-基于py2neo的ICD-11疾病分类的知识图谱的查询与问答实战应用

大家好,我是微学AI,今天给大家介绍一下知识图谱实战应用28-基于py2neo的ICD-11疾病分类的知识图谱的查询与问答实战应用。使用基于py2neo的ICD-11疾病分类知识图谱,我们能够像探索一座生物医学宇宙般,穿梭在各种疾病之间。这个神奇的图谱可以帮助我们揭示各种疾病之间复杂而…...

20.Xaml GroupBox控件 ---->带标题的内容控件

1.运行效果 2.运行源码 a.Xaml源码 <Window x:Class="testView.MainWindow"xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"xmlns:d="http://schemas.mic…...

基于CycleGAN的山水风格画迁移

基于CycleGAN的山水风格画迁移 1、简介 1.1 研究背景及意义 绘画是人类重要的一种艺术形式&#xff0c;其中中国的山水画源远流长&#xff0c;具有丰富的美学内涵&#xff0c;沉淀着中国人的情思。游山玩水的大陆文化意识&#xff0c;以山为德、水为性的内在修为意识&#x…...

​@Cacheable 注解​

1. 功能说明 Cacheable 注解在方法上&#xff0c;表示该方法的返回结果是可以缓存的。也就是说&#xff0c;该方法的返回结果会放在缓存中&#xff0c;以便于以后使用相同的参数调用该方法时&#xff0c;会返回缓存中的值&#xff0c;而不会实际执行该方法。 注意&#xff0c;这…...

vue3+ts项目打包后的本地访问

注意&#xff1a;打包之后不可直接点击html访问&#xff0c;需要给项目安装本地服务&#xff01; 1、安装servenpm i -g serve 2、打包项目npm run build 生成dist文件夹 3、本地访问serve dist 运行service dist之后的控制台 可复制下方的地址运行打包后的项目&#xff0c;运行…...

探索程序员需要掌握的算法?

文章目录 一&#xff1a;引言二&#xff1a;常见算法介绍三&#xff1a;重点算法总结 &#x1f389;欢迎来到数据结构学习专栏~探索程序员需要掌握的算法&#xff1f; ☆* o(≧▽≦)o *☆嗨~我是IT陈寒&#x1f379;✨博客主页&#xff1a;IT陈寒的博客&#x1f388;该系列文章…...

性能测试 —— Jmeter定时器

固定定时器 如果你需要让每个线程在请求之前按相同的指定时间停顿&#xff0c;那么可以使用这个定时器&#xff1b;需要注意的是&#xff0c;固定定时器的延时不会计入单个sampler的响应时间&#xff0c;但会计入事务控制器的时间 1、使用固定定时器位置在http请求中&#xf…...

mp4视频太大怎么压缩?几种常见压缩方法

mp4视频太大怎么压缩&#xff1f;科技的飞速发展使得视频成为人们生活中不可或缺的一部分。然而&#xff0c;随着视频质量的不断提高&#xff0c;视频文件的大小也与日俱增&#xff0c;给我们的存储和传输带来了巨大的挑战和困扰。特别是MP4格式的视频&#xff0c;由于其出色的…...

论文复制ChatGPT按钮被发表,撤回后再曝多个类似案例;Midjourney 生成大师级的人像

&#x1f989; AI新闻 &#x1f680; 论文复制ChatGPT按钮被发表&#xff0c;撤回后再曝多个类似案例 摘要&#xff1a;一篇物理论文复制了ChatGPT按钮内容&#xff0c;经过两个月同行评审并在杂志上发表。这一现象被知名打假人发现后&#xff0c;发表商决定撤回该论文。此外…...

Python自动化测试 史上最全的进阶教程

Python自动化测试就是把以前人为测试转化为机器测试的一种过程。自动化测试是一种比手工测试更快获得故障反馈的方法。 随着时代的变革&#xff0c;也许在未来测试这个职位的需求会越来越少甚至消失&#xff0c;但是每一个组织&#xff0c;每一个客户对软件质量的要求是永远不…...

centos pip失效

在 CentOS 上安装和配置 pip3 可能需要以下步骤&#xff1a; 确保 Python 3 已正确安装&#xff1a;请确保您已经正确地安装了 Python 3。在 CentOS 上&#xff0c;Python 3 可能默认安装在 /usr/bin/python3 路径下。您可以通过运行以下命令来验证 Python 3 是否正确安装&…...

Java——》ThreadLocal

推荐链接&#xff1a; 总结——》【Java】 总结——》【Mysql】 总结——》【Redis】 总结——》【Kafka】 总结——》【Spring】 总结——》【SpringBoot】 总结——》【MyBatis、MyBatis-Plus】 总结——》【Linux】 总结——》【MongoD…...

如何做好利益相关方的期望管理?

利益相关方对项目而言非常重要&#xff0c;有效管理利益相关方的期望可以帮助项目团队更好地满足利益相关方的需求&#xff0c;助于建立良好的合作伙伴关系&#xff0c;提高项目的可持续性和成功率。 如果项目团队无法满足利益相关方的需求&#xff0c;可能会引发冲突、争议或其…...

使用VSCode开发Django指南

使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架&#xff0c;专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用&#xff0c;其中包含三个使用通用基本模板的页面。在此…...

AI Agent与Agentic AI:原理、应用、挑战与未来展望

文章目录 一、引言二、AI Agent与Agentic AI的兴起2.1 技术契机与生态成熟2.2 Agent的定义与特征2.3 Agent的发展历程 三、AI Agent的核心技术栈解密3.1 感知模块代码示例&#xff1a;使用Python和OpenCV进行图像识别 3.2 认知与决策模块代码示例&#xff1a;使用OpenAI GPT-3进…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

跨链模式:多链互操作架构与性能扩展方案

跨链模式&#xff1a;多链互操作架构与性能扩展方案 ——构建下一代区块链互联网的技术基石 一、跨链架构的核心范式演进 1. 分层协议栈&#xff1a;模块化解耦设计 现代跨链系统采用分层协议栈实现灵活扩展&#xff08;H2Cross架构&#xff09;&#xff1a; 适配层&#xf…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...