题解：B4174 [BCSP-X 2024 6 月初中组] 厂房

· · 题解

前言：好久没有写题解了，拯救一下狂掉（半年掉100）的估值。

正文：

我们可以使用双指针进行机器人的遍历：\ （设左指针为 l，右指针为 r）

第 1 步：

1 5 11 2 6 2 7
l r

此时家族列表为 \begin{bmatrix} 1 \end{bmatrix}。

第 2 步：

1 5 11 2 6 2 7
l r

此时家族列表为 \begin{bmatrix} 1 & 5 \end{bmatrix}。

第 3 步：

1 5 11 2 6 2 7
l r

此时家族列表为 \begin{bmatrix} 1 & 5 & 11\end{bmatrix}。

第 4 步：

1 5 11 2 6 2 7
l r

因为 2 不是 \begin{bmatrix} 1,3,5,7,9,11...... \end{bmatrix} 的子序列，所以将家族列表清空，将家族数增加 1，并加入 2。此时家族列表为 \begin{bmatrix} 2 \end{bmatrix}。

第 5 步：

1 5 11 2 6 2 7
l r

此时家族列表为 \begin{bmatrix} 2 & 6 \end{bmatrix}。

第 6 步：

1 5 11 2 6 2 7
l r

因为 2 已经在家族列表出现过了，所以将家族列表清空，将家族数增加 1，并加入 2。此时家族列表为 \begin{bmatrix} 2 \end{bmatrix}。

（下略，后同）

最终即可得出答案。

代码：

#include <bits/stdc++.h>
using namespace std;
int p[1000005];
int main()
{
    set<int> tmp;
    int n;
    cin >> n;
    int temp = -1;
    int ans = 0;
    for(int i = 1;i <= n;i++) cin >> p[i];
    for(int i = 1;i <= n;i++)
    {
        if(__gcd(temp,abs(p[i] - p[i - 1])) <= 1 || abs(p[i] - p[i - 1]) == 0 || temp == -1 || tmp.find(p[i]) != tmp.end())
        {
            temp = abs(p[i] - p[i + 1]);
            ans++;
            tmp.clear();
        }
        else temp = __gcd(temp,abs(p[i] - p[i - 1]));
        tmp.insert(p[i]);
    }
    cout << ans;
    return 0;
}