acwing第 126 场周赛 (扩展字符串)
5281. 扩展字符串
一、题目要求
某字符串序列 s0,s1,s2,… 的生成规律如下:
- s0=
DKER EPH VOS GOLNJ ER RKH HNG OI RKH UOPMGB CPH VOS FSQVB DLMM VOS QETH SQB - sn=
DKER EPH VOS GOLNJ UKLMH QHNGLNJ A+sn−1+AB CPH VOS FSQVB DLMM VOS QHNG A+sn−1+AB,其中 n≥1
你需要回答 q个询问,其中第 i 个询问给定两个整数 n,k,并请你输出字符串 sn 中的第 k 个字符(字符串中的字符索引编号从 1 开始),如果 sn 的长度小于 k,则输出 ‘.’。
输入格式
第一行包含整数 q。
接下来 q行,每行包含两个整数 n,k,表示一个询问。
输出格式
共一行,一个长度为 q 的字符串,其中第 i 个字符表示第 i 个询问的答案。
保证答案的首尾字符不是空格。
数据范围
前 3 个测试点满足 0≤n≤5。
所有测试点满足 1≤q≤10,0≤n≤10^5,1≤k≤10^18。
输入样例1:
3
1 1
1 2
1 1000000000000000000
输出样例1:
DK.
输入样例2:
5
0 69
1 194
1 139
0 47
1 66
输出样例2:
EFGHI
二、思路
1.预处理字符串的长度 f[i] ,代表第i个字符串的长度
2. 通过递归找到第i个字符串长度的第k个位置的字符是多少
3.推导递归的规律


