题解：AT1202Contest_h Incomplete Notes

_GIGjqw12_ · 2025-08-23 11:19:04 · 题解

这题中归中距

实现代码：

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

// 简化分数表示
struct Fraction {
    long long num, den;  // 分子, 分母

    Fraction(long long n, long long d) {
        if (d == 0) {
            num = 0;
            den = 1;
            return;
        }
        // 确保分母为正
        if (d < 0) {
            n = -n;
            d = -d;
        }
        // 计算最大公约数
        long long g = __gcd(abs(n), abs(d));
        num = n / g;
        den = d / g;
    }

    bool operator==(const Fraction& other) const {
        return num == other.num && den == other.den;
    }
};

// 为Fraction定义哈希函数，使其可以作为unordered_map的键
namespace std {
    template<> struct hash<Fraction> {
        size_t operator()(const Fraction& f) const {
            return hash<long long>()(f.num) ^ hash<long long>()(f.den);
        }
    };
}

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

    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];
    }

    // 预计算B中非零元素的位置和值
    vector<pair<int, int>> B_non_zero;
    for (int j = 0; j < M; ++j) {
        if (B[j] != 0) {
            B_non_zero.emplace_back(j, B[j]);
        }
    }

    // 如果B全为0，则所有可能的子序列都满足条件
    if (B_non_zero.empty()) {
        cout << N - M + 1 << endl;
        return 0;
    }

    int count = 0;

    // 检查每个可能的子序列
    for (int i = 0; i <= N - M; ++i) {
        bool valid = true;
        Fraction ratio(1, 1);  // 默认比例
        bool ratio_set = false;

        for (const auto& [j, b_val] : B_non_zero) {
            int a_val = A[i + j];

            // A的当前位置为0，而B的对应位置不为0，无效
            if (a_val == 0) {
                valid = false;
                break;
            }

            // 计算比例 B[j]/A[i+j]
            Fraction current_ratio(b_val, a_val);

            if (!ratio_set) {
                ratio = current_ratio;
                ratio_set = true;
            } else if (ratio != current_ratio) {
                // 比例不一致，无效
                valid = false;
                break;
            }
        }

        // 额外检查：A中有非零元素而B中对应位置为0的情况
        if (valid) {
            for (int j = 0; j < M; ++j) {
                if (B[j] == 0 && A[i + j] != 0) {
                    // 这种情况是允许的，因为我们可以将B[j]替换为任意正实数
                    // 所以不需要标记为无效
                }
            }
        }

        if (valid) {
            count++;
        }
    }

    cout << count << endl;

    return 0;
}