蓝桥杯 子串分值(难)
2022/1/17 23:35:49
本文主要是介绍蓝桥杯 子串分值(难),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述
对于一个字符串 SS,我们定义 SS 的分值 f(S)f(S) 为 SS 中恰好出现一次的字符个数。例如 f(aba) = 1,f(abc) = 3, f(aaa) = 0f(aba)=1,f(abc)=3,f(aaa)=0。
输入描述
输入一行包含一个由小写字母组成的字符串 S。
输出描述
输出一个整数表示答案。
输入输出样例
示例
输入:ababc
输出:21
代码:
#include<stdio.h> #include<string.h> #define N 100002 int main() { char s[N]; int last[26]; //记录 a~z中每个字符最后被扫描的位置,即下标 int pre[N]; //记录前面与第i个字符相同的字符的位置,即下标 int next[N]; //记录后面与第i个字符相同的字符的位置,即下标 gets(s); int k,i,l; int sum=0; //sum=sum+(i-pre[i])*(next[i]-i) l=strlen(s); //字符串长度 for(i=0; i<26; i++) //由于下标从0开始,所有字符在没出现第一次前都是 -1 last[i]=-1; for(i=0; i<l; i++) { k=s[i]-'a'; pre[i]=last[k]; //前面与第i个字符相同的字符的位置 last[k]=i; //更新字符的位置 } for(i=0; i<26; i++) //由于下标从0开始,从后面到前面,所有字符在没出现第一次前都是 l last[i]=l; for(i=l-1; i>=0; i--) { k=s[i]-'a'; next[i]=last[k]; //后面与第i个字符相同的字符的位置 last[k]=i; //更新字符的位置 } for(i=0; i<l; i++) { sum+=(i-pre[i])*(next[i]-i); //(i-pre[i])为前面与第i个字符相同的字符与s[i]的距离 //(next[i]-i)为后面与第i个字符相同的字符与s[i]的距离 } printf("%d",sum); return 0; }
题目链接:子串分值 - 蓝桥云课 (lanqiao.cn)
这篇关于蓝桥杯 子串分值(难)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求