bzoj1267 3784

时间:2022-09-30 10:40:18

双倍经验题
像这种方案太多不能全部求出来但求前k大一般有这样一个思路
将所有方案无重复不漏的分为若干类,每个类的元素满足单调性,然后我们用堆维护就行了!
对于这道题,可以想到用树的分治来处理路径,当处理根为x时
我们处理当前的子树每个点i和之前的子树上的组成的路径,
我们完全可以把访问顺序状态记录成一条链(状态是nlogn规模不会爆)
当前子树的每个点i在链上都有一段连续的可选区间,这个区间的点和i构成一条过根x的路径
这样链上的每个点就代表了一类路径
很明显,我们就可以noi超级钢琴的做法来解决,st表预处理+堆维护

 type way=record
po,num,next:longint;
end;
node=record
l,r,s,t:longint;
end; var e:array[..] of way;
h:array[..] of node;
w:array[..,..] of longint;
d:array[..] of longint;
a:array[..] of longint;
q:array[..,..] of longint;
f,p,s:array[..] of longint;
v:array[..] of boolean;
l,r,root,len,t,tot,i,n,k,x,y,z,j:longint;
m:node; function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end; function mx(x,y:longint):longint;
begin
if a[x]>a[y] then exit(x) else exit(y);
end; function ask(x,y:longint):longint;
var k:longint;
begin
k:=trunc(ln(y-x+)/ln());
exit(mx(w[x,k],w[y-d[k]+,k]));
end; procedure swap(var a,b:node);
var c:node;
begin
c:=a;
a:=b;
b:=c;
end; procedure add(x,y,z:longint);
begin
inc(len);
e[len].po:=y;
e[len].num:=z;
e[len].next:=p[x];
p[x]:=len;
end; procedure up(i:longint);
var j:longint;
begin
j:=i shr ;
while j> do
begin
if a[h[j].s]+a[h[j].t]<a[h[i].s]+a[h[i].t] then
begin
swap(h[i],h[j]);
i:=j;
j:=j shr ;
end
else break;
end;
end; procedure sift(i:longint);
var j:longint;
begin
j:=i shl ;
while j<=t do
begin
if (j<t) and (a[h[j+].s]+a[h[j+].t]>a[h[j].s]+a[h[j].t]) then inc(j);
if a[h[j].s]+a[h[j].t]>a[h[i].s]+a[h[i].t] then
begin
swap(h[i],h[j]);
i:=j;
j:=j shl ;
end
else break;
end;
end; procedure getroot(x,fa:longint);
var i,y:longint;
begin
s[x]:=;
f[x]:=;
i:=p[x];
while i<> do
begin
y:=e[i].po;
if (y<>fa) and not v[y] then
begin
getroot(y,x);
s[x]:=s[x]+s[y];
f[x]:=max(f[x],s[y]);
end;
i:=e[i].next;
end;
f[x]:=max(f[x],tot-s[x]);
if f[x]<f[root] then root:=x;
end; procedure get(x,fa,len:longint);
var i,y:longint;
begin
inc(t);
a[t]:=len;
q[t,]:=l; q[t,]:=r;
i:=p[x];
while i<> do
begin
y:=e[i].po;
if (y<>fa) and not v[y] then get(y,x,len+e[i].num);
i:=e[i].next;
end;
end; procedure work(x:longint);
var i,y:longint;
begin
v[x]:=true;
i:=p[x];
inc(t);
l:=t;
r:=t;
q[t,]:=l; q[t,]:=r;
while i<> do
begin
y:=e[i].po;
if not v[y] then
begin
r:=t;
get(y,x,e[i].num);
end;
i:=e[i].next;
end;
i:=p[x];
while i<> do
begin
y:=e[i].po;
if not v[y] then
begin
root:=;
tot:=s[y];
getroot(y,);
work(root);
end;
i:=e[i].next;
end;
end; begin
readln(n,k);
for i:= to n- do
begin
readln(x,y,z);
add(x,y,z);
add(y,x,z);
end;
f[]:=;
tot:=n;
getroot(,);
work(root);
tot:=trunc(ln(t)/ln());
d[]:=;
for i:= to tot do
d[i]:=d[i-]*; for i:= to t do
w[i,]:=i;
for j:= to tot do
for i:= to t do
if i+d[j]-<=t then
w[i,j]:=mx(w[i,j-],w[i+d[j-],j-])
else break; tot:=t; t:=;
for i:= to tot do
begin
inc(t);
with h[t] do
begin
l:=q[i,]; r:=q[i,];
s:=i;
t:=ask(l,r);
end;
up(t);
end;
for i:= to k do
begin
writeln(a[h[].s]+a[h[].t]);
swap(h[],h[t]);
m:=h[t];
dec(t);
sift();
if m.t>m.l then
begin
inc(t);
with h[t] do
begin
l:=m.l; r:=m.t-;
s:=m.s;
t:=ask(l,r);
end;
up(t);
end;
if m.t<m.r then
begin
inc(t);
with h[t] do
begin
l:=m.t+; r:=m.r;
s:=m.s;
t:=ask(l,r);
end;
up(t);
end;
end;
end.

 

