数三角形 bzoj 3505

要知道一个公式就是(a,b)和(x,y)两点所成线段上面的整点数是gcd(a-x,b-y)-1，通过枚举原点到map上任意一点所能成的三角形，再平移，得到要去掉的三点共线的点对。

我当时弱智地弄了个O(n^6)的枚举，不过好歹还是对的拿了三十分。

= =满分程序和30分程序几乎一样长。

program triangle;var m,n,i,j:integer;    ans,t:qword;function gcd(a,b:integer):integer;begin  if a=0 then exit(b);  if b=0 then exit(a);  if a mod b=0 then exit(b) else exit(gcd(b,a mod b));end;begin{
     main}  readln(m,n);  t:=(m+1)*(n+1);  ans:=t*(t-1)*(t-2) div 6;  for i:=0 to m do    for j:=0 to n do      if not ((i=0) and (j=0)) then        begin          if (i=0) or (j=0) then ans:=ans-(gcd(i,j)-1)*(m-i+1)*(n-j+1)          else ans:=ans-2*(gcd(i,j)-1)*(m-i+1)*(n-j+1);        end;  writeln(ans);end.

机械排序臂 bzoj 3506

那天早上还是写的O(n^2)骗的30分，不过这回30和100的代码长度就差远了…

7/2开始写这题，7/2当天晚上学习&码完splay，是对的，但是之后的lazy tag，没什么资料，C++的程序又看不太懂，我调了这么多天简直崩溃了好吗！最后发现是左子树注入tag的时候不应该直接赋值true而应该赋反，这一点在switch里面想到了，但是在主程序里没想到。对着sort1.in这个n=1000的输入文件我愣了好久啊，为什么输出的前80%是对的但是之后就有的对有的不对了呢。一开始我以为是树的fa啊，lc、rc啊没消除干净，导致被删的结点又重新回来，后来发现这也不是回事…

不过还好找到了错误所在，现在整个人心情爆好！！

200行的程序，况且这还不是完全的splay…弱渣的我到时候要好好背一下…

program sort3;var n,i,root,c,x,t,temp:longint;    f,ff,loc,l,fa,lc,rc,da,tot:array[0..100010] of longint;    lazy:array[0..100010] of boolean;function dd(x,xloc,y,yloc:longint):boolean;begin  if x
      
       y then exit(true);  if (x=y) and (xloc>yloc) then exit(true);  exit(false);end;procedure qsort(l,r:longint);var mid,mid_loc,i,j,temp:longint;begin  i:=l;j:=r;mid:=f[(l+r) div 2];mid_loc:=loc[(l+r) div 2];  while i<=j do    begin      while dd(f[i],loc[i],mid,mid_loc) do inc(i);      while gg(f[j],loc[j],mid,mid_loc) do dec(j);      if i<=j then        begin          temp:=f[i];f[i]:=f[j];f[j]:=temp;          temp:=loc[i];loc[i]:=loc[j];loc[j]:=temp;          inc(i);dec(j);        end;    end;  if i
       
        0 then fa[rc[p]]:=q;  rc[p]:=q;  fa[q]:=p;  tot[q]:=tot[lc[q]]+tot[rc[q]]+1;  tot[p]:=tot[lc[p]]+tot[rc[p]]+1;end;procedure rrot(p:longint);var q:longint;begin  q:=fa[p];fa[p]:=fa[q];  if q=root then root:=p else    if lc[fa[q]]=q then lc[fa[q]]:=p else      rc[fa[q]]:=p;  rc[q]:=lc[p];  if lc[p]<>0 then fa[lc[p]]:=q;  lc[p]:=q;  fa[q]:=p;  tot[q]:=tot[lc[q]]+tot[rc[q]]+1;  tot[p]:=tot[lc[p]]+tot[rc[p]]+1;end;procedure switch(p:longint);var t:longint;begin  if lazy[p]=false then exit;  t:=lc[p];lc[p]:=rc[p];rc[p]:=t;  lazy[p]:=false;  lazy[lc[p]]:=not lazy[lc[p]];  lazy[rc[p]]:=not lazy[rc[p]];end;procedure clear(p:longint);begin  if p=root then    begin      if lazy[p] then switch(p);      exit;    end;  clear(fa[p]);  if lazy[p] then switch(p);end;procedure splay(p:longint);var t,tt:longint;begin  while p<>root do    begin      if p=lc[fa[p]] then //p is lc        begin          if fa[p]=root then lrot(p) else            if fa[p]=lc[fa[fa[p]]] then              begin                lrot(fa[p]);lrot(p);              end            else              begin                lrot(p);rrot(p);              end;        end      else        begin          if fa[p]=root then rrot(p) else            if fa[p]=rc[fa[fa[p]]] then              begin                rrot(fa[p]);rrot(p);              end            else              begin                rrot(p);lrot(p);              end;        end;    end;  fa[p]:=0;end;procedure insert(x:longint);var t,tt:longint;begin  inc(c);  fa[c]:=0;lc[c]:=0;rc[c]:=0;da[c]:=f[x];  if root=0 then    begin      root:=c;      tot[root]:=1;    end  else    begin      t:=root;      repeat        begin          tt:=t;          if loc[x]
        
         0 do        begin          t:=rc[t];          if lazy[t] then switch(t);        end;      fa[rc[i]]:=0;fa[lc[i]]:=0;root:=lc[i];temp:=rc[i];tot[i]:=0;      if lc[i]=0 then root:=rc[i];      rc[i]:=0;lc[i]:=0;fa[i]:=0;      if t<>0 then        begin          clear(t);//from down to top then top to down          splay(t);          fa[temp]:=t;rc[t]:=temp;tot[t]:=tot[t]+tot[rc[t]];        end    end;  //close(input);close(output);end.