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

题解:CF1937B(Binary Path)

题解:CF1937B(Binary Path)

一、 理解题意

1. 题目链接

CodeForces;
洛谷。

2. 题目翻译

给定一个 由 0 0 0 1 1 1 组成的 2 2 2 n n n 列的网格上寻找一条路径,使得这条路径上所有的数串联起来形成的01串的字典序是所有路径里面最小的,并找出有多少种不同的做法能够取出相同的01串。

3. 数据范围

多测, t t t 组数据, 1 ≤ t ≤ 1 0 4 1\leq t\leq 10^4 1t104;
1 ≤ ∑ n ≤ 2 ⋅ 1 0 5 1\leq \sum n\leq 2\cdot 10^5 1n2105

二、 设计算法

1. 观察数据范围

本题可以接受 O ( n ) O(n) O(n) 的线性做法。

2. 设计合理算法

这道题为什么只有 2 2 2 行,而不是给定的 m m m 行?
我们思考二者的区别,显然,对于前者,我们总共只会向下走一次。
进一步想。如果现在我们不在最下面一行或者最右面一列(也就是说我们可以向右或者向下走),假设这一步我们往右走,下一步我们可以继续向右(走到右侧的右侧)或者向下(走到右下侧),而假设我们这一步往下走,下一步我们只能向右走(走到右下侧)。显然,向右走的情况包括了向下走的情况。
因此,我们考虑贪心的走每一步,假设我们现在位于 ( x , y ) (x,y) (x,y)
①当 x = 2 x=2 x=2 时,往右走;
②当 y = n y=n y=n 时,往下走;
③当 a x + 1 , y ≥ a x , y + 1 a_{x+1,y}\geq a_{x,y+1} ax+1,yax,y+1 时,往右走;
④当 a x + 1 , y < a x , y + 1 a_{x+1,y}<a_{x,y+1} ax+1,y<ax,y+1时,往下走。
我们要记录唯一一次往下走是在哪一列(这里记为 i d z idz idz),后面会用到。
现在我们已经知道最终的路径,但是如何求出一共有几种不同的情况呢?
显然,在第 i d z idz idz 列及它之前,如果有一段连续的区间使得区间内对于区间内所有的 x x x a 1 , x a_{1,x} a1,x a 2 , x − 1 a_{2,x-1} a2,x1 都相等,那么在这一段区间内,选择哪个 x − 1 x-1 x1 作为最终的那次往下走的步骤都是可以的。当然,这段连续区间的右端点必然是 i d z idz idz。答案就是区间长度加上 1 1 1,加的就是我们贪心贪出来的那种情况。

3. 计算时间代价

妥妥的 O ( n ) O(n) O(n),妥妥的 A C AC AC

三、 实现代码

#include<bits/stdc++.h>
#define N 220000
using namespace std;
int t,n;
int sum[N];
char a[3][N];
int main(){scanf("%d",&t);while(t--){scanf("%d",&n);for(int i=1;i<=n;i++){sum[i]=0;}for(int i=1;i<=2;i++){scanf("%s",a[i]+1);}int idx=1,idy=1,idz=0;printf("%c",a[idx][idy]);while(idx!=2||idy!=n){if(idx==2){idy++;}else{if(idy==n){idx++;idz=idy;}else{if(a[idx][idy+1]==a[idx+1][idy]){idy++;}else{if(a[idx][idy+1]<a[idx+1][idy]){idy++;}else{idx++;idz=idy;}}}}printf("%c",a[idx][idy]);}printf("\n");int ans=1;for(int i=idz;i>1;i--){if(a[1][i]==a[2][i-1]){ans++;}else{break;}}printf("%d\n",ans);}return 0;
}

相关文章:

题解:CF1937B(Binary Path)

题解&#xff1a;CF1937B&#xff08;Binary Path&#xff09; 一、 理解题意 1. 题目链接 CodeForces&#xff1b; 洛谷。 2. 题目翻译 给定一个 由 0 0 0 和 1 1 1 组成的 2 2 2 行 n n n 列的网格上寻找一条路径&#xff0c;使得这条路径上所有的数串联起来形成的0…...

JS——9大陷阱

一、警惕A>X>B写法 3>2>1 返回值为false&#xff08;原因&#xff1a;3>2为true&#xff0c;会默认转成数字1&#xff0c;1>1为false&#xff09; 1<4<3 返回值为true&#xff08;原因&#xff1a;1<4为true&#xff0c;会默认转成数字1&#xff…...

