【BZOJ 2054】 2054: 疯狂的馒头 (并查集特技)
2024-09-16 15:16:04
Input
第一行四个正整数N,M,p,q
Output
一共输出N行,第i行表示第i个馒头的最终颜色(如果最终颜色是白色就输出0)。
Sample Input
4 3 2 4Sample Output
2
2
3
0HINT
【分析】
想要不带log,就从后往前做,每个点只染色一次,用神奇的并查集维护即可。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define Maxn 1000010 int col[Maxn],rt[Maxn]; int rtt(int x)
{
if(rt[x]!=x) rt[x]=rtt(rt[x]);
return rt[x];
} int tot=;
void solve(int l,int r,int nw)
{
while(l<=r)
{
if(col[l]==)
{
col[l]=nw;
rt[l]=rtt(l+);
l=rtt(l);
tot++;
}
l=rtt(l);
}
} int main()
{
int n,m,p,q;
scanf("%d%d%d%d",&n,&m,&p,&q);
memset(col,,sizeof(col));
for(int i=;i<=n+;i++) rt[i]=i;
for(int i=m;i>=;i--)
{
if(tot==n) break;
int l=(i*p+q)%n+,r=(i*q+p)%n+;
if(l<=r) solve(l,r,i);
else solve(r,l,i);
}
for(int i=;i<=n;i++) printf("%d\n",col[i]);
return ;
}
还有就是不要理解错那个区间。。[r,l]也是可以的。
2017-03-06 20:57:21
最新文章
- PowerDesginer 生成的Oracle 11g 组合触发器代码编译错误(29): PLS-00103
- 自动验证是ThinkPHP
- JavaScript 面向对象程序设计(下)&mdash;&mdash;继承与多态 【转】
- centeros iptable模板文件
- uname命令
- Java学习笔记-嵌套类
- 文本超出显示省略号/数字英文字母折行有关css 属性/显示两行,第二行省略号显示css方法
- request&;response
- LODOP中预览界面查看打印机的可打区域具体值
- 一招制敌 - 玩转 AngularJS 指令的 Scope (作用域),讲得特别好
- url 编码和解码网址
- python Exception raise
- 141. Linked List Cycle&;142. Linked List Cycle II(剑指Offer-链表中环的入口节点)
- 多点搜的bfs
- thread库,附带程序介绍
- Servlet组件之 jsp 技术
- 现代OpenGL渲染管线介绍
- ORACLE 11G 利用泠备份恢复standby库
- geomesa hbase geoserver
- 温故vue对vue计算属性computed的分析