首页 > 代码库 > BOZJ 2045:疯狂的馒头(并查集)

BOZJ 2045:疯狂的馒头(并查集)

题目大意:有n个馒头排成一排,初始时颜色为0,进行m次染色,第i次将(i*p+q)mod n到(i*q+p)mod n的馒头全部染成颜色i,求最后所有馒头颜色。n<=10^6 m<=10^7

分析:nm很大不能线段树,可以考虑用并查集,我们发现每个馒头可能会被染色多次,但只有最后一次染色能决定它的最终颜色,故倒着做,并且使每个点颜色只修改一次,对于区间[x,y],从x开始将除以外的点父亲全部指向下一个,这样这个区间全部指向了y,下一次修改时会跳过该区间,由于只会修改n个点故效率为O(n)

代码:

技术分享
program asfd;
var
  a:array[0..1000001]of longint;
  f:array[0..1000001]of longint;
  n,i,m,p,q,k,x,y,t,j:longint;
function find(x:longint):longint;
var i,j,k:longint;
begin
  i:=x; j:=x;
  while i<>f[i] do i:=f[i];
  while i<>j do
   begin
     k:=f[j]; f[j]:=i; j:=k;
   end;
  exit(i);
end;
begin
  readln(n,m,p,q);
  for i:=1 to n do f[i]:=i; k:=0;
  for i:=m downto 1 do
   begin
     x:=(i*p mod n+q)mod n+1;
     y:=(i*q mod n+p)mod n+1;
     if x>y then begin t:=x; x:=y; y:=t; end;
     j:=find(x);
     while j<=y do
      begin
        a[j]:=i; f[j]:=j+1; inc(k);
        if k=n then break;
        j:=find(j);
      end;
   end;
  for i:=1 to n do
   writeln(a[i]);
  readln;
end.
View Code

 

BOZJ 2045:疯狂的馒头(并查集)