题目链接

模串

题目描述

小歪有一个初始为零的整数 。他会依次读入 个字符串。对于第 个字符串（ 从 1 到 ），其长度为 。根据以下规则来更新 的值：

  • 如果满足条件 ，则将 加一。
  • 否则，将 减一。

整个目标是求解这个过程中 能达到的最大值。

解题思路

本题的解法是一个直接的模拟。题目给出的规则清晰明了，我们只需要按照描述逐步实现即可。

算法实现

  1. 读入字符串数量 和模数 。
  2. 初始化一个变量 用来记录当前值，以及一个变量 用来记录整个过程中的最大值。
  3. 我们使用一个从 1 到 的循环来依次处理每个字符串。设循环变量为 。
  4. 在循环的第 次迭代中，读入第 个字符串 ，并获取其长度 。
  5. 判断核心条件 是否成立。
  6. 如果条件成立， 的值加 1。
  7. 如果条件不成立， 的值减 1。
  8. 每次更新 之后，我们都需要更新 ，即 max_l = max(max_l, l)。
  9. 当循环结束后， 中存储的就是整个过程中的最大值。将其输出即可。

注意事项

  • 的取值：题目中明确指出是“第 个字符串”，所以我们的循环计数器需要从 1 开始。
  • 数据范围： 和 的最大值为 ，所有字符串的总长度不超过 。这意味着一个 的循环，每次循环内部进行 的计算，加上读入字符串的时间，是完全可以接受的。为了防止潜在的读入性能问题，建议使用较快的 I/O 方式（如 C++ 的 cin.tie(NULL)，Java 的 BufferedReader，Python 的 sys.stdin.readline）。

代码

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    long long m;
    cin >> n >> m;

    long long l = 0;
    long long max_l = 0;

    // 循环从 1 到 n，对应题目的第 i 个字符串
    for (int i = 1; i <= n; ++i) {
        string s;
        cin >> s;
        long long len = s.length();
        
        if (len % m == i % m) {
            l++;
        } else {
            l--;
        }
        max_l = max(max_l, l);
    }

    cout << max_l << endl;

    return 0;
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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());
        long m = Long.parseLong(st.nextToken());

        long l = 0;
        long max_l = 0;

        // 循环从 1 到 n，对应题目的第 i 个字符串
        for (int i = 1; i <= n; i++) {
            String s = br.readLine();
            long len = s.length();

            if (len % m == i % m) {
                l++;
            } else {
                l--;
            }
            max_l = Math.max(max_l, l);
        }

        System.out.println(max_l);
    }
}

import sys

def solve():
    n, m = map(int, sys.stdin.readline().split())
    
    l = 0
    max_l = 0
    
    # 循环从 1 到 n，对应题目的第 i 个字符串
    for i in range(1, n + 1):
        s = sys.stdin.readline().strip()
        s_len = len(s)
        
        if s_len % m == i % m:
            l += 1
        else:
            l -= 1
        max_l = max(max_l, l)
        
    print(max_l)

solve()

算法及复杂度

  • 算法：模拟
  • 时间复杂度：读入所有字符串的总时间复杂度为 ，模拟过程的复杂度为 。因此，总时间复杂度为 。
  • 空间复杂度：我们只需要常数个变量来维护状态，每次读入的字符串可以被覆盖。因此，空间复杂度为 ，即最长字符串的长度。