牛客巅峰赛S2第6场题解

2023-05-16

牛客编程巅峰赛S2第6场

A-StringⅡ

题目

题目描述

给出一个仅包含小写字母的字符串s,你最多可以操作k次,使得任意一个小写字母变为与其相邻的小写字母(ASCII码差值的绝对值为1),请你求出可能的最长相等子序列(即求这个字符串修改至多k次后的的一个最长子序列,且需要保证这个子序列中每个字母相等)。

子序列:从原字符串中取任意多个字母按照先后顺序构成的新的字符串。

示例1

输入

2,"abcde"

返回值

3

示例2

输入

10,"acesxd"

返回值

4

备注:

数据满足: 1 ≤ ∣ s ∣ ≤ 2 10 , 1 ≤ k ≤ 3000 1\leq |s|\leq 2^{10}, 1\leq k \leq3000 1s210,1k3000,其中 ∣ s ∣ |s| s表示字符串的长度。

思路

找到所有字符串中所有字符到每个字母的距离,排序。

找每个字母所能得到的最大长度。

代码

class Solution {
public:
    /**
     * 
     * @param k int整型 表示最多的操作次数
     * @param s string字符串 表示一个仅包含小写字母的字符串
     * @return int整型
     */
    int string2(int k, string s) {
        // write code here
        sort(s.begin(), s.end());
        int n = s.size();
        vector<vector<int> > dist(26);
        for(int i = 0; i < 26; i++){
            for(int j = 0; j < n; j++){
                dist[i].push_back(abs(i+'a'-s[j]));
            }
        }
        for(int i = 0; i < 26; i++) sort(dist[i].begin(), dist[i].end());
        int ans = 1;
        for(int i = 0; i < 26; i++){
            int sums = 0, p = 0;
            while(p < n){
                sums += dist[i][p++];
                if(sums > k) break;
                ans = max(ans, p);
            }
            //cout << sums << " " << p << endl;
            //if(p == n) return n;
        }
        
        return ans;
    }
};

B-Bang Bang

题目

题目描述

音游狂热爱好者牛牛接到了一个新的任务,那就是给一张乐谱设计重音符。每当玩家敲击重音符的时候就会发出"bang"的美妙声音!!

每一张乐谱都有 n n n个音符从左到右一字排开,现在牛牛的任务就是选出其中 m m m个音符将其标记为重音符,同时任意两个重音符之间都必须隔着至少 k k kk个音符。

一个有意思的问题诞生了,请求出这样合法的设计方案种数,并输出答案对 1000000007 1000000007 1000000007取模的结果。

示例1

输入

3,2,1

返回值

1

备注:

数据范围 3 ≤ n ≤ 1000 , m ( 0 ≤ m ≤ n ) , k ( 0 ≤ k ≤ n ) 3≤n≤1000,m(0≤m≤n),k(0≤k≤n) 3n1000m(0mn)k(0kn)

思路

动态规划

一个位置只有两种可能:放重音符和不放重音符。

那么用 d p [ i ] [ j ] dp[i][j] dp[i][j]代表前 j j j个字符中放了 i i i个重音符可能的情况总数。

代码

const int mod = 1e9+7;
#define ll long long
class Solution {
public:
    /**
     * 
     * @param n int整型 乐谱总音符数
     * @param m int整型 重音符数
     * @param k int整型 重音符之间至少的间隔
     * @return long长整型
     */
    long long solve_bangbang(int n, int m, int k) {
        // write code here
        if(m == 0) return 1;
        vector<vector<int> > dp(1010, vector<int>(1010, 0));
        
        dp[0][0] = 1;
        // 不是重音符
        for(int i = 0; i <= n; i++) dp[1][i] = 1;
        
        for(int i = 2; i <= m; i++){
            for(int j = k + 2; j <= n; j++){
                // 不放重音符和放重音符的和
                dp[i][j] = (dp[i][j-1] + dp[i-1][j-k-1]) % mod;
            }
        }
        
        long long res = 0;
        for(int i = 1; i <= n; i++){
            res = (res +  dp[m][i]) % mod;
        }
        
        return res;
    }
};

C-天花板

题目

题目描述

牛牛想知道 ∑ i = 1 n ⌈ n i ⌉ \sum_{i=1}^n \left \lceil \frac{n}{i} \right \rceil i=1nin的值是多少(式子中 ⌈ n i ⌉ \left \lceil \frac{n}{i} \right \rceil in表示向上取整),现在牛牛给你 n \mathit n n,请你告诉牛牛和是多少。