USB - 通过configfs配置Linux USB Gadget

Linux USB gadget configured through configfs Overview USB Linux 小工具是一种具有 UDC&#xff08;USB 设备控制器&#xff09;的设备&#xff0c;可连接到 USB 主机&#xff0c;以扩展其附加功能&#xff0c;如串行端口或大容量存储功能。 A USB Linux Gadget is a device…...

迷宫与陷阱(蓝桥杯)

文章目录 迷宫与陷阱问题描述bfs解题思路代码 迷宫与陷阱 问题描述 小明在玩一款迷宫游戏&#xff0c;在游戏中他要控制自己的角色离开一间由 N x N 个格子组成的2D迷宫。 小明的起始位置在左上角&#xff0c;他需要到达右下角的格子才能离开迷宫&#xff0c;每一步&#xf…...

Temple of Doom靶场nodejs获取shellss-manager漏洞tcpdump提权

下载链接&#xff1a; Temple of Doom: 1 ~ VulnHub 下载完成后直接在vxbox中导入即可&#xff0c;网络链接模式根据自身情况而定&#xff08;我采用的桥接模式&#xff09; 正文&#xff1a; 先用nmap进行扫描靶机ip nmap -sn 192.168.1.1/24 对192.168.1.5进行端口探测&a…...

day03_mysql_课后练习 - 参考答案

文章目录 day03_mysql_课后练习mysql练习题第1题第2题第3题第4题第5题 day03_mysql_课后练习 mysql练习题 第1题 案例&#xff1a; 1、创建一个数据库&#xff1a;day03_test01_school 2、创建如下表格 表1 Department表的定义 字段名字段描述数据类型主键外键非空唯一D…...

creator-webview与Android交互

title: creator-webview与Android交互 categories: Cocos2dx tags: [cocos2dx, creator, webview, 交互] date: 2024-03-23 13:17:20 comments: false mathjax: true toc: true creator-webview与Android交互 前篇 Android&#xff1a;你要的WebView与 JS 交互方式 都在这里了…...

22.WEB渗透测试-BurpSuite(一)

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 内容参考于&#xff1a; 易锦网校会员专享课 上一个内容&#xff1a;21.WEB渗透测试-HTTP协议&#xff08;下&#xff09;-CSDN博客 工具的使用需要先搭建靶场…...

前端性能优化:防抖与节流

一、防抖和节流主要是干什么的 防抖和节流主要用于控制函数执行的频率&#xff0c;通过限制函数的触发次数&#xff0c;避免函数被过度调用而引发的性能问题或产生不必要的副作用。 二、防抖 防抖是什么: 1、对于在事件被触发 n 秒后再执行的回调 --> 延迟执行 2、如果…...

Copilot 编程助手的介绍及使用

介绍 Copilot 是2021年由 GitHub 与 OpenAI 合作研发的一款编程助手&#xff0c;同时也是全球首款使用OpenAI Codex模型&#xff08;GPT-3后代&#xff09;打造的大规模生成式AI开发工具。 Copilot 底层模型目前经过了数十亿行公开代码的训练&#xff0c;与大多数代码辅助工具…...

数据库专题(oracle基础和进阶)

前言 本专题主要记录自己最近学的数据库&#xff0c;有兴趣一起补习的可以一起看看&#xff0c;有补充和不足之处请多多指出。希望专题可以给自己还有读者带去一点点提高。 数据库基本概念 本模块有参考&#xff1a;数据库基本概念-CSDN博客 数据库管理系统是一个由互相关联的…...

web蓝桥杯2022省赛真题:水果拼盘

代码及注释&#xff1a; /* TODO&#xff1a;待补充代码 */ #pond {display: flex; //flex布局flex-direction: column; //主轴方向从上到下flex-wrap: wrap; //子元素换行 } 知识点&#xff1a; flex弹性布局 父元素&#xff1a;diasplay: flex; flex-d…...

Web核心

目录 Web核心HTTP概念&#xff1a;协议特点&#xff1a;请求数据格式响应数据格式 Tomcat简介基本使用配置部署项目IDEA中创建 Maven Web 项目 IDEA使用Tomcat Servlet简介快速入门执行流程生命周期体系结构Servlet urlPattern配置一个Servlet&#xff0c;可以配置多个 urlPatt…...

