Input

第一行四个正整数N,M,p,q

Output

一共输出N行,第i行表示第i个馒头的最终颜色(如果最终颜色是白色就输出0)。

Sample Input

4 3 2 4

Sample Output

2
2
3
0

HINT

 
 
 
【分析】
  想要不带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

最新文章

  1. PowerDesginer 生成的Oracle 11g 组合触发器代码编译错误(29): PLS-00103
  2. 自动验证是ThinkPHP
  3. JavaScript 面向对象程序设计(下)&mdash;&mdash;继承与多态 【转】
  4. centeros iptable模板文件
  5. uname命令
  6. Java学习笔记-嵌套类
  7. 文本超出显示省略号/数字英文字母折行有关css 属性/显示两行,第二行省略号显示css方法
  8. request&amp;response
  9. LODOP中预览界面查看打印机的可打区域具体值
  10. 一招制敌 - 玩转 AngularJS 指令的 Scope (作用域),讲得特别好
  11. url 编码和解码网址
  12. python Exception raise
  13. 141. Linked List Cycle&amp;142. Linked List Cycle II(剑指Offer-链表中环的入口节点)
  14. 多点搜的bfs
  15. thread库,附带程序介绍
  16. Servlet组件之 jsp 技术
  17. 现代OpenGL渲染管线介绍
  18. ORACLE 11G 利用泠备份恢复standby库
  19. geomesa hbase geoserver
  20. 温故vue对vue计算属性computed的分析

热门文章

  1. laravel后台返回ajax数据
  2. 洛谷 Sorting a Three-Valued Sequence 三值的排序
  3. 【leetcode 简单】第二题 反转整数
  4. 实验吧CTF题库之二叉树遍历
  5. Linux内核多线程实现方法 —— kthread_create函数【转】
  6. python slots源码分析
  7. 设计模式之笔记--职责链模式(Chain of Responsibility)
  8. [转载]FFmpeg完美入门[3] - FFmpeg功能及使用说明
  9. Linux下的各类文件
  10. JAVA(一)变量