POI2014

orz hhw posted @ 2017年11月22日 22:46 in 做题记录 with tags 解题报告 POI , 87 阅读

T1 Salad Bar 写了个$nlg^2n$的树状数组单点修改区间最值被鏼死了。。改成$nlgn$的线段树才卡过。。大概就是单调栈维护出每个点向左、向右最多扩展的点,然后只要一个点的$l[j]\leq i$且$i\leq l[j]\leq r[i]$则该点合法,每次把符合条件的点加入统计出$i-r[i]$中出现的最大值即可更新答案

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1001000
#define inf 1e9
using namespace std;
int n,i,t,ans,tot,x,w[N],c[N],a[N],q[N],r[N],l[N],la[N],ne[N],fir[N];char s[N];
void add(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void ins(int x,int v){
	w[x]=v;
	for(;x<=n;x+=x&-x){
		c[x]=v;
		for(int j=1;j<x&-x;j<<=1)c[x]=max(c[x],c[x-j]);
	}
}
int query(int l,int r){
	int ans=w[r];
	while(1){
		ans=max(ans,w[r]);
		if(l==r)return ans;
		for(r--;r-l>=r&-r;r-=r&-r)ans=max(ans,c[r]);
	}
	return ans;
}
int main(){
	scanf("%d%s",&n,s+2);n++;a[n+1]=-inf;
	for(i=2;i<=n;i++)a[i]=a[i-1]+(s[i]=='p'?1:-1);
	for(i=1;i<=n+1;q[++t]=i++)for(;t&&a[i]<a[q[t]];)r[q[t--]]=i-1;
	for(a[0]=inf,t=0,i=n;i>=0;q[++t]=i--)for(;t&&a[i]>a[q[t]];)l[q[t--]]=i+1;
	for(i=1;i<=n;i++)add(l[i],i);
	for(x=1;x<=n;x++){
		for(i=fir[x];i;i=ne[i])ins(la[i],la[i]);
		ans=max(ans,query(x,r[x])-x);
	}
	printf("%d",ans);
}
#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 1001000
#define inf 1e9
using namespace std;
int n,i,t,ans,tot,x,a[N],q[N],r[N],l[N],la[N],ne[N],fir[N];char s[N];
struct Tr{int l,r,v;}T[N*4];
void add(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void bt(int k,int l,int r){
	T[k].l=l;T[k].r=r;int mid=l+r>>1;
	if(l==r)return;
	bt(k<<1,l,mid);bt(k<<1|1,mid+1,r);
}
void ins(int k,int x){
	int l=T[k].l,r=T[k].r,mid=l+r>>1;
	if(l==r){T[k].v=l;return;}
	if(x<=mid)ins(k<<1,x);else ins(k<<1|1,x);
	T[k].v=max(T[k<<1].v,T[k<<1|1].v);
}
int query(int k,int x,int y){
	int l=T[k].l,r=T[k].r,mid=l+r>>1;
	if(x<=l&&r<=y)return T[k].v;
	if(x>mid)return query(k<<1|1,x,y);else
	if(y<=mid)return query(k<<1,x,y);else
	return max(query(k<<1,x,mid),query(k<<1|1,mid+1,y));
}
int main(){
	scanf("%d%s",&n,s+2);n++;a[n+1]=-inf;
	for(i=2;i<=n;i++)a[i]=a[i-1]+(s[i]=='p'?1:-1);
	for(i=1;i<=n+1;q[++t]=i++)for(;t&&a[i]<a[q[t]];)r[q[t--]]=i-1;
	for(a[0]=inf,t=0,i=n;i>=0;q[++t]=i--)for(;t&&a[i]>a[q[t]];)l[q[t--]]=i+1;
	for(i=1;i<=n;i++)add(l[i],i);bt(1,1,n);
	for(x=1;x<=n;x++){
		for(i=fir[x];i;i=ne[i])ins(1,la[i]);
		ans=max(ans,query(1,x,r[x])-x);
	}
	printf("%d",ans);
}

T2 Hotel 首先很好想到枚举中心店,然后找到离它距离相等的三个点即为答案,我一开始暴力地写了一遍,发现会出现重复统计的情况,因为三个点可能来自同一个子树中,所以要对所有出边各做一次DFS再统计答案,就能得到正确的结果

#include<cstdio>
#include<cstring>
#define N 5010
typedef long long LL;LL sum,cnt[N],ans[N];
int n,i,j,x,y,tot,dis[N],fir[N],la[N<<1],ne[N<<1];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int fa,int dp){
	++dis[dp];
	for(int i=fir[x];i;i=ne[i])if(la[i]!=fa)dfs(la[i],x,dp+1);
}
int main(){
	scanf("%d",&n);
	for(i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
	for(x=1;x<=n;x++){
		memset(cnt,0,sizeof(cnt));memset(ans,0,sizeof(ans));
		for(i=fir[x];i;i=ne[i]){
			memset(dis,0,sizeof(dis));
			dfs(la[i],x,1);
			for(j=1;j<=n;j++){
				sum+=ans[j]*dis[j];
				ans[j]+=cnt[j]*dis[j];
				cnt[j]+=dis[j];
			}
		}
	}
	printf("%lld",sum);
}

T3 Bricks 写了个贪心爆了好几发,终于A啦

#include<cstdio>
#include<algorithm>
#define N 1001000
using namespace std;
int n,m,i,s,t,x,la,rt,top,ans[N],val[N],son[N][2];
int merge(int x,int y){
	if(!x||!y)return x+y;
	if(val[x]<val[y]||val[x]==val[y]&&y==t)swap(x,y);
	son[x][1]=merge(son[x][1],y);
	swap(son[x][0],son[x][1]);
	return x;
}
int main(){
	scanf("%d%d%d",&n,&s,&t);val[s]--;val[t]--;
	for(i=1;i<=n;i++){
		scanf("%d",&x);
		m+=x,val[i]+=x;
		if(val[i]<0)return puts("0"),0;
		rt=merge(rt,i);
	}
	if(m==1){
		if(s==t&&t==1)return printf("%d",s),0;
		return puts("0"),0;
	}
	ans[++top]=s;
	for(la=s,i=2;i<m;i++){
		if(rt==la){
			x=rt;rt=merge(son[rt][0],son[rt][1]);
			if(--val[la=rt]<0)return puts("0"),0;
			rt=merge(son[rt][0],son[rt][1]);
			son[x][0]=son[x][1]=son[la][0]=son[la][1]=0;
			rt=merge(rt,x);
		}else{
			if(--val[la=rt]<0)return puts("0"),0;
			rt=merge(son[rt][0],son[rt][1]);
			son[la][0]=son[la][1]=0;
		}
		rt=merge(rt,la);ans[++top]=la;
	}
	ans[++top]=t;
	for(i=1;i<=top;i++)printf("%d ",ans[i]);
}

T4 Couriers 写了个莫队T了。。只好写个主席树,好卡空间啊、、

#include<cstdio>
#include<algorithm>
#define N 501000
using namespace std;
int n,m,i,l,r,a[N],pos[N],ans[N],BS=100;
struct EG{int l,r,z;}eg[N];
struct T{int l,r,v,fm;}t[N*4];
bool cmp(EG a,EG b){if(pos[a.l]==pos[b.l])return a.r<b.r;return a.l<b.l;}
void bt(int k,int l,int r){
	t[k].l=l;t[k].r=r;int mid=l+r>>1;
	if(l==r){t[k].fm=l;return;}
	bt(k<<1,l,mid);bt(k<<1|1,mid+1,r);
}
void ins(int k,int x,int z){
	int l=t[k].l,r=t[k].r,mid=l+r>>1;
	if(l==r){t[k].v+=z;return;}
	if(x<=mid)ins(k<<1,x,z);else ins(k<<1|1,x,z);
	if(t[k<<1].v>t[k<<1|1].v)t[k].v=t[k<<1].v,t[k].fm=t[k<<1].fm;
	else t[k].v=t[k<<1|1].v,t[k].fm=t[k<<1|1].fm;
}
int main(){
	scanf("%d%d",&n,&m);for(i=1;i<=n;i++)scanf("%d",&a[i]),pos[i]=(i-1)/BS+1;
	for(i=1;i<=m;i++)scanf("%d%d",&eg[i].l,&eg[i].r),eg[i].z=i;
	sort(eg+1,eg+m+1,cmp);bt(1,1,n);
	for(i=1,l=1,r=0;i<=m;i++){
		for(;r<eg[i].r;r++)ins(1,a[r+1],1);
		for(;r>eg[i].r;r--)ins(1,a[r],-1);
		for(;l<eg[i].l;l++)ins(1,a[l],-1);
		for(;l>eg[i].l;l--)ins(1,a[l-1],1);
		if(t[1].v>(eg[i].r-eg[i].l+1)/2)ans[eg[i].z]=t[1].fm;
	}
	for(i=1;i<=m;i++)printf("%d\n",ans[i]);
}
#include<cstdio>
#define N 9999999
int n,m,x,y,sz,i,root[500010],ls[N],rs[N],sum[N];
void ins(int l,int r,int x,int &y,int v){
	sum[y=++sz]=sum[x]+1;
	if(l==r)return;int mid=(l+r)>>1;ls[y]=ls[x];rs[y]=rs[x];
	if(v<=mid)ins(l,mid,ls[x],ls[y],v);else ins(mid+1,r,rs[x],rs[y],v);
}
int query(int l,int r,int x,int y,int v){
	if(l==r)return l;int mid=(l+r)>>1;
	if(sum[ls[y]]-sum[ls[x]]>v)return query(l,mid,ls[x],ls[y],v);
	else if(sum[rs[y]]-sum[rs[x]]>v)return query(mid+1,r,rs[x],rs[y],v);
	return 0;
}
int main(){
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)scanf("%d",&x),ins(1,n,root[i-1],root[i],x);
	for(i=1;i<=m;i++){
		scanf("%d%d",&x,&y);
		printf("%d\n",query(1,n,root[x-1],root[y],(y-x+1)/2));
	}
}

T6 Card 写了个分块,但一开始T了,调了会参还是T,然后加了个读入优化卡过哈哈,代码长度再次碾压

#include<cstdio>
#include<algorithm>
#define N 200020
using namespace std;
int n,i,x,y,bx,by,n1,n2,now,m,BN,BS=200,down[N],up[N],a[N],b[N];char ch;
void read(int &x){
	for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
	for(x=0;ch>='0';ch=getchar())x=x*10+ch-'0';
}
void get(int x){
	n1=a[(x-1)*BS+1];n2=b[(x-1)*BS+1];
	for(i=(x-1)*BS+2;i<=x*BS&&i<=n;i++){
		if(n1>b[i])n1=1e9;else if(n1>a[i])n1=b[i];else n1=a[i];
		if(n2>b[i])n2=1e9;else if(n2>a[i])n2=b[i];else n2=a[i];
	}
	down[x]=n1;up[x]=n2;
}
int main(){
	read(n);BN=(n-1)/BS+1;
	for(i=1;i<=n;i++){
		read(a[i]);read(b[i]);
		if(a[i]>b[i])swap(a[i],b[i]);
	}
	for(x=1;x<=BN;x++)get(x);scanf("%d",&m);
	while(m--){
		read(x);read(y);bx=(x-1)/BS+1;by=(y-1)/BS+1;
		swap(a[x],a[y]);swap(b[x],b[y]);get(bx);get(by);
		for(now=down[1],i=2;i<=BN;i++)if(now>up[i])now=1e9;else if(now>down[i])now=up[i];else now=down[i];
		if(now==1e9)puts("NIE");else puts("TAK");
	}
}

T7 Around the world 处理出每个点往后的尽量后的点,然后从一个点开始走,每次走尽量后的点,走n步后一定会走到以后优的点。于是从这个优的点出发再走一圈就可以得到答案,时间复杂度$O(ns)$。

#include<bits/stdc++.h>
int n,s,d,i,j,z,p,w,o,ff,a[1001000],ne[1001000];
int main(){
	for(scanf("%d%d",&n,&s),i=0;i<n;i++)scanf("%d",&a[i]);
	for(;s--;){
		for(scanf("%d",&d),i=j=ff=z=0;i<n;i++){
			for(;z+a[j%n]<=d;j++)z+=a[j%n];
			if(!(ne[i]=j-i))ff=1;z-=a[i];
		}
		if(ff){puts("NIE");continue;}
		for(i=w=p=0;i<n;i++)w=(w+ne[w])%n;
		for(o=w;o<w+n;p++)o+=ne[o%n];
		printf("%d\n",p);
	}
}

T8 Criminals 题目大意:给你一个颜色序列,有两个人会分别从左往右和从右往左走,并在途中任意取走几个格子里面的颜色,直到两个人相遇。已知两个人所取走的颜色序列,并且保证这两个颜色序列的最后一个元素都是同一种颜色,代表两个人相遇的点。还知道两个人出发点的颜色都是相同的,并且他们不会取出发点的颜色(即在两个人的序列中都不会出现)。同时还发现不存在任意一个颜色在这两个序列中出现两次。求出可能的相遇点有多少个,并输出。$N\leq1000000$。

由于每个颜色在序列中只会出现一次 ,于是可以对于每个i找到左边最大的$j$,使得从$j$开始到$i-1$有第一个子序列;找到右边最小的$j$,使得$j$到$i-1$有第二个子序列。通过单调性记录$f[i]$表示长度为$i$的子序列的答案,做到$O(n)$的复杂度。然后枚举相遇点的位置,如果$L[i]$左边、$R[i]$右边存在相同颜色就可以,这也可以单调扫一遍做到$O(n)$复杂度。

#include<bits/stdc++.h>
#define N 1001000
int n,k,x,i,j,m,l,o,t,a[N],c[N],h[N],ne[N],f[N],L[N],R[N],q[N],c1[N],c2[N];
int main(){
	for(scanf("%d%d",&n,&k),i=1;i<=n;i++)scanf("%d",&c[i]);
	for(scanf("%d%d",&m,&l),i=1;i<=m;i++)scanf("%d",&a[i]);
	for(i=m+l-1;i>=m;i--)scanf("%d",&a[i]);
	for(i=1;i<=n;i++)ne[i]=h[c[i]],h[c[i]]=i,f[i]=n+1;
	for(i=n;i;i--)if(R[i]=l>1?f[m+l-1]:i,c[i]==a[m+1])for(f[m+1]=i,j=m+2;j<m+l;j++)for(;(x=f[j]<=n?ne[f[j]]:h[a[j]])>f[j-1];f[j]=x);
	for(i=1;i<=n;i++)h[i]=n+1,f[i]=0;
	for(i=n;i;i--)ne[i]=h[c[i]],h[c[i]]=i;
	for(i=1;i<=n;i++)if(L[i]=m>1?f[1]:i,c[i]==a[m-1])for(f[m-1]=i,j=m-2;j;j--)for(;(x=f[j]?ne[f[j]]:h[a[j]])<f[j+1];f[j]=x);
  	for(i=1;i<=n;i++)if(L[i]>1&&R[i]<n){
  		for(j=n;j>R[i];j--)c2[c[j]]++;
  		for(j=1;j<L[i];j++)if((!c1[c[j]]++)&&c2[c[j]])o++;
  		if(o&&c[i]==a[m])q[++t]=i;break;
	}
	for(i++;i<=n;i++){
		if(R[i]>=n)break;
		for(j=R[i-1];j<R[i];j++)if((!--c2[c[j]])&&c1[c[j]])o--;
		for(j=L[i-1];j<L[i];j++)if((!c1[c[j]]++)&&c2[c[j]])o++;
		if(o&&c[i]==a[m])q[++t]=i;
	}
	for(printf("%d\n",t),i=1;i<=t;i++)printf("%d ",q[i]);
}

T9 FarmCraft 考虑树形DP,对于一个子树x维护两个值d[]和f[]分别表示走完子树的距离和走完这个子树的最少时间,关键是怎么计算f[]

如果第$i$个走的子树是$y$,它的贡献是$\sum_{j<i} (d[j]+2)+f[x]+1$,目标就是最小化$max(\sum_{j<i}(d[j]+2)+f[x]+1)$

对于相邻两个子树$i,j$,如果$i$比$j$优$max(f[i],d[i]+2+f[j])<max(f[j],d[j]+2+f[i])$

$f[x]=max(c[x],$每个子树的贡献),DFS一遍最后统计答案即可

#include<cstdio>
#include<algorithm>
#define N 500100
using namespace std;
int n,i,x,y,tot,q[N],c[N],d[N],f[N],fir[N],la[N<<1],ne[N<<1];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
bool cmp(int x,int y){return max(f[x],d[x]+2+f[y])<max(f[y],d[y]+2+f[x]);}
void dfs(int x,int fa){
	int i,t=0,sum=0;
	for(int i=fir[x];i;i=ne[i])if(la[i]!=fa)dfs(la[i],x),d[x]+=d[la[i]]+2;
	for(i=fir[x];i;i=ne[i])if(la[i]!=fa)q[++t]=la[i];
	sort(q+1,q+t+1,cmp);
	for(i=1;i<=t;sum+=d[q[i++]]+2)f[x]=max(f[x],sum+f[q[i]]+1);
}
int main(){
	scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&c[i]),f[i]=c[i];
	for(i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
	dfs(1,0);printf("%d",max(c[1]+d[1],f[1]));
}

T10 Freight T[i]=max(T[i],T[i-1]+1),f[i]=min(max(T[i],f[j]+i-j-1)+s*2+i-j-1)=min(max(-j+T[i],f[j]-2*j+i-1))+s*2+i-1=min(min(-j)+T[i](f[j]-j<=T[i]-i+1),min(f[j]-2*j)+i-1(f[j]-j>=T[i]-i+1))+s*2+i-1,用BIT来维护两个最小值就可以了。

#include<bits/stdc++.h>
#define N 1001000
using namespace std;typedef long long LL;int n,i,x,W;LL y,z,S,c[N],d[N],f[N],T[N],v[N];
void A1(int x,LL z){for(;x;x-=x&-x)c[x]=min(c[x],z);}void A2(int x,LL z){for(;x<=W;x+=x&-x)d[x]=min(d[x],z);}
LL Q1(int x){LL V=1e18;for(;x<=W;x+=x&-x)V=min(V,c[x]);return V;}LL Q2(int x){LL V=1e18;for(;x;x-=x&-x)V=min(V,d[x]);return V;}
int main(){
	for(scanf("%d%lld",&n,&S),T[0]=-1e9,i=1;i<=n;i++)scanf("%lld",&T[i]),T[i]=max(T[i],T[i-1]+1),v[i]=T[i]-i+1;
	for(sort(v+1,v+n+2),W=unique(v+1,v+n+2)-v-1,i=1;i<=W;i++)c[i]=d[i]=1e18;
	for(A1(1,0),A2(1,0),i=1;i<=n;i++){
		x=lower_bound(v+1,v+W+1,T[i]-i+1)-v;y=Q1(x);z=Q2(x);
		f[i]=min(y+i,z+T[i])+S*2+i-1;A1(upper_bound(v+1,v+W+1,f[i]-i)-v-1,f[i]-2*i);A2(lower_bound(v+1,v+W+1,f[i]-i)-v,-i);
	}printf("%lld",f[n]);
}

T11 Little Bird 一开始想$nlgn$的DP,但发现最短的500B不到,所以觉得不太可能就改成单调队列,维护一个dp值下降的单调队列,dp值相同时取高度高的,这样就可以保证正确性啦

#include<cstdio>
#define N 1001000
int n,i,Q,x,h,t,f[N],a[N],q[N];
int main(){
	scanf("%d",&n);for(i=1;i<=n;i++)scanf("%d",&a[i]);
	for(scanf("%d",&Q);Q--;){
		scanf("%d",&x);q[h=t=1]=1;
		for(i=2;i<=n;i++){
			for(;h<=t&&i-q[h]>x;h++);
			f[i]=f[q[h]]+(a[i]>=a[q[h]]);
			for(;h<=t&&(f[i]<f[q[t]]||f[i]==f[q[t]]&&a[i]>=a[q[t]]);t--);
			q[++t]=i;
		}
		printf("%d\n",f[n]);
	}
}

T12 Rally 这题蛮神的,加一个虚拟源点S和一个虚拟汇点T,对所有点进行一遍拓扑DP求出从S到该点的最大距离f[]和该点到T的最大距离g[],那么一条边$x\to y$的权值是$f[x]+g[y]$,这个图的最长链就是所有边边权的最大值

然后拓扑序删点,按照拓扑序依次将该点入边删掉,此时最大值为答案,然后把该点出边加入

我写了个set,顺便还搞懂了multiset的正确姿势,感谢数国队让我代码长度碾压啦

#include<cstdio>
#include<algorithm>
#include<set>
#define N 501000
using namespace std;
multiset<int>st;
int n,m,x,y,h,t,i,j,tot,u,ans,q[N],du[N],fir[N],fir2[N],f[N],g[N],ne[N<<2],la[N<<2];
void ins(int x,int y){du[y]++;la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void ins2(int x,int y){la[++tot]=y;ne[tot]=fir2[x];fir2[x]=tot;}
int main(){
	scanf("%d%d",&n,&m);ans=1e9;
	while(m--)scanf("%d%d",&x,&y),ins(x,y),ins2(y,x);
	for(i=1;i<=n;i++)if(!du[i])q[++t]=i;
	while(h<t)for(i=fir[x=q[++h]];i;i=ne[i])if(!--du[la[i]])q[++t]=la[i];
	for(j=1;j<=n;j++)for(f[x=q[j]]=max(f[x],1),i=fir[x];i;i=ne[i])f[la[i]]=max(f[la[i]],f[x]+1);
	for(j=n;j;j--)for(g[x=q[j]]=max(g[x],1),i=fir[x];i;i=ne[i])g[x]=max(g[x],g[la[i]]+1);
	for(i=1;i<=n;i++)st.insert(g[i]);st.insert(0);
	for(j=1;j<=n;j++){
		for(i=fir2[x=q[j]];i;i=ne[i])st.erase(st.find(f[la[i]]+g[x]));
		st.erase(st.find(g[x]));
		if(*--st.end()<ans)ans=*--st.end(),u=x;
		for(i=fir[x];i;i=ne[i])st.insert(f[x]+g[la[i]]);
		st.insert(f[x]);
	}
	printf("%d %d",u,ans-1);
}

T14 Solar Panels 只需要找到k使得$gcd[\frac{a}{k}~\frac{b}{k},\frac{c}{k}~\frac{d}{k}]\geq1$即可,大力容斥一下就行啦

#include<cstdio>
#include<algorithm>
using namespace std;
int T,a,b,c,d,i,j,ans;
int main(){
	for(scanf("%d",&T);T--;){
		scanf("%d%d%d%d",&a,&b,&c,&d);
		if(b>d)swap(a,c),swap(b,d);a--;c--;
		for(i=1;i<=b;i=j+1){
			j=min(b/(b/i),d/(d/i));
			if(b/j>a/j&&d/j>c/j)ans=j;
		}
		printf("%d\n",ans);
	}
}

T15 Supercomputer $sum[i]$表示深度大于$i$的点数,$ans=max(i+\frac{sum[i]}{k})$,现在有$Q$个$k$值要一一给出答案,可以利用单调性维护答案就可以在$O(n)$时间内出解

#include<cstdio>
#include<algorithm>
#define N 1001000
using namespace std;typedef long long LL;
int n,Q,i,x,u,tot,h,t,q[N],a[N],sum[N],cnt[N],fir[N],la[N],ne[N],ans[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int fa,int hi){
	cnt[hi]++;u=max(u,hi);
	for(int i=fir[x];i;i=ne[i])if(la[i]!=fa)dfs(la[i],x,hi+1);
}
int ceil(int a,int b){return a/b+(a%b>0);}
int main(){
	scanf("%d%d",&n,&Q);for(i=1;i<=Q;i++)scanf("%d",&a[i]);
	for(i=2;i<=n;i++)scanf("%d",&x),ins(x,i);
	dfs(1,0,1);for(i=u;i;i--)sum[i]=sum[i+1]+cnt[i+1];
	for(h=1,i=u;i;q[++t]=i--)for(;h<t&&(LL)(sum[i]-sum[q[t]])*(q[t-1]-q[t])>=(LL)(sum[q[t-1]]-sum[q[t]])*(i-q[t]);t--);
	for(i=1;i<=u;i++)printf("%d\n",sum[i]);
	for(i=n;i;i--){
		for(;h<t&&(LL)i*(q[h]-q[h+1])<=sum[q[h+1]]-sum[q[h]];h++);
		ans[i]=q[h]+ceil(sum[q[h]],i);
	}
	for(i=1;i<=Q;i++)printf(i<Q?"%d ":"%d",a[i]>n?u:ans[a[i]]);
}

T16 Tourism 题目大意:一张$n$个点$m$条边的无向图,每个点有一个权值$C_i$,选出权值和最小的若干关键点,使得任意点离最近关键点的距离不超过$1$。任意两点间不存在节点数超过$10$的简单路径,$n\leq20000,m\leq25000$。

先DFS出一颗树,树深度不超过$10$,且非树边都是前向边。
考虑dp,$f(x)[i][j]$表示在$x$点,深度为$i$,状态为$j$的最小代价。0表示没选,1表示没选且没相邻关键点,2表示没选且有相邻关键点。 
找出所有该点的祖先,考虑转移:
1、不选该点,那么若其祖先有一个点选了,$f[i][j+2*pw[i]]=min(f[i][j+2*pw[i]],f[i-1][j])$;
2、选该点,那么其祖先状态为1的都可以改为2,$f[i][newj]=min(f[i][newj],f[i-1][j]+co[x])$。
然后继续DFS,递归完后用儿子来更新祖先,$f[i][j]=min(f[i+1][j],f[i+1][j+2*pw[i+1]])$。
时间复杂度$O((n+m)*3^{10})$,空间复杂度$O(10*3^{10})$。
#include<bits/stdc++.h>
#define N 20020
using namespace std;bool v[N];
int n,m,i,x,y,A,tot,f[15][N*3],d[N],fir[N],la[N*3],ne[N*3],q[N],a[N],pw[N];
void ins(int x,int y){la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
int G(int x,int y){return x/pw[y]%3;}
void dfs(int x,int z){
	v[x]=1;d[x]=z;int i,y,S,t=0,A,B;
	if(!z)f[z][0]=a[x],f[z][1]=0,f[z][2]=2e9;else{
		for(i=fir[x];i;i=ne[i])if(y=la[i],v[y]&&d[y]<z)q[++t]=d[y];
		for(S=0;S<pw[z+1];S++)f[z][S]=2e9;
		for(S=0;S<pw[z];S++){
			for(A=i=1,B=S;i<=t;i++)if(!G(S,q[i]))A=2;else if(G(S,q[i])==1)B+=pw[q[i]];
			f[z][S+A*pw[z]]=min(f[z][S+A*pw[z]],f[z-1][S]);f[z][B]=min(f[z][B],f[z-1][S]+a[x]);
		}
	}
	for(i=fir[x];i;i=ne[i])if(!v[y=la[i]])for(dfs(y,z+1),S=0;S<pw[z+1];S++)f[z][S]=min(f[z+1][S],f[z+1][S+2*pw[z+1]]);
}
int main(){
	for(pw[0]=i=1;i<12;i++)pw[i]=pw[i-1]*3;
	for(scanf("%d%d",&n,&m),i=1;i<=n;i++)scanf("%d",&a[i]);
	for(;m--;ins(x,y),ins(y,x))scanf("%d%d",&x,&y);
	for(i=1;i<=n;i++)if(!v[i])dfs(i,0),A+=min(f[0][0],f[0][2]);
	printf("%d",A);
}

T17 Ant colony 从食蚁兽所在的边开始DFS,维护两个值[l,r]表示蚂蚁数量的可行范围,在叶子节点时二分查找所在区间即可

#include<cstdio>
#include<algorithm>
#define N 1001000
using namespace std;typedef long long LL;
int n,m,k,i,x,y,tot,fir[N],du[N],a[N],la[N<<1],ne[N<<1];
LL ans,inf=2e9;void ins(int x,int y){du[x]++;la[++tot]=y;ne[tot]=fir[x];fir[x]=tot;}
void dfs(int x,int fa,LL l,LL r){
	if(du[x]==1)ans+=(LL)k*((upper_bound(a+1,a+m+1,(int)r)-a)-(lower_bound(a+1,a+m+1,(int)l)-a));
	for(int i=fir[x];i;i=ne[i])if(la[i]!=fa)dfs(la[i],x,min(l*max(du[la[i]]-1,1),inf),min((r+1)*max(du[la[i]]-1,1)-1,inf));
}
int main(){
	scanf("%d%d%d",&n,&m,&k);for(i=1;i<=m;i++)scanf("%d",&a[i]);sort(a+1,a+m+1);
	for(i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
	dfs(la[1],la[2],min((LL)k*max(du[la[1]]-1,1),inf),min((LL)(k+1)*max(du[la[1]]-1,1)-1,inf));
	dfs(la[2],la[1],min((LL)k*max(du[la[2]]-1,1),inf),min((LL)(k+1)*max(du[la[2]]-1,1)-1,inf));
	printf("%lld",ans);
}