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

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,… 的生成规律如下&#xff1a; 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&#xff0c;其…...

Milvus 介绍

Milvus 介绍 Milvus 矢量数据库是什么&#xff1f;关键概念非结构化数据嵌入向量向量相似度搜索 为什么是 Milvus?支持哪些索引和指标&#xff1f;索引类型相似度指标(Similarity metrics) 应用示例Milvus 是如何设计的&#xff1f;开发者工具API访问Milvus 生态系统工具 本页…...

Linux绝对路径和相对路径

在 Linux 中&#xff0c;简单的理解一个文件的路径&#xff0c;指的就是该文件存放的位置。 只要我们告诉 Linux 系统某个文件存放的准确位置&#xff0c;那么它就可以找到这个文件。指明一个文件存放的位置&#xff0c;有 2 种方法&#xff0c;分别是使用绝对路径和相对路径。…...

Linux:firewalld防火墙-基础使用(2)

上一章 Linux&#xff1a;firewalld防火墙-介绍&#xff08;1&#xff09;-CSDN博客https://blog.csdn.net/w14768855/article/details/133960695?spm1001.2014.3001.5501 我使用的系统为centos7 firewalld启动停止等操作 systemctl start firewalld 开启防火墙 systemct…...

【每日一练】20231023

统计每个字符出现的次数相关问题 方法一&#xff1a;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 逻辑处理 关键字&#xff1a; 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 数据库基础概念,基本简单操作及数据类型介绍

文章目录 数据库基础为什么需要数据库&#xff1f;创建数据库mysql架构SQL语句分类编码集修改数据库属性数据库备份 表的基本操作存在时更新&#xff0c;不存在时插入 数据类型日期类型enum和set 数据库基础 以特定的格式保存文件&#xff0c;叫做数据库&#xff0c;这是狭义上…...

异步加载 JavaScript

目录 ​编辑 前言&#xff1a;异步加载 JavaScript 的重要性 详解&#xff1a;异步加载 JavaScript 的方法 使用 使用动态创建标签&#xff1a; 使用模块引入&#xff08;ES6模块&#xff09;&#xff1a; 解析&#xff1a;异步加载 JavaScript 的重要性和优势 实践和注…...

汽车屏类产品(四):仪表Cluster

###前言 仪表Cluster/仪表盘Dashboard,作为伴随汽车诞生就存在的一个主要零部件之一,从机械到电子到数字,可以说也是逐渐发展到现在的。 目前的主流框图如下,中间processor就是主控芯片,可能有buttons/switches,有display显示屏+backlight背光,有audio->speake…...

【GA-ELM】基于遗传算法优化极限学习机回归预测研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

DFT和ATE岗位前景薪资对比,手把手教你如何选择岗位?

ATE测试和DFT可测性设计&#xff0c;虽然二者都对芯片测试至关重要&#xff0c;但是两个岗位的区别还是很大的。 两个岗位应该如何做选择&#xff1f; 先讲产业环节 我们知道芯片设计、芯片制造、芯片封测每个环节都是大工程&#xff0c;且每个环节都关键且重要。测试是芯片诞…...

驱动day4作业

通过字符设备驱动的分步实现编写LED驱动&#xff0c;另外实现特备文件和设备的绑定 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 存储过程

环境说明 系统环境 系统&#xff1a;Windows XP IDE&#xff1a; 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配置正确&#xff0c;直接看6&#xff0c;pull的位置是你执行pull的目录下。 --------------------------------------------------------------------------------------------------------------------------------- 使用adb命令获取当前应用的元素需要先连接到手机或模…...

SpringSecurity源码学习四:会话管理

目录 1. 什么是会话管理2. springSecurity中的session管理怎么做的3. springSecurity源码中的session管理4. 代码示例5. 源码5.1 不同策略的含义 6. 集群模式session管理7. 总结 1. 什么是会话管理 会话管理是指在Java应用程序中管理用户会话状态的过程。在Spring框架中&#…...

Kotlin笔记(七):协程

1. 协程的定义 协程属于Kotlin中非常有特色的一项技术&#xff0c;因为大部分编程语言中是没有协程这个概念的。 什么是协程呢&#xff1f;它其实和线程是有点类似的&#xff0c;可以简单地将它理解成一种轻量级的线程。要知道&#xff0c;线程是非常重量级的&#xff0c;它需要…...

存储优化知识复习二详细版解析

存储优化 知识复习二 一、 选择题 1、 对数据库调优的方法中&#xff0c;最困难但是最有成效的是( )。 A、优化表的架构设计 B、添加内存 C、索引优化 D、查询语句优化 【参考答案】A2、 防止与处理死锁的方法有&#xff08; &#xff09;。 A、尽量避免或尽快处理阻塞 B、访…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

(一)单例模式

一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...

MySQL的pymysql操作

本章是MySQL的最后一章&#xff0c;MySQL到此完结&#xff0c;下一站Hadoop&#xff01;&#xff01;&#xff01; 这章很简单&#xff0c;完整代码在最后&#xff0c;详细讲解之前python课程里面也有&#xff0c;感兴趣的可以往前找一下 一、查询操作 我们需要打开pycharm …...