www.cnblogs.com/shaokele/

---

bzoj2054：瘋狂的饅頭

　　Time Limit: 10 Sec
　　Memory Limit: 162 MB

Description

　　
　

Input

　　第一行四個正整數N，M，p，q
　

Output

　　一共輸出N行，第i行表示第i個饅頭的最終顏色（如果最終顏色是白色就輸出0）。
　

Sample Input

　　4 3 2 4
　

Sample Output

　　2
　　2
　　3
　　0
　　

HINT

　　
　　

題目地址：　　bzoj2054:瘋狂的饅頭

題目大意： 　　題目很簡潔了：）

　　

題解：

　　并查集巧用
　　因為顏色是覆蓋上去的
　　所以我們只要考慮最后一次染了什么顏色就可以了
　　倒著做上來
　　對于一個染色的區間 \(l,r\) ，我們只要將 \(l\) 指向 \(r+1\) 就好了，類似鏈表的操作
　　用并查集維護操作
　　
　　本地測要加棧 或者 用非遞歸并查集
　　不然無限RE
　　數據下載[data](https://files.cnblogs.com/files/shaokele/2054.zip)
　　

---

AC代碼

#include <cstdio> #include <algorithm> using namespace std; const int N=1e6+5; int n,m,p,q,l,r,sum; int fa[N],ans[N]; int find(int x){int p=x;while(p!=fa[p])p=fa[p];while(x!=p){int tmp=fa[x];fa[x]=p;x=tmp;}return x; } int main(){scanf("%d%d%d%d",&n,&m,&p,&q);for(int i=1;i<=n+1;i++)fa[i]=i;for(int i=m;i>=1;i--){l=(1ll*i*p+q)%n+1;r=(1ll*i*q+p)%n+1;if(l>r)swap(l,r);for(int k=find(l);k<=r;k=find(k)){ans[k]=i;fa[k]=k+1;sum++;if(sum==n)break;}if(sum==n)break;}for(int i=1;i<=n;i++)printf("%d\n",ans[i]);return 0; }

轉載于:https://www.cnblogs.com/shaokele/p/9114804.html

總結

以上是生活随笔為你收集整理的bzoj2054疯狂的馒头（巧用非递归并查集）的全部內容，希望文章能夠幫你解決所遇到的問題。

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