bzoj1267 3784的更多相关文章

  1. BZOJ 3784&colon; 树上的路径

    Description 问一棵树上前 \(k\) 大路径的边权. Sol 边分治. 非常感谢数据没有菊花图. 为了写写边分治试试然后就开了这道题. 边分治非常好想,选一条重边,分成两部分,然后分别求最 ...

  2. bzoj 3784&colon; 树上的路径 堆维护第k大

    3784: 树上的路径 Time Limit: 10 Sec  Memory Limit: 256 MBSubmit: 88  Solved: 27[Submit][Status][Discuss] ...

  3. POJ 3784&period;Running Median

    2015-07-16 问题简述: 动态求取中位数的问题,输入一串数字,每输入第奇数个数时求取这些数的中位数. 原题链接:http://poj.org/problem?id=3784 解题思路: 求取中 ...

  4. bzoj 3784

    第三道点分治. 首先找到黄学长的题解,他叫我参考XXX的题解,但已经没有了,然后找到另一个博客的简略题解,没看懂,最后看了一个晚上黄学长代码,写出来然后,写暴力都拍了小数据,但居然超时,....然后改 ...

  5. HDU 3784 继续xxx定律 &amp&semi; HDU 2578 Dating with girls&lpar;1&rpar;

    HDU 3784 继续xxx定律 HDU 2578 Dating with girls(1) 做3748之前要先做xxx定律  对于一个数n,如果是偶数,就把n砍掉一半:如果是奇数,把n变成 3*n+ ...

  6. 【POJ 3784】 Running Median

    [题目链接] http://poj.org/problem?id=3784 [算法] 对顶堆算法 要求动态维护中位数,我们可以将1-M/2(向下取整)小的数放在大根堆中,M/2+1-M小的数放在小根堆 ...

  7. POJ 3784 Running Median &lpar;动态中位数&rpar;

    题目链接:http://poj.org/problem?id=3784 题目大意:依次输入n个数,每当输入奇数个数的时候,求出当前序列的中位数(排好序的中位数). 此题可用各种方法求解. 排序二叉树方 ...

  8. POJ 3784 Running Median【维护动态中位数】

    Description For this problem, you will write a program that reads in a sequence of 32-bit signed int ...

  9. Running Median POJ - 3784 (对顶堆&sol;优先队列 &vert; 链表)

    For this problem, you will write a program that reads in a sequence of 32-bit signed integers. After ...

随机推荐

  1. OpenSceneGraph in ActiveX by ActiveQt

    OpenSceneGraph in ActiveX by ActiveQt eryar@163.com Abstract. Qt’s ActiveX and COM support allows Qt ...

  2. 原生js验证简洁美观注册登录页面

    序 一个以js验证表单的简洁的注册登录页面,不多说直接上图 效果 主要文件 完整代码 sign_up.html 注册表单 <!DOCTYPE html> <html lang=&qu ...

  3. Mina入门:Java NIO基础概念

    JDK1.4引入了Java NIO API(Java New IO),Java NIO得到了广泛应用.NIO允许程序进行非阻塞IO操作.java.nio.* 包括以下NIO基本结构: Buffer - ...

  4. LintCode-丢失的第一个正整数

    题目描述: 给出一个无序的正数数组,找出其中没有出现的最小正整数. 样例 如果给出 [1,2,0], return 3 如果给出 [3,4,-1,1], return 2 挑战 只允许时间复杂度O(n ...

  5. 转 SQL 基础--&gt&semi; NEW&lowbar;VALUE 的使用

    --=============================== -- SQL 基础--> NEW_VALUE 的使用 --=============================== 通常 ...

  6. UVALive 4850 Installations

    题目大意:有若干个任务,每个任务耗时si,期限为di,同一时间只能做一个任务.对于一个任务,惩罚值为max(0,完成时间-期限).问怎么安排,使(最大惩罚值+次大惩罚值)最小,O(n^2). 如果没有 ...

  7. 在js中实现新窗口打开页面

    我们都知道可以在html代码中使用<a href="xxxx" target="_blank"></a>这种方式来打开一个新的窗口打开一 ...

  8. 一种多线程写日志文件的解决方案 c&num;源代码演示

    using System;using System.Collections.Generic;using System.Collections;using System.Text;using Syste ...

  9. 将不同级别的logging 日志信息写入不同文件

    将不同级别的logging 日志信息写入不同文件 # -*- coding: utf-8 -*- import os import time from logging.handlers import ...

  10. 博客转移至github

    博客转移到github 鉴于github的各种优势,博客转移!