注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

z55250825

一只蒟蒻

 
 
 

日志

 
 

【某迈克杯】【包围圈】  

2013-10-26 22:25:21|  分类: AC题目 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
    这道题目爆零了,只能说是咱的线段树还不过关。
    问题很简单,就是区间染色再问每种颜色染了多少个格子。问题在于范围在1~1000000000之间,直接用线段树果断会挂,但是我们可以发现给出的区间只有 N=50000个,咱就可以想到对区间进行离散化再用线段树做。先找出所有在题目中插入过的区间的端点,然后对它们进行排序,并以排序后的数组下标作为它们的新值,这样子最多只有100000个点,即区间只有1~100000,原来假设插入范围为A~B,我们在排序数组中二分找到它们的下标i,j,然后把染成某颜色的线段i,j插入线段树就可以了,这样子线段树只需要200000个节点就可以了。然后我们再把所有的出兵的区间按出兵顺序插入线段树并染色,然后再询问线段树中每一个单位区间的颜色,这里我们定义每个节点X表示的A[X],B[X]为离散后的半开半闭区间 (A[X],B[X]】,我们通过直接用下标就可以查找离散前的区间。然后线段树的插入查询都为 O(LOGN)的,则复杂度为O(NLOGN),常数可能比较大,对于10^5 还是可以勉强过的吧。
  但是关键还是线段树的区间的定义这里有问题。因为原数据可能存在X,Y相同的情况,这个时候咱当时就是直接读入的,现在感觉到不对劲了,只要把区间改为半开半闭区间,问题就可以解决了,因为 X<=Y,半开半闭X要减去1,肯定小于y的节奏。所以这样子的确就可以AC了,考试的时候调试之前的线段树就有点慌了,果然还是得多练练。
  另外还有一点就是要把军队所属阵营按输入顺序输出,这就要求在输入的时候能够判重,为了能够判重,咱最好的办法便是写一个字符串的HASH函数,将HASH值存放在一个HASH表中,再用一个线性表存字符串,若HASH有重复就不加入,否则就把线性表长度加1,插入字符串。HASH函数的选取也很关键,咱选的是最简单的,令hash=hash*3+ord(s[i])*255+21
 再取模,255这个长度可以有效的区分相邻字符了。
  附原线段树程序
program baoweiquan;
var s:array[1..50000]of string;
    site:array[1..100000]of longint;
    lisan:array[0..100000]of longint;
    x,y,w:array[1..50000]of longint;
    hash:array[0..10000000]of longint;
    ans:array[1..50000]of longint;
    tot,stot,n:longint;
    a,b,see,l,r:array[1..100000]of longint;

function h(s:string):longint;
var i,ss,j:longint;
begin
  j:=length(s);
  ss:=j;
  for i:=1 to j do
    ss:=(ss*3+ord(s[i])*255+21)mod 10000001;
  exit(ss);
end;

procedure qsort(l,r:longint);
var i,j,x,y:longint;
begin
  i:=l;j:=r;
  x:=site[(l+r)shr 1];
  repeat
    while site[i]<x do inc(i);
    while site[j]>x do dec(j);
    if i<=j then begin
      y:=site[i];site[i]:=site[j];site[j]:=y;
      inc(i);dec(j);end;
  until i>j;
  if i<r then qsort(i,r);
  if j>l then qsort(l,j);
end;

procedure prepare;
var i:longint;
begin
  lisan[0]:=1;
  lisan[1]:=site[1];
  for i:=2 to n*2 do
   if site[i]<>site[i-1] then begin
     inc(lisan[0]);lisan[lisan[0]]:=site[i];end;
end;

procedure init;
var i,j:longint;
    sp:string;
begin
  read(n);
  stot:=0;tot:=0;
  fillchar(hash,sizeof(hash),0);
  for i:=1 to n do
   begin
     read(site[i*2-1]);
     readln(site[i*2]);
     x[i]:=site[i*2-1];
     y[i]:=site[i*2];
     readln(sp);
     j:=h(sp);
     if hash[j]=0 then begin
     inc(stot);
     s[stot]:=sp;
     hash[j]:=stot;
     w[i]:=stot;
     end;
   end;
  qsort(1,n*2);
  prepare;
end;

procedure build(s,t:longint);
var x,mid:longint;
begin
  inc(tot);x:=tot;
  a[x]:=s;b[x]:=t;see[x]:=0;
  if s+1<t then begin
   mid:=(s+t)shr 1;
   l[x]:=tot+1;build(s,mid);
   r[x]:=tot+1;build(mid,t);
  end
  else begin l[x]:=0;r[x]:=0;end;
end;

function find(u:longint):longint;
var l,r,mid:longint;
begin
  l:=1;r:=lisan[0];
  while l<=r do
   begin
     mid:=(l+r)shr 1;
     if lisan[mid]=u then exit(mid);
     if lisan[mid]>u then r:=mid-1
                    else l:=mid+1;
   end;
  exit(-1);
end;

procedure release(x:longint);
begin
  if see[x]<>0 then
  begin
  see[l[x]]:=see[x];
  see[r[x]]:=see[x];
  see[x]:=0;
  end;
end;

procedure insert(s,t,x,c:longint);
var mid:longint;
begin
  if (a[x]>=s)and(b[x]<=t) then begin see[x]:=c;exit;end;
  release(x);
  mid:=(a[x]+b[x])shr 1;
  if mid>s then insert(s,t,l[x],c);
  if mid<t then insert(s,t,r[x],c);
end;

function query(s,t,x:longint):longint;
var mid:longint;
begin
  if (a[x]+1=b[x]) then begin exit(see[x]);end;
  release(x);
  mid:=(a[x]+b[x])shr 1;
  if mid<t then exit(query(s,t,r[x]));
  if mid>s then exit(query(s,t,l[x]));
end;

procedure main;
var i,j:longint;
begin
  build(0,lisan[0]*2);
  for i:=1 to n do
   insert(find(x[i])-1,find(y[i]),1,w[i]);
  for i:=1 to lisan[0] do
   begin
     j:=query(i-1,i,1);
     if i=1 then ans[j]:=ans[j]+1
            else ans[j]:=ans[j]+lisan[i]-lisan[i-1];
   end;
  for i:=1 to stot do
   if i=stot then write(s[i],' ',ans[i])
             else writeln(s[i],' ',ans[i]);
end;

begin
  init;
  main;
end.





  
  评论这张
 
阅读(5)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018