双倍经验题
像这种方案太多不能全部求出来但求前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的更多相关文章
-
BZOJ 3784: 树上的路径
Description 问一棵树上前 \(k\) 大路径的边权. Sol 边分治. 非常感谢数据没有菊花图. 为了写写边分治试试然后就开了这道题. 边分治非常好想,选一条重边,分成两部分,然后分别求最 ...
-
bzoj 3784: 树上的路径 堆维护第k大
3784: 树上的路径 Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 88 Solved: 27[Submit][Status][Discuss] ...
-
POJ 3784.Running Median
2015-07-16 问题简述: 动态求取中位数的问题,输入一串数字,每输入第奇数个数时求取这些数的中位数. 原题链接:http://poj.org/problem?id=3784 解题思路: 求取中 ...
-
bzoj 3784
第三道点分治. 首先找到黄学长的题解,他叫我参考XXX的题解,但已经没有了,然后找到另一个博客的简略题解,没看懂,最后看了一个晚上黄学长代码,写出来然后,写暴力都拍了小数据,但居然超时,....然后改 ...
-
HDU 3784 继续xxx定律 &; HDU 2578 Dating with girls(1)
HDU 3784 继续xxx定律 HDU 2578 Dating with girls(1) 做3748之前要先做xxx定律 对于一个数n,如果是偶数,就把n砍掉一半:如果是奇数,把n变成 3*n+ ...
-
【POJ 3784】 Running Median
[题目链接] http://poj.org/problem?id=3784 [算法] 对顶堆算法 要求动态维护中位数,我们可以将1-M/2(向下取整)小的数放在大根堆中,M/2+1-M小的数放在小根堆 ...
-
POJ 3784 Running Median (动态中位数)
题目链接:http://poj.org/problem?id=3784 题目大意:依次输入n个数,每当输入奇数个数的时候,求出当前序列的中位数(排好序的中位数). 此题可用各种方法求解. 排序二叉树方 ...
-
POJ 3784 Running Median【维护动态中位数】
Description For this problem, you will write a program that reads in a sequence of 32-bit signed int ...
-
Running Median POJ - 3784 (对顶堆/优先队列 | 链表)
For this problem, you will write a program that reads in a sequence of 32-bit signed integers. After ...
随机推荐
-
OpenSceneGraph in ActiveX by ActiveQt
OpenSceneGraph in ActiveX by ActiveQt eryar@163.com Abstract. Qt’s ActiveX and COM support allows Qt ...
-
原生js验证简洁美观注册登录页面
序 一个以js验证表单的简洁的注册登录页面,不多说直接上图 效果 主要文件 完整代码 sign_up.html 注册表单 <!DOCTYPE html> <html lang=&qu ...
-
Mina入门:Java NIO基础概念
JDK1.4引入了Java NIO API(Java New IO),Java NIO得到了广泛应用.NIO允许程序进行非阻塞IO操作.java.nio.* 包括以下NIO基本结构: Buffer - ...
-
LintCode-丢失的第一个正整数
题目描述: 给出一个无序的正数数组,找出其中没有出现的最小正整数. 样例 如果给出 [1,2,0], return 3 如果给出 [3,4,-1,1], return 2 挑战 只允许时间复杂度O(n ...
-
转 SQL 基础-->; NEW_VALUE 的使用
--=============================== -- SQL 基础--> NEW_VALUE 的使用 --=============================== 通常 ...
-
UVALive 4850 Installations
题目大意:有若干个任务,每个任务耗时si,期限为di,同一时间只能做一个任务.对于一个任务,惩罚值为max(0,完成时间-期限).问怎么安排,使(最大惩罚值+次大惩罚值)最小,O(n^2). 如果没有 ...
-
在js中实现新窗口打开页面
我们都知道可以在html代码中使用<a href="xxxx" target="_blank"></a>这种方式来打开一个新的窗口打开一 ...
-
一种多线程写日志文件的解决方案 c#源代码演示
using System;using System.Collections.Generic;using System.Collections;using System.Text;using Syste ...
-
将不同级别的logging 日志信息写入不同文件
将不同级别的logging 日志信息写入不同文件 # -*- coding: utf-8 -*- import os import time from logging.handlers import ...
-
博客转移至github
博客转移到github 鉴于github的各种优势,博客转移!