三、代码
#include<bits/stdc++.h>
#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
const int N=1e5+10;
const int inf=0x3f3f3f3f;
int n,k=0;
int f[N];
string s="#DKER EPH VOS GOLNJ UKLMH QHNGLNJ A";//长度34
string ss="#AB CPH VOS FSQVB DLMM VOS QHNG A";//长度32
string t="#AB";//长度2
string s0="#DKER EPH VOS GOLNJ ER RKH HNG OI RKH UOPMGB CPH VOS FSQVB DLMM VOS QETH SQB";
//s0长度75
struct node
{int f,x;
} q[N];
void init()//预处理字符串的长度
{int i;f[0]=75;for(i=1;;i++){f[i]=f[i-1]*2+68;//s+ss+s0=34+32+2=68; if(f[i]>1e18)break;}for(i++;i<=1e5;i++)//当n还未达到1e5的时候,若对应的字符串长度达到了1e18 {f[i]=f[i-1];//让之后的字符串长度就等于接近1e18那时候的最大长度 }
}
char dfs(int n,int k)
{if(n==0)return s0[k];else if(k<=34)return s[k];else if(k<=34+f[n-1])return dfs(n-1,k-34);else if(k<=34+f[n-1]+32)return ss[k-34-f[n-1]];else if(k<=34+32+f[n-1]*2)return dfs(n-1,k-34-32-f[n-1]);elsereturn t[k-32-34-f[n-1]*2];}
void solve()
{init();cin>>n;
// cout<<"s0="<<s0.size()<<' '<<"s="<<s.size()<<' '<<"ss="<<ss.size()<<' '<<"t="<<t.size()<<endl;int i,j;for(i=1; i<=n; i++){cin>>q[i].f>>q[i].x;}for(i=1;i<=n;i++){if(q[i].x>f[q[i].f])cout<<'.';elsecout<<dfs(q[i].f,q[i].x);}cout<<endl;
}
signed main()
{int t=1;while(t--){solve();}return 0;
}
相关文章:
acwing第 126 场周赛 (扩展字符串)
5281. 扩展字符串 一、题目要求 某字符串序列 s0,s1,s2,… 的生成规律如下: s0 DKER EPH VOS GOLNJ ER RKH HNG OI RKH UOPMGB CPH VOS FSQVB DLMM VOS QETH SQBsnDKER EPH VOS GOLNJ UKLMH QHNGLNJ Asn−1AB CPH VOS FSQVB DLMM VOS QHNG Asn−1AB,其…...
Milvus 介绍
Milvus 介绍 Milvus 矢量数据库是什么?关键概念非结构化数据嵌入向量向量相似度搜索 为什么是 Milvus?支持哪些索引和指标?索引类型相似度指标(Similarity metrics) 应用示例Milvus 是如何设计的?开发者工具API访问Milvus 生态系统工具 本页…...
Linux绝对路径和相对路径
在 Linux 中,简单的理解一个文件的路径,指的就是该文件存放的位置。 只要我们告诉 Linux 系统某个文件存放的准确位置,那么它就可以找到这个文件。指明一个文件存放的位置,有 2 种方法,分别是使用绝对路径和相对路径。…...
Linux:firewalld防火墙-基础使用(2)
上一章 Linux:firewalld防火墙-介绍(1)-CSDN博客https://blog.csdn.net/w14768855/article/details/133960695?spm1001.2014.3001.5501 我使用的系统为centos7 firewalld启动停止等操作 systemctl start firewalld 开启防火墙 systemct…...
【每日一练】20231023
统计每个字符出现的次数相关问题 方法一:map的put方法遍历 public class Test {public static void main(String[] args) {StringBuilder sb new StringBuilder("");Random ran new Random();for(int i0;i<2000000;i) {sb.append((char) (a ran.n…...
【项目经理】工作流引擎
项目经理之 工作流引擎 一、业务系统管理目的维护信息 二、组织架构管理目的维护信息 三、角色矩阵管理目的维护信息 四、条件变量管理目的维护信息 五、流程模型管理目的维护信息 六、流程版本管理目的维护信息 七、流程监管控制目的维护信息 系列文章版本记录 一、业务系统管…...
025-第三代软件开发-实现需求长时间未操作返回登录界面
第三代软件开发-实现需求长时间未操作返回登录界面 文章目录 第三代软件开发-实现需求长时间未操作返回登录界面项目介绍实现需求长时间未操作返回登录界面实现思路用户操作监控QML 逻辑处理 关键字: Qt、 Qml、 QTimer、 timeout、 eventFilter 项目介绍 欢迎…...
驱动开发LED灯绑定设备文件
头文件 #ifndef __HEAD_H__ #define __HEAD_H__typedef struct {unsigned int MODER;unsigned int OTYPER;unsigned int OSPEEDR;unsigned int PUPDR;unsigned int IDR;unsigned int ODR; }gpio_t;#define PHY_LED1_ADDR 0x50006000 #define PHY_LED2_ADDR 0x50007000 #defin…...
MySql 数据库基础概念,基本简单操作及数据类型介绍
文章目录 数据库基础为什么需要数据库?创建数据库mysql架构SQL语句分类编码集修改数据库属性数据库备份 表的基本操作存在时更新,不存在时插入 数据类型日期类型enum和set 数据库基础 以特定的格式保存文件,叫做数据库,这是狭义上…...
异步加载 JavaScript
目录 编辑 前言:异步加载 JavaScript 的重要性 详解:异步加载 JavaScript 的方法 使用 使用动态创建标签: 使用模块引入(ES6模块): 解析:异步加载 JavaScript 的重要性和优势 实践和注…...
汽车屏类产品(四):仪表Cluster
###前言 仪表Cluster/仪表盘Dashboard,作为伴随汽车诞生就存在的一个主要零部件之一,从机械到电子到数字,可以说也是逐渐发展到现在的。 目前的主流框图如下,中间processor就是主控芯片,可能有buttons/switches,有display显示屏+backlight背光,有audio->speake…...
【GA-ELM】基于遗传算法优化极限学习机回归预测研究(Matlab代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
DFT和ATE岗位前景薪资对比,手把手教你如何选择岗位?
ATE测试和DFT可测性设计,虽然二者都对芯片测试至关重要,但是两个岗位的区别还是很大的。 两个岗位应该如何做选择? 先讲产业环节 我们知道芯片设计、芯片制造、芯片封测每个环节都是大工程,且每个环节都关键且重要。测试是芯片诞…...
驱动day4作业
通过字符设备驱动的分步实现编写LED驱动,另外实现特备文件和设备的绑定 head.h #ifndef __HEAD_H__ #define __HEAD_H__ typedef struct{unsigned int MODER;unsigned int OTYPER;unsigned int OSPEEDR;unsigned int PUPDR;unsigned int IDR;unsigned int ODR; }…...
【Oracle】VC6.0使用 odbc 访问 Oracle 存储过程
环境说明 系统环境 系统:Windows XP IDE: Microsoft Visual C 6.0 使用的对象 msado15.tlh _ConnectionPtr m_pConnection; HRESULT hr m_pConnection.CreateInstance(“ADODB.Connection”); _RecordsetPtr m_pRecordset; m_pRecordset.CreateInstan…...
QWidget快速美化-圆形蓝色单选框
将代码复制进QRadioButton的样式表 效果: 代码: QRadioButton{font:75 9pt "Arial";background:transparent;color:white;border:none; }QRadioButton:disabled{color:gray; }QRadioButton::indicator{width:12px;height:12px;border-radius:8px; }QRadioButton::i…...
adb 获取当前界面元素
adb配置正确,直接看6,pull的位置是你执行pull的目录下。 --------------------------------------------------------------------------------------------------------------------------------- 使用adb命令获取当前应用的元素需要先连接到手机或模…...
SpringSecurity源码学习四:会话管理
目录 1. 什么是会话管理2. springSecurity中的session管理怎么做的3. springSecurity源码中的session管理4. 代码示例5. 源码5.1 不同策略的含义 6. 集群模式session管理7. 总结 1. 什么是会话管理 会话管理是指在Java应用程序中管理用户会话状态的过程。在Spring框架中&#…...
Kotlin笔记(七):协程
1. 协程的定义 协程属于Kotlin中非常有特色的一项技术,因为大部分编程语言中是没有协程这个概念的。 什么是协程呢?它其实和线程是有点类似的,可以简单地将它理解成一种轻量级的线程。要知道,线程是非常重量级的,它需要…...
存储优化知识复习二详细版解析
存储优化 知识复习二 一、 选择题 1、 对数据库调优的方法中,最困难但是最有成效的是( )。 A、优化表的架构设计 B、添加内存 C、索引优化 D、查询语句优化 【参考答案】A2、 防止与处理死锁的方法有( )。 A、尽量避免或尽快处理阻塞 B、访…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:
一、属性动画概述NETX 作用:实现组件通用属性的渐变过渡效果,提升用户体验。支持属性:width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项: 布局类属性(如宽高)变化时&#…...
OkHttp 中实现断点续传 demo
在 OkHttp 中实现断点续传主要通过以下步骤完成,核心是利用 HTTP 协议的 Range 请求头指定下载范围: 实现原理 Range 请求头:向服务器请求文件的特定字节范围(如 Range: bytes1024-) 本地文件记录:保存已…...
在Ubuntu中设置开机自动运行(sudo)指令的指南
在Ubuntu系统中,有时需要在系统启动时自动执行某些命令,特别是需要 sudo权限的指令。为了实现这一功能,可以使用多种方法,包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法,并提供…...
Neo4j 集群管理:原理、技术与最佳实践深度解析
Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...
12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
CMake 从 GitHub 下载第三方库并使用
有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...
Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...
USB Over IP专用硬件的5个特点
USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中,从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备(如专用硬件设备),从而消除了直接物理连接的需要。USB over IP的…...
SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)
上一章用到了V2 的概念,其实 Fiori当中还有 V4,咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务),代理中间件(ui5-middleware-simpleproxy)-CSDN博客…...
