PAT 1040有几个PAT
2024-09-04 04:37:12
1040 有几个PAT (25 分)
字符串 APPAPT
中包含了两个单词 PAT
,其中第一个 PAT
是第 2 位(P
),第 4 位(A
),第 6 位(T
);第二个 PAT
是第 3 位(P
),第 4 位(A
),第 6 位(T
)。
现给定字符串,问一共可以形成多少个 PAT
?
输入格式:
输入只有一行,包含一个字符串,长度不超过1,只包含 P
、A
、T
三种字母。
输出格式:
在一行中输出给定字符串中包含多少个 PAT
。由于结果可能比较大,只输出对 1000000007 取余数的结果。
输入样例:
APPAPT
输出样例:
2
暴力也能做O(n^3)的复杂度
#include<bits/stdc++.h>
using namespace std;
int main()
{
char c[];
scanf("%s",c);
int l=strlen(c); long long time=;
for(int i=;i<l;i++)
{
if(c[i]=='P')
{
for(int j=i+;j<l;j++)
{
if(c[j]=='A')
{
for(int k=j+;k<l;k++)
{
if(c[k]=='T')
{
time++;
}
}
}
}
}
}
int t=;
printf("%lld",time%t);
return ;
}
然后写了一个这个
#include<bits/stdc++.h>
using namespace std;
int main()
{
char c[];
scanf("%s",c);
int l=strlen(c);
long long numt,numat,numpat;
numt=numat=numpat=;
for(int i=;i<l;i++)
{
if(c[i]=='P')
numt++;
else if(c[i]=='A')
{
numat+=numt;
}
else
{
numpat+=numat;
}
}
int t=;
printf("%lld",numpat%t);
return ;
}
O(n)的复杂度
最新文章
- eclipse maven web环境搭建
- java加密算法之AES小记
- 字符串匹配(KMP算法)
- paper 91:边缘检测近期最新进展的讨论
- 斯坦福大学Andrew Ng教授主讲的《机器学习》公开课观后感[转]
- .net 安装remoting服务
- ASP.NET 委托,异步调用例子 .
- c++ 类的定义和使用
- 10 Easy Steps to a Complete Understanding of SQL
- UNIX域协议(无名套接字)
- ASP.NET Aries 高级开发教程:Excel导入配置之规则说明(下)
- 使用Java代码发送邮件
- css多列居中
- 走你!Github 开源整合
- ros自定义消息的时候报错ImportError: No module named em
- Sequel简介
- Oracle查询client编码集
- Could not load file or assembly &#39;Microsoft.Practices.EnterpriseLibrary.Common, Version=5.0.414.0, ...
- bzoj 4397: [Usaco2015 dec]Breed Counting -- 前缀和
- encoder-decoder环境部署问题