首页 > 其他分享 >折半搜索

折半搜索

时间:2024-04-25 17:14:17浏览次数:18  
标签:折半 return int sum dfs 搜索

简介

折半搜索是一种优化搜索的方法,一般可以将 \(O(2^N)\) 优化为 \(O(2^{\frac{N}{2}})\) 。其思想为将一个搜索拆分成两个搜索,分别处理前一半和后一半,使用 mapvector 等东西记录第一次搜索的信息,在第二次搜索时查询。

如以下代码:

void dfs(int x, int sum) {
  if(x > k) {
    return;
  }
  if(x > n) {
    ans += (sum == k);
    return;
  }
  dfs(x + 1, sum);
  dfs(x + 1, sum + a[x]);
}

dfs(1, 0);

用折半搜索会这么写

void dfs(int x, int sum) {
  if(x > k) {
    return;
  }
  if(x == mid + 1) {
    mp[sum]++;
    return;
  }
  dfs(x + 1, sum);
  dfs(x + 1, sum + a[x]);
}

void dfs2(int x, int sum) {
  if(x > k) {
    return;
  }
  if(x == n + 1) {
    ans += mp[k - sum];
    return;
  }
  dfs2(x + 1, sum);
  dfs2(x + 1, sum + a[x]);
}

mid = n / 2, dfs(1, 0), dfs2(mid + 1, 0);

标签:折半,return,int,sum,dfs,搜索
From: https://www.cnblogs.com/yaosicheng124/p/18158124

相关文章

  • 在Linux中,如何使用grep命令搜索文本?
    grep是Linux系统中非常强大的文本搜索工具,它允许用户使用正则表达式搜索文本,并将匹配的行打印到标准输出。下面我将详细解释如何使用grep命令进行文本搜索。1.基本语法grep[OPTIONS]PATTERN[FILE...]PATTERN:要搜索的模式或正则表达式。FILE:要搜索的文件名。如果省......
  • Bootstrip HTML 查询搜索常用格式模版
    BootstripHTML查询搜索常用格式模版<formclass="form-inlinemy-3d-flexalign-items-centerjustify-content-start"method="get"action="{%url'repair:repair_unaccepted'%}"><divclass="form-groupmr-2fle......
  • Everything搜索非NTFS格式文件
    Everything是一款非常优秀的文件搜索软件,但是普通用户只是通过它来进行文件名的搜索。其实该软件还隐藏了很多的搜索功能,用户只要熟练的使用这些功能,就可以快速查询到自己需要的文件内容。搜索非NTFS格式文件Everything软件在默认情况下只能对NTFS格式的文件进行搜索,但是由于现......
  • langchain + ollama 实现本地文档搜索
    fromlangchain.document_loadersimportOnlinePDFLoaderfromlangchain.vectorstoresimportChromafromlangchain.embeddingsimportGPT4AllEmbeddingsfromlangchainimportPromptTemplatefromlangchain.llmsimportOllamafromlangchain.callbacks.managerimp......
  • 2024天梯赛【搜索】
    吉利矩阵题目大意dfs思路搜索策略:每一行每一行的搜索,(1,1)->(1,2)->...->(1,n)->(2,1)->...(n,n)剪枝策略:记录每一行与每一列的总和,sumRow,sumCol,接下来要填的数要小于等于l-sumRow[x]与l-sumCol[y],如果当前行填完了,要判断当前行sumRow[x]是否等于l。题目代码#inc......
  • Reddit采集API reddit文章评论和搜索 实时数据接口
    近期调研发现iDataRiver平台https://www.idatariver.com/zh-cn/提供开箱即用的Reddit数据采集API,是目前用下来最方便简单的API,可以抓取reddit公开数据,例如subreddit中的帖子、按关键字搜索以及文章评论等,供用户按需调用。接口使用详情请参考RedditAPI接口接口列表1.获......
  • 泛型模板化设计使用-订单搜索接口
    泛型模板化设计使用-订单搜索接口1.定义订单搜索接口packagecom.example.core.mydemo.java.templateQuery;//暂不使用该接口//publicinterfaceSearchService<TextendsBaseRequest,FextendsBaseResponse>{publicinterfaceSearchService<T,F>{/***订单......
  • 数据结构与算法学习(1)——DFS(深度优先搜索)
    DFS基础深度优先搜索算法(英语:Depth-First-Search,缩写为DFS)是一种用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索树的分支。当节点v的所在边都己被探寻过,搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发......
  • 语义搜索相关配置
    1.打开services项目,在pom文件中引入依赖如下<dependency><groupId>com.hankcs</groupId><artifactId>hanlp</artifactId><version>portable-1.8.3</version></dependency>2.在hanlpgithub下载语言模型,放入项目根目录下3.在service......
  • JZ68 二叉搜索树的最近公共祖先
    classSolution{public://在哪分开,哪里就是公共祖先!//中序遍历二叉树TreeNode*ans;intlowestCommonAncestor(TreeNode*root,intp,intq){//writecodehereintMin=min(p,q);intMax=max(p,q);InOrder(......