AT1202Contest_h 题解

题意理解

给定两个序列 A 和 B，长度分别为 N 和 M。需要找出有多少个 A 的长度为 M 的连续子序列 C，满足以下条件：

可以将 B 和 C 中所有值为 0 的元素替换成任意正实数
将 C 的所有元素乘以某个正实数 t
经过上述操作后，B 和 C 能够完全相等

核心思路

关键观察：如果两个序列在替换 0 值后能通过缩放变得相等，那么它们非零元素的比值必须相同。

对于每个可能的子序列 C = (A[i], A[i+1], ..., A[i+M-1])，我们需要检查它是否能与 B 匹配。

匹配规则

对于 B 和 C 的每一对对应位置 (B[j], C[j])：

B[j] = 0 的情况
- C[j] 可以是任意值（包括 0 或非 0）
- 因为我们可以把 B[j] 替换成任意正实数来匹配
B[j] ≠ 0 且 C[j] = 0 的情况
- 这种情况不匹配
- 因为无论如何缩放，0 都无法变成非零值
B[j] ≠ 0 且 C[j] ≠ 0 的情况
- 计算比值 ratio = B[j] / C[j]
- 这个比值就是缩放系数 t
- 所有这样的位置计算出的比值必须相同

算法流程

CPP

对于每个起始位置 i (从 0 到 N-M)：
    初始化 ratio = -1（表示还未找到比值）
    valid = true

    对于每个位置 j (从 0 到 M-1)：
        如果 B[j] = 0：
            跳过这个位置（C[j] 可以是任意值）
        否则（B[j] ≠ 0）：
            如果 C[j] = 0：
                valid = false，跳出循环
            否则（C[j] ≠ 0）：
                计算 current_ratio = B[j] / C[j]
                如果这是第一个比值：
                    ratio = current_ratio
                否则：
                    如果 |current_ratio - ratio| > eps：
                        valid = false，跳出循环

    如果 valid = true：
        计数器加 1

样例分析

样例 1

CPP

输入：
N=9, M=4
A = [9, 3, 0, 0, 2, 99, 4, 0, 0]
B = [6, 2, 0, 4]

让我们检查几个关键位置：

i=0: C=[9, 3, 0, 0]
- B[0]=6, C[0]=9 → ratio = 6/9 = 2/3
- B[1]=2, C[1]=3 → 2/3 = 2/3 ✓
- B[2]=0 → 跳过
- B[3]=4, C[3]=0 → 不匹配 ✗
i=5: C=[99, 4, 0, 0]
- B[0]=6, C[0]=99 → ratio = 6/99 = 2/33
- B[1]=2, C[1]=4 → 2/4 = 1/2 ≠ 2/33 → 不匹配 ✗

通过逐个检查，共有 4 个位置满足条件。

样例 2

CPP

输入：
N=8, M=2
A = [0, 0, 0, 0, 0, 0, 0, 0]
B = [0, 0]

由于 B 的所有元素都是 0，任何子序列 C 都可以匹配（因为 B[j]=0 时，C[j] 可以是任意值）。

A 中有 N-M+1 = 8-2+1 = 7 个长度为 2 的子序列，全部匹配。

输出：7 ✓

代码实现

CPP

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

const double EPS = 1e-9;

int main() {
    int N, M;
    cin >> N >> M;

    vector<int> A(N), B(M);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    for (int i = 0; i < M; i++) {
        cin >> B[i];
    }

    int count = 0;

    // 检查每个起始位置 i
    for (int i = 0; i <= N - M; i++) {
        bool valid = true;
        double ratio = -1.0;

        // 检查从 i 开始的子序列是否能匹配 B
        for (int j = 0; j < M; j++) {
            int b_val = B[j];
            int c_val = A[i + j];

            if (b_val == 0) {
                // B[j] 是 0，C[i+j] 可以是任意值
                continue;
            } else {
                // B[j] 非零
                if (c_val == 0) {
                    // 无法缩放 0 到非零
                    valid = false;
                    break;
                } else {
                    // 两者都非零，检查比值
                    double current_ratio = (double)b_val / c_val;
                    if (ratio < 0) {
                        // 第一个找到的比值
                        ratio = current_ratio;
                    } else {
                        // 检查比值是否与之前的一致
                        if (fabs(current_ratio - ratio) > EPS) {
                            valid = false;
                            break;
                        }
                    }
                }
            }
        }

        if (valid) {
            count++;
        }
    }

    cout << count << endl;

    return 0;
}

复杂度分析

时间复杂度：O(N×M)
- 外层循环 O(N-M+1) ≈ O(N)
- 内层循环 O(M)
- 由于有早期跳出优化，实际运行时间会更快
空间复杂度：O(N+M)
- 存储两个输入数组

关键要点

浮点数比较：使用 EPS (1e-9) 处理浮点数精度问题
比值初始化：使用 -1 标记"尚未找到有效比值"
特殊情况：正确处理 B[j]=0 的情况（直接跳过）
早期终止：一旦发现不匹配立即 break，提高效率

题解：AT1202Contest_h Incomplete Notes

文章操作