来自FallDream的博客，未经允许，请勿转载，谢谢。
-----------------------------------------------------------------------------
hzwer这次不都出省选题了，干脆直接扔出了APIO三道+一道NOI，然后按照惯例最后留了一个模板题。有两道apio是2014的，以前做过了，剩下的题调来调去，还剩20分钟终于做完了。
-------------------------------------------------------------------------------
A.[apio2012] dispatching派遣
给定一棵n个点的树和一个费用m，每个点有一个忍者，派遣它的费用是ci，它的领导力是li。你要选择一个点作为领导，并且在它的子树中(包括它)选出尽可能多的点，满足费用不超过m且选出的点的数量*领导的领导力最大。n<=100000 m,c,l<=10^9
题解：这道题很多做法吧..首先费用少的肯定先选，我们每次肯定是从费用小的开始选，所以题目可以转换为求所有点的子树中最多能选几个点。
做法1：平衡树/优先队列+启发式合并
把费用装进一个平衡树/优先队列里面，然后启发式合并，合并次数是nlogn，总复杂度nlog^2n
我的做法：树剖那样子标号，满足子树的dfs序连续，然后主席树，复杂度是nlogn
#include<iostream>
#include<cstdio>
#include<queue>
#define MN 100000
#define MM 5000000
#define INF 2000000000
#define ll long long
using namespace std;
inline int read()
{
int x = , f = ; char ch = getchar();
while(ch < '' || ch > ''){ if(ch == '-') f = -; ch = getchar();}
while(ch >= '' && ch <= ''){x = x * + ch - '';ch = getchar();}
return x * f;
} int n,dfn=,cnt=,mx[MN+],size[MN+],nl[MN+],nr[MN+],head[MN+],id[MN+],rt[MN+];
ll c[MN+],l[MN+],ans=,m;
struct edge{
int to,next;
}e[MN+];
struct TREE{
int l,r,size;ll x;
}T[MM+]; void ins(int f,int t)
{
e[++cnt]=(edge){t,head[f]};head[f]=cnt;
} void dfs1(int x)
{
size[x]=;mx[x]=;int maxn=;
for(int i=head[x];i;i=e[i].next)
{
dfs1(e[i].to);
size[x]+=size[e[i].to];
if(size[e[i].to]>maxn){maxn=size[e[i].to];mx[x]=e[i].to;}
}
} void dfs2(int x)
{
nl[x]=++dfn;id[dfn]=x;
if(mx[x]) dfs2(mx[x]);
for(int i=head[x];i;i=e[i].next)
if(e[i].to!=mx[x])
dfs2(e[i].to);
nr[x]=dfn;
} void ins(int x,int nx,ll c)
{
T[nx].size=T[x].size+;T[nx].x=T[x].x+c;
ll l=,r=INF,mid;
while(l<r)
{
mid=l+r>>;
if(c<=mid)
{
T[nx].r=T[x].r;T[nx].l=++cnt;
r=mid;nx=T[nx].l;x=T[x].l;
}
else
{
T[nx].l=T[x].l;T[nx].r=++cnt;
l=mid+;nx=T[nx].r;x=T[x].r;
}
T[nx].size=T[x].size+;T[nx].x=T[x].x+c;
}
} int query(int x,int nx,ll cc)
{
ll l=,r=INF,mid,num=;
while(l<r)
{
mid=l+r>>;
// cout<<T[T[nx].l].x-T[T[x].l].x<<" "<<T[T[nx].l].size-T[T[x].l].size<<endl;
if(T[T[nx].l].x-T[T[x].l].x<=cc)
{
cc-=T[T[nx].l].x-T[T[x].l].x;
num+=T[T[nx].l].size-T[T[x].l].size;
x=T[x].r;nx=T[nx].r;l=mid+;
}
else
{
x=T[x].l;nx=T[nx].l;
r=mid;
}
}
if(T[nx].size-T[x].size>)
{
int x=cc/((T[nx].x-T[x].x)/(T[nx].size-T[x].size));
num+=x;
}
return num;
} main()
{ n=read();m=read();
for(int i=;i<=n;i++)
{
int fa=read();c[i]=read();l[i]=read();
if(fa) ins(fa,i);
}
dfs1();dfs2();cnt=;
for(int i=;i<=n;i++)
ins(rt[i-],rt[i]=++cnt,c[id[i]]);
for(int i=;i<=n;i++)
ans=max(ans,l[i]*1LL*query(rt[nl[i]-],rt[nr[i]],m));
// for(int i=1;i<=n;i++)
// cout<<i<<" "<<l[i]*1LL*query(rt[nl[i]-1],rt[nr[i]],m)<<endl;
cout<<ans;
return ;
}
B.C是APIO2014的两道题，我已经写过题解啦 http://www.cnblogs.com/FallDream/p/apio2014.html
Ｄ.[NOI2010]超级钢琴
给定n个数，你要选出不同的k段区间，满足长度属于[l,r]并且总和最大。 n<=500000
题解：我们发现以每个点作为左边界点，能选的区间都是连续的一段。我们可以从这一段中找到最值，然后扔到pq里面。
每次我们从pq中取出最大的，然后那一段区间被我们选的那个数劈成了两半，我们对两半同样的做法，找到最值之后扔到pq，一直这么做直到拿出k个，就行啦。
至于区间查最值 st表~线段树~看情况乱搞~
复杂度nlogn
#include<iostream>
#include<cstdio>
#include<queue>
#define MN 500005
#define N 524288
#define RG register
#define ll long long
#define INF 1000000000000000000LL
using namespace std;
inline int read()
{
int x = , f = ; char ch = getchar();
while(ch < '' || ch > ''){ if(ch == '-') f = -; ch = getchar();}
while(ch >= '' && ch <= ''){x = x * + ch - '';ch = getchar();}
return x * f;
} ll ans=;
int n,k,L,R,s[MN+];
struct data{
ll x;int from;
data operator + (data y)
{
return x>y.x?*this:y;
}
data operator -(ll num)
{
return (data){x-num,from};
}
}t[N*+];
struct node{int l,r,rg;data s;
bool operator < (const node & y) const
{
return s.x<y.s.x;
}
}now;
priority_queue<node> q; data query(data*T,int l,int r)
{
data sum=(data){-INF,};
for(l+=N-,r+=N+;l^r^;l>>=,r>>=)
{
if(~l&) sum=sum+T[l+];
if( r&) sum=sum+T[r-];
}
return sum;
} main()
{
n=read();k=read();L=read();R=read();
for(int i=;i<=N*+;i++)t[i]=(data){-INF,};
for(RG int i=;i<=n;i++)s[i]=read()+s[i-];
for(RG int i=;i<=n;i++) t[i+N]=(data){s[i],i};
for(RG int i=N;i;i--) t[i]=t[i<<]+t[i<<|];
for(int i=;i+L-<=n;i++)
q.push((node){i+L-,min(i+R-,n),i,query(t,i+L-,min(i+R-,n))-s[i-]});
for(int i=;i<=k;i++)
{
now=q.top();q.pop();
ans+=now.s.x;
if(now.s.from->=now.l)
q.push((node){now.l,now.s.from-,now.rg,(query(t,now.l,now.s.from-)-s[now.rg-])});
if(now.s.from+<=now.r)
q.push((node){now.s.from+,now.r,now.rg,(query(t,now.s.from+,now.r)-s[now.rg-])});
}
cout<<ans;
return ;
}
E.
给定n个物品，每个物品有一个编号num和一个价值。你要取出一些物品，满足不存在一个非空子集满足异或和等于0，且价值最大。
n<=1000 num<=10^18
题解：显然排序之后按照价值大小添加最优，然后就是线性基裸题啦。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 1005
#define ll long long
using namespace std;
inline ll read()
{
ll x = , f = ; char ch = getchar();
while(ch < '' || ch > ''){ if(ch == '-') f = -; ch = getchar();}
while(ch >= '' && ch <= ''){x = x * + ch - '';ch = getchar();}
return x * f;
} int n;
ll p[];
struct node{ll num;int x;}s[MAXN+]; bool cmp(node x,node y){return x.x>y.x;} int main()
{
n=read();
for(int i=;i<=n;i++) s[i].num=read(),s[i].x=read();
sort(s+,s+n+,cmp);
int ans=;
for(int i=;i<=n;i++)
{
for(int j=;j>=;j--)
if(s[i].num&(1LL<<j))
if(!p[j]) {p[j]=s[i].num;break;}
else s[i].num^=p[j];
if(s[i].num>)ans+=s[i].x;
//cout<<i<<" "<<s[i].num<<endl;
}
cout<<ans;
return ;
}