蓝桥杯23年第十四届省赛真题-填充|DFS,贪心

题目链接:

1.填充 - 蓝桥云课 (lanqiao.cn)

蓝桥杯2023年第十四届省赛真题-填充 - C语言网 (dotcpp.com)

说明: 

dfs就不再多说了,对于每个?都有0和1两个分支,数据范围是:

那么有m个 ?,时间复杂度就是 O(2^{m}),会超时。蓝桥杯官网可以过35%的数据,暴力先拿到一部分再说。

这里需要注意的是:对于?的字符的每层,最后要把它复原,恢复为?

DFS代码:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
string s;
int mx=0;
int len;//参数含义:当前搜索层数k,搜索到第k个字符(从0开始),cn:前面是否有一个单个的字符可以出现00或11串  
//num当前找到的不重叠的00或11子串 数量 
void dfs(int k,int cn,int num){//剩下所有字符都可以组成合法子串加上当前数量都比已经找到的数量小,不再搜索 if(num+(len-k)/2<mx) return;//k个字符都已经搜索过,递归出口 if(k==len){if(num>mx){mx=num;}return;}if(s[k]!='?'){//同时满足 前面是否有一个单个的字符,两个字符相同才计数 ,单个字符数计为0 if(cn==1&&s[k]==s[k-1]){dfs(k+1,0,num+1);}else{//不满足,不计数,该字符是一个单一的字符 dfs(k+1,1,num);}}else{s[k]='0';if(cn==1&&s[k]==s[k-1])dfs(k+1,0,num+1);elsedfs(k+1,1,num);s[k]='1';if(cn==1&&s[k]==s[k-1])dfs(k+1,0,num+1);elsedfs(k+1,1,num);//退出前 要还原成'?' s[k]='?'; }
} signed main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>s;len=s.size();int cnt=0;for(int i=0;i<len;i++){if(s[i]!='?'){//i为0时特别处理,防止i-1越界 if(i==0){cnt=1;}else{if(cnt==1&&s[i]==s[i-1]){cnt=0;mx++;}else{cnt=1;	}}}int n=mx;if(s[i]=='?'){//i为0时特别处理,防止i-1越界 if(i==0) {s[i]='0';dfs(i+1,1,n);s[i]='1';dfs(i+1,1,n);}else{dfs(i,cnt,n);}	break;}}cout<<mx;return 0;
}/*
测试数据
01?1001???101?1?0000?0110????0?001?110?0?00?01?1??答案:22 */

贪心:当前能组成一个合法子串的时候我就组合起来,因为如果我放弃这个组合,我最多让后面一个字符和它后面的字符组成一个合法子串,而浪费了我当前这个字符,组合更多的合法子串就是尽量利用每一个可以利用的字符。
再观察可得: 
 '00、11、0?、1?、?1、?0、??'都是正确的,01,10 不行 。可以组成合法子串时,这两个字符已经成对不用再看了,跳过这两个字符,不能成对,看下个字符,因为下个字符可能和他的下个字符成对,我们需要 利用每一个可以利用的字符成对 。

贪心代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;int len;
int mx=0;//最大值 signed main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);string s;cin>>s;len=s.size();for(int i=0;i<len-1;){//贪心,当前能组成一个合法子串的时候我就组合起来,因为如果我放弃这个组合//我最多让后面一个字符和它后面的字符组成一个合法子串,而浪费了我当前这个字符//组合更多的合法子串就是尽量利用每一个可以利用的字符//再观察可得: //'00、11、0?、1?、?1、?0、??'都是正确的,01,10 不行 //可以组成合法子串时,这两个字符已经成对不用再看了,跳过这两个字符,不能成对,看下个字符,因为下个字符可能和他的下个字符成对//需要 利用每一个可以利用的字符成对 if(s[i]==s[i+1]||s[i]=='?'||s[i+1]=='?') {i+=2;mx++;}else   i++;}cout<<mx;return 0;
}

 参考:蓝桥杯真题讲解:填充(贪心)-CSDN博客

