CF|Codeforces 451D Count Good Substrings(组合数学)
题目链接：Codeforces 451D Count Good Substrings
【CF|Codeforces 451D Count Good Substrings(组合数学)】 题目大意：定义good string，就是就一个字符串的连续相同字符用一个该字符替代后，形成回文串的字符串。现在给出一个字符串，问说该字符串的子串中，为good string的串有多少个，分长度为奇数和偶数的输出。
解题思路：因为字符串的组成为a和b，所以只要是头尾相同的子串都是满足的。所以我们计算在奇数和偶数位置的奇数个数和偶数个数即可，然后用组合数学求出答案。
#include
#include
#include using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
char str[maxn];
ll cal (ll u) {
return u * (u-1) / 2;
}int main () {
ll oddA = 0, evenA = 0;
ll oddB = 0, evenB = 0;
scanf("%s", str);
int len = strlen(str);
for (int i = 0;
i < len;
i++) {
if (str[i] == 'a') {
if (i&1)
oddA++;
else
evenA++;
} else {
if (i&1)
oddB++;
else
evenB++;
}
}ll even = oddA * evenA + oddB * evenB;
ll odd = cal(oddA) + cal(evenA) + cal(oddB) + cal(evenB) + len;
printf("%lld %lld\n", even, odd);
return 0;
} 推荐阅读
- 2019年PB|2019年PB County Senior Open, 保龄生涯（64）
- CountDownLatch-线程并发的发令枪
- SQL优化（二）|SQL优化（二） 快速计算Distinct Count
- 24、CountIF函数和CountIFS函数
- python基础-numpy.bincount详解
- 【JUC】CountDownLatch共享节点队列
- HDU 5528【2015长春现场赛 B】 Count a * b
- codeforces B. Young Explorers
- codeforces C. Mere Array
- codeforces D. Omkar and Bed Wars