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

USACO12OPEN Balanced Cow Subsets G(meet in the middle)

洛谷P3067 [USACO12OPEN] Balanced Cow Subsets G

题目大意

我们定义一个奶牛集合 S S S是平衡的,当且仅当满足以下两个条件:

  • S S S非空
  • S S S可以被划分为两个集合 A , B A,B A,B,满足 A A A里的奶牛产量之和等于 B B B里的牛奶产量之和

现在给定大小为 n n n的奶牛集合 S S S,询问它有多少个子集是平衡的。

1 ≤ n ≤ 20 , 1 ≤ a i ≤ 1 0 8 1\leq n\leq 20,1\leq a_i\leq 10^8 1n20,1ai108


题解

前置知识:折半搜索(meet in the middle)

我们考虑枚举 S S S的子集 S ′ S' S,在枚举子集 S ′ S' S中的每个子集来判断 S ′ S' S是否平衡。每个奶牛有三种情况:不在 S S S中,在 S S S中但不在 S ′ S' S中,在 S S S中且在 S ′ S' S中。如果枚举每种情况的话,时间时间复杂度是 O ( 3 n ) O(3^n) O(3n)的,我们考虑优化。

我们可以用折半搜索,将所有奶牛分为两个部分。

设前一部分中划分到集合 A A A的元素的值之和为 a a a,划分到集合 B B B的元素的值之和为 b b b

设后一部分中划分到集合 A A A的元素的值之和为 c c c,划分到集合 B B B的元素的值之和为 d d d

那么, a + c = b + d a+c=b+d a+c=b+d,移项的 a − b = c − d a-b=c-d ab=cd

我们先处理出前一部分的 a − b a-b ab,然后对于每一个 c − d c-d cd,在前面处理出的 a − b a-b ab中查找与 c − d c-d cd相等的并判断这两部分构成的集合是否是平衡的,是的话就更新答案即可。

处理前一部分和后一部分的时间复杂度都为 O ( 3 n / 2 ) O(3^{n/2}) O(3n/2),合并的时间复杂度为 O ( n 3 n ) O(n3^n) O(n3n),所以总时间复杂度为 O ( n 3 n ) O(n3^n) O(n3n)

code

#include<bits/stdc++.h>
using namespace std;
int n,cnt=0,ans=0,a[25],z[1<<20];
map<int,int>mp;
vector<int>v[1<<20];
void dfs1(int t,int sum,int now){if(t==n/2+1){if(!mp[sum]) mp[sum]=++cnt;v[mp[sum]].push_back(now);return;}dfs1(t+1,sum+a[t],now|(1<<t-1));dfs1(t+1,sum-a[t],now|(1<<t-1));dfs1(t+1,sum,now);
}
void dfs2(int t,int sum,int now){if(t==n+1){int tmp=mp[sum];if(tmp)for(int i=0;i<v[tmp].size();i++){z[v[tmp][i]|now]=1;}return;}dfs2(t+1,sum+a[t],now|(1<<t-1));dfs2(t+1,sum-a[t],now|(1<<t-1));dfs2(t+1,sum,now);
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}dfs1(1,0,0);dfs2(n/2+1,0,0);for(int i=1;i<1<<n;i++) ans+=z[i];printf("%d",ans);return 0;
}

相关文章:

USACO12OPEN Balanced Cow Subsets G(meet in the middle)

洛谷P3067 [USACO12OPEN] Balanced Cow Subsets G 题目大意 我们定义一个奶牛集合 S S S是平衡的&#xff0c;当且仅当满足以下两个条件&#xff1a; S S S非空 S S S可以被划分为两个集合 A , B A,B A,B&#xff0c;满足 A A A里的奶牛产量之和等于 B B B里的牛奶产量之和 …...

GIT常用操作记录

1、后悔药&#xff1a;强制回退到某个具体历史提交记录&#xff0c;并强制推送到远程仓库 强制回退到某个具体历史提交记录&#xff0c;即要删除它之后的所有提交&#xff0c;可以用 git reset 命令。 首先找到目标提交记录的ID&#xff0c;可以在github远程仓库的历史提交记…...

【ETL工具】Datax-ETL-SqlServerToHDFS