的另一个版本 ,更好想更好梳理思路一些。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;int len;
int mx=0;//最大值 
bool st[N];//标记是否被匹配过 
signed main() {ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);string s;cin>>s;len=s.size();//   for(int i=0;i<len-1;){//贪心,当前能组成一个合法子串的时候我就组合起来,因为如果我放弃这个组合//我最多让后面一个字符和它后面的字符组成一个合法子串,而浪费了我当前这个字符//组合更多的合法子串就是尽量利用每一个可以利用的字符//再观察可得: //'00、11、0?、1?、?1、?0、??'都是正确的,01,10 不行 //可以组成合法子串时,这两个字符已经成对不用再看了,跳过这两个字符,不能成对,看下个字符,因为下个字符可能和他的下个字符成对//需要 利用每一个可以利用的字符成对 //	if(s[i]==s[i+1]||s[i]=='?'||s[i+1]=='?') {
//		i+=2;
//		mx++;
//	}
//   	else   i++;
//   }//另一种角度的贪心,每个字符优先跟前一个字符匹配,不能,再跟后面的字符匹配for(int i=0;i<len;i++){//因为是一个一个挪的 首先要判断 当前 字符是否已经匹配过 if(s[i]!='?'&&!st[i]){if(i-1>=0&&(s[i-1]==s[i])&&!st[i-1]){st[i]=true;st[i-1]=true;mx++;}else if(i+1<len&&(s[i+1]==s[i])){st[i]=true;st[i+1]=true;mx++;}}//?可以匹配 任意落单的字符   else{if(st[i]) continue;if(i-1>=0&&!st[i-1]){s[i]=s[i-1]; st[i]=true;st[i-1]=true;mx++;}else if(i+1<len){s[i]=s[i+1]; st[i]=true;st[i+1]=true;mx++;}}}cout<<mx;return 0;
}/*
测试数据
01?1001???101?1?0000?0110????0?001?110?0?00?01?1??答案:22 */

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/290514.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

视频无水印爬虫采集工具|抖音视频批量下载软件|可导出视频分享链接

全新视频无水印爬虫采集工具&#xff0c;助力您快速获取所需视频&#xff01; 视频无水印爬虫采集工具&#xff0c;为用户提供了强大的视频采集和下载功能。它可以批量提取关键词相关的视频&#xff0c;同时支持单独视频的提取和下载&#xff0c;操作简便&#xff0c;使用方便。…

CSS及javascript

一、CSS简介 css是一门语言&#xff0c;用于控制网页的表现。 cascading style sheet:层叠样式表 二、css的导入方式 css代码与html代码的结合方式 &#xff08;1&#xff09;css导入html有三种方式&#xff1a; 1.内联样式&#xff1a;<div style"color:red&quo…

深度学习每周学习总结P3(天气识别)

&#x1f368; 本文为&#x1f517;365天深度学习训练营 中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 | 接辅导、项目定制 数据链接 提取码&#xff1a;o3ix 目录 0. 总结1. 数据导入部分数据导入部分代码详解&#xff1a;a. 数据读取部分a.1 提问&#xff1a;关…

智慧工厂视频汇聚与安全风险智能识别预警方案设计与功能

在智慧工厂的建设中&#xff0c;智能视频监控方案扮演着至关重要的角色。它不仅能够实现全方位、无死角的监控&#xff0c;还能够通过人工智能技术&#xff0c;实现智能识别、预警和分析&#xff0c;为工厂的安全生产和高效运营提供有力保障。 TSINGSEE青犀智慧工厂智能视频监…

网络爬虫框架Scrapy的入门使用

Scrapy的入门使用 Scrapy概述引擎&#xff08;Engine&#xff09;调度器&#xff08;Scheduler&#xff09;下载器&#xff08;Downloader&#xff09;SpiderItem Pipeline 基本使用安装scrapy创建项目定义Item数据模型对象创建爬虫(Spider)管道pipeline来保存数据启动爬虫 其他…

霸榜京东数据库图书热卖榜!《图数据库:理论与实践》热销中

《图数据库&#xff1a;理论与实践》自2月上市以来&#xff0c;受到了数据库行业的广泛关注与热烈支持&#xff0c;问世两周便销量破千本&#xff01;近期还荣登京东 “数据库图书榜”热卖榜第二名&#xff0c;广获好评&#xff01; 在此&#xff0c;真挚的感谢各位读者的认可…

实现定时任务

定时任务的实现方式有很多&#xff0c;比如XXL-Job等。但是其实核心功能和概念都是类似的&#xff0c;很多情况下只是调用的API不同而已。 这里就先用SpringBoot为我们提供的定时任务的API来实现一个简单的定时任务&#xff0c;让大家先对定时任务里面的一些核心概念有个大致的…

基于微信小程序的民宿短租系统设计与实现(论文+源码)_kaic

摘 要 随着社会的发展&#xff0c;出差、旅游成为常态&#xff0c;也就造成民宿短租市场的兴起。人们新到陌生的环境里找民宿一般都是通过中介。中介虽然可以快速找到合适的民宿但会收取大量的中介费用&#xff0c;这对刚到新环境里的人们来说是一笔大的资金支出。也有一些人通…

elasticsearch 8.12+kibana 8.12

