题解：CF1483B Playlist

__galaxy_1202__ · 2024-08-22 19:44:45 · 题解

此题涉及知识：单向循环链表、队列。

解题思路：

对于这道题，首先能想到的就是建立一个单向循环链表，重复枚举每个点，当这个点的值与下一个点的值互质时删除下一个点。直到一轮后没进行任何操作后停止。

但很可惜，这个方法由于 n \le 10^5，并不能通过此题。

那么怎么优化呢？注意到在有些情况，一对组合要被算很多次，而明显这些第二个数没被删除的组合是不互质的，那我们为什么要算这些组合呢？。

根据这个思路，我们可以发现以下规律：

• 当一对组合不互质的时候，这对组合就没必要验证了，无论如何都不互质。
• 如果这对组合互质的话，那它的第二个值就会变成第二个值后面的那个值，产生一个新的组合。

知道了这个方法后，我们就可以用队列来维护组合：定义一个含有两个值的队列，分别代表组合的第一个值和第二个值。把初始的 n 对组合入队（也就是 (1,2),(2,3)...(n - 1, n),(n, 1) 这些组合）。接着循环直到队列为空，每次验证这对组合的值是否互质，如果互质则将新的组合入队（见上文），记录下原来组合的第二个点并把它删除（用链表实现），而且别忘了把这对组合弹出队列。

Tips：

1. 记得多测清空。
2. 由于第二个数被删除，所以要标记一下，以它开头的组合要跳过。
3. 答案为了节省空间可以用 vector，记得 clear()。

CODE：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
int t, n, a, vis[100001], val[100001], r[100001];
vector <int> x;
queue < pair <int, int> > Q;
int main()
{
    cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++)
        {
            cin >> a;
            val[i] = a;
            r[i] = i + 1;
            if (i != n) Q.push({i, i + 1});
        }
        r[n] = 1;
        Q.push({n, 1});
        while (!(Q.empty()))
        {
            int ai = Q.front().first, bi = Q.front().second;
            Q.pop();
            if (vis[ai]) continue;
            if (__gcd(val[ai], val[bi]) == 1)
            {
                vis[bi] = 1;
                r[ai] = r[bi];
                Q.push({ai, r[ai]});
                x.push_back(bi);
            }
        }
        cout << x.size();
        for (auto it : x) cout << ' ' << it;
        cout << '\n';
        memset(vis, 0, sizeof(val));
        memset(val, 0, sizeof(vis));
        memset(r, 0, sizeof(r));
        x.clear();
    }
    return 0;
}