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

【学习笔记】子集DP

背景

有一类问题和子集有关。
给你一个集合 S S S,令 T T T S S S 的超集,也就是 S S S 所有子集的集合,求 T T T 中所有元素的和。

暴力1

先预处理子集的元素和 A i A_i Ai,再枚举子集。

for(int s=0; s<(1<<n); s++)for(int i=0; i<(1<<n); i++)if(s&i) f[s]+=A[i];

时间复杂度 O ( n 4 ) O(n^4) O(n4)

暴力2

其实枚举子集有个小 trick

for(int s=0; s<(1<<n); s++)for(int i=s; i>0; i=(i-1)&s)f[s]+=A[i];

由二项式定理,时间复杂度为 O ( 3 n ) O(3^n) O(3n)

子集DP

g s , i g_{s,i} gs,i 为状态为 s s s,只考虑后 i i i 位转移的答案。
那么转移就是

g s , i = { g s , i − 1 s & ( 1 < < i ) = 0 g s , i − 1 + g s ⨁ ( 1 < < i ) , i − 1 o t h e r w i s e g_{s,i} = \begin{cases} g_{s,i-1} & s\&(1<<i)=0 \\g_{s,i-1} +g_{s\bigoplus(1<<i),i-1}&otherwise\end{cases} gs,i={gs,i1gs,i1+gs(1<<i),i1s&(1<<i)=0otherwise
这样可以做到不重不漏的转移。
推荐一篇blog,非常形象:https://www.cnblogs.com/maple276/p/17975253

可以发现,这个转移只和上一层有关,所以第二维是可以省略的。

前缀和(子集向超集转移)
for(int i=0; i<n; i++)
{for(int s=0; s<(1<<n); s++){if(s&_2)(f[s]+=f[s^_2])%(mod-1);}_2<<=1;
}
后缀和(超集向子集转移)
for(int i=0; i<n; i++)
{for(int s=0; s<(1<<n); s++){if(!(s&_2))(f[s]+=f[s^_2])%(mod-1);}_2<<=1;
}
差分
//后缀差分
for(int i=0; i<20; i++)
{for(int s=0; s<S; s++){if(!(s&_2))(f[s]-=f[s^_2])%=mod;}_2<<=1;
}

例题

CF165E

定义 x x x y y y 相容为 x & y = 0 x\&y=0 x&y=0,给你一个序列 A A A,对于每个元素,在 A A A 中找到和它相容的元素。 ∣ A ∣ ≤ 1 0 6 , A i ≤ 4 × 1 0 6 |A|\leq 10^6,A_i\leq 4\times 10^6 A106,Ai4×106

思路

x & y = 0 x\&y=0 x&y=0 等价于 x ˜ & y = y \~x\&y=y x˜&y=y,那么只需要对 A A A做类似前缀和的操作,加法改成覆盖即可。

代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int S=1<<22;
void O_o()
{int n;cin>>n;vector<int> f(S,-1),a(n+1);for(int i=1; i<=n; i++){cin>>a[i];f[a[i]]=a[i];}int _2=1;for(int i=0; i<=21; i++){for(int s=0; s<S; s++){if(!(s&_2)) continue;if(f[s^_2]!=-1)f[s]=f[s^_2];}_2<<=1;}int t=S-1;for(int i=1; i<=n; i++){cout<<f[t^a[i]]<<" ";}cout<<"\n";
}
signed main()
{ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);cout<<fixed<<setprecision(2);int T=1;
//	cin>>T;while(T--){O_o();}
}

相关文章:

【学习笔记】子集DP

背景 有一类问题和子集有关。 给你一个集合 S S S&#xff0c;令 T T T 为 S S S 的超集&#xff0c;也就是 S S S 所有子集的集合&#xff0c;求 T T T 中所有元素的和。 暴力1 先预处理子集的元素和 A i A_i Ai​&#xff0c;再枚举子集。 for(int s0; s<(1<…...

苦学Opencv的第十四天:人脸检测和人脸识别

Python OpenCV入门到精通学习日记&#xff1a;人脸检测和人脸识别 前言 经过了十三天的不懈努力&#xff0c;我们终于也是来到了人脸检测和人脸识别啦&#xff01;相信大家也很激动吧。接下来我们开始吧&#xff01; 人脸识别是基于人的脸部特征信息进行身份识别的一种生物识…...

PyTorch学习(1)

PyTorch学习&#xff08;1&#xff09; CIFAR-10数据集-图像分类 数据集来源是官方提供的&#xff1a; torchvision.datasets.CIFAR10()共有十类物品&#xff0c;需要用CNN实现图像分类问题。 代码如下&#xff1a;(CIFAR_10_Classifier_Self_1.py) import torch import t…...

三思而后行:计算机行业的决策智慧

在计算机行业&#xff0c;"三思而后行"这一原则显得尤为重要。在这个快速发展、技术不断更新换代的领域&#xff0c;每一个决策都可能对项目的成功与否产生深远的影响。以下是一篇关于在计算机行业中三思重要性的文章。 三思而后行&#xff1a;计算机行业的决策智慧 …...

Linux--Socket编程UDP

前文&#xff1a;Socket套接字编程 UDP协议特点 无连接&#xff1a;UDP在发送数据之前不需要建立连接&#xff0c;减少了开销和发送数据之前的时延。尽最大努力交付&#xff1a;UDP不保证可靠交付&#xff0c;主机不需要维持复杂的连接状态表。面向报文&#xff1a;UDP对应用层…...

《javaEE篇》--单例模式详解

目录 单例模式 饿汉模式 懒汉模式 懒汉模式(优化) 指令重排序 总结 单例模式 单例模式属于一种设计模式&#xff0c;设计模式就好比是一种固定代码套路类似于棋谱&#xff0c;是由前人总结并且记录下来我们可以直接使用的代码设计思路。 单例模式就是&#xff0c;在有…...

Java核心 - Lambda表达式详解与应用示例

作者&#xff1a;逍遥Sean 简介&#xff1a;一个主修Java的Web网站\游戏服务器后端开发者 主页&#xff1a;https://blog.csdn.net/Ureliable 觉得博主文章不错的话&#xff0c;可以三连支持一下~ 如有疑问和建议&#xff0c;请私信或评论留言&#xff01; 前言 Lambda表达式是…...

算法通关:006_1二分查找

二分查找 查找一个数组里面是否存在num主要代码运行结果 详细写法自动生成数组和num&#xff0c;利用对数器查看二分代码是否正确 查找一个数组里面是否存在num 主要代码 /*** Author: ggdpzhk* CreateTime: 2024-07-27*/ public class cg {//二分查找public static boolean …...

总结一些vue3小知识3

总结一些vue3小知识1&#xff1a;http://t.csdnimg.cn/C5vER 总结一些vue3小知识2&#xff1a;http://t.csdnimg.cn/sscid 1.限制时间选择器只能选择后面的日期 说明&#xff1a;disabled-date属性是一个用来判断该日期是否被禁用的函数&#xff0c;接受一个 Date 对象作为参…...

JAVAWeb实战(前端篇)

项目实战一 0.项目结构 1.创建vue3项目&#xff0c;并导入所需的依赖 npm install vue-router npm install axios npm install pinia npm install vue 2.定义路由&#xff0c;axios&#xff0c;pinia相关的对象 文件&#xff08;.js&#xff09; 2.1路由(.js) import {cre…...

axios请求大全

本文讲解axios封装方式以及针对各种后台接口的请求方式 axios的介绍和基础配置可以看这个文档: 起步 | Axios中文文档 | Axios中文网 axios的封装 axios封装的重点有三个&#xff0c;一是设置全局config,比如请求的基础路径&#xff0c;超时时间等&#xff0c;第二点是在每次…...

C# 简单的单元测试

文章目录 前言参考文档新建控制台项目新建测试项目添加引用添加测试方法测试结果(有错误)测试结果&#xff0c;通过正规的方法抛出异常 总结 前言 听说复杂的项目最好都要单元测试一下。我这里也试试单元测试这个功能。到时候调试起来也方便。 参考文档 C# 单元测试&#xf…...

Linux中Mysql5.7主从架构(一主多从)配置教程

&#x1f3e1;作者主页&#xff1a;点击&#xff01; &#x1f427;Linux基础知识(初学)&#xff1a;点击&#xff01; &#x1f427;Linux高级管理防护和群集专栏&#xff1a;点击&#xff01; &#x1f510;Linux中firewalld防火墙&#xff1a;点击&#xff01; ⏰️创作…...

BACnet物联网关BL103:Modbus协议转BACnet/MSTP

随着物联网技术在楼宇自动化与暖通控制系统中的迅猛发展&#xff0c;构建一种既经济高效又高度可靠的协议转换物联网关成为了不可或缺的核心硬件组件。在此背景下&#xff0c;我们钡铼特别推荐一款主流的BAS&#xff08;楼宇自动化系统&#xff09;与BACnet物联网关——BL103&a…...

Go 语言条件变量 Cond

1.Cond 的使用方法 Go 标准库提供 Cond 同步原语的目的是为等待/通知场景下的并发操作提供支持。Cond 通常用于等待某个条件的一组 goroutine,当条件变为 true 时,其中一个或者所有的 goroutine 会被唤醒执行。 Cond 与某个条件相关,这个条件需要一组 goroutine 协作达到。当这…...

PostgreSQL 中如何重置序列值:将自增 ID 设定为特定值开始

我是从excel中将数据导入&#xff0c;然后再通过sql插入数据&#xff0c;就报错。 需要设置自增ID开始值 1、确定序列名称&#xff1a; 首先&#xff0c;需要找到与的增字段相关的序列名称。假设表名是 my_table 和自增字段是 id&#xff0c;可以使用以下查询来获取序列名称…...

Unity 之 【Android Unity 共享纹理】之 Android 共享图片给 Unity 显示

Unity 之 【Android Unity 共享纹理】之 Android 共享图片给 Unity 显示 目录 Unity 之 【Android Unity 共享纹理】之 Android 共享图片给 Unity 显示 一、简单介绍 二、共享纹理 1、共享纹理的原理 2、共享纹理涉及到的关键知识点 3、什么可以实现共享 不能实现共享…...

Go语言的数据结构

数据结构 数组 支持多维数组&#xff0c;属于值类型&#xff0c;支持range遍历 例子&#xff1a;随机生成长度为10整数数组 package main import ("fmt""math/rand" ) // 赋值 随机获取100以内的整数 func RandomArrays() {var array [10]int //声明var…...

python_在sqlite中创建表并写入表头

python_在sqlite中创建表并写入表头 import sqlite3def write_title_to_sqlite(tableName,titleList,dataTypeGroupsList,database_path):conn sqlite3.connect(database_path)# 创建游标cursor conn.cursor()#MEMO 长文本#create_table_bodycreate_table_body "序号 …...

1.c#(winform)编程环境安装

目录 安装vs创建应用帮助查看器安装与使用&#xff08; msdn&#xff09; 安装vs 安装什么版本看个人心情&#xff0c;或者公司开发需求需要 而本栏全程使用vs2022进行开发c#&#xff0c;着重讲解winform桌面应用开发 使用***.net framework***开发 那先去官网安装企业版的vs…...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式

一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明&#xff1a;假设每台服务器已…...

如何为服务器生成TLS证书

TLS&#xff08;Transport Layer Security&#xff09;证书是确保网络通信安全的重要手段&#xff0c;它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书&#xff0c;可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

音视频——I2S 协议详解

I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议&#xff0c;专门用于在数字音频设备之间传输数字音频数据。它由飞利浦&#xff08;Philips&#xff09;公司开发&#xff0c;以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...

深入浅出深度学习基础:从感知机到全连接神经网络的核心原理与应用

文章目录 前言一、感知机 (Perceptron)1.1 基础介绍1.1.1 感知机是什么&#xff1f;1.1.2 感知机的工作原理 1.2 感知机的简单应用&#xff1a;基本逻辑门1.2.1 逻辑与 (Logic AND)1.2.2 逻辑或 (Logic OR)1.2.3 逻辑与非 (Logic NAND) 1.3 感知机的实现1.3.1 简单实现 (基于阈…...

Xela矩阵三轴触觉传感器的工作原理解析与应用场景

Xela矩阵三轴触觉传感器通过先进技术模拟人类触觉感知&#xff0c;帮助设备实现精确的力测量与位移监测。其核心功能基于磁性三维力测量与空间位移测量&#xff0c;能够捕捉多维触觉信息。该传感器的设计不仅提升了触觉感知的精度&#xff0c;还为机器人、医疗设备和制造业的智…...

解析两阶段提交与三阶段提交的核心差异及MySQL实现方案

引言 在分布式系统的事务处理中&#xff0c;如何保障跨节点数据操作的一致性始终是核心挑战。经典的两阶段提交协议&#xff08;2PC&#xff09;通过准备阶段与提交阶段的协调机制&#xff0c;以同步决策模式确保事务原子性。其改进版本三阶段提交协议&#xff08;3PC&#xf…...

云安全与网络安全:核心区别与协同作用解析

在数字化转型的浪潮中&#xff0c;云安全与网络安全作为信息安全的两大支柱&#xff0c;常被混淆但本质不同。本文将从概念、责任分工、技术手段、威胁类型等维度深入解析两者的差异&#xff0c;并探讨它们的协同作用。 一、核心区别 定义与范围 网络安全&#xff1a;聚焦于保…...