題目鏈接：點擊查看

題目大意：給出一個長度為 $n$ 的數列，規定其是一個首尾相接的環，不斷的遍歷該環，如果滿足 $gcd(a_i,a_{i+1})==1$ 的話，將刪除掉 $a_{i+1}$ 且 $i$ 的位置向后迭代 $1$，現在要求按照順序輸出被刪除的位置

題目分析：和鑫爺去年掛的一個題的模型是一樣的，鑫爺的那個題是雙線鏈表每次可以更新出 $4$ 個點，而這個題目是循環鏈表每次可以更新出 $1$ 個點，簡單證明一下這個模型的時間復雜度吧：

當刪掉一個點的時候，會影響到 $k$ 個點，也就是說會有 $k$ 個點入隊，每個點至多被刪除一次，也就是說總共會入隊 $k?n$ 次，所以時間復雜度是 $O(k?n)$ 的

對于本題來說，如果點 $x$ 被刪除了的話，那么下一輪 $x+1$ 的位置有可能被刪除，同理，假如 $x$ 沒有被刪除的話，$x+1$ 下一輪一定不會被刪除

所以對原數列維護一個循環鏈表，然后用 $bfs$ 不斷擴展即可，因為每個點都會被入隊一次，所以加上 $gcd$ 的時間復雜度是 $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; }

總結

以上是生活随笔為你收集整理的CodeForces - 1484D Playlist(循环链表+bfs)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。