E卷-最长连续方波信号(100分)

最长连续方波信号

问题描述

输入一串方波信号，求取最长的完全连续交替方波信号，并将其输出。如果有相同长度的交替方波信号，输出任一即可。方波信号高位用 1 标识，低位用 0 标识。

说明：

1. 一个完整的信号一定以 0 开始然后以 0 结尾，即 010 是一个完整信号，但 101，1010，0101 不是。
2. 输入的一串方波信号是由一个或多个完整信号组成。
3. 两个相邻信号之间可能有 0 个或多个低位，如 0110010，011000010。
4. 同一个信号中可以有连续的高位，如 01110101011110001010，前 14 位是一个具有连续高位的信号。
5. 完全连续交替方波是指 10 交替，如 01010 是完全连续交替方波，0110 不是。

示意图：

连续方波信号：   0   1   1   1   0   1   0   1   0   0   0   1   0   1   0   0   0
                |___|¯¯¯¯¯¯¯|___|¯|___|¯|___|_______|¯|___|¯|___|_______|
二进制表示：    0 1 1 1 0 1 0 1 0 0 0 1 0 1 0 0 0

输入格式

输入一行，为信号字符串（长度 且 ）。 注：输入总是合法的，不用考虑异常情况。

输出格式

输出一行，为最长的完全连续交替方波信号串。 若不存在完全连续交替方波信号串，输出 -1。

样例输入

00101010101100001010010

样例输出

01010

样例解释

输入信号串中有三个信号：

1. 0 010101010110（第一个信号段）
2. 00 01010（第二个信号段）
3. 010（第三个信号段）

第一个信号虽然有交替的方波信号段，但出现了 11 部分的连续高位，不算完全连续交替方波。在剩下的连续方波信号串中，01010 最长。

数据范围

• 输入字符串长度：

题解

这道题的核心在于识别和提取完全连续交替的方波信号。解题思路如下：

1. 遍历输入字符串，将其分割成多个以 0 开始和结束的信号段。
2. 对每个信号段，检查是否为完全连续交替的方波信号。
3. 记录并更新最长的完全连续交替方波信号。

关键点在于理解什么是有效的信号段和完全连续交替的方波：

• 有效信号段：以 0 开始，以 0 结束。
• 完全连续交替方波：形如 (01)+ 0 的模式。

使用正则表达式 ^(01)+0$ 可以很方便地匹配完全连续交替的方波信号。时间复杂度为 O(n)，其中 n 是输入字符串的长度。考虑到输入长度最大为 1024，这个解法的效率是可以接受的。

参考代码

• Python

import re

def find_longest_alternating_wave(signal):
    # 正则表达式模式，匹配完全连续交替的方波信号
    pattern = re.compile(r'^(01)+0$')
    
    max_length = 0
    longest_wave = '-1'
    current_wave = ''
    
    for char in signal:
        if char == '0':
            if current_wave and current_wave[-1] == '0':
                # 检查当前波形是否是完全连续交替的，并更新最长波形
                if pattern.match(current_wave) and len(current_wave) > max_length:
                    max_length = len(current_wave)
                    longest_wave = current_wave
                current_wave = ''
        current_wave += char
    
    # 检查最后一个波形
    if pattern.match(current_wave) and len(current_wave) > max_length:
        longest_wave = current_wave
    
    return longest_wave

# 读取输入
signal = input().strip()

# 查找最长的完全连续交替方波信号并输出
print(find_longest_alternating_wave(signal))

• C

// 部分通过，后续会完善
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define MAX_LENGTH 2025  // 最大输入长度 + 1 (用于存储字符串结束符)

// 检查是否为完全连续交替的方波信号
int is_alternating_wave(const char* wave) {
    int len = strlen(wave);
    if (wave[0] != '0' || wave[len-1] != '0') return 0;
    for (int i = 1; i < len - 1; i++) {
        if (wave[i] == wave[i-1]) return 0;
    }
    return 1;
}

// 查找最长的完全连续交替方波信号
void find_longest_alternating_wave(const char* signal, char* result) {
    int max_length = 0;
    char current_wave[MAX_LENGTH] = {0};
    int current_index = 0;
    
    for (int i = 0; signal[i]; i++) {
        if (signal[i] == '0' && current_index > 0 && current_wave[current_index-1] == '0') {
            if (is_alternating_wave(current_wave) && current_index > max_length) {
                max_length = current_index;
                strcpy(result, current_wave);
            }
            current_index = 0;
        }
        current_wave[current_index++] = signal[i];