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

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

vulnyx Blogger writeup

信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面&#xff0c;gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress&#xff0c;说明目标所使用的cms是wordpress&#xff0c;访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...

计算机基础知识解析:从应用到架构的全面拆解

目录 前言 1、 计算机的应用领域&#xff1a;无处不在的数字助手 2、 计算机的进化史&#xff1a;从算盘到量子计算 3、计算机的分类&#xff1a;不止 “台式机和笔记本” 4、计算机的组件&#xff1a;硬件与软件的协同 4.1 硬件&#xff1a;五大核心部件 4.2 软件&#…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...