CodeForces - 1484D Playlist(循环链表+bfs)

2024-03-26 11:23:29

题目大意：给出一个长度为 n n n 的数列，规定其是一个首尾相接的环，不断的遍历该环，如果满足 g c d ( a i , a i + 1 ) = = 1 gcd(a_i,a_{i+1})==1 gcd(ai,ai+1)==1 的话，将删除掉 a i + 1 a_{i+1} ai+1 且 i i i 的位置向后迭代 1 1 1，现在要求按照顺序输出被删除的位置

题目分析：和鑫爷去年挂的一个题的模型是一样的，鑫爷的那个题是双线链表每次可以更新出 4 4 4 个点，而这个题目是循环链表每次可以更新出 1 1 1 个点，简单证明一下这个模型的时间复杂度吧：

当删掉一个点的时候，会影响到 k k k 个点，也就是说会有 k k k 个点入队，每个点至多被删除一次，也就是说总共会入队 k ∗ n k*n k∗n 次，所以时间复杂度是 O ( k ∗ n ) O(k*n) O(k∗n) 的

对于本题来说，如果点 x x x 被删除了的话，那么下一轮 x + 1 x+1 x+1 的位置有可能被删除，同理，假如 x x x 没有被删除的话， x + 1 x+1 x+1 下一轮一定不会被删除

所以对原数列维护一个循环链表，然后用 b f s bfs bfs 不断扩展即可，因为每个点都会被入队一次，所以加上 g c d gcd gcd 的时间复杂度是 O ( n l o g C ) O(nlogC) O(nlogC) 的

代码：

// Problem: D. Playlist
// Contest: Codeforces - Codeforces Round #709 (Div. 2, based on Technocup 2021 Final Round)
// URL: https://codeforces.com/contest/1484/problem/D
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// #pragma GCC optimize(2)
// #pragma GCC optimize("Ofast","inline","-ffast-math")
// #pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
#include<list>
#include<unordered_map>
#define lowbit(x) x&-x
using namespace std;
typedef long long LL;
typedef unsigned long long ull;
template<typename T>
inline void read(T &x)
{
	T f=1;x=0;
	char ch=getchar();
	while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
	while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
	x*=f;
}
template<typename T>
inline void write(T x)
{
	if(x<0){x=~(x-1);putchar('-');}
    if(x>9)write(x/10);
    putchar(x%10+'0');
}
const int inf=0x3f3f3f3f;
const int N=1e6+100;
int a[N],nt[N];
bool ban[N];
int main()
{
#ifndef ONLINE_JUDGE
//	freopen("data.in.txt","r",stdin);
//	freopen("data.out.txt","w",stdout);
#endif
//	ios::sync_with_stdio(false);
	int w;
	cin>>w;
	while(w--) {
		int n;
		read(n);
		memset(ban,false,n+5);
		for(int i=1;i<=n;i++) {
			read(a[i]);
			nt[i]=i+1;
		}
		nt[n]=1;
		queue<int>q;
		vector<int>ans;
		for(int i=1;i<=n;i++) {
			if(__gcd(a[i],a[nt[i]])==1) {
				ans.push_back(nt[i]);
				ban[nt[i]]=true;
				q.push(i);
				nt[i]=nt[nt[i]];
				i++;
			}
		}
		while(q.size()) {
			int i=q.front();
			q.pop();
			if(ban[i]) {
				continue;
			}
			if(__gcd(a[i],a[nt[i]])==1) {
				ans.push_back(nt[i]);
				ban[nt[i]]=true;
				q.push(i);
				nt[i]=nt[nt[i]];
			}
		}
		cout<<ans.size();
		for(auto it:ans) {
			printf(" %d",it);
		}
		puts("");
	}
	return 0;
}

码农公寓