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;
}
0 条评论