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

每日一题——博弈论(枚举与暴力)

博弈论

题目描述

运行代码

#include<iostream>
#include<vector>
using namespace std;
int main(){int n;cin >> n;vector<int> d(n,0);for(int i = 0;i < n;i++){cin >> d[i];}vector<int> in(1000,0);for(int k = 1;k<=3;k++){for(int i=0;i<=n-k;i++){int t = 0;for(int j=i;j<i+k;j++){t = 10*t+d[j];}in[t] = 1;}}for(int i = 0;i < 1000;i++)if(in[i] == 0){cout << i << endl;return 0;}return 0;
}

代码思路

  1. 输入处理:

    • 首先,程序接收一个整数n,表示数字序列的长度。
    • 然后,程序读取接下来的n个整数并存储在一个名为dvector(动态数组)中。
  2. 初始化标记数组:创建一个大小为1000的vector in,并将其所有元素初始化为0。这个数组用来标记长度为1至3位的整数是否在给定序列中出现过。由于最大的3位数是999,因此1000的大小足够覆盖所有可能的情况。

  3. 检查数字序列:对于长度为1、2、3的子序列,程序遍历所有可能的起始位置i:计算从位置i开始,长度为k(当前循环的长度)的子序列对应的整数t。这是通过将子序列中的每个数字乘以相应位值(10的幂)并求和得到的。将计算出的整数tin数组中标记为1,表示这个数值已经在输入序列中出现过了。

  4. 寻找未出现的最小整数:

    • 遍历in数组,找到第一个值为0的元素的索引,这代表了未在输入序列中出现过的最小正整数。
    • 一旦找到这样的索引,立即输出该索引(即对应的整数),并结束程序。
  5. 返回:如果遍历完整个in数组都没有找到未出现的整数(理论上这种情况不应该发生,但代码逻辑没有直接处理这种特殊情况),程序会正常结束。

改进思路

  1. 减少内存使用:目前使用了一个大小为1000的vector来标记数字是否出现,其实最大只需要到n的长度变化的所有组合即可,特别是当n远小于3时。可以通过动态调整in的大小或者使用更高效的数据结构如setunordered_set来改进。

  2. 优化寻找未出现数字的步骤:当前实现是线性查找in数组中值为0的第一个元素,若大多数数字都已出现,则效率较低。可以在遍历过程中直接记录第一个未出现的数字,减少后续查找步骤。

  3. 增加对极端情况的处理:例如,当输入序列为空或全为0时,原始代码可能表现得不够直观或正确。

改进代码

#include <iostream>
#include <vector>
#include <unordered_set>
using namespace std;int main() {int n;cin >> n;vector<int> d(n, 0);// 输入数字序列for (int i = 0; i < n; ++i) {cin >> d[i];}// 使用unordered_set存储已出现的数字,自动去重且查找效率高unordered_set<int> appeared;// 检查数字序列,添加长度为1到3的数字到集合中for (int k = 1; k <= min(3, n); ++k) { // 添加边界条件避免n<k时的无效迭代for (int i = 0; i <= n - k; ++i) {int t = 0;for (int j = i; j < i + k; ++j) {t = 10 * t + d[j];}appeared.insert(t);}}// 寻找未出现的最小正整数int i = 1;while (appeared.find(i) != appeared.end()) {++i;}cout << i << endl;return 0;
}
  1. 通过使用unordered_set来存储已出现的数字,提高了查找未出现数字的效率。
  2. 通过直接在遍历过程中寻找未出现的最小整数,避免了最后单独的查找循环,使得代码更加简洁。
  3. 增加了对输入序列长度的边界检查,确保了代码的健壮性。
注意点:

改进代码为AI生成,并且这个代码的数据通过率97%,无法通过所有测试数据

相关文章:

每日一题——博弈论(枚举与暴力)

博弈论 题目描述 运行代码 #include<iostream> #include<vector> using namespace std; int main(){int n;cin >> n;vector<int> d(n,0);for(int i 0;i < n;i){cin >> d[i];}vector<int> in(1000,0);for(int k 1;k<3;k){for(int…...

pytorch笔记:torch.nn.Flatten()

1 介绍 torch.nn.Flatten(start_dim1, end_dim-1) 将一个连续的维度范围扁平化为一个张量 start_dim (int)要开始扁平化的第一个维度&#xff08;默认值 1&#xff09;end_dim (int)要结束扁平化的最后一个维度&#xff08;默认值 -1&#xff09; 2 举例 input torch.ra…...

