题解

题面描述

给定一条石砖铺成的小路，该小路上有 $n$ 块石砖，每块石砖最多可以坐下一只青蛙，用只包含 $0$ 和 $1$ 的字符串 $s$ 表示：

• 当 $s_i = 1$ 时，代表从左起第 $i$ 块石砖上有一只青蛙；
• 当 $s_i = 0$ 时，代表该石砖上没有青蛙。

如果这条小路上最长连续坐着青蛙的数量正好等于 $9$，则认为这条小路是幸运的；否则是不幸运的。对于每组测试数据，输出结果为 $lucky$ 或 $unlucky$。

思路

1. 输入

   • 首先读入测试数据的组数 $T$。
   • 对于每组测试数据，读取石砖数 $n$ 以及一个长度为 $n$ 的字符串 $s$。

2. 处理过程

   • 遍历字符串 $s$，统计所有连续 $1$ 的长度，并记录其中的最大值 $maxCount$。
   • 每当遇到 $1$ 则连续计数器加一；若遇到 $0$ 则重置计数器为 $0$。
   • 遍历结束后，判断 $maxCount$ 是否等于 $9$。

3. 输出

   • 如果 $maxCount = 9$，则输出 $lucky$；否则输出 $unlucky$。

代码分析

1. 时间复杂度：
   算法仅需一次遍历字符串 $s$，因此时间复杂度为 $O(n)$，其中 $n$ 为字符串的长度。

2. 空间复杂度：
   只需常数级别的额外空间，因此空间复杂度为 $O(1)$。

3. 问题本质：
   该题目本质上考察对字符串的简单遍历与状态统计，核心在于如何正确统计连续 $1$ 的数量以及注意边界的重置问题，保证统计到所有可能的连续区间。

C++

#include <iostream>
#include <string>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T; // 测试用例组数
    cin >> T;
    while(T--) {
        int n; // 石砖数量
        cin >> n;
        string s; // 表示石砖上是否有青蛙的字符串
        cin >> s;
        int current = 0; // 当前连续 '1' 的数量
        int maxCount = 0; // 最大连续 '1' 的数量
        
        for (int i = 0; i < n; i++) {
            if(s[i] == '1') { // 如果当前石砖上有青蛙，则连续计数器加一
                current++;
                if(current > maxCount) {
                    maxCount = current; // 更新最大值
                }
            } else { // 遇到 '0' 时重置连续计数器
                current = 0;
            }
        }
        
        // 检查是否存在连续 '1' 的区间长度刚好为 9
        if(maxCount == 9) {
            cout << "lucky" << "\n";
        } else {
            cout << "unlucky" << "\n";
        }
    }
    return 0;
}

Python

# 读取测试数据的组数
T = int(input())
for _ in range(T):
    n = int(input())  # 石砖数量
    s = input().strip()  # 表示石砖上是否有青蛙的字符串
    
    current = 0  # 当前连续 '1' 的数量
    max_count = 0  # 最大连续 '1' 的数量
    
    # 遍历字符串
    for char in s:
        if char == '1':  # 如果石砖上有青蛙，连续计数器加一
            current += 1
            if current > max_count:
                max_count = current  # 更新最大值
        else:  # 如果石砖上没有青蛙，则重置计数器
            current = 0
    
    # 判断是否连续 '1' 的数量正好为 9
    if max_count == 9:
        print("lucky")
    else:
        print("unlucky")

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt(); // 测试用例组数
        while(T-- > 0) {
            int n = sc.nextInt(); // 石砖数量
            String s = sc.next(); // 表示石砖上是否有青蛙的字符串
            int current = 0; // 当前连续 '1' 的数量
            int maxCount = 0; // 最大连续 '1' 的数量

            // 遍历字符串
            for (int i = 0; i < n; i++) {
                if(s.charAt(i) == '1') { // 石砖上有青蛙，计数器加一
                    current++;
                    if(current > maxCount) {
                        maxCount = current; // 更新最大值
                    }
                } else { // 石砖上没有青蛙，重置计数器
                    current = 0;
                }
            }
            
            // 判断最长连续 '1' 的数量是否正好为 9
            if(maxCount == 9) {
                System.out.println("lucky");
            } else {
                System.out.println("unlucky");
            }
        }
        sc.close();
    }
}

题目内容

多多路过了一个湖泊，湖泊旁有一条小路上坐着一群青蛙。这条小路有$n$, 个石砖按顺序排列,每个石砖上最多可以坐下一只青蛙.可以用仅包含$0$ 和$1$的字符串s来表示这条小路。其中$s_i(1≤i≤n)$等于$1$时表示第 左起$i$块石砖上坐着青蛙，等于$0$时则表示没有

如果这条路上最长的相邻青蛙数正好等于$9$，那么则认为这条小路是幸运的。多多想要知道这条小路是不是幸运的,如果是则输出$lucky$否则输 出 $unlucky$

输入描述

第一行,包含一个正整数T(1≤T≤10)代表测试数据的组数。

对于每组测试数据，分别有两行：

第一行，仅有一个正整数$n(1≤n≤10^5)$,表示这条小路的石砖数量。

第二行，有一个仅由$0$和$1$组成，长度为$n$字符串$s$，其中$s_i(1≤i≤n)$表示从坐起第$i$块砖是否有青蛙，等于$1$时有，等于$0$时没有。

输出描述

对于每组数据,如果这条小路是幸运的则输出$lucky$否则输出$unlucky$

样例1

输入

2
10
1110110011
11
11111111101

输出

unlucky
lucky