首页 > 代码库 > CodeForces 451D Count Good Substrings
CodeForces 451D Count Good Substrings
哎，最近都在做图论，没有练DP，现在一遇到DP就不会了= =
因为有合并这个操作，所以只要是首位相同的字符串肯定是能够构成good串的，那么只要统计在奇数位上出现的0，1的个数和偶数位数，随便递推一下就出来了
#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>using namespace std;typedef long long LL;const int maxn = 100005;LL cntodd[2],cnteven[2];char buf[maxn];int main() { scanf("%s",buf + 1); int len = strlen(buf + 1); LL sumodd = 0,sumeven = 0; for(int i = 1;i <= len;i++) { int now = buf[i] - ‘a‘; if(i & 1) cntodd[now]++; else cnteven[now]++; if(i & 1) { sumodd += cntodd[now]; sumeven += cnteven[now]; } else { sumodd += cnteven[now]; sumeven += cntodd[now]; } } cout << sumeven << " " << sumodd << endl; return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。