首页 > 其他分享 >【学习笔记】折半搜索 Meet In The Middle

【学习笔记】折半搜索 Meet In The Middle

时间:2023-09-10 16:44:25浏览次数:51  
标签:折半 10 比赛 leq int sum Middle Meet 500

点击查看目录

目录

题单
oi-wiki

算法实现

我们正常的搜索应该是一个指数级的:\(2^n\)。

DFS

然而我们可以把这个搜索拆成两半,设小于整张图的限制 \(limit\) 为合法:

对于上半搜索,我们有若干符合限制的答案 \(sum_1\),对于下半搜索,我们有若干符合限制的答案 \(sum_2\)。

因此对于下半搜索,有一个匹配的限制:\(limit-sum_2[i],i\in sum_2\),在这个限制下,有多个上半搜索的匹配,类似于:

杂题乱写

[CEOI2015 Day2] 世界冰球锦标赛

题目链接

折叠题干

[CEOI2015 Day2] 世界冰球锦标赛

题目描述

译自 CEOI2015 Day2 T1「Ice Hockey World Championship

今年的世界冰球锦标赛在捷克举行。Bobek 已经抵达布拉格,他不是任何团队的粉丝,也没有时间观念。他只是单纯的想去看几场比赛。如果他有足够的钱,他会去看所有的比赛。不幸的是,他的财产十分有限,他决定把所有财产都用来买门票。

给出 Bobek 的预算和每场比赛的票价,试求:如果总票价不超过预算,他有多少种观赛方案。如果存在以其中一种方案观看某场比赛而另一种方案不观看,则认为这两种方案不同。

输入格式

第一行,两个正整数 \(N\) 和 \(M(1 \leq N \leq 40,1 \leq M \leq 10^{18})\),表示比赛的个数和 Bobek 那家徒四壁的财产。

第二行,\(N\) 个以空格分隔的正整数,均不超过 \(10^{16}\),代表每场比赛门票的价格。

输出格式

输出一行,表示方案的个数。由于 \(N\) 十分大,注意:答案 \(\le 2^{40}\)。

样例 #1

样例输入 #1

5 1000
100 1500 500 500 1000

样例输出 #1

8

提示

样例解释
八种方案分别是:

  • 一场都不看,溜了溜了
  • 价格 \(100\) 的比赛
  • 第一场价格 \(500\) 的比赛
  • 第二场价格 \(500\) 的比赛
  • 价格 \(100\) 的比赛和第一场价格 \(500\) 的比赛
  • 价格 \(100\) 的比赛和第二场价格 \(500\) 的比赛
  • 两场价格 \(500\) 的比赛
  • 价格 \(1000\) 的比赛

有十组数据,每通过一组数据你可以获得 10 分。各组数据的数据范围如下表所示:

数据组号 \(1-2\) \(3-4\) \(5-7\) \(8-10\)
\(N \leq\) \(10\) \(20\) \(40\) \(40\)
\(M \leq\) \(10^6\) \(10^{18}\) \(10^6\) \(10^{18}\)

