科大讯飞笔试编程第三题

小红定义一个字符串是“好串”,当且仅当该字符串的长度不小于2,且首尾相同。

一个仅包含小写字母的字符串,长度不超过200000。

输出描述

如果无法切割且该字符串本身不是好串,请输出-1。否则输出最终的好串数量。

思路:正常dp转移是dp[i]=max(dp[i],dp[x]+1), a[x]=a[i], 复杂度是O(n^2)的

改进:dp[i]表示[1,i]中最大分割次数;trans[i-1]堆维护第i个字母后面一个位置(假设是x)dp[x]的最大值;dp[i]的转移位置由trans[a[i]]来维护,转移的过程中必须得保证转移的位置合法。(今天才发现不用堆也行,只要最大值就行)

这题确实有点东西,第一次感受到笔试编程题带来的压迫感

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+100;
priority_queue<int> trans[26];//以a[i]后面一格的最大dp值
string s;
int a[maxn];
int dp[maxn],n; 
int main(){
    cin>>s;
    for(int i=1;i<=s.size();i++){
        a[i]=s[i-1]-'a';
    }
    n=s.size();

    memset(dp,-1,sizeof(dp));
    dp[0]=0;
    for(int i=1;i<=n;i++){
        if(trans[a[i]].empty()){
        if(dp[i-1]!=-1){//身后元素是合法状态 
        trans[a[i]].push(dp[i-1]); 
}
continue;
}
        int mx=trans[a[i]].top();
        dp[i]=mx+1;
        if(dp[i-1]!=-1){//身后元素是合法状态 
    trans[a[i]].push(dp[i-1]); 
}
    }
    cout<<dp[n]<<endl;
全部评论
请问是双机位双摄像头吗?
1 回复 分享
发布于 2023-07-15 16:47 江苏
同学你好,讯飞正式批开启了,欢迎来主页投递!
点赞 回复 分享
发布于 2023-07-21 23:19 安徽
不改进的话..能AC吗?还是超时呀?
点赞 回复 分享
发布于 2023-07-09 20:55 湖北

相关推荐

不愿透露姓名的神秘牛友
昨天 15:58
点赞 评论 收藏
分享
05-12 11:09
已编辑
门头沟学院 后端
已注销:没必要放这么多专业技能的描述。这些应该是默认已会的,写这么多行感觉在凑内容。项目这块感觉再包装包装吧,换个名字,虽然大家的项目基本都是网上套壳的,但是你这也太明显了。放一个业务项目,再放一个技术项目。技术项目,例如中间件的一些扩展和尝试。
简历中的项目经历要怎么写
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
今天 12:31
以前小时候我最痛恨出轨、偷情的人,无论男女,为什么会出轨?现在我成了自己最讨厌的人,没想到分享的东西在牛客会被这么多人看,大家的评价都很中肯,我也认同,想过一一回复,但我还是收声了,我想我应该说说这件事,这件事一直压在我心里,是个很大的心结,上面说了人为什么出轨,我大概能明白了。我们大一下半年开始恋爱,开始恋爱,我给出了我铭记3年的承诺,我对她好一辈子,我永远不会背叛,我责任心太重,我觉得跟了我,我就要照顾她一辈子,我们在一起3年我都没有碰过她,她说往东我就往东,她说什么我做什么,她要我干什么,我就干什么!在学校很美好,中途也出过一些小插曲,比如男闺蜜、男闺蜜2号等等等。但我都强迫她改掉了,我...
牛客刘北:两个缺爱的人是没有办法好好在一起的,但世界上哪有什么是非对错?你后悔你们在一起了,但是刚刚在一起的美好也是真的呀,因为其他人的出现,你开始想要了最开始的自己,你的确对不起自己,21岁的你望高物远,你完全可以不谈恋爱,去过你想要的生活,你向往自由,在一起之后,你要想的不是一个人,而是两个人,你不是变心了,就像你说的,你受够了,你不想包容了,冷静几天是你最优的选择,爱人先爱己。
社会教会你的第一课
点赞 评论 收藏
分享
评论
5
17
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务