首页 > 编程语言 >【c++】枚举详解

【c++】枚举详解

时间:2024-11-12 19:16:05浏览次数:3  
标签:int ++ c++ met 枚举 详解 MAXN ans

简介

枚举(英语:Enumerate)是基于已有知识来猜测答案的一种问题求解策略。

枚举的思想是不断地猜测,从可能的集合中一一尝试,然后再判断题目的条件是否成立。

要点

给出解空间

建立简洁的数学模型。

枚举的时候要想清楚:可能的情况是什么?要枚举哪些要素?

减少枚举的空间

枚举的范围是什么?是所有的内容都需要枚举吗?

在用枚举法解决问题的时候,一定要想清楚这两件事,否则会带来不必要的时间开销。

选择合适的枚举顺序

根据题目判断。比如例题中要求的是最大的符合条件的素数,那自然是从大到小枚举比较合适

例题

一个数组中的数互不相同,求其中和为0的数对的个数。

 枚举两个数的代码很容易就可以写出来。

for (int i = 0; i < n; ++i)
  for (int j = 0; j < n; ++j)
    if (a[i] + a[j] == 0) ++ans;

来看看枚举的范围如何优化。由于题中没要求数对是有序的,答案就是有序的情况的两倍(考虑如果 (a, b) 是答案,那么 (b, a) 也是答案)。对于这种情况,只需统计人为要求有顺序之后的答案,最后再乘上  就好了。

不妨要求第一个数要出现在靠前的位置。代码如下:

for (int i = 0; i < n; ++i)
  for (int j = 0; j < i; ++j)
    if (a[i] + a[j] == 0) ++ans;

不难发现这里已经减少了  的枚举范围,减少了这段代码的时间开销。

我们可以在此之上进一步优化。

两个数是否都一定要枚举出来呢?枚举其中一个数之后,题目的条件已经确定了其他的要素(另一个数)的条件,如果能找到一种方法直接判断题目要求的那个数是否存在,就可以省掉枚举后一个数的时间了。较为进阶地,在数据范围允许的情况下,我们可以使用桶1记录遍历过的数。

bool met[MAXN * 2 + 1];
memset(met, 0, sizeof(met));
for (int i = 0; i < n; ++i) {
  if (met[MAXN - a[i]]) ++ans;
  met[MAXN + a[i]] = true;
}

标签:int,++,c++,met,枚举,详解,MAXN,ans
From: https://blog.csdn.net/2401_88851881/article/details/143658769

相关文章

  • 【c++】结构体和类详解
    结构体结构体(struct),可以看做是一系列称为成员元素的组合体。可以看做是自定义的数据类型。Note本页描述的 struct 不同于C中 struct,在C++中 struct 被扩展为类似 class 的类说明符。定义结构体structObject{intweight;intvalue;}e[array_length];......
  • C++笔记---智能指针
    1.什么是智能指针1.1 RALL设计思想RAII(ResourceAcquisitionIsInitialization,资源获取即初始化)是一种资源管理类的设计思想,广泛应用于C++等支持对象导向编程的语言中。它的核心思想是将资源的管理与对象的生命周期紧密绑定,通过在对象的构造函数中获取资源,并在析构函数中......
  • 详解连接 MySQL8.4 出现 Client does not support authentication protocol requested
    文章目录项目场景问题描述原因分析解决方案方案一(不推荐)方案二(推荐)总结项目场景在开发过程中,我们在Node.js项目中使用MySQL数据库,并且通过typeorm和mysql库进行数据库连接。然而,在项目启动时,遇到了数据库连接失败的问题,导致项目无法正常运行。问题描述......
  • 打卡信奥刷题(222)用C++信奥P1746[普及组/提高] 离开中山路
    离开中山路题目背景《爱与愁的故事第三弹·shopping》最终章。题目描述爱与愁大神买完东西后,打算坐车离开中山路。现在爱与愁大神在x1,......
  • C++语法·三
    内联函数(inline)简介:用inline修饰的函数叫内联函数,编译时C++编译器会在调用的地方站开内联函数,这样调用函数就不需要创建栈帧了,可以提高效率。内联函数与宏函数:C++中的内联函数与C中的宏函数很相似,都是直接在预处理时展开函数,将函数直接替换到调用位置,不额外创建栈帧。但内联......
  • 【系统架构设计师-2024下半年真题】综合知识-参考答案及部分详解(完整回忆版)
    更多内容请见:备考系统架构设计师-专栏介绍和目录文章目录【第1题】【第2题】【第3题】【第4题】【第5题】【第6~10题】【第11~12题】【第13~14题】【第15题】【第16题】【第17题】【第18题】【第19题】【第20题】【第21题】【第22题】【第23题】......
  • 自动驾驶仿真:软件在环(SIL)测试详解(精简版入门)
    自动驾驶仿真:软件在环(SIL)测试详解一、引言自动驾驶技术的快速发展对测试验证提出了更高要求。软件在环(Software-in-the-Loop,简称SIL)仿真测试作为自动驾驶系统验证的重要手段,通过将自动驾驶的控制软件与虚拟仿真平台结合,实现对自动驾驶系统的软件功能、稳定性和安全性的全面测......
  • 【C++】详细介绍模版进阶,细节满满
    目录一、非类型模版参数:1、介绍:2、使用:3、注意:4、应用二、模版特化(一)、概念(二)、函数模版特化1、步骤:2、举例:3、不建议使用函数模版特化(三)、类模版特化1.全特化:2、偏特化2.1、部分特化2.2、参数更进一步的限制2.3、注意:2.4、普通指针变量传递给const指针变量......
  • PLSQL 最新版永久免费注册(详解)
    打开plsql,登录或者不登录账号都可,进入菜单【帮助】->【注册】弹出框中依次录入以下信息:产品编号:ke4tv8t5jtxz493kl8s2nn3t6xgngcmgf3序列号:264452密码:xs374ca点击【注册】,即注册成功!......
  • C++学习路线(求补充)
    研二女本硕211明年找工作看网上各种经验帖总结了个C++自学路线求各位大佬指正时间有点紧不知道学这些够不够学习内容:黑马C++基础语法书籍:C++primerplus1,2结束后开始刷代码随想录一天两道复习复习语法侯捷视频:侯捷-STL泛型编程(必看)侯捷-C++11新特性(必看)侯捷-......