这不板子题(

Miku's Code
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define rg register int
#define MYMAX 20070831
typedef long double llf;
typedef long long ll;
typedef pair<int,int> PII;
const double eps=1e-8;
int Max(int x,int y)<%if(x<y)	return y;return x;%>
int Min(int x,int y)<%if(x<y)	return x;return y;%>
int Abs(int x)<%if(x<0)	return x*(-1);return x;%>
#if ONLINE_JUDGE
char in[1<<20],*p1=in,*p2=in;
#define getchar() (p1==p2&&(p2=(p1=in)+fread(in,1,1<<20,stdin),p1==p2)?EOF:*p1++)
#endif
inline ll read(){
	char c=getchar();
    ll x=0,f=1;
    while(c<48)<%if(c=='-')f=-1;c=getchar();%>
    while(c>47)x=(x*10)+(c^48),c=getchar();
    return x*f;
}const int maxn=45;

int n;
ll m,cost[maxn];
vector<ll> s1,s2;

void dfs(int st,int to,ll sum,vector<ll>&now){
	if(sum>m)	return;
	if(st>to){
		now.push_back(sum);
		return;
	}
	dfs(st+1,to,sum+cost[st],now);
	dfs(st+1,to,sum,now);
}

int main(){
	n=read(),m=read();
	for(rg i=1;i<=n;++i) cost[i]=read();
	dfs(1,n/2,0,s1);
	dfs(n/2+1,n,0,s2);
	sort(s1.begin(),s1.end());
	ll ans=0;
	int len2=s2.size()-1;
	for(rg i=0;i<=len2;++i)	ans+=upper_bound(s1.begin(),s1.end(),m-s2[i])-s1.begin();
	printf("%lld\n",ans);
}

标签:折半,10,比赛,leq,int,sum,Middle,Meet,500
From: https://www.cnblogs.com/sonnety-v0cali0d-kksk/p/17691466.html

相关文章

  • Why Software Developers Are Silent in Meetings
    TheyShouldn’tBeEversatinaSprintRetrowhereyourScrumMasterdidn’tarrivefortenminutes?Ijustdid.Wesatinsilence.EverbeeninaSprintRetrowherealmostnobodyparticipates?AreyouthinkingIjustdid?You’reagreatblogreaderifyo......
  • Spikformer: When Spiking Neural Network Meets Transformer
    郑重声明:原文参见标题,如有侵权,请联系作者,将会撤销发布!PublishedasaconferencepaperatICLR2023(同大组工作) ABSTRACT我们考虑了两种生物学合理的结构,脉冲神经网络(SNN)和自注意机制。前者为深度学习提供了一种节能且事件驱动的范式,而后者则能够捕获特征依赖性,使Trans......
  • WorkPlus Meet白板和文档共享功能上线,私有化视频会议全新升级
    在迅猛发展的数字化时代,私有化视频会议成为企业高效沟通和协作的关键工具。WorkPlusMeet作为领先品牌,倾力打造私有化视频会议平台,并且最新上线了全新的白板和文档共享模块。本文将重点介绍WorkPlusMeet如何通过创新功能和稳定性,提供卓越的私有化视频会议体验,助力企业实现高效沟通......
  • 折半搜索 学习笔记
    关于算法折半搜索,又称meetinthemiddle算法。顾名思义,就是将整个搜索的过程分成两个部分分别进行搜索,然后再将两个部分搜索出来的答案进行合并,得到最终的答案。dfs搜索算法一般都是指数级别的,那么我们假如每次dfs时都有两种决策,那么我们执行dfs算法的时间复杂度为\(O......
  • 万人在线,一站式自动化运维 SysOM 3.0重磅发布!龙蜥社区系统运维 MeetUp 回顾来了
    8月12日,由龙蜥社区系统运维SIG主办,乘云数字协办的,主题为“观测,让运维更简单!”的系统运维MeetUp于杭州圆满结束。来自乘云数字、谐云科技、乐维、云杉网络、擎创科技、观测云、阿里云以及浙江大学等众多厂商及高校的11位专家和教授,分享了精彩主题演讲,带来了前沿技术见解。......
  • 插入排序:直接插入排序、折半插入排序、希尔排序的实现
    直接插入排序定义:直接插入排序是一种最简单的排序方法,其基本操作是将一条记录插入到已排好序的有序表中,从而得到一个新的、记录数量增1的有序表。算法的代码:#include<stdio.h>#include<stdlib.h>voidprint_series(constintseries[],intlen){for(inti=0;......
  • 【NestJS系列】核心概念:Middleware中间件
    前言用过express与koa的同学,对中间件这个概念应该非常熟悉了,中间件可以拿到Request、Response对象和next函数.一般来讲中间件有以下作用:执行任何代码对请求与响应拦截并改造结束request-response周期通过next()调用下一个中间件如果当前中间件没有结束当前request-respons......
  • align属性absMiddle、AbsBottom、Baseline、Bottom、Left、Middle、NotSet、Right、Te
    AbsBottom图像的下边缘与同一行中最大元素的下边缘对齐。AbsMiddle图像的中间与同一行中最大元素的中间对齐。Baseline图像的下边缘与第一行文本的下边缘对齐。Bottom图像的下边缘与第一行文本的下边缘对齐。Left图像沿网页的左边缘对齐,文字在图像右边换行。Middle图像......
  • 「学习笔记」meet in the middle(折半搜索)
    meetinthemiddle,适用于输入数据较小,但也没小到可以直接用暴力搜索通过的情况。主要的思想就是讲整个搜索过程分成两半进行,最后在将这两半的结果进行合并,对于搜索复杂度为\(O(a^b)\)的情况,meetinthemiddle可以将它优化为\(O(a^{\frac{b}{2}})\)。题目P5691[NOI2001]......
  • 二分查找法(折半查找)
    二分查找法是一种在有序数组中查找特定元素的算法。为了理解它的工作原理,我们需要知道数组是有序的,也就是说,数组中的元素按照升序或降序排列。二分查找法的基本步骤如下:选择数组的中间元素。如果中间元素正好是目标值,则搜索结束。如果目标值大于中间元素,则只需在数组的......