示例1

输入

10

返回值

33

备注:

1 ≤ n ≤ 1 0 9 1\leq n\leq 10^9 1n109

思路

比赛中一直在oeis中找公式,害,大意了啊

分块

模拟一遍样例:

1  2  3  4  5  6  7  8  9  10
10 5  4  3  2  2  2  2  2  1

可以得到 ⌈ n i ⌉ \left \lceil \frac{n}{i} \right \rceil in的值在一段区间里是不变的,那么只要找到区间的左右端点就行了。

左端点是很容易得到的。

右端点计算方法如下:

  • 二分查找右边界
  • 直接计算右边界

统计即为答案。

代码

#define ll long long
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     * 
     * @param n int整型 
     * @return long长整型
     */ 
    ll findr(ll n, ll i){
        ll l = i, r = n;
        ll ans = l;
        while(l <= r){
            ll mid = (l+r)/2;
            int x = ceil(1.0 * n / i), y = ceil(1.0 * n / mid);
            if(x <= y) {
                l = mid + 1;
                ans = mid;
            }
            else r = mid - 1;
        }
        return ans;
    }
    /*
    ** 1  2  3  4  5  6  7  8  9  10
    ** 10 5  4  3  2  2  2  2  2  1
    */
    long long Sum(int n) {
        // write code here
        ll sums = 0;
        ll j;
        for(ll i = 1; i <= n; i = j + 1){
            if(i == n) j = n;
            else j = (n - 1) / ((n - 1) / i);
			// j = find(n, i);
            sums += ceil(1.0 * n / i) * (j-i+1);
        }
        return sums;
    }
};
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