iOS应用审核问题解决方案及优化方法 ✨

摘要 本文将针对iOS应用提交审核时可能遇到的问题&#xff0c;如“你必须在Xcode中添加com.apple.developer.game-center密钥”&#xff0c;以及突然间提交送审报错情况进行探讨。通过大量查询资料和尝试&#xff0c;结合案例分析&#xff0c;提供了解决方案和优化方法&#xf…...

java post、get请求第三方https接口

java post、get请求第三方https接口 前段时间做项目新加功能由于要对接其它系统&#xff0c;请求系统接口传输数据。写完后发现我写的这个方法和网上现有的例子有点不太一样&#xff0c;可能是因为我做的项目是政务网的原因&#xff0c;但我想正常的即便是互联网的系统请求方式…...

【C语言】鸡兔同笼,鸡和兔共 100 只,共 284 只脚,求鸡和兔的个数。

鸡兔同笼&#xff0c;鸡和兔共 100 只&#xff0c;共 284 只脚&#xff0c;求鸡和兔的个数。 int main() {for (int i 0; ; i){if (2 * i 4 * (100 - i) 284){printf("鸡的数量&#xff1a;%d,兔子的数量&#xff1a;%d", i, 100 - i);break;} } }这里直接算出题…...

沪漂8年回郑州三年如何走上创业之路

大家好&#xff0c;我是大牛&#xff0c;目前人在郑州。 现在标签是&#xff1a; 创业者&#x1f697;&#x1f438; (注册有自己的公司&#xff0c;主要是为了自己的产品和接外包项目)独立开发者&#x1f468;&#x1f3fb;&#x1f4bb; (有自己的小项目)数字游民&…...

MySQL数据库—事务与存储类型

一、事务&#xff1a; 1.事务的概念&#xff1a; 事务是一种机制、一个操作序列&#xff0c;包含了一组数据库操作命令&#xff0c;并且把所有的命令作为一个整体一起向系统提交或撤销操作请求&#xff0c;即这组数据库命令要么都执行&#xff0c;要么都不执行。事务是一个不…...

蓝桥杯刷题8

1. 世纪末的星期 import java.util.Calendar; public class Main {public static void main(String[] args) {Calendar calendar Calendar.getInstance();for(int year 1999;year<100000;year100){calendar.set(Calendar.YEAR,year);calendar.set(Calendar.MONTH,11);cale…...

Java中的String字符串练习

目录 Java中的String字符串练习 01-用户登录 02-遍历字符串并统计字符个数 03-字符串拼接 04-字符串反转 注意点 05-金额转化(简单) 代码解释: 06-手机号屏蔽 07-身份证号码查看 易错点: 08-敏感词替换 01-用户登录 package com.xiaonan.exercise06;import java.u…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

day52 ResNet18 CBAM

在深度学习的旅程中&#xff0c;我们不断探索如何提升模型的性能。今天&#xff0c;我将分享我在 ResNet18 模型中插入 CBAM&#xff08;Convolutional Block Attention Module&#xff09;模块&#xff0c;并采用分阶段微调策略的实践过程。通过这个过程&#xff0c;我不仅提升…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

HDFS分布式存储 zookeeper

hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架&#xff0c;允许使用简单的变成模型跨计算机对大型集群进行分布式处理&#xff08;1.海量的数据存储 2.海量数据的计算&#xff09;Hadoop核心组件 hdfs&#xff08;分布式文件存储系统&#xff09;&a…...

NXP S32K146 T-Box 携手 SD NAND(贴片式TF卡):驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

2025年渗透测试面试题总结-腾讯[实习]科恩实验室-安全工程师(题目+回答)

安全领域各种资源&#xff0c;学习文档&#xff0c;以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具&#xff0c;欢迎关注。 目录 腾讯[实习]科恩实验室-安全工程师 一、网络与协议 1. TCP三次握手 2. SYN扫描原理 3. HTTPS证书机制 二…...

腾讯云V3签名

想要接入腾讯云的Api&#xff0c;必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口&#xff0c;但总是卡在签名这一步&#xff0c;最后放弃选择SDK&#xff0c;这次终于自己代码实现。 可能腾讯云翻新了接口文档&#xff0c;现在阅读起来&#xff0c;清晰了很多&…...

群晖NAS如何在虚拟机创建飞牛NAS

套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...