CF1484D. Playlist

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

Solution

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

我们设 nxt_i 表示 i 后的一个位置,开始时 nxt_i=i+1nxt_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;
}
分类: 数论

0 条评论

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注