准备工作&#xff1a;1.下载相关的安装包放到/usr/local/ES下面 elasticsearch下载地址:Download Elasticsearch | Elastic elasticsearch-head-master下载地址:https://github.com/mobz/elasticsearch-head/archive/master.zip node下载地址:Index of /dist/ kibana地址:Downl…

网络服务练习题

综合练习&#xff1a;请给 openlab 搭建 web 网站 网站需求&#xff1a; 1. 基于域名 www.openlab.com 可以访问网站内容为 welcome to openlab!!! 2. 给该公司创建三个子界面分别显示学生信息&#xff0c;教学资料 和缴费网站&#xff0c;基于&#xff0c; www.openlab.c…

正弦实时数据库(SinRTDB)的使用(5)-历史数据查询

前文已经将正弦实时数据库的使用进行了介绍&#xff0c;需要了解的可以先看下面的博客&#xff1a; 正弦实时数据库(SinRTDB)的安装 正弦实时数据库(SinRTDB)的使用(1)-使用数据发生器写入数据 正弦实时数据库(SinRTDB)的使用(2)-接入OPC DA的数据 正弦实时数据库(SinRTDB)…

微服务概述

微服务 概述1.单体架构2.分布式架构3.微服务的架构特征&#xff1a; 服务拆分和远程调用提供者与消费者 概述 1.单体架构 单体架构&#xff1a;将业务的所有功能集中在一个项目中开发&#xff0c;打成一个包部署。 单体架构的优缺点如下&#xff1a; 优点&#xff1a; 架构…

Vue-vue3

一、Vue3简介二、Vue3有那些优化性能的提升源码升级拥抱TypeScript新的特性 三、创建Vue3.0工程四、Vue3工程结构&#xff08;使用cli创建的vue3&#xff09;五、常用的Composition API&#xff08;组合式API&#xff09;setupsetup的两个注意点 ref函数reactive函数Vue3.0中的…

微服务(基础篇-004-Feign)

目录 http客户端Feign Feign替代RestTemplate&#xff08;1&#xff09; Feign的介绍&#xff08;1.1&#xff09; 使用Feign的步骤&#xff08;1.2&#xff09; 自定义配置&#xff08;2&#xff09; 配置Feign日志的两种方式&#xff08;2.1&#xff09; Feign使用优化…

架构整洁之道-读书总结

1 概述 1.1 关于本书 《架构整洁之道》&#xff08;Clean Architecture: A Craftsman’s Guide to Software Structure and Design&#xff09;是由著名的软件工程师Robert C. Martin&#xff08;又称为Uncle Bob&#xff09;所著。这本书提供了软件开发和架构设计的指导原则…

基于unbantu的nginx的配置

目录 前言: 1.安装nginx并进行测试 1.1使用nginx -v 命令查看版本 1.2开启服务 查看端口 1.3测试 2.nginx的静态资源访问配置 2.1创建静态资源存放的目录 2.2写入目录中测试文件对应的内容 2.3修改配置文件 2.4 测试 3.虚拟主机配置 3.1创建目录 3.2写入测试…

JoyPac:产品立项的5个思考及成功产品分析 | TopOn变现干货

5月26日&#xff0c;TopOn、罗斯基、广大大共同主办的《游戏赛道新机会》主题沙龙长沙站举办。活动邀请到多家头部平台和知名厂商的负责人&#xff0c;大家分别从自身的业务角度出发&#xff0c;分享了最新的行业变化和市场趋势。 在活动上&#xff0c;JoyPac产品VP王泽带来了…

HTML input 实现回车切换到下一个输入框功能

前言 遇到需求&#xff0c;在客户填写单子时&#xff0c;有多个输入框&#xff0c;为了省事&#xff0c;不需要频繁移动光标填写。 实现效果 实现方式一 HTML <input type"text" name"serialNumber1" onkeydown"cursor(this);"/><in…

DDos系列攻击原理与防御原理

七层防御体系 静态过滤 命中黑名单 对确定是攻击的流量直接加入黑名单&#xff08;源地址命中黑名单直接丢弃&#xff0c;缺乏机动性和扩展性&#xff09; 畸形报文过滤 畸形报文攻击 TCP包含多个标记位&#xff0c;排列组合有规律 • 现象&#xff1a;TCP标记位全为1 …

2015年认证杯SPSSPRO杯数学建模A题(第二阶段)绳结全过程文档及程序

2015年认证杯SPSSPRO杯数学建模 A题 绳结 原题再现&#xff1a; 给绳索打结是人们在日常生活中常用的技能。对登山、航海、垂钓、野外生存等专门用途&#xff0c;结绳更是必不可少的技能之一。针对不同用途&#xff0c;有多种绳结的编制方法。最简单的绳结&#xff0c;有时称…