Educational Codeforces Round 74 (Rated for Div. 2) D. AB-string
链接:
https://codeforces.com/contest/1238/problem/D
题意:
The string t1t2…tk is good if each letter of this string belongs to at least one palindrome of length greater than 1.
A palindrome is a string that reads the same backward as forward. For example, the strings A, BAB, ABBA, BAABBBAAB are palindromes, but the strings AB, ABBBAA, BBBA are not.
Here are some examples of good strings:
t = AABBB (letters t1, t2 belong to palindrome t1…t2 and letters t3, t4, t5 belong to palindrome t3…t5);
t = ABAA (letters t1, t2, t3 belong to palindrome t1…t3 and letter t4 belongs to palindrome t3…t4);
t = AAAAA (all letters belong to palindrome t1…t5);
You are given a string s of length n, consisting of only letters A and B.
You have to calculate the number of good substrings of string s.
思路:
考虑ABB这种无法满足, 可以推出一只有一个a或b且处于子串的左右两边的时候,不满足, 记录不满足的个数,减一下.
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 3e5+10;
char s[MAXN];
int n;
int main()
{
cin >> n;
cin >> (s+1);
LL cnt = 0;
for (int i = 1, j;i < n;i = j)
{
j = i;
while (j+1 <= n && s[j+1] == s[i])
j++;
i = j;
while (j+1 <= n && s[j+1] != s[i])
j++;
cnt += j-i;
}
for (int i = n, j;i > 1;i = j)
{
j = i;
while (j-1 >= 1 && s[j-1] == s[i])
j--;
i = j;
while (j-1 >= 1 && s[j-1] != s[i])
j--;
if (i-j-1 > 0)
cnt += i-j-1;
}
LL ans = (1LL*n*(n-1))/2-cnt;
cout << ans << endl;
return 0;
}
最新文章
- Reactive Extensions(Rx) 学习
- [ZOJ 1005] Jugs (dfs倒水问题)
- 百家搜索:在网站中添加Google、百度等搜索引擎
- 浩顺AC671指纹考勤机二次开发(demo)
- PHP代码实现MySQL读写分离
- python包管理-distutils,setuptools,pip,virtualenv等介绍
- 一旦配置oracle em经验
- 浅析ArrayList,LinkedList的执行效率
- MySQL5.5多实例编译安装——多配置文件
- 【&#9733;】SPF(Dijkstra)算法完美教程
- hadoop2.6.0实践:004 启动伪分布式hadoop的进程
- 如何将composer设置为全局变量?
- zeptojs库解读1之整体框架
- c# 爬虫(一) HELLO WORLD
- golang之流程控制(注意点)
- 在Eclipse中配置Tomcat7.0
- WPF中使用WPFMediaKit视频截图案例
- Spring---bean的实例化
- PID控制及整定算法
- 规划ASM DISK GROUP、查看asm 磁盘当前状态、mount or dismount 磁盘组、检查磁盘组 metadata 的内部一致性