牛客 第二十届西南科技大学ACM程序设计竞赛(同步赛):祖玛

本文主要是介绍牛客 第二十届西南科技大学ACM程序设计竞赛(同步赛):祖玛,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!


 

题目描述

wzy 在玩一种很新的祖玛。

给定一个仅包含 小写字母 的字符串 sss , sss 由 mmm 个不同的小写字母组成,每个字母代表一种小球,在消去时会获得 相应 的分数:


  • 两个及以上 相同的小球相碰就会消失(在发射小球前因为无相碰,所以有两个及以上小球相邻也不会消失)。
  • 每次碰撞后,消失获得的分数为:对应小球分数×消失个数

     

你可以进行 一次 操作:

发射一个任意小球于 sss 的任意位置(也可以是 头和尾 )。

发射小球后,按照规则进行,直到不能碰撞为止。

请你求出经过一次操作后取得的 最大分数

输入描述:

 

第一行包含两个整数 n,m(1≤n≤105,1≤m≤26)n,m(1\le n \le 10^5,1\le m\le 26)n,m(1≤n≤105,1≤m≤26) - 表示字符串长度 和 字符集大小。

第二行包含一个长度为 nnn 字符串 sss。

接下来 mmm 行,每行包含 c,k(′a′≤c≤c,k('a'\le c\lec,k(′a′≤c≤ ′z′,1≤k≤109)'z',1\le k\le10^9)′z′,1≤k≤109) - 表示每消除一个字母 ccc 有 kkk 分。

保证:字符串 sss 中的字母必定在给定字符集中出现。

输出描述:

输出一次操作能获得的最高得分。

示例1

输入

复制6 3 abccba a 1 b 2 c 3

6 3
abccba
a 1
b 2
c 3

输出

复制15

15

说明

样例一的解释:

