来自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 = 0 , f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();} while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();} return x * f; } int n,dfn=0,cnt=0,mx[MN+5],size[MN+5],nl[MN+5],nr[MN+5],head[MN+5],id[MN+5],rt[MN+5]; ll c[MN+5],l[MN+5],ans=0,m; struct edge{ int to,next; }e[MN+5]; struct TREE{ int l,r,size;ll x; }T[MM+5]; void ins(int f,int t) { e[++cnt]=(edge){t,head[f]};head[f]=cnt; } void dfs1(int x) { size[x]=1;mx[x]=0;int maxn=0; 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+1;T[nx].x=T[x].x+c; ll l=1,r=INF,mid; while(l<r) { mid=l+r>>1; 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+1;nx=T[nx].r;x=T[x].r; } T[nx].size=T[x].size+1;T[nx].x=T[x].x+c; } } int query(int x,int nx,ll cc) { ll l=1,r=INF,mid,num=0; while(l<r) { mid=l+r>>1; // 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+1; } else { x=T[x].l;nx=T[nx].l; r=mid; } } if(T[nx].size-T[x].size>0) { 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=1;i<=n;i++) { int fa=read();c[i]=read();l[i]=read(); if(fa) ins(fa,i); } dfs1(1);dfs2(1);cnt=0; for(int i=1;i<=n;i++) ins(rt[i-1],rt[i]=++cnt,c[id[i]]); for(int i=1;i<=n;i++) ans=max(ans,l[i]*1LL*query(rt[nl[i]-1],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 0; }
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 = 0 , f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();} while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();} return x * f; } ll ans=0; int n,k,L,R,s[MN+5]; 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*2+5]; 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,0}; for(l+=N-1,r+=N+1;l^r^1;l>>=1,r>>=1) { if(~l&1) sum=sum+T[l+1]; if( r&1) sum=sum+T[r-1]; } return sum; } main() { n=read();k=read();L=read();R=read(); for(int i=1;i<=N*2+1;i++)t[i]=(data){-INF,0}; for(RG int i=1;i<=n;i++)s[i]=read()+s[i-1]; for(RG int i=1;i<=n;i++) t[i+N]=(data){s[i],i}; for(RG int i=N;i;i--) t[i]=t[i<<1]+t[i<<1|1]; for(int i=1;i+L-1<=n;i++) q.push((node){i+L-1,min(i+R-1,n),i,query(t,i+L-1,min(i+R-1,n))-s[i-1]}); for(int i=1;i<=k;i++) { now=q.top();q.pop(); ans+=now.s.x; if(now.s.from-1>=now.l) q.push((node){now.l,now.s.from-1,now.rg,(query(t,now.l,now.s.from-1)-s[now.rg-1])}); if(now.s.from+1<=now.r) q.push((node){now.s.from+1,now.r,now.rg,(query(t,now.s.from+1,now.r)-s[now.rg-1])}); } cout<<ans; return 0; }
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 = 0 , f = 1; char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar();} while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();} return x * f; } int n; ll p[66]; struct node{ll num;int x;}s[MAXN+5]; bool cmp(node x,node y){return x.x>y.x;} int main() { n=read(); for(int i=1;i<=n;i++) s[i].num=read(),s[i].x=read(); sort(s+1,s+n+1,cmp); int ans=0; for(int i=1;i<=n;i++) { for(int j=60;j>=0;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>0)ans+=s[i].x; //cout<<i<<" "<<s[i].num<<endl; } cout<<ans; return 0; }