codeforces 451D Count Good Substrings

时间:2022-04-17 08:38:07

题意:给定一个字符串,求有多少个奇数子串和多少偶数子串为 “回文串”   这边回文串很特殊之含有  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的更多相关文章

  1. codeforces D&period; Count Good Substrings

    http://codeforces.com/contest/451/problem/D 题意:给你一个字符串,然后找出奇数和偶数长度的子串的个数,这些字串符合,通过一些连续相同的字符合并后是回文串. ...

  2. Codeforces Round &num;258 &lpar;Div&period; 2&rpar; D&period; Count Good Substrings 水题

    D. Count Good Substrings 题目连接: http://codeforces.com/contest/451/problem/D Description We call a str ...

  3. Codeforces Round &num;258 &lpar;Div&period; 2&rpar; D&period; Count Good Substrings —— 组合数学

    题目链接:http://codeforces.com/problemset/problem/451/D D. Count Good Substrings time limit per test 2 s ...

  4. CF451D Count Good Substrings (DP)

    Codeforces Round #258 (Div. 2) Count Good Substrings D. Count Good Substrings time limit per test 2 ...

  5. 【Leetcode&lowbar;easy】696&period; Count Binary Substrings

    problem 696. Count Binary Substrings 题意:具有相同个数的1和0的连续子串的数目: solution1:还不是特别理解... 遍历元数组,如果是第一个数字,那么对应 ...

  6. Codeforces 451D

    题目链接 D. Count Good Substrings time limit per test 2 seconds memory limit per test 256 megabytes inpu ...

  7. Codeforces Round &num;258 D Count Good Substrings --计数

    题意:由a和b构成的字符串,如果压缩后变成回文串就是Good字符串.问一个字符串有几个长度为偶数和奇数的Good字串. 分析:可知,因为只有a,b两个字母,所以压缩后肯定为..ababab..这种形式 ...

  8. 【Codeforces 258D】 Count Good Substrings

    [题目链接] http://codeforces.com/contest/451/problem/D [算法] 合并后的字符串一定是形如"ababa","babab&qu ...

  9. &lbrack;LeetCode&rsqb; Count Binary Substrings 统计二进制子字符串

    Give a string s, count the number of non-empty (contiguous) substrings that have the same number of ...

随机推荐

  1. 几种I&sol;O模型功能和性能对比

    对比图 同步阻塞I/O服务端通信模型(一客户端一线程) 伪异步I/O服务端通信模型(M:N) NIO服务端和客户端通信时序图

  2. Handler Should be static or leaks Occur?

    解决办法: public class SampleActivity extends Activity { /** * Instances of static inner classes do not ...

  3. Tlist

    Tlist (Classes.pas) 在我刚开始接触TList的时候,TList搞得我迷雾重重,都是Capacity属性惹的祸.我查了Delphi的帮助,它说Capacity是TList的最大容量, ...

  4. Robot Framework-DatabaseLibrary数据库&lpar;MySql&rpar;

    Robot Framework-Mac版本安装 Robot Framework-Windows版本安装 Robot Framework-工具简介及入门使用 Robot Framework-Databa ...

  5. linux 内核驱动--Platform Device和Platform&lowbar;driver注册过程

    linux 内核驱动--Platform Device和Platform_driver注册过程 从 Linux 2.6 起引入了一套新的驱动管理和注册机制 :Platform_device 和 Pla ...

  6. BZOJ2802&colon; &lbrack;Poi2012&rsqb;Warehouse Store

    2802: [Poi2012]Warehouse Store Time Limit: 10 Sec  Memory Limit: 64 MBSec  Special JudgeSubmit: 121  ...

  7. mac系统不能使用127&period;0&period;0&period;2的解决方案

    英语学得不好,国外这位大神的精彩解释不是特能看的懂.我模仿的试了一下. 解决方案: 1.打开mac终端 2.输入:sudo ifconfig lo0 alias 127.1.1.1 netmask 0 ...

  8. Oracle多行记录合并的几种方法

    今天正好遇到需要做这个功能,顺手搜了一下网络,把几种方法都列出来,方便以后参考. 1 什么是合并多行字符串(连接字符串)呢,例如: SQL> desc test; Name Type Nulla ...

  9. 一道简单的CTF登录题题解

    一.解题感受 这道题50分,在实验吧练习场算比较高分,而且通过率只有14%,比较低的水平. 看到这两个数据,一开始就心生惬意,实在不应该呀! 也是因为心态原因,在发现test.php之后,自以为在SQ ...

  10. 虚拟机中安装Linux系统

    本教程的运行环境:Windows 10 , 虚拟机 VirtualBox,Ubuntu 16.04 1.准备 下载 VirtualBox 下载OVA镜像64位 http://releases.ubun ...