&#x1f984; 个人主页——&#x1f390;个人主页 &#x1f390;✨&#x1f341; &#x1fa81;&#x1f341;&#x1fa81;&#x1f341;&#x1fa81;&#x1f341;&#x1fa81;&#x1f341; 感谢点赞和关注 &#xff0c;每天进步一点点&#xff01;加油&#xff01;&…...

Kubernetes (K8S)概述

1、K8S 是什么&#xff1f; K8S 的全称为 Kubernetes (K12345678S)&#xff0c;PS&#xff1a;“嘛&#xff0c;写全称也太累了吧&#xff0c;不如整个缩写”。 1.1 作用 用于自动部署、扩展和管理“容器化&#xff08;containerized&#xff09;应用程序”的开源系统。 可以…...

11月14号|Move生态Meetup相约浪漫土耳其

Move是基于Rust编程语言&#xff0c;由Mysten Labs联合创始人兼CTO Sam Blackshear在Meta的Libra项目中开发而来&#xff0c;旨在为开发者提供比现有区块链语言更通用的开发语言。Sam的目标是创建Web3的JavaScript&#xff0c;即一种跨平台语言&#xff0c;使开发人员能够在多个…...

mac vim没有颜色 问题

vim ~/.vimrc syntax on set nu! set autoindent...

Servlet核心API

目录 HttpServlet init destory service 实例&#xff1a;处理get、post、put、delete请求 1.通过postman得到请求 2.通过ajax得到请求 HttpServletRequest 常见方法 前端给后端传参 1.GET,query string 2.POST,form 3.POST&#xff0c;json HttpSeverletRespons…...

crs 维护模式 exclusive mode

How To Validate ASM Instances And Diskgroups On A RAC Cluster (When CRS Does Not Start). (Doc ID 1609127.1)​编辑To Bottom [rootrac1 ~]# ps -ef|grep grid root 2477 1 1 20:47 ? 00:00:51 /opt/oracle.ahf/jre/bin/java -server -Xms32m -Xmx64…...

【OpenCV实现平滑图像形态学变化】

文章目录 概要目标腐蚀膨胀开运算结构元素&#xff08;内核&#xff09;小结 概要 形态学变化是一组简单的图像操作&#xff0c;主要用于处理二值图像&#xff0c;即只包含黑和白两种颜色的图像。这些操作通常需要两个输入&#xff0c;原始图像和一个内核&#xff08;kernel&a…...

Ubuntu服务器中java -jar 后台运行Spring Boot项目

问&#xff1a;我在我的服务器中java -jar 运行springboot项目&#xff0c;但是我操作不了命令了&#xff0c;必须要终止掉才能执行后面的操作&#xff0c;怎么样才能让他后台运行呢&#xff1f;比如我的jar包名是tools-boot-0.0.1-SNAPSHOT.jar 使用nohup命令&#xff1a; 在…...

微服务parent工程和子工程pom文件配置注意

parent工程 重要配置&#xff1a; <!-- 父工程 --><packaging>pom</packaging><!-- 聚合 --><modules><module>../base</module><module>../gateway</module><module>../user-service</module><mod…...

STM32G030F6P6点灯闪烁

前言 &#xff08;1&#xff09;如果有嵌入式企业需要招聘湖南区域日常实习生&#xff0c;任何区域的暑假Linux驱动实习岗位&#xff0c;可C站直接私聊&#xff0c;或者邮件&#xff1a;zhangyixu02gmail.com&#xff0c;此消息至2025年1月1日前均有效 &#xff08;2&#xff0…...

K8s开发人员也需要了解的相关知识

工作变动总结一下之前的笔记&#xff0c;整理一个速查的东西&#xff0c;方便之后查阅 K8s开发相关 1、k8s yml apiverison: Kubernetes (k8s) 的 API 版本表示资源定义在 API 服务器中的稳定性和支持程度。API 版本由一个字符串表示&#xff0c;如 v1 或 apps/v1&#xff0c…...

创建并启动华为HarmonyOS本地与远程模拟器及远程真机

1.打开设备管理器 2.选择要添加的手机设备,然后点击安装 3.正在下载华为手机模拟器 4.下载完成 5.创建新模拟器 下载系统镜像 点击下一步,创建模拟器 创建成功 启动模拟器 华为模拟器启动成功 6.登陆华为账号并使用远程模拟器 7.使用远程真机...

