题目大意

题目要求找出整数数组 a 中的所有连续子数组 [L, R]，使得在这个子数组中恰好有 k 个元素能被 x 整除。

题目意思也比较简单重点我们看到思路。

思路

1. 关键点分析

• 由于我们要统计恰好 k 个能被 x 整除的数的区间，我们方便统计可以将 a 转化为一个二进制数组 b，其中：
  • b[i] = 1 表示 a[i] 能被 x 整除。
  • b[i] = 0 表示 a[i] 不能被 x 整除。
• 然后，我们转换问题为：寻找恰好包含 k 个 1 的子数组数量。

2. 使用暴力的直接计算方法会超时

• 遍历所有可能的 [L, R] 子数组，然后计算 b[L] ~ b[R] 中 1 的个数，时间复杂度是 $O(n^2)$，显然对于 n 较大时（最大 $10^5$）会超时。

3. 使用“最多 K 个 1 的区间数”来求解

我们可以使用滑动窗口（双指针）的方式高效计算至多 k 个 1 的子数组数量。

使用滑动窗口求解最多有 k 个 1 的子数组：

• 维护一个窗口 [left, right]，其中窗口内 1 的个数不超过 k。

• right 指针向右移动，right每移动一次，新扩展的元素为1的话，更新窗口内 1 的个数

• 当窗口内 1 的个数超过 k 时，我们移动 left 指针，直到窗口内的 1 的个数不超过 k。此时，left 就是右端点 right 能够保持窗口内 1 的个数不超过 k 的最左位置。因此，对于每个 i，如果 left <= i <= right，那么区间 [i, right] 中的 1 的个数都不超过 k。

我们需要计算恰好有 k 个 1 的子数组数量。为了做到这一点，我们可以通过先计算**最多有 k 个 1的子数组数量，然后再减去 最多有k-1 个 1 的子数组数量。

这样做的原因是：

• 最多有 k 个 1的子数组包含了最多有 k-1 个 1的子数组和恰好有 k 个 1的子数组。

• 所以，当我们从最多 k 个 1的子数组数量中减去最多 k-1 个 1的子数组数量时，剩下的就是恰好有 k 个 1的子数组数量。

• 这样我们就得到想要的答案。

时间复杂度分析

• 转换 b 数组: O(n)
• 滑动窗口计算 countAtMostK(b, k): O(n)
• 计算 countAtMostK(b, k-1): O(n)
• 总时间复杂度: O(n)

相比暴力解法（$O(n^2)$），这个方法可以在 n=10^5 时高效运行！

贴上我们的ac代码仅供参考

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()

c++代码

#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;
}

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);
    }
}

本题为2024年10月26日中国电信机考原题

题目内容

给定一个整数序列 $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]$ 。