一个人应该怎么操作抖音小店呢?店铺操作流程给你讲解清楚!

大家好&#xff0c;我是电商小V 现在入驻抖音小店的有很多新手&#xff0c;新手最关心的就是一个人应该如何操作抖音小店&#xff0c;操作抖音小店需要做好哪几步呢&#xff1f;关于这个问题咱们就来详细的讲解一下&#xff0c; 第一点&#xff1a;开店 开店是做店的第一步&…...

“等保测评与安全运维的协同:保障企业网络安宁

"等保测评与安全运维的协同&#xff1a;保障企业网络安宁"是一个涉及信息安全领域的重要话题。这里&#xff0c;我们可以从几个方面来探讨这个主题。 1. 等保测评&#xff08;等级保护测评&#xff09; 等保测评&#xff0c;即信息安全等级保护测评&#xff0c;是依…...

python抽取pdf中的参考文献

想将一份 pdf 论文中的所有参考文献都提取出来&#xff0c;去掉不必要的换行&#xff0c;放入一个 text 文件&#xff0c;方便复制。其引用是 ieee 格式的&#xff0c;形如&#xff1a; 想要只在引用序号&#xff08;如 [3]&#xff09;前换行&#xff0c;其它换行都去掉&…...

Java进阶学习笔记21——泛型概念、泛型类、泛型接口

泛型&#xff1a; 定义类、接口、方法的时候&#xff0c;同时声明了一个或者多个类型变量&#xff08;如: <E>&#xff09;,称之为泛型类、泛型接口、泛型方法&#xff0c;我们统称之为泛型。 说明这是一个泛型类。 如果不使用泛型&#xff0c;我们可以往ArrayList中传…...

深入理解计算机系统 家庭作业4.55

...

第二天-⑦前后端需要注意的事项

①防xss跨站脚本攻击...

Socket 函数详细讲解(Socket编程步骤、socket函数、TCP和UDP的区别)

Socket 函数详细讲解和 C 示例 一、 Socket 基本概念1. Socket 简介2. Socket 编程步骤3. TCP Socket 编程示例服务器端客户端 4. 详细说明 二、 socket 函数1. domain 通讯的协议家族2. type 数据传输的类型3. protocol 最终使用的协议返回值示例 三、TCP 和 UDP的区别1. TCP&…...

【限免】杂波环境下线性调频脉冲、巴克码、频率步进脉冲雷达MTI、脉冲压缩【附MATLAB代码】

来源&#xff1a;微信公众号&#xff1a;EW Frontier 本代码主要模拟杂波环境&#xff08;飞机、地杂波、鸟类信号&#xff09;下&#xff0c;Chirp脉冲、巴克码脉冲、频率步进脉冲雷达信号的脉冲压缩及MTI、​匹配滤波。 MATLAB主代码 % 定义参数 fs 1000; % 采样率 T 1; …...

前端最新面试题(Javascript模块篇)

目录 1 数据类型基础 1.1 JS内置类型 1.2 null和undefined区别 1.3 null是对象吗?为什么? 1.4 1.toString()为什么可以调用? 1.5 0.1+0.2为什么不等于0.3?如何让其相等 1.6 如何理解BigInt 1.7 JS 整数是怎么表示的 1.8 Number() 的存储空间是多大?如果后台发送了…...

Android11热点启动和关闭

Android官方关于Wi-Fi Hotspot (Soft AP) 的文章&#xff1a;https://source.android.com/docs/core/connect/wifi-softap?hlzh-cn 在 Android 11 的WifiManager类中有一套系统 API 可以控制热点的开和关&#xff0c;代码如下&#xff1a; 开启热点&#xff1a; // SoftApC…...

DI-engine强化学习入门(三)DI-ZOO强化学习环境搭建与示例运行——Atari

Atari是一家知名的电子游戏公司&#xff0c;成立于1972年&#xff0c;是早期电子游戏产业的先驱之一。在强化学习领域&#xff0c;提到Atari通常指的是Atari 2600游戏的一系列环境&#xff0c;这些环境是用于开发和测试强化学习算法的标准平台。 Atari 2600 强化学习环境概述 …...

【一站式学会Kotlin】第十节:kotlin 语言的可控性特点和安全调用操作符

作者介绍: 百度资深Android工程师T6,在百度任职7年半。 目前:成立赵小灰代码工作室,欢迎大家找我交流Android、微信小程序、鸿蒙项目。= 一:通俗易懂的人工智能教程:https://www.captainbed.cn/nefu/ 点一下,打开新世界的大门。 二:【一站式学会Kotlin】免费领取:作者…...