责任链模式应用案例

前几天系统商品折扣功能优化&#xff0c;同事采用了责任链模式重构了代码&#xff0c;现整理如下。 一、概念 责任链模式是为请求创建一个处理者对象的链条&#xff0c;所有处理者&#xff08;除最末端&#xff09;都含有下一个对象的引用从而形成一条处理链&#xff0c;该模…...

给你一个整数 num ,返回 num 中能整除 num 的数位的数目

给你一个整数 num &#xff0c;返回 num 中能整除 num 的数位的数目。 如果满足 nums % val 0 &#xff0c;则认为整数 val 可以整除 nums 。 示例 1&#xff1a; 输入&#xff1a;num 7 输出&#xff1a;1 解释&#xff1a;7 被自己整除&#xff0c;因此答案是 1 。 示例 2&…...

Java后端开发——房贷计算器(Ajax版、Json版、等额本息+等额本金)

MVC房贷计算器&#xff08;Ajax版&#xff09; 1.新建一个JavaWeb项目hslcalweb&#xff0c;设置tomcat10。 2.创建房贷计算器JavaBean&#xff1a;HslCalBean.java&#xff0c;增加以下的属性&#xff0c;并生成Getter/Setter方法。 private double total; //贷款额度pr…...

2023.10.28 关于 synchronized 原理

目录 synchronized 特性 synchronized 优化机制 锁升级&#xff08;锁膨胀&#xff09; 其他优化机制 锁消除 锁粗化 synchronized 特性 开始时是乐观锁&#xff0c;如果锁冲突频繁&#xff0c;就转为悲观锁开始是轻量级锁&#xff0c;如果锁被持有的时间较长&#xff0c…...

力扣 27. 移除元素

目录 1.解题思路2.代码实现 1.解题思路 利用双指针思路&#xff0c;当让一个指针先走&#xff0c;指针指向的位置不等于val时&#xff0c;将此时该指针的值给另一个指针并且两个指针都加一&#xff0c;如果等于val,则让该指针加一继续走.最后另一个指针的下标就为排好的数组的…...

redis爆满导致数据丢失

记一则redis爆满导致数据丢失的一场事故 某功能上线后&#xff0c;发现出现问题&#xff0c;最后定位到了 redis. 由于存储的数据过多&#xff0c;导致阿里云4G大小的 redis 爆满&#xff0c;触发了回收策略。 于是临时扩容,运维同学当时未找到阿里云配置。 后面我用工具连接了…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具

文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

在Ubuntu24上采用Wine打开SourceInsight

1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

大家好&#xff0c;我是java1234_小锋老师&#xff0c;看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】&#xff0c;分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...

C#学习第29天:表达式树(Expression Trees)

目录 什么是表达式树&#xff1f; 核心概念 1.表达式树的构建 2. 表达式树与Lambda表达式 3.解析和访问表达式树 4.动态条件查询 表达式树的优势 1.动态构建查询 2.LINQ 提供程序支持&#xff1a; 3.性能优化 4.元数据处理 5.代码转换和重写 适用场景 代码复杂性…...

Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换

目录 关键点 技术实现1 技术实现2 摘要&#xff1a; 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式&#xff08;自动驾驶、人工驾驶、远程驾驶、主动安全&#xff09;&#xff0c;并通过实时消息推送更新车…...

基于Java+VUE+MariaDB实现(Web)仿小米商城

仿小米商城 环境安装 nodejs maven JDK11 运行 mvn clean install -DskipTestscd adminmvn spring-boot:runcd ../webmvn spring-boot:runcd ../xiaomi-store-admin-vuenpm installnpm run servecd ../xiaomi-store-vuenpm installnpm run serve 注意&#xff1a;运行前…...

【Post-process】【VBA】ETABS VBA FrameObj.GetNameList and write to EXCEL

ETABS API实战:导出框架元素数据到Excel 在结构工程师的日常工作中,经常需要从ETABS模型中提取框架元素信息进行后续分析。手动复制粘贴不仅耗时,还容易出错。今天我们来用简单的VBA代码实现自动化导出。 🎯 我们要实现什么? 一键点击,就能将ETABS中所有框架元素的基…...

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

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