AtCoder - 4496 G - k-DMC

佚名 5年前 (2019-11-25) 算法 1986人围观抢沙发百度已收录

AtCoder - 4496 G - k-DMC

题目

长度为n的字符串，q次查询,问“DMC”（不要求连续）在字符串中出现的次数，其中D和M的距离不超过k。

错误思路

通过遍历字符串中的每一个“M”，再移动窗口，处理左右“D”、“C”的数量。（TLE）

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

题解

滑动窗口，维护当前窗口中"D"、“M”、“DM”的数量，遇“C”则ans加上"DM"的数量。

代码

#include <cstdio>
#include <iostream>
#include <vector>
#include <set>
#include <ctime>
#include <cstdlib>
using namespace std;
typedef long long ll;
int main(){
    int n,q;
    string s;
    cin>>n>>s>>q;
    while (q--) {
        int k;cin>>k;
        ll d=0,m=0,dm=0,dmc=0,i;
        for(i=0;i<k;i++){
            switch (s[i]) {
                case 'D':
                    d++;
                    break;
                    
                case 'M':
                    dm+=d;
                    m++;
                    break;
                    
                case 'C':
                    dmc+=dm;
            }
        }
        for(;i<n;i++){
            switch (s[i-k]) {
                case 'D':
                    d--;
                    dm-=m;
                    break;
                    
                case 'M':
                    m--;
            }
            switch (s[i]) {
                case 'D':
                    d++;
                    break;
                    
                case 'M':
                    dm+=d;
                    m++;
                    break;
                    
                case 'C':
                    dmc+=dm;
            }
        }
        printf("%lld\n",dmc);
    }
}