题意:给定一个字符串,求有多少个奇数子串和多少偶数子串为 “回文串” 这边回文串很特殊之含有 ab 两种字母 而且 相邻的字母相同则消去一个 一直到不存在相邻的相同。
思路: 在这种串中 ,消到最后 一定是 abababababa。。。 或者 bababababab。。。 那么 只要头尾一样 那么这个串 一定是 回文串。
那么 只需要 统计下 奇数位上 和 偶数位上a b个数就能直接计算。 一个在奇数位一个在偶数为 长度位偶数, 两个都在 奇数位 或者偶数位 则长度为奇数。
#include <iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#define LL long long
#define f(x) ((x)*(x+1)/2)
using namespace std;
char s[100050];
int main() {
LL odda,oddb,evena,evenb;
odda=oddb=evena=evenb=0;
scanf(" %s",s);
int len=strlen(s);
for(int i=0;i<len;++i)
{
if(s[i]=='a')
{
if(i&1)
odda++;
else
evena++;
}
else
{
if(i&1)
oddb++;
else
evenb++;
} }
LL ans1=odda*evena+oddb*evenb;
LL ans2=f(odda)+f(oddb)+f(evena)+f(evenb);
printf("%I64d %I64d\n",ans1,ans2);
return 0;
}
codeforces 451D Count Good Substrings的更多相关文章
-
codeforces D. Count Good Substrings
http://codeforces.com/contest/451/problem/D 题意:给你一个字符串,然后找出奇数和偶数长度的子串的个数,这些字串符合,通过一些连续相同的字符合并后是回文串. ...
-
Codeforces Round #258 (Div. 2) D. Count Good Substrings 水题
D. Count Good Substrings 题目连接: http://codeforces.com/contest/451/problem/D Description We call a str ...
-
Codeforces Round #258 (Div. 2) D. Count Good Substrings —— 组合数学
题目链接:http://codeforces.com/problemset/problem/451/D D. Count Good Substrings time limit per test 2 s ...
-
CF451D Count Good Substrings (DP)
Codeforces Round #258 (Div. 2) Count Good Substrings D. Count Good Substrings time limit per test 2 ...
-
【Leetcode_easy】696. Count Binary Substrings
problem 696. Count Binary Substrings 题意:具有相同个数的1和0的连续子串的数目: solution1:还不是特别理解... 遍历元数组,如果是第一个数字,那么对应 ...
-
Codeforces 451D
题目链接 D. Count Good Substrings time limit per test 2 seconds memory limit per test 256 megabytes inpu ...
-
Codeforces Round #258 D Count Good Substrings --计数
题意:由a和b构成的字符串,如果压缩后变成回文串就是Good字符串.问一个字符串有几个长度为偶数和奇数的Good字串. 分析:可知,因为只有a,b两个字母,所以压缩后肯定为..ababab..这种形式 ...
-
【Codeforces 258D】 Count Good Substrings
[题目链接] http://codeforces.com/contest/451/problem/D [算法] 合并后的字符串一定是形如"ababa","babab&qu ...
-
[LeetCode] Count Binary Substrings 统计二进制子字符串
Give a string s, count the number of non-empty (contiguous) substrings that have the same number of ...
随机推荐
-
几种I/O模型功能和性能对比
对比图 同步阻塞I/O服务端通信模型(一客户端一线程) 伪异步I/O服务端通信模型(M:N) NIO服务端和客户端通信时序图
-
Handler Should be static or leaks Occur?
解决办法: public class SampleActivity extends Activity { /** * Instances of static inner classes do not ...
-
Tlist
Tlist (Classes.pas) 在我刚开始接触TList的时候,TList搞得我迷雾重重,都是Capacity属性惹的祸.我查了Delphi的帮助,它说Capacity是TList的最大容量, ...
-
Robot Framework-DatabaseLibrary数据库(MySql)
Robot Framework-Mac版本安装 Robot Framework-Windows版本安装 Robot Framework-工具简介及入门使用 Robot Framework-Databa ...
-
linux 内核驱动--Platform Device和Platform_driver注册过程
linux 内核驱动--Platform Device和Platform_driver注册过程 从 Linux 2.6 起引入了一套新的驱动管理和注册机制 :Platform_device 和 Pla ...
-
BZOJ2802: [Poi2012]Warehouse Store
2802: [Poi2012]Warehouse Store Time Limit: 10 Sec Memory Limit: 64 MBSec Special JudgeSubmit: 121 ...
-
mac系统不能使用127.0.0.2的解决方案
英语学得不好,国外这位大神的精彩解释不是特能看的懂.我模仿的试了一下. 解决方案: 1.打开mac终端 2.输入:sudo ifconfig lo0 alias 127.1.1.1 netmask 0 ...
-
Oracle多行记录合并的几种方法
今天正好遇到需要做这个功能,顺手搜了一下网络,把几种方法都列出来,方便以后参考. 1 什么是合并多行字符串(连接字符串)呢,例如: SQL> desc test; Name Type Nulla ...
-
一道简单的CTF登录题题解
一.解题感受 这道题50分,在实验吧练习场算比较高分,而且通过率只有14%,比较低的水平. 看到这两个数据,一开始就心生惬意,实在不应该呀! 也是因为心态原因,在发现test.php之后,自以为在SQ ...
-
虚拟机中安装Linux系统
本教程的运行环境:Windows 10 , 虚拟机 VirtualBox,Ubuntu 16.04 1.准备 下载 VirtualBox 下载OVA镜像64位 http://releases.ubun ...