牛客巅峰赛S2第6场题解 的相关文章

  • FTP的port模式和pasv模式

    FTP的port模式和pasv模式 FTP具有两种模式 xff0c 分别是port模式 也叫主动模式 和pasv模式 也叫被动模式 主动模式 主动模式的FTP是指服务器主动连接客户端的数据端口 xff0c 可以理解为服务端主动给客户端传输文
  • shell for循环多个变量

    1 使用花括号 var1 var2 var3 a 61 span class token string 34 apple 34 span span class token punctuation span b 61 span class t
  • shell 基本运算符

    文章目录 1 算数运算2 关系运算符3 布尔运算符4 逻辑运算符5 字符串运算符6 文件测试运算符知识点 1 算数运算 方法一 sum1 61 96 expr 3 span class token operator 43 span 5 96
  • Dockerfile简介

    1 什么是dockerfile Dockerfile是一个包含用于组合映像的命令的文本文档 可以使用在命令行中调用任何命令 Docker通过读取Dockerfile中的指令自动生成映像 docker build命令用于从Dockerfile
  • 容器通信之跨链接通信

    前言 同一主机下搭建容器应用栈的环境 xff0c 只需要完成容器互联来实现容器间的通信即可 xff0c 这里采用docker run link选项建立容器间的互联关系 docker官方已不推荐使用docker run link来链接2个容器
  • Linux进程间通信

    1 unix域套接字 域套接字 xff1a 1 只能用于同一设备上不同进程之间的通信 xff1b 2 效率高于网络套接字 域套接字仅仅是复制数据 xff0c 并不走协议栈 xff1b 3 可靠 xff0c 全双工 xff1b 2 IP套接字
  • 什么是API

    1 什么是API API是Application Programming Interface xff08 应用程序接口 xff09 的缩写 是一些预先定义的函数 xff0c 目的是提供应用程序与开发人员基于某软件或硬件得以访问一组例程的能力
  • FreeRTOS(二)任务基础知识

    一 前后台系统与RTOS 前后台系统 61 死循环 xff08 通常为1个 xff09 43 中断服务程序 xff08 通常为若干个 xff09 应用程序是一个无限循环 xff0c 循环中调用 API 函数完成所需的操作 xff0c 这个大
  • SBUS协议(20200210)

    最近看到很多sbus协议 xff0c 就专门搜集了一些资料学习一下 1 介绍 SBUS是一个接收机串行总线输出 xff0c 通过这根总线 xff0c 可以获得遥控器上所有通道的数据 目前很多模型及无人机电子设备都支持SBUS总线的接入 使用
  • 【openmv专题】串口通信

    这篇文章主要讲述openmv串口通信过程中会出现错位 xff0c 因缓存空间不足带来的串口报错问题 xff0c 直接进入正题 xff1a 串口通信有同步和异步之分 xff0c 而openmv用的是异步通信 xff0c 需要有缓存区 xff0
  • FreeRTOS任务上下文切换与任务状态切换的区别及联系

    FreeRTOS 中的任务上下文切换和任务状态切换是两个不同的概念 1 任务状态切换是指任务从一种状态切换到另一种状态 FreeRTOS 中的任务状态包括就绪态 阻塞态和运行态 当任务从就绪态切换到运行态时 xff0c 任务开始执行 xff
  • XGBOD:用无监督表示学习改进有监督离群点检测

    XGBOD Improving Supervised Outlier Detection with Unsupervised Representation Learning 论文链接 xff1a https www andrew cmu e
  • 小觅S系列相机运行vins-mono(轨迹飘飞解决版)

    小觅S系列相机运行vins mono xff08 轨迹飘飞解决版 xff09 1 SDK驱动2 获得相机标定数据3 下载MYNT EYE VINS Sample4 运行 前期准备 xff1a 安装并成功运行VINS MONO 1 SDK驱动
  • 嵌入式第0部分:嵌入式工程师完全学习指南

    一 什么是嵌入式 xff08 一 xff09 定义 xff1a 传统定义 xff08 狭义嵌入式 xff09 xff1a 嵌入式系统是以应用为中心 xff0c 以计算机技术为基础 xff0c 并且软硬件课裁剪 xff0c 适用于应用系统对功
  • 【SLAM 十四讲】---第七讲、视觉里程计

    第七讲 视觉里程计
  • Vscode配置git

    1 Git介绍和安装 Git是什么 Git是目前世界上最先进的分布式版本控制系统 xff08 没有之一 xff09 简单来说 它是控制项目版本的一个工具 我们可以利用Git进行多人协作和代码备份等工作 下载git xff08 64bit w
  • Xshell连接虚拟机Ubantu失败解决办法(主机和虚拟机能够互ping的前提)

    主机和虚拟机互ping 在主机命令行里输入ipconfig指令 xff0c 查询主机ip地址 xff0c 在虚拟机Ubantu终端里输入ping 主机ip地址 xff0c ping通后 xff0c 按ctrl 43 c停止 在虚拟机Uban
  • windows 11系统安装

    安装前注意事项 1 准备8G或8G以上U盘 xff08 32G以内 xff09 2 安装系统前备份好个人需要数据 xff08 制作U盘会格式化U盘 xff0c U盘内的重要文件也要事先备份好 xff09 3 预装office的务必记住自己激
  • docker 权限问题 Got permission denied while trying to connect to the Docker daemon socket at

    一 前言 docker安装完成 xff0c 一般用户没有权限启动docker服务 xff0c 只能通过sudo来通过root用户权限来启动docker xff0c 此时对于一般用户而言 xff0c 需要执行docker ps或者docker
  • Neo4j(七)——创建新数据库(如何在Neo4j中创建新数据库)

    方法一 xff1a 找到neo4j安装目录 xff0c 编辑conf文件夹中的neo4j conf 找到dbms active database 61 xff0c 将下图中的graph db用其他名称替换 xff0c 并解除注释 xff08