PaddleClas 指定gpu

在使用PaddleClas进行模型训练或预测时&#xff0c;如果您想要指定使用特定的GPU设备&#xff0c;可以通过CUDA_VISIBLE_DEVICES环境变量来设置。 在命令行中设置GPU的方法如下&#xff1a; # 指定第0号GPU export CUDA_VISIBLE_DEVICES0 # 之后运行PaddleClas的命令&#xf…...

langchain进阶一:特殊的chain,轻松实现对话,与数据库操作,抽取数据,以及基于本地知识库的问答

特殊的chain langchain中的Chain有很多,能够轻松实现部分需求,极致简化代码,但是实现效果与模型智慧程度有关 会话链 效果与LLMChain大致相同 javascript 复制代码 from langchain.chains import ConversationChain from langchain_community.llms import OpenAI conversat…...

【Spring Boot】响应式编程

响应式编程 1.WebFlux2.比较 MVC 和 WebFlux2.1 工作方式2.2 Spring MVC 与 Spring WebFlux 的区别2.3 使用 WebFlux 的好处 3.Mono 和 Flux3.1 Mono 和 Flux 是什么3.2 Mono 和 Flux 的区别 4.开发 WebFlux 的流程4.1 注解式开发流程4.2 响应式开发流程 5.用注解式开发实现 He…...

【C++练级之路】【Lv.21】C++11——列表初始化和声明

快乐的流畅&#xff1a;个人主页 个人专栏&#xff1a;《算法神殿》《数据结构世界》《进击的C》 远方有一堆篝火&#xff0c;在为久候之人燃烧&#xff01; 文章目录 引言一、列表初始化1.1 内置类型1.2 结构体或类1.3 容器 二、声明2.1 auto2.2 decltype2.3 nullptr 三、STL的…...

输入一串字符串,前中后都有*号,去掉字符串中间和后面的*号,保留前面的*号和字母

#include <stdio.h> void fun(char* a) {//***df**fr*fg***int i 0, j 0,n0,m0;char* p;p a;while (p[i] ! \0){i;//i是一共的字符的个数}printf("%d\n",i);while (a[n] *){n;//计算字母前的*的个数}printf("%d\n", n);m n;for (j n; j < …...

【机器学习与大模型】驱动下的应用图像识别与处理

摘要&#xff1a; 本文深入探讨了机器学习在图像识别与处理领域的应用&#xff0c;特别是在大模型的推动下所取得的巨大进展。详细阐述了图像识别与处理的基本原理、关键技术&#xff0c;以及机器学习算法和大模型如何提升其性能和准确性。通过实际案例分析了其在多个领域的广泛…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

【力扣数据库知识手册笔记】索引

索引 索引的优缺点 优点1. 通过创建唯一性索引&#xff0c;可以保证数据库表中每一行数据的唯一性。2. 可以加快数据的检索速度&#xff08;创建索引的主要原因&#xff09;。3. 可以加速表和表之间的连接&#xff0c;实现数据的参考完整性。4. 可以在查询过程中&#xff0c;…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)

骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术&#xff0c;它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton)&#xff1a;由层级结构的骨头组成&#xff0c;类似于人体骨骼蒙皮 (Mesh Skinning)&#xff1a;将模型网格顶点绑定到骨骼上&#xff0c;使骨骼移动…...

基于PHP的连锁酒店管理系统

有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发&#xff0c;数据库mysql&#xff0c;前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...

nnUNet V2修改网络——暴力替换网络为UNet++

更换前,要用nnUNet V2跑通所用数据集,证明nnUNet V2、数据集、运行环境等没有问题 阅读nnU-Net V2 的 U-Net结构,初步了解要修改的网络,知己知彼,修改起来才能游刃有余。 U-Net存在两个局限,一是网络的最佳深度因应用场景而异,这取决于任务的难度和可用于训练的标注数…...

微服务通信安全:深入解析mTLS的原理与实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、引言&#xff1a;微服务时代的通信安全挑战 随着云原生和微服务架构的普及&#xff0c;服务间的通信安全成为系统设计的核心议题。传统的单体架构中&…...

Python学习(8) ----- Python的类与对象

Python 中的类&#xff08;Class&#xff09;与对象&#xff08;Object&#xff09;是面向对象编程&#xff08;OOP&#xff09;的核心。我们可以通过“类是模板&#xff0c;对象是实例”来理解它们的关系。 &#x1f9f1; 一句话理解&#xff1a; 类就像“图纸”&#xff0c;对…...