CF1484D. Playlist

题目链接：https://codeforces.com/contest/1484/problem/D

Solution

算法其实不难想到，考场上算错了复杂度…….

我们设 nxt_i 表示 i 后的一个位置，开始时 nxt_i=i+1 （nxt_n=1），到后来如果要删掉互质数对(x,y) （x,y 表示位置）的后一个数字位置 y ，，就要令nxt_x=nxt_y 。相当于一个链表。

我们用一个队列 q 装互质的点对，在开始时按照 (1,2) ,(2,3), (3,4), …, (n,1) 的顺序扫描，如果互质就使其进 q 。

然后按照顺序开始出队，如果队首的点对的 (x,y) 两个位置都没有被删除，就删掉 y ，然后更新一下链表连接（不妨设此次更新为 z = nxt_x=nxt_y），此时在判断如果 (x,z) 上的数字互质，就让他进队尾，否则就直接丢掉）。

如果队首的点对 (x,y) 有任何一个数已经被删除了，那么无视掉这对就好。因为题目说

after he deletes a song, he can’t delete the next song immediately.

这对点对其实已经不存在了。

因为考虑开始时队列中最多有 2*n 个点对，而每一次都能至少能删除一个点（要么删除、要么不进队），所以复杂度是 O(n) （（应该是这样吧…

队列好就好在他能维护删除顺序

#include<bits/stdc++.h>
#define fi first
#define se second
const int N = 1e5+10;
int a[N];
int T,n,nxt[N];
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;++i)
            scanf("%d",&a[i]);
        std::queue<std::pair<int,int> > q;
        for(int i=1;i<=n;++i){
            nxt[i] = (i%n)+1;
            if(std::__gcd(a[i],a[(i%n)+1])==1) 
                q.push(std::make_pair(i,(i%n)+1));
        }
        std::vector<int> ans;
        std::vector<int> v(n+2,1);
        while(!q.empty()){
            std::pair<int,int> x = q.front(); q.pop();
            if(!v[x.fi]||!v[x.se]) continue;
            ans.push_back(x.se);
            v[x.se] = 0 ;
            nxt[x.fi] = nxt[x.se];
            if(std::__gcd(a[x.fi],a[nxt[x.fi]])==1)
                q.push(std::make_pair(x.fi,nxt[x.fi]));
        }
        printf("%d ",ans.size());
        for(auto p :ans)
            printf("%d ",p);
        puts("");
    }
    return 0;
}