随机推荐

  • python VScode使用gitlab简单使用流程

    一 下载安装软件 1 安装好vscode xff0c 如未安装 xff0c 下载并且安装 https code visualstudio com Download 2 安装git windows客户端 https git scm com d
  • keil5工程函数无法跳转到函数定义解决方法

    问题描述 在使用keil查看工程代码时 xff0c 进行函数的跳转 xff0c 跳转不成功并提示以下错误 这是因为在编译工程的时候少勾选了一个选项 xff0c 按下以下方式勾选上然后重新Rebuild一下工程就好了
  • Codeforces D. Prefix-Suffix Palindrome

    Codeforces D Prefix Suffix Palindrome 题解 xff1a 和D1相同 xff0c 区别是找中间的回文串要压缩时间 xff0c 用到了马拉车算法 xff08 算法介绍在下面 xff1a span class
  • codeforces 1326 E.Bombs

    codeforces 1326 E Bombs 题意 xff1a 给定 1 n 1 n 1 n 的排列p q xff0c 将
  • Educational Codeforces Round 84 题解

    Educational Codeforces Round 84 题解 A Sum of Odd Integers 题意 xff1a n n n 是否能表示为 k k k 个不同的正奇
  • codeforces 1332 E - Height All the Same(组合数学、奇偶性)

    codeforces 1332 E Height All the Same 组合数学 奇偶性 题意 xff1a 现在有一个 n m n m n m 的方格 xff0c 第 i
  • codeforces 1330 C.D.题解

    codeforces 1330 C D 题解 Dreamoon Likes Coloring 题意 xff1a 给 n lt 61 100000 n lt 61 100000 n lt 61
  • LeetCode数独问题中Bitset的巧妙用处

    LeetCode数独问题中Bitset的巧妙用处 36 有效的数独 判断一个 9x9 的数独是否有效 只需要根据以下规则 xff0c 验证已经填入的数字是否有效即可 数字 1 9 在每一行只能出现一次 数字 1 9 在每一列只能出现一次 数
  • Morris 遍历

    Morris 遍历 中序遍历 前言 我们在中序遍历的时候 一定先遍历左子树 然后遍历当前节点 最后遍历右子树 在常规方法中 我们用递归回溯或者是栈来保证遍历完左子树可以再回到当前节点 但这需要我们付出额外的空间代价 我们需要用一种巧妙地方法
  • 第九届蓝桥杯c/c++A组省赛题解

    分数 题目 1 1 43 1 2 43 1 4 43 1 8 43 1 16 43 每项是前一项的一半 xff0c 如果一共有20项 求这个和是多少 xff0c 结果用分数表示出来 类似 xff1a 3 2 当然 xff0c 这只是加了前2
  • Ltp介绍及实践(20200925)

    Ltp中源代码和模型包括 xff1a 中文分词 词性标注 未登录词识别 依存句法 语义角色标注几个模块 目录 1 标注集合 分词标注集 词性标注集 命名实体识别标注集 依存句法关系 语义角色类型 2 快速使用 载入模型 分句 用户自定义词典
  • 第十一届蓝桥杯省赛C/C++B组题解

    试题 A 跑步训练 本题总分 xff1a 5 分 题目 问题描述 小明要做一个跑步训练 初始时 xff0c 小明充满体力 xff0c 体力值计为 10000 如果小明跑步 xff0c 每分钟损耗 600 的体力 如果小明休息 xff0c 每
  • codeforces Round680 C. Division 题解

    codeforces Round680 C Division 题解 题目 Oleg s favorite subjects are History and Math and his favorite branch of mathematic
  • Codeforces Round #677 (Div. 3) 题解

    Codeforces Round 677 Div 3 题解 A Boring Apartments 题目 题解 简单签到题 xff0c 直接数 xff0c 小于这个数的 43 10 43 10 43 1 0 代码 span class to
  • Leetcode 327. 区间和的个数 (前缀和 + 离散化 + 树状数组)

    Leetcode 327 区间和的个数 前缀和 43 离散化 43 树状数组 题目 题意 有多少个连续的子数组 xff0c 其和在 l o w e r
  • 01 Trie 专题

    01 Trie 专题 异或最大值 The xor largest pair 题意 xff1a 异或最大值的模板 一个数和一个序列中一个数的异或最大值是多少 xff1f 要支持询问 思路 考虑把序列插入 xff0c 构建一个 Trie tex
  • DFS序专题

    牛客专题之DFS序 简介 dfs序 每个节点在dfs深度优先遍历中的进出栈的时间序列 xff0c 也就是tarjan算法中的dfn数组 画个图理解一下 xff1a 这棵树的dfs序 xff1a 1 3 2 4 2 5 6 7 6 5 1 那
  • 牛客编程巅峰赛S2第4场题解

    牛客编程巅峰赛S2第4场 牛牛摆玩偶 题目描述 牛牛有 n 2 n 1 0
  • Leetcode第 217 场周赛(思维量比较大)

    Leetcode第 217 场周赛 比赛链接 xff1a 点这里 做完前两题我就知道今天的竞赛我已经结束了 这场比赛思维量还是比较大的 1673 找出最具竞争力的子序列 题目 给你一个整数数组 nums 和一个正整数 k xff0c 返回长
  • 牛客巅峰赛S2第6场题解

    牛客编程巅峰赛S2第6场 A String 题目 题目描述 给出一个仅包含小写字母的字符串s xff0c 你最多可以操作k次 xff0c 使得任意一个小写字母变为与其相邻的小写字母 xff08 ASCII码差值的绝对值为1 xff09 xf