当前位置: 首页 > 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;可能会引发冲突、争议或其…...

C++初阶-list的底层

目录 1.std::list实现的所有代码 2.list的简单介绍 2.1实现list的类 2.2_list_iterator的实现 2.2.1_list_iterator实现的原因和好处 2.2.2_list_iterator实现 2.3_list_node的实现 2.3.1. 避免递归的模板依赖 2.3.2. 内存布局一致性 2.3.3. 类型安全的替代方案 2.3.…...

Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误

HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误&#xff0c;它们的含义、原因和解决方法都有显著区别。以下是详细对比&#xff1a; 1. HTTP 406 (Not Acceptable) 含义&#xff1a; 客户端请求的内容类型与服务器支持的内容类型不匹…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

51c自动驾驶~合集58

我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留&#xff0c;CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制&#xff08;CCA-Attention&#xff09;&#xff0c;…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

【分享】推荐一些办公小工具

1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由&#xff1a;大部分的转换软件需要收费&#xff0c;要么功能不齐全&#xff0c;而开会员又用不了几次浪费钱&#xff0c;借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...

NPOI操作EXCEL文件 ——CAD C# 二次开发

缺点:dll.版本容易加载错误。CAD加载插件时&#xff0c;没有加载所有类库。插件运行过程中用到某个类库&#xff0c;会从CAD的安装目录找&#xff0c;找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库&#xff0c;就用插件程序加载进…...

nnUNet V2修改网络——暴力替换网络为UNet++

更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...