USACO12OPEN Balanced Cow Subsets G(meet in the middle)

这篇具有很好参考价值的文章主要介绍了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)文章来源地址https://www.toymoban.com/news/detail-717079.html

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)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【已解决】git 撤销上次提交后修改文件再次提交 触发:Cannot do a soft reset in the middle of a merge

    记录一次 git 操作 git 撤销上次提交后修改文件,然后同步触发以下命令及报错(报错来源与git输出面板) 同步包含两步: pull push git pull 此次合并未处理(变更记录未覆盖任何冲突处) git pull 此次合并未处理干净(变更记录未完全覆盖所有冲突处) git pull 此次拉取前未提交

    2024年02月15日
    浏览(57)
  • Detecting Everything in the Open World: Towards Universal Object Detection

    论文题目《Detecting Everything in the Open World: Towards Universal Object Detection》 发表情况,CVPR2023 [论文地址][https://arxiv.org/pdf/2303.11749.pdf] [代码地址][https://github.com/zhenyuw16/UniDetector] 本文旨在解决通用目标检测问题,也即 检测任意场景、任意类别的目标 。 对手工标注的依赖、有限的

    2024年02月13日
    浏览(44)
  • 【蓝桥杯冲冲冲】动态规划初步[USACO2006 OPEN] 县集市

    [USACO2006 OPEN] 县集市 The County Fair 每年,FJ 都喜欢去参加县集市,集市上有 n n n 个展位,每个摊位 i i i 都会在当天的特定时间 p i p_i p i ​ 发放精美的礼品。FJ 已经听说了这一点,他希望能收集尽可能多的礼品和他的奶牛们一起分享。要想获得摊位 i i i 发放的礼品,FJ 必须确

    2024年01月22日
    浏览(35)
  • LeetCode //C - 2095. Delete the Middle Node of a Linked List

    You are given the head of a linked list. Delete the middle node, and return the head of the modified linked list. The middle node of a linked list of size n is the [ n / 2 ] t h [n / 2]^{th} [ n /2 ] t h node from the start using 0-based indexing, where ⌊x⌋ denotes the largest integer less than or equal to x. For n = 1, 2, 3, 4, and 5, the middle nodes a

    2024年02月02日
    浏览(47)
  • USACO24Bronze 游记兼 TJ All in Once

    我没有其他组别的号了。所以只能写 Bronze 的游记了。 如果行的话,下一次我会写 Silver 的。 一开始看了看三道题,T1T2 感觉都很不可做,直奔 T3。 一看 T3(Bessie 很 nb,会各种各样的东西,会科学,会魔法,今天我们发现她会分身术),不就是个二分吗?秒杀。 好的,现在

    2024年02月19日
    浏览(39)
  • android10系统手机获取IMSI报错:The user 10116 does not meet the requirements to access device identifiers

    最近在项目调试中,获取手机的IMSI,IMEI等信息,发现在Android10以下系统的设备上正常,但是在Android10以上系统的设备上报错:The user 10116 does not meet the requirements to access device identifiers 出现该问题的原因如下: Android 10(API 级别 29)起,您的应用必须是设备,或者个人资料所

    2024年02月13日
    浏览(48)
  • [综述] Generative AI meets 3D: A Survey on Text-to-3D in AIGC Era

    论文| 改文章是23年5月27日挂在arxiv上,本文重点关注4.1节Text Guided 3D Avatar Generation、4.4节Text Guided 3D Shape Transformation和第5章Discussion DreamAvatar DreamAvatar: Text-and-Shape Guided 3D Human Avatar Generation via Diffusion Models https://arxiv.org/abs/2304.00916生成姿态可控的高质量3D人体avatar,包含以下几

    2024年02月16日
    浏览(57)
  • Win11预览体验计划显示Your PC does not meet the minimum hardware requirements...的解决方案

    某一天你心血来潮,打算参与Win11 预览体验计划,但体验计划页面却显示“Your PC does not meet the minimum hardware requirements for Windows11…”。 一种解决思路: 去以下网页下载Offline Insider Enroll软件,管理员权限运行后,选择你想参与的体验计划通道。 Offline Insider Enroll https://github.

    2024年02月04日
    浏览(73)
  • P2921 [USACO08DEC] Trick or Treat on the Farm G

    Portal. 每只奶牛的终止条件是到达自己已经访问过的点,换言之,就是该奶牛的路线构成了一个环。并且,每一个房间通往的房间都是固定且唯一的,所以说只要进入的这个房间在环上,这个房间之后会获得的糖果数已经固定了。 我们开一个数组 s 记录当前位置的糖果数量,

    2024年02月06日
    浏览(237)
  • vscode连接docker报错:The remote host may not meet VS Code Server‘s prerequisites for glibc and libstdc+

    1. 环境介绍: 1)docker系统境:ubuntu18.04; 2)vscode :1.86版本 2. 连接方式 : ssh连接 3. 报错: The remote host may not meet VS Code Server‘s prerequisites for glibc and libstdc+ 4.分析: vscode的升级到1.86版本之后,其对于ubuntu中 glibc 和 libstdc+版本需求更高,容易出现连接不上的问题,其在v

    2024年04月15日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包