最终将全部字母消除,得分为 3×3+2×2+2×1=153×3+2×2+2×1 = 153×3+2×2+2×1=15 即为最大
#include<bits/stdc++.h>
using namespace std;
int n,m;
string s,s2;
long long score[30];
long long ans;
int p[300010];
long long pre[100010];
void mlc(){int mid,mr=0;for(int i=1;i<s2.size();i++){if(i<mr) p[i]=min(p[mid*2-i],mr-i);else p[i]=1;while(s2[i-p[i]]==s2[i+p[i]]) p[i]++;if(i+p[i]>mr){mr=i+p[i];mid=i;}}
}
int main(){scanf("%d%d",&n,&m);cin>>s;for(int i=1;i<=m;i++){char c;long long num;cin>>c;scanf("%lld",&num);score[c-'a']=num;}s2+='&';s2+=s[0];pre[1]=score[s2[1]-'a'];for(int i=1,j=1;i<s.size();i++){if(s[i]!=s[i-1]) {s2+=s[i];j++;pre[j]=pre[j-1]+score[s[i]-'a'];//s2的前缀和}else{pre[j]+=score[s[i]-'a'];}}s2+='^';
//将s中连续出现的某个字母合并成只有一个,最终形成s2,这样的s2的回文串只能为奇数,因此直接头和尾加一个不同的字符即可,不用再加‘#’mlc();for(int i=1;i<s2.size();i++){long long res;res=pre[i+p[i]-1]-pre[i-p[i]]+score[s2[i]-'a']; //以i为中心,左右分别延长p[i]-1的回文串ans=max(ans,res);}cout<<ans;
}

这篇关于牛客 第二十届西南科技大学ACM程序设计竞赛(同步赛):祖玛的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1068412

相关文章

基于MySQL Binlog的Elasticsearch数据同步实践

一、为什么要做 随着马蜂窝的逐渐发展,我们的业务数据越来越多,单纯使用 MySQL 已经不能满足我们的数据查询需求,例如对于商品、订单等数据的多维度检索。 使用 Elasticsearch 存储业务数据可以很好的解决我们业务中的搜索需求。而数据进行异构存储后,随之而来的就是数据同步的问题。 二、现有方法及问题 对于数据同步,我们目前的解决方案是建立数据中间表。把需要检索的业务数据,统一放到一张M

服务器集群同步时间手记

1.时间服务器配置(必须root用户) (1)检查ntp是否安装 [root@node1 桌面]# rpm -qa|grep ntpntp-4.2.6p5-10.el6.centos.x86_64fontpackages-filesystem-1.41-1.1.el6.noarchntpdate-4.2.6p5-10.el6.centos.x86_64 (2)修改ntp配置文件 [r

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能

从戴尔公司中国大饭店DTF大会,看科技外企如何在中国市场发展

【科技明说 | 科技热点关注】 2024戴尔科技峰会在8月如期举行,虽然因事未能抵达现场参加,我只是观看了网上在线直播,也未能采访到DTF现场重要与会者,但是通过数十年对戴尔的跟踪与观察,我觉得2024戴尔科技峰会给业界传递了6大重要信号。不妨简单聊聊:从戴尔公司中国大饭店DTF大会,看科技外企如何在中国市场发展? 1)退出中国的谣言不攻自破。 之前有不良媒体宣扬戴尔将退出中国的谣言,随着2

每日一题|牛客竞赛|四舍五入|字符串+贪心+模拟

每日一题|四舍五入 四舍五入 心有猛虎,细嗅蔷薇。你好朋友,这里是锅巴的C\C++学习笔记,常言道,不积跬步无以至千里,希望有朝一日我们积累的滴水可以击穿顽石。 四舍五入 题目: 牛牛发明了一种新的四舍五入应用于整数,对个位四舍五入,规则如下 12345->12350 12399->12400 输入描述: 输入一个整数n(0<=n<=109 ) 输出描述: 输出一个整数

C语言程序设计(数据类型、运算符与表达式)

一、C的数据类型 C语言提供的数据类型: 二、常量和变量 2.1常量和符号常量 在程序运行过程中,其值不能被改变的量称为常量。 常量区分为不同的类型: 程序中用#define(预处理器指令)命令行定义变量将代表常量,用一个标识符代表一个常量,称为符合常量。 2.2变量 变量代表内存中具有特定属性的一个存储单元,用来存放数据,在程序运行期间,这些值是可以 改变的。 变

C语言程序设计(选择结构程序设计)

一、关系运算符和关系表达式 1.1关系运算符及其优先次序 ①<(小于) ②<=(小于或等于) ③>(大于) ④>=(大于或等于 ) ⑤==(等于) ⑥!=(不等于) 说明: 前4个优先级相同,后2个优先级相同,关系运算符的优先级低于算术运算符,关系运算符的优先级高于赋值运算符 1.2关系表达式 用关系运算符将两个表达式(可以是算术表达式或关系表达式,逻辑表达式,赋值表达式,字符

MySQL主从同步延迟原理及解决方案

概述 MySQL的主从同步是一个很成熟的架构,优点为: ①在从服务器可以执行查询工作(即我们常说的读功能),降低主服务器压力; ②在从主服务器进行备份,避免备份期间影响主服务器服务; ③当主服务器出现问题时,可以切换到从服务器。 相信大家对于这些好处已经非常了解了,在项目的部署中也采用这种方案。但是MySQL的主从同步一直有从库延迟的问题,那么为什么会有这种问题。这种问题如何解决呢? MyS

2024年AMC10美国数学竞赛倒计时两个月:吃透1250道真题和知识点(持续)

根据通知,2024年AMC10美国数学竞赛的报名还有两周,正式比赛还有两个月就要开始了。计划参赛的孩子们要记好时间,认真备考,最后冲刺再提高成绩。 那么如何备考2024年AMC10美国数学竞赛呢?做真题,吃透真题和背后的知识点是备考AMC8、AMC10有效的方法之一。通过做真题,可以帮助孩子找到真实竞赛的感觉,而且更加贴近比赛的内容,可以通过真题查漏补缺,更有针对性的补齐知识的短板。