解题思路

• 题意：给长度为 n 的数字串 s（只含 '0'~'9'），给定一个偶数 k。若某个长度为 k 的子串的前 k/2 个数字之和等于后 k/2 个数字之和，则该子串为“幸运子串”。统计所有幸运子串个数。

• 算法：前缀和 + 滑动窗口 将字符转为数字，建立前缀和数组 pre[i] 表示前 i 个数字之和。任意窗口 [l, l+k-1]：

  • 前半和 sum1 = pre[l+k/2] - pre[l]
  • 后半和 sum2 = pre[l+k] - pre[l+k/2]
  • 若 sum1 == sum2，答案加一。 依次枚举起点 l = 0..n-k 即可。

• 核心实现：一次构建前缀和，O(1) 时间求每个窗口两半的和，单次测试整体 O(n)。

复杂度分析

• 时间复杂度：对每组数据为 O(n)（构建前缀和 O(n)，枚举窗口 O(n)；题目保证所有测试的 n 之和 ≤ 1e6）。
• 空间复杂度：O(n)（前缀和数组）。

代码实现

Python

# -*- coding: utf-8 -*-
import sys

def count_lucky(n, k, s):
    # 将字符转为对应的数字
    a = [ord(c) - 48 for c in s]
    # 前缀和，pre[0] = 0
    pre = [0] * (n + 1)
    for i in range(n):
        pre[i + 1] = pre[i] + a[i]
    # 枚举每个长度为 k 的窗口
    half = k // 2
    ans = 0
    for l in range(0, n - k + 1):
        sum1 = pre[l + half] - pre[l]
        sum2 = pre[l + k] - pre[l + half]
        if sum1 == sum2:
            ans += 1
    return ans

def main():
    data = sys.stdin.read().strip().split()
    t = int(data[0])
    idx = 1
    out_lines = []
    for _ in range(t):
        n = int(data[idx]); k = int(data[idx + 1]); idx += 2
        s = data[idx].strip(); idx += 1
        out_lines.append(str(count_lucky(n, k, s)))
    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    main()

Java

// 注意：ACM 风格，类名为 Main
import java.io.*;
import java.util.*;

public class Main {
    // 功能函数：统计幸运子串数量
    static int countLucky(int n, int k, String s) {
        int[] pre = new int[n + 1]; // 前缀和
        for (int i = 0; i < n; i++) {
            pre[i + 1] = pre[i] + (s.charAt(i) - '0');
        }
        int half = k / 2;
        int ans = 0;
        for (int l = 0; l + k <= n; l++) {
            int sum1 = pre[l + half] - pre[l];        // 前半部分和
            int sum2 = pre[l + k] - pre[l + half];    // 后半部分和
            if (sum1 == sum2) ans++;
        }
        return ans;
    }

    public static void main(String[] args) throws Exception {
        // 依据数据量，使用 BufferedReader + StringTokenizer 读取
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        int t = Integer.parseInt(st.nextToken());
        StringBuilder sb = new StringBuilder();
        for (int cas = 0; cas < t; cas++) {
            // 读取 n, k
            st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            int k = Integer.parseInt(st.nextToken());
            // 读取字符串 s
            String s = br.readLine().trim();
            sb.append(countLucky(n, k, s)).append('\n');
        }
        System.out.print(sb.toString());
    }
}

C++

// ACM 风格：主函数读入与输出，功能写在外部函数
#include <bits/stdc++.h>
using namespace std;

// 统计幸运子串数量的函数
long long countLucky(const string& s, int k) {
    int n = (int)s.size();
    vector<int> pre(n + 1, 0);               // 前缀和
    for (int i = 0; i < n; ++i) pre[i + 1] = pre[i] + (s[i] - '0');
    int half = k / 2;
    long long ans = 0;
    for (int l = 0; l + k <= n; ++l) {
        int sum1 = pre[l + half] - pre[l];        // 前半部分和
        int sum2 = pre[l + k] - pre[l + half];    // 后半部分和
        if (sum1 == sum2) ++ans;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t; 
    if (!(cin >> t)) return 0;
    while (t--) {
        int n, k; 
        cin >> n >> k;
        string s; 
        cin >> s;            // 只含数字字符
        cout << countLucky(s, k) << "\n";
    }
    return 0;
}

题目内容

给定一个仅包含数字字符的字符串$s$，长度为$n$ 。又给定一个偶数$k$ ，满足$2≤k≤n$ 。

我们称字符串$s$中所有长度为$k$ 的子串为幸运子串，当且仅当该子串的前$k/2$个字符对应的数字之和等于后$k/2$个字符对应的数字之和。

请计算并输出字符串$s$中幸运子串的总数。

【名词解释】

• 子串：从字符串中连续选取一段字符（可以是整个字符串，也可以是空串）得到的新字符串；

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$t(1＜t＜10^4)$代表测试用例数。

每组测试数据描述如下：

• 在一行上输入两个整数$n,k$ ($2≤n≤10^6$；$2≤k≤n$；$k$为偶数)；
• 在一行上输入一个长度为$n$ 、仅由数字字符 "$0$" 到 "$9$" 构成的字符串 。

除此之外，保证所有测试用例中$n$ 的总和不超过 $10^6$。

输出描述

对于每个测试用例，新起一行，输出一个整数，表示字符串 $s$中幸运子串的数量。

样例1

输入

2
4 2
1122
6 4
121212

输出

2
3