寒假训练第二周

whatdo / 2024-01-31 / 原文

G-天气预报_2022年中国高校计算机大赛-团队程序设计天梯赛（GPLT）上海理工大学校内选拔赛（重现赛）@IR101 (nowcoder.com)

用到算法（前缀和+尺取法）

题解：实现前缀和求一下某一个段里0和1的数量，分别记录下雨和不下雨天数

然后开始尺取

首先枚举终点一个for 类似双指针思想

然后一个k从前往后跑，直到不符合条件whlie结束，记录k-1个答案，因为符合条件是1到k所以有k-1个区间

然后继续枚举终点不断循环即可

#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <cmath>
//#define double long double
#define int long long
//#define endl '\n'
using namespace std;
const int N=1e6+7,M=1e1;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int mod=998244353;
typedef pair<int,int> PII;
int kmp(int a,int k,int p)
{
    int ans=1;
    while (k)
    {
        if(k&1) ans=ans*a%p;
        k>>=1;
        a=a*a%p;
    }
    return ans;
}  // 快速幂

int ans[N];
int ans1[N];
void solve()
{
    int n,a,b;
    cin>>n>>a>>b;
    string s;
    cin>>s;
    s=' '+s;
    for(int i=1;i<=n;i++)
    {
        if(s[i]=='1')
        {
            ans[i]=ans[i-1]+1;
            ans1[i]=ans1[i-1];
        }
        else
        {
            ans[i]=ans[i-1];
            ans1[i]=ans1[i-1]+1;
        }
    }
    int sum=0;
    int cnt=0;
    int k=1;
        for (int i = 1; i <= n; i++) {
            while (ans[i] - ans[k-1] >= b && ans1[i]-ans1[k-1]>=a && k<=i)
            {
                k++;
            }
            sum+=k-1;
            cnt=0;
        }
    if(a==0 &&b==0) sum++;
    cout<<sum<<endl;
}
signed main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int T=1;
//     cin>>T;
    while(T--){
        solve();
    }
    return 0;
}