模串

思路分析

这道题其实就是一道纯模拟题，但我们需要仔细读清楚题意。

题目说的是什么呢？小歪有一个数字 $l$ ，初始为零。他依次读入 $n$ 个字符串，对于第 $i$ 个字符串，执行以下操作：

如果第 $i$ 个字符串的长度 $\text{len}_i$ 满足 $\text{len}_i \bmod m = i \bmod m$ ，则 $l$ 加一；
否则， $l$ 减一。

最终要求整个过程中 $l$ 能达到的最大值。

那思路就很直接了：逐个读入字符串，每读一个就判断长度模 $m$ 是否等于下标模 $m$ ，然后更新 $l$ ，同时维护一个最大值即可。

我们来手动模拟一下示例 1： $n=5, m=4$ ，字符串分别为 "d", "dd", "ddd", "ddddd", "d"。

$i$	字符串	$\text{len}_i$	$\text{len}_i \bmod 4$	$i \bmod 4$	是否相等	$l$
1	`d`	1	1	1	是	1
2	`dd`	2	2	2	是	2
3	`ddd`	3	3	3	是	3
4	`ddddd`	5	1	0	否	2
5	`d`	1	1	1	是	3

$l$ 的变化为 $0 \to 1 \to 2 \to 3 \to 2 \to 3$ ，最大值为 $3$ ，符合预期。

这道题没有什么算法上的难度，核心就是理解题意 + 正确模拟。注意下标从 $1$ 开始。

代码

C++
Java

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;

    int l = 0, ans = 0;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s;
        int len = (int)s.size();
        if (len % m == i % m) {
            l++;
        } else {
            l--;
        }
        ans = max(ans, l);
    }

    cout << ans << "\n";
    return 0;
}

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int l = 0, ans = 0;
        for (int i = 1; i <= n; i++) {
            String s = br.readLine();
            int len = s.length();
            if (len % m == i % m) {
                l++;
            } else {
                l--;
            }
            ans = Math.max(ans, l);
        }

        System.out.println(ans);
    }
}

复杂度分析

时间复杂度： $O(L)$ ，其中 $L$ 是所有字符串长度之和。读入每个字符串需要 $O(\text{len}_i)$ ，判断和更新只要 $O(1)$ 。
空间复杂度： $O(\max(\text{len}_i))$ ，只需要存储当前读入的一个字符串。