题面描述

给定一个整数序列 $a$，以及两个整数 $x$ 和 $k$。

求出有多少个区间 $[L, R]$（$L \leq R$），使得该区间中恰好有 $k$ 个 $a_i$（$L \leq i \leq R$）满足 $a_i$ 能被 $x$ 整除。

思路

双指针，计算“至多有 $k$ 个 $1$”的子数组数量，再减去“至多有 $k-1$ 个 $1$”的子数组数量，即得到恰好有 $k$ 个 $1$ 的子数组数量。

具体实现

1. 函数设计：实现一个辅助函数 countAtMostK，用于统计二进制数组中至多有 $k$ 个 $1$ 的子数组数量。
2. 滑动窗口：
   • 使用两个指针 left 和 right，表示当前窗口的左右边界。
   • 当窗口内的 $1$ 的数量超过 $k$ 时，移动左指针以缩小窗口，直到窗口内的 $1$ 数量不超过 $k$。
   • 每移动一次右指针，就累加当前窗口中满足条件的子数组数量。
3. 主函数逻辑：
   • 将原数组映射为二进制数组。
   • 计算 countAtMostK(b, k) - countAtMostK(b, k-1) 即为答案。

cpp

#include <bits/stdc++.h>
using namespace std;

// 统计二进制数组中至多有 k 个 1 的子数组数量
long long countAtMostK(const vector<int>& b, int k) {
    int left = 0;
    long long result = 0;
    int count = 0;
    for(int right = 0; right < b.size(); ++right){
        if(b[right] == 1){
            count++;
        }
        while(count > k){
            if(b[left] == 1){
                count--;
            }
            left++;
        }
        result += (right - left + 1);
    }
    return result;
}

int main(){
    // 读取第一行，整数序列 a
    string line;
    getline(cin, line);
    vector<int> a;
    int num;
    stringstream ss(line);
    while(ss >> num){
        a.push_back(num);
    }
    
    // 读取第二行，x 和 k
    int x, k;
    cin >> x >> k;
    
    // 将 a 映射为二进制数组 b，1 表示能被 x 整除，0 否则
    vector<int> b(a.size(), 0);
    for(int i = 0; i < a.size(); ++i){
        if(a[i] % x == 0){
            b[i] = 1;
        }
    }
    
    // 计算答案
    long long total = countAtMostK(b, k);
    if(k > 0){
        total -= countAtMostK(b, k-1);
    }
    cout << total;
    return 0;
}

python

def countAtMostK(b, k):
    left = 0
    result = 0
    count = 0
    for right in range(len(b)):
        if b[right] == 1:
            count += 1
        while count > k:
            if b[left] == 1:
                count -= 1
            left += 1
        result += (right - left + 1)
    return result

def main():
    import sys
    # 读取第一行，整数序列 a
    a = list(map(int, sys.stdin.readline().split()))
    # 读取第二行，x 和 k
    x, k = map(int, sys.stdin.readline().split())
    # 将 a 映射为二进制数组 b，1 表示能被 x 整除，0 否则
    b = [1 if num % x == 0 else 0 for num in a]
    # 计算答案
    total = countAtMostK(b, k)
    if k > 0:
        total -= countAtMostK(b, k-1)
    print(total)

if __name__ == "__main__":
    main()

java

import java.util.*;
import java.io.*;

public class Main {
    // 统计二进制数组中至多有 k 个 1 的子数组数量
    public static long countAtMostK(int[] b, int k){
        int left = 0;
        long result = 0;
        int count = 0;
        for(int right = 0; right < b.length; right++){
            if(b[right] == 1){
                count++;
            }
            while(count > k){
                if(b[left] == 1){
                    count--;
                }
                left++;
            }
            result += (right - left + 1);
        }
        return result;
    }
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 读取第一行，整数序列 a
        String line = br.readLine();
        String[] tokens = line.trim().split("\\s+");
        int n = tokens.length;
        int[] a = new int[n];
        for(int i = 0; i < n; i++) a[i] = Integer.parseInt(tokens[i]);
        // 读取第二行，x 和 k
        line = br.readLine();
        tokens = line.trim().split("\\s+");
        int x = Integer.parseInt(tokens[0]);
        int k = Integer.parseInt(tokens[1]);
        // 将 a 映射为二进制数组 b，1 表示能被 x 整除，0 否则
        int[] b = new int[n];
        for(int i = 0; i < n; i++){
            if(a[i] % x == 0){
                b[i] = 1;
            }
        }
        // 计算答案
        long total = countAtMostK(b, k);
        if(k > 0){
            total -= countAtMostK(b, k-1);
        }
        System.out.println(total);
    }
}

题目内容

给定一个整数序列 $a$ ，以及 $2$ 个整数 $x$ ，$k$ 。

求出有多少区间$[L, R](L <= R)$，使得该区间中恰好有 $k$ 个$a_i(L <= i <= R)$满足 $a_i$ 能被 $x$ 整除。

时间限制：1000ms

内存限制：262mb

输入描述

$1 <= length(a), x <= 10^5$ $0 <= k <= 10^5$

输出描述

返回答案

样例1

输入

1 2 3 4
2 1

输出

6

说明

总共有 $6$ 个区间，满足恰好有 $1$ 个数被 $2$ 整除。

$[1,2],[1,3],[2,2],[2,3],[3,4],[4,4]$ 。