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

织梦网站首页模板更换/全网推广平台有哪些

织梦网站首页模板更换,全网推广平台有哪些,淄博那里有做网站的,北京网络营销外包公司哪家好洛谷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里的牛奶产量之和 …

洛谷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;触发了回收策略。 于是临时扩容,运维同学当时未找到阿里云配置。 后面我用工具连接了…...

Android14 WMS启动流程

一 概述 本文Android14源代码可参考&#xff1a;Search 在 Android 系统中&#xff0c;从设计的角度来看&#xff0c;窗口管理系统是基于 C/S 模式的。整个窗口系统分为服务端和客户端两大部分&#xff0c;客户端负责请求创建窗口和使用窗口&#xff0c;服务端完成窗口的维护…...

磁盘管理(初始化,引导块,坏块管理,固态硬盘)

目录 1.磁盘初始化2.引导块3.坏块的管理1.坏块检查2.坏块链表3.扇区备用 4.固态硬盘&#xff08;SSD&#xff09;1.原理2.组成3.读写性能特性4.与机械硬盘相比5.磨损均衡技术 1.磁盘初始化 ①进行低级格式化&#xff08;物理格式化&#xff09;&#xff0c;将磁盘的各个磁道划分…...

mysql冷拷贝大表

1、简述&#xff1a; mysql数据迁移有多种方式&#xff0c;最常见的就是先把数据库导出&#xff0c;然后导入新的数据库。拷贝数据目录data是另外一种方式。 尤其是当数据库启动不了&#xff0c;或者大型数据库迁移的时候&#xff0c;可以考虑这个方式。 2、场景&#xff1a…...

苍穹外卖-01

苍穹外卖-01 课程内容 软件开发整体介绍苍穹外卖项目介绍开发环境搭建导入接口文档Swagger 项目整体效果展示&#xff1a; ​ 管理端-外卖商家使用 ​ 用户端-点餐用户使用 当我们完成该项目的学习&#xff0c;可以培养以下能力&#xff1a; 1. 软件开发整体介绍 作为一名…...

GAMP源码阅读(中)伪距单点定位 SPP

原始 Markdown文档、Visio流程图、XMind思维导图见&#xff1a;https://github.com/LiZhengXiao99/Navigation-Learning 文章目录 一、SPP 解算1、spp()&#xff1a;单点定位主入口函数2、estpos()3、estpose_()4、valsol()&#xff1a;GDOP和卡方检验结果有效性 二、卫星位置钟…...

Epinoia-有状态网络的意图验证模块,略读

Epinoia relies on a unified model for NFs by leveraging the causal precedence relationshipsthat exist between NF packet I/Os and states. 这句话的意思是&#xff1a;“Epinoia依靠一种统一的网络功能&#xff08;NF&#xff09;模型&#xff0c;通过利用存在于 NF 包…...

14.力扣c++刷题-->有效括号

题目&#xff1a;给定一个只包括 ‘(’&#xff0c;‘)’&#xff0c;‘{’&#xff0c;‘}’&#xff0c;‘[’&#xff0c;‘]’ 的字符串 s &#xff0c;判断字符串是否有效。 有效字符串需满足&#xff1a; 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合…...

scrapy-redis分布式爬虫(分布式爬虫简述+分布式爬虫实战)

一、分布式爬虫简述 &#xff08;一&#xff09;分布式爬虫优势 1.充分利用多台机器的带宽速度 2.充分利用多台机器的ip地址 &#xff08;二&#xff09;Redis数据库 1.Redis是一个高性能的nosql数据库 2.Redis的所有操作都是原子性的 3.Redis的数据类型都是基于基本数据…...

单目深度估计之图像重构原理解析

一、参考资料 浅析自监督深度估计中的光度损失(Photometric Loss) 二、图像重构原理 设输入位姿估计网络的3帧连续单目序列为 < I t − 1 , I t , I t 1 > <I_{t-1},I_{t},I_{t1}> <It−1​,It​,It1​>&#xff0c;其中 t t t 为时间索引&#xff0c;…...

【爬虫】charles手机抓包环境设置(设置系统证书)

1.说明 想要对手机抓包&#xff0c;最关键的是需要设置好根证书&#xff0c;用户证书在安卓7.0之后就不受信任了&#xff0c;想要对手机app抓包&#xff0c;就需要把用户证书设置为系统证书&#xff08;根证书&#xff09; 注意&#xff0c;想要设置为根证书&#xff0c;你的…...