洛谷 P2646 数数zzy
2024-10-01 18:58:25
题目描述
zzy自从数学考试连续跪掉之后,上数学课就从来不认真听了(事实上他以前也不认真听)。于是他开始在草稿纸上写写画画,比如写一串奇怪的字符串。然后他决定理♂性♂愉♂悦♂一下:统计这串字符串当中共有多少个为“zzy”的子序列(注意是子序列而非子串)。但是由于他写的字符串实在是太长啦,而且他是个超级大蒟蒻,根本就数不过来。所以他决定请求你这个超级大神犇的帮助。你可以帮帮他吗?
输入输出格式
输入格式:
一行仅含小写字母的字符串。
输出格式:
一行,一个非负整数,表示输入的字符串中为“zzy”的子序列的个数。
输入输出样例
说明
70%的数据满足:1<=n<=100。
100%的数据满足:1<=n<=1000000。
n表示字符串的长度
数据保证答案不超过2^63-1
思路:数学
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
char s[];
long long sum[];
long long ans,len,num;
int main(){
scanf("%s",s);
len=strlen(s);
for(int i=;i<=;i++) sum[i]=sum[i-]+i;
for(int i=;i<len;i++){
if(s[i]=='z') num++;
if(s[i]=='y') ans+=sum[num-];
}
cout<<ans;
}
最新文章
- [转]IPTABLES中SNAT和MASQUERADE的区别
- 与Perl兼容的正则表达式函数
- 周赛D题
- 《AngularJS》--指令的相互调用
- Android Studio导入GitHub上的项目常见问题(以图片轮播开源项目为实例)
- JAVA基础之内部类
- 1.在CentOS 6.4安装python3
- SSH key introduction
- 0.计划用libgdx写一个六边形回合制slg兵棋游戏
- 【shiro】(3)---了解Shiro
- BZOJ2746: [HEOI2012]旅行问题(AC自动机 LCA)
- 行业观察报告:从SAAS困局看行业趋势 ZT
- odoo11登录之后返回的session信息分析
- 2018.4.24 flask_mail使用
- 快速解决MariaDB无密码就可以登录的问题
- Linux tar包相关命令
- Centos warning: setlocale: LC_CTYPE: cannot change locale (UTF-8): No such file or directory
- [JQuery] jQuery选择器ID、CLASS、标签获取对象值、属性、设置css样式
- 关于Virtual的英语含义
- iOS彩票项目--第一天,自定义TabBar控制器和自定义TabBar,自定义导航控制器