← Go Back

Incomplete Notes

题目大意

给定两个长度分别为 $N$$N$ 和 $M$$M$ 的非负整数序列 $A=(A_1,\dots ,A_N)$$A\ =\ (A_1,\ \dots,\ A_N)$ 和 $B=(B_1,\dots ,B_M)$$B\ =\ (B_1,\ \dots,\ B_M)$。 求满足以下条件的整数 $i$$i$ 的个数，其中 $1\le i\le N-M+1$$1\ \le\ i\ \le\ N\ -\ M\ +\ 1$。

定义序列 $C$$C$ 为由 $A$$A$ 的长度为 $M$$M$ 的连续子序列，$C=(A_i,\dots ,A_{i+M-1})$$C\ =\ (A_i,\ \dots,\ A_{i\ +\ M\ -\ 1})$。接下来，将序列 $B$$B$ 和 $C$$C$ 中所有值为 $0$$0$ 的元素用任意 正实数 替换（替换后的值可以相同）。然后，对于任意 正实数 $t$$t$，将序列 $C$$C$ 的所有元素乘以 $t$$t$。通过这样的操作，可以使得序列 $B$$B$ 和 $C$$C$ 相等。

输入以以下格式给出：$NM$$N\ M$ $A_1{A}_2\dots A_N$$A_1\ A_2\ \dots\ A_N$ $B_1{B}_2\dots B_M$$B_1\ B_2\ \dots\ B_M$

输出满足条件的整数个数。

• $1\le M\le N\le 5\times {10}^5$$1\ \leq\ M\ \leq\ N\ \leq\ 5\ \times\ 10^5$

• $0\le A_i\le 5\times {10}^5$$0\ \leq\ A_i\ \leq\ 5\ \times\ 10^5$ $(i=1,\dots ,N)$$(i\ =\ 1,\ \ldots,\ N)$

• $0\le B_i\le 5\times {10}^5$$0\ \leq\ B_i\ \leq\ 5\ \times\ 10^5$ $(i=1,\dots ,M)$$(i\ =\ 1,\ \ldots,\ M)$

总体解题思路

这道题主要考察的是如何通过数学推导和编程技巧解决一个较为复杂的整数序列匹配问题。解题的关键在于如何有效地构建和利用序列 $C$$C$，以及如何根据给定的条件进行合理的替换和乘法操作。

具体解题步骤

1. 构建序列 $C$$C$：首先，根据题目要求，我们需要构建一个长度为 $M$$M$ 的子序列 $C$$C$，该子序列从 $A$$A$ 中连续选取元素。这里可以通过滑动窗口的方式实现，即每次将窗口向右滑动一位，从而生成新的子序列。

2. 处理 $0$$0$ 值元素：题目要求将 $B$$B$ 和 $C$$C$ 中所有值为 $0$$0$ 的元素用任意正实数替换。这一步可以通过遍历两个序列来实现，当遇到值为 $0$$0$ 的元素时，用一个随机正实数替换。需要注意的是，这里需要保证替换后的值在题目约束范围内。

3. 乘法操作：接下来，需要对序列 $C$$C$ 的所有元素乘以任意正实数 $t$$t$。这一步可以通过遍历 $C$$C$ 序列并逐个元素乘以 $t$$t$ 来实现。同样，需要保证乘法操作后的值在题目约束范围内。

4. 匹配检查：最后，我们需要检查经过以上操作后的 $B$$B$ 和 $C$$C$ 是否相等。这一步可以通过逐个比较两个序列的元素来实现。如果所有对应位置的元素都相等，则认为满足条件。

5. 计数与输出：统计满足条件的整数个数，并输出结果。

时间复杂度分析

• 构建序列 $C$$C$：需要遍历 $A$$A$ 序列两次，时间复杂度为 $O(N)$$O(N)$。

• 处理 $0$$0$ 值元素和乘法操作：需要遍历两个序列，时间复杂度为 $O(M)$$O(M)$。

• 匹配检查：需要遍历两个序列，时间复杂度为 $O(M)$$O(M)$。

• 计数与输出：常数时间复杂度。

因此，总时间复杂度为 $O(N+M)$$O(N + M)$。