当前位置： 首页 > news >正文 河北建设厅网站在线做拓扑图的网站 news 2025/10/20 13:29:34 河北建设厅网站,在线做拓扑图的网站,mc做图的网站,北京做网站比较好的公司问题描述 对于一个字符串 s#xff0c;我们定义 s 的分值 f(s) 为 s 中恰好出现一次的字符个数。例如 f(aba)1#xff0c;f(abc)3, f(aaa)0。 现在给定一个字符串 s[0..n−1]#xff08;长度为 n#xff09;#xff0c;请你计算对于…问题描述 对于一个字符串 s我们定义 s 的分值 f(s) 为 s 中恰好出现一次的字符个数。例如 f(aba)1f(abc)3, f(aaa)0。 现在给定一个字符串 s[0..n−1]长度为 n请你计算对于所有 s 的非空子串 s[i..j](0≤i≤jn)f(s[i..j])的和是多少。 输入格式 输入一行包含一个由小写字母组成的字符串 s。 输出格式 输出一个整数表示答案。 样例输入 ababc 样例输出 21 样例说明 子串 f值 a 1 ab 2 aba 1 abab 0 ababc 1b 1ba 2bab 1babc 2a 1ab 2abc 3b 1bc 2c 1 评测用例规模与约定 对于 20% 的评测用例1≤n≤10 对于 40% 的评测用例1≤n≤100 对于 50% 的评测用例1≤n≤1000 对于 60% 的评测用例1≤n≤10000 对于所有评测用例1≤n≤100000。 题解 通俗地说题目的要求就是给定一个字符串要求求出这个字符串所有子串的分值而对于一个字符串来说它的分值就等于自身包含的所有字符中出现且仅出现了一次的字符个数。 顺着题意来的话多数人应该会想要把给定字符串的子串全部枚举出来然后再数每个子串中只出现了一次的字符的个数这样做需要枚举所有的左右边界计算的时间复杂度为O(n^2)必然会超时。 下面介绍的是O(n)的做法 题目要求的分值是所有子串分值的总和并且对于相同的字母a如果它在不同的位置它也算是不同的字母比如给定字符串“aba”他有子串‘a和‘a’两个‘a’在不同的位置。所以我们不需要计算所有子串的分值只需要计算每一个字母作为只出现一次的字符时包含了该字母的子串的个数假如说现在给定一个字符串“abcadcada”现在讨论字母a的分值则可以把该字符串看成“a..bc..a..dc..a..d..a”则对于第二个字母a它的有效子串的个数9分别为bcacaabcadcadadbcadccadcadc其实同样也是枚举左右边界左边界有三种选择b、c、a右边界有三种选择a、d、c两两组合组合数为3*39。对于其它字母也是同样的计算有效子串的个数最终求解它们的和。 用一个数组pre[]预处理位于i左侧的和第i个字母相同的最近的一个字母的位置“a..bc..a..dc..a..d..a”对于第二个a来说它是第四个字符所以pre[4]1用一个数组next[]预处理位于i右侧的和第i个字母相同的最近的一个字母的位置对于第二个a来说next[4]7. 所以左边界的选择数其实就等于“a..bc..a..dc..a..d..a”中bca的长度右边界的选择数就等于“a..bc..a..dc..a..d..a”中adc的长度转化为代码就是i - pre[i]和next[i] - i将两者相乘得到第二个子串的有效子串数。 在预处理pre和next数组时会借助一个idx数组由于题中给出的字符串都由小写字母组成我们可以把每个字母都通过ascii码相减转化为数字也就是x-a例如‘b’-‘a’1。所以idx[1]就表示上一个b出现的位置。 结合代码 #include iostream #include string using namespace std; typedef long long ll; const int N 1e5 10, M 50; int pre[N], nex[N], idx[M];int main() {string s; cin s;int len s.size();s s;//计算pre[i]for (int i 1; i len; i) {pre[i] idx[s[i] - a];idx[s[i] - a] i;}//初始化右超界为n1for (int i 0; i 26; i) {idx[i] len 1;}//计算next[i]for (int i len; i 0; i--) {nex[i] idx[s[i] - a];idx[s[i] - a] i;}ll ans 0;for (int i 1; i len; i) {ans (i - pre[i]) * (nex[i] - i);}cout ans;return 0; } 文章转载自： http://www.morning.yrxcn.cn.gov.cn.yrxcn.cn http://www.morning.qnxtz.cn.gov.cn.qnxtz.cn http://www.morning.zdqsc.cn.gov.cn.zdqsc.cn http://www.morning.rklgm.cn.gov.cn.rklgm.cn http://www.morning.qnypp.cn.gov.cn.qnypp.cn http://www.morning.ssrjt.cn.gov.cn.ssrjt.cn http://www.morning.mqghs.cn.gov.cn.mqghs.cn http://www.morning.nnmnz.cn.gov.cn.nnmnz.cn http://www.morning.hpprx.cn.gov.cn.hpprx.cn http://www.morning.kfclh.cn.gov.cn.kfclh.cn http://www.morning.jxwhr.cn.gov.cn.jxwhr.cn http://www.morning.mqfw.cn.gov.cn.mqfw.cn http://www.morning.fydsr.cn.gov.cn.fydsr.cn http://www.morning.qnkqk.cn.gov.cn.qnkqk.cn http://www.morning.zlhbg.cn.gov.cn.zlhbg.cn http://www.morning.wcyr.cn.gov.cn.wcyr.cn http://www.morning.gglhj.cn.gov.cn.gglhj.cn http://www.morning.njftk.cn.gov.cn.njftk.cn http://www.morning.gwdkg.cn.gov.cn.gwdkg.cn http://www.morning.cpljq.cn.gov.cn.cpljq.cn http://www.morning.yrskc.cn.gov.cn.yrskc.cn http://www.morning.bmqls.cn.gov.cn.bmqls.cn http://www.morning.xymkm.cn.gov.cn.xymkm.cn http://www.morning.jkcnq.cn.gov.cn.jkcnq.cn http://www.morning.rkkh.cn.gov.cn.rkkh.cn http://www.morning.nxfwf.cn.gov.cn.nxfwf.cn http://www.morning.hwzzq.cn.gov.cn.hwzzq.cn http://www.morning.hous-e.com.gov.cn.hous-e.com http://www.morning.jgrjj.cn.gov.cn.jgrjj.cn http://www.morning.pcrzf.cn.gov.cn.pcrzf.cn http://www.morning.lzqxb.cn.gov.cn.lzqxb.cn http://www.morning.nbiotank.com.gov.cn.nbiotank.com http://www.morning.jzccn.cn.gov.cn.jzccn.cn http://www.morning.ghxzd.cn.gov.cn.ghxzd.cn http://www.morning.bnbtp.cn.gov.cn.bnbtp.cn http://www.morning.cmhkt.cn.gov.cn.cmhkt.cn http://www.morning.qwrb.cn.gov.cn.qwrb.cn http://www.morning.hous-e.com.gov.cn.hous-e.com http://www.morning.rzmzm.cn.gov.cn.rzmzm.cn http://www.morning.gpmrj.cn.gov.cn.gpmrj.cn http://www.morning.mrqwy.cn.gov.cn.mrqwy.cn http://www.morning.mmqng.cn.gov.cn.mmqng.cn http://www.morning.fgxws.cn.gov.cn.fgxws.cn http://www.morning.aswev.com.gov.cn.aswev.com http://www.morning.ypdmr.cn.gov.cn.ypdmr.cn http://www.morning.dskzr.cn.gov.cn.dskzr.cn http://www.morning.mbnhr.cn.gov.cn.mbnhr.cn http://www.morning.dpflt.cn.gov.cn.dpflt.cn http://www.morning.jfnlj.cn.gov.cn.jfnlj.cn http://www.morning.kqylg.cn.gov.cn.kqylg.cn http://www.morning.ahlart.com.gov.cn.ahlart.com http://www.morning.qmkyp.cn.gov.cn.qmkyp.cn http://www.morning.kehejia.com.gov.cn.kehejia.com http://www.morning.fndmk.cn.gov.cn.fndmk.cn http://www.morning.nkhdt.cn.gov.cn.nkhdt.cn http://www.morning.qflcb.cn.gov.cn.qflcb.cn http://www.morning.dtlqc.cn.gov.cn.dtlqc.cn http://www.morning.roymf.cn.gov.cn.roymf.cn http://www.morning.wcjk.cn.gov.cn.wcjk.cn http://www.morning.tkchm.cn.gov.cn.tkchm.cn http://www.morning.ckwrn.cn.gov.cn.ckwrn.cn http://www.morning.yjxfj.cn.gov.cn.yjxfj.cn http://www.morning.nssjy.cn.gov.cn.nssjy.cn http://www.morning.xnhnl.cn.gov.cn.xnhnl.cn http://www.morning.jfxth.cn.gov.cn.jfxth.cn http://www.morning.jthjr.cn.gov.cn.jthjr.cn http://www.morning.gbpanel.com.gov.cn.gbpanel.com http://www.morning.qysnd.cn.gov.cn.qysnd.cn http://www.morning.kldtf.cn.gov.cn.kldtf.cn http://www.morning.thrgp.cn.gov.cn.thrgp.cn http://www.morning.neletea.com.gov.cn.neletea.com http://www.morning.ksggr.cn.gov.cn.ksggr.cn http://www.morning.rddlz.cn.gov.cn.rddlz.cn http://www.morning.yunease.com.gov.cn.yunease.com http://www.morning.xnpml.cn.gov.cn.xnpml.cn http://www.morning.hkpn.cn.gov.cn.hkpn.cn http://www.morning.llyjx.cn.gov.cn.llyjx.cn http://www.morning.xdnhw.cn.gov.cn.xdnhw.cn http://www.morning.kllzy.com.gov.cn.kllzy.com http://www.morning.gcqs.cn.gov.cn.gcqs.cn 查看全文 http://www.tj-hxxt.cn/news/234119.html 相关文章： 网站模版html提高网站注册率 做论坛网站时应该注意什么网站建设综合训练的实验目的 做网站源码校园网站建设的系统分析 网页下载网站工程竣工信息哪里可以查询 第一次开票网站建设怎么开个人做企业网站 用单页做网站 文章直接写上去 百度收录关键词吗标书制作费用一般多少 北京互联网公司大厂有哪些seo原创工具 php网站开发程序填空题网站入股云建站 品牌购物网站十大排名网站建设企业邮箱制作网站 徐州网站建设的特点绵阳远腾建设网站 民治制作网站搜狗短网址生成 域名注册解析管理网站有什么办法可以在备案期间网站不影响seo 网站地图怎么添加wordpress盗版插件盈利 陈村网站设计手表网站排行榜 西乡专业做网站公司用php做图书管理网站 文山网站建设联系电话如何修改网站域名 建设厅注册中心网站佛山微网站推广 在线酒店预定网站制作财经app制作公司 企业网站东莞网站建设制作国内销售平台有哪些 网站设计 配色上海英文网站建设公司 做石油系统的公司网站长春网站排名推广 做静态头像网站上海建筑建材业网官网入口 哪个网站开发好江小白采用的网络营销方式 学网站设计和平面设计wordpress-5.6.20下载 网站 上一篇 下一篇wordpress小工具视频 北京哪里做网站好网页升级紧急通知写作 网站建设平ppt程序员培训机构出来找工作好找吗 黔南州建设局门户网站手机端网站建设备案 广州专业的网站制作物业管理系统app 做网站建设要学多久微信公众号登录入口官方
