POI2014题解

POI2014题解

[BZOJ3521][Poi2014]Salad Bar

把p当作\(1\)，把j当作\(-1\)，然后做一遍前缀和。

一个合法区间\([l,r]\)要满足条件就需要满足所有前缀和\(\ge 0\)，所有后缀和\(\ge 0\)，也就是\(\forall i\in[l,r],sum_i-sum_{l-1}\ge 0,sum_r-sum_{i-1}\ge 0\)。

也就是说\(sum_{l-1}\)要是\([l-1,r]\)内的最小值，\(sum_r\)要是\([l-1,r]\)内的最大值。

可以每个位置求出\(L_i,R_i\)表示他作为右/左端点时最远的左/右端点可以延伸到哪里。然后我们要统计这样的点对：\(R_i\ge j,L_j \le i\)。

按照\(R_i\)值从小到大枚举\(i\)，在树状数组中插入所有\(j\le R_i\)的\(j\)，维护最大值即可。

#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 1e6+5;
int n,sum[N],S[N],top,L[N],R[N],id[N],c[N],ans;char s[N];
bool cmp(int i,int j){return R[i]<R[j];}
void mdf(int k,int v){while(k<=n)c[k]=max(c[k],v),k+=k&-k;}
int qry(int k){int s=0;while(k)s=max(s,c[k]),k^=k&-k;return s;}
int main(){
	scanf("%d%s",&n,s+2);++n;
	for (int i=2;i<=n;++i) sum[i]=sum[i-1]+(s[i]=='p'?1:-1);
	for (int i=1;i<=n;++i){
		while (top&&sum[S[top]]<=sum[i]) --top;
		L[i]=S[top]+1;S[++top]=i;
	}
	S[top=0]=n+1;
	for (int i=n;i;--i){
		while (top&&sum[S[top]]>=sum[i]) --top;
		R[i]=S[top]-1;S[++top]=i;
	}
	for (int i=1;i<=n;++i) id[i]=i;
	sort(id+1,id+n+1,cmp);
	for (int i=1,j=1;i<=n;++i){
		int x=id[i];
		while (j<=R[x]) mdf(L[j],j),++j;
		ans=max(ans,qry(x)-x);
	}
	printf("%d\n",ans);return 0;
}

[BZOJ3522&4543][Poi2014]Hotel

设\(f_{i,j}\)表示\(i\)子树内距离\(i\)的深度为\(j\)的点数，\(g_{i,j}\)表示\(i\)子树内满足第三个点和\(i\)的距离为\(j\)的点对数目。

使用长链剖分将复杂度优化到线性。

#include<cstdio>
#include<algorithm>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
#define ll long long
const int N = 1e5+5;
int n,to[N<<1],nxt[N<<1],head[N],cnt,len[N],son[N];
ll tmp[N<<2],*f[N],*g[N],*id=tmp,ans;
void link(int u,int v){
	to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
	to[++cnt]=u;nxt[cnt]=head[v];head[v]=cnt;
}
void dfs(int u,int ff){
	for (int e=head[u];e;e=nxt[e])
		if (to[e]!=ff){
			dfs(to[e],u);
			if (len[to[e]]>len[son[u]]) son[u]=to[e];
		}
	len[u]=len[son[u]]+1;
}
void dp(int u,int ff){
	if (son[u]) f[son[u]]=f[u]+1,g[son[u]]=g[u]-1,dp(son[u],u);
	f[u][0]=1;ans+=g[u][0];
	for (int e=head[u];e;e=nxt[e]){
		int v=to[e];if (v==ff||v==son[u]) continue;
		f[v]=id;id+=len[v]<<1;g[v]=id;id+=len[v]<<1;dp(v,u);
		for (int j=0;j<len[v];++j){
			if (j) ans+=f[u][j-1]*g[v][j];
			ans+=g[u][j+1]*f[v][j];
		}
		for (int j=0;j<len[v];++j){
			g[u][j+1]+=f[u][j+1]*f[v][j];
			if (j) g[u][j-1]+=g[v][j];
			f[u][j+1]+=f[v][j];
		}
	}
}
int main(){
	n=gi();
	for (int i=1;i<n;++i) link(gi(),gi());
	dfs(1,0);
	f[1]=id;id+=len[1]<<1;g[1]=id;id+=len[1]<<1;dp(1,0);
	printf("%lld\n",ans);return 0;
}

[BZOJ3523][Poi2014]Bricks

每次填当前剩的最多的颜色就行了。如果剩的数量相同就优先填末尾的颜色。注意多判一些无解。

（有一个数据点它前后颜色相同，但是这种颜色只有一个。。。）

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
const int N = 1e6+5;
int n,m,S,T,ans[N];
struct node{
	int x,y;
	bool operator < (const node &b) const{
		if (y^b.y) return y<b.y;
		return b.x==T;
	}
};
priority_queue<node>Q;
int main(){
	n=gi();S=gi();T=gi();
	for (int i=1;i<=n;++i){
		int x=gi();m+=x;
		if (i==S) --x;if (i==T) --x;
		if (x<0) return putchar('0'),0;
		if (x) Q.push((node){i,x});
	}
	ans[1]=S;
	for (int i=2;i<m;++i){
		node a=Q.top();Q.pop();
		if (ans[i-1]!=a.x){
			ans[i]=a.x,--a.y;
			if (a.y) Q.push(a);
		}
		else if (Q.empty()) return putchar('0'),0;
		else{
			node b=Q.top();Q.pop();
			ans[i]=b.x,--b.y;
			if (b.y) Q.push(b);Q.push(a);
		}
	}
	if (ans[m-1]==T) return putchar('0'),0;
	for (int i=1;i<m;++i) printf("%d ",ans[i]);
	printf("%d",T);return 0;
}

[BZOJ3524][Poi2014]Couriers

主席树模板题。把去年写的代码魔改成了现在的样子。

#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 5e5+5;
struct president_tree{int ls,rs,sz;}t[N*20];
int n,m,rt[N],tot,S;
int gi(){
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
void modify(int &x,int l,int r,int p){
	t[++tot]=t[x];++t[x=tot].sz;
	if (l==r) return;int mid=l+r>>1;
	if (p<=mid) modify(t[x].ls,l,mid,p);
	else modify(t[x].rs,mid+1,r,p);
}
int query(int x,int y,int l,int r){
	if (l==r) return l;int mid=l+r>>1;
	if (t[t[x].ls].sz-t[t[y].ls].sz>S) return query(t[x].ls,t[y].ls,l,mid);
	if (t[t[x].rs].sz-t[t[y].rs].sz>S) return query(t[x].rs,t[y].rs,mid+1,r);
	return 0;
}
int main(){
	n=gi();m=gi();
	for (int i=1;i<=n;i++) modify(rt[i]=rt[i-1],1,n,gi());
	while (m--){
		int l=gi(),r=gi();S=r-l+1>>1;
		printf("%d\n",query(rt[r],rt[l-1],1,n));
	}
	return 0;
}

[BZOJ3526][Poi2014]Card

线段树。在每个点用\(f_{0/1,0/1}\)表示这个区间首位使用的\(0/1\)，末位使用的\(0/1\)时是否可以单调不降。\(O(16)\)合并两个儿子的信息。实测循环展开跑得很快。

#include<cstdio>
#include<algorithm>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
const int N = 2e5+5;
int n,m,a[N][2],t[N<<2][2][2];
void pushup(int x,int l,int r,int mid){
	for (int i=0;i<=1;++i)
		for (int j=0;j<=1;++j){
			t[x][i][j]=0;
			t[x][i][j]|=t[x<<1][i][0]&t[x<<1|1][0][j]&(a[mid][0]<=a[mid+1][0]);
			t[x][i][j]|=t[x<<1][i][0]&t[x<<1|1][1][j]&(a[mid][0]<=a[mid+1][1]);
			t[x][i][j]|=t[x<<1][i][1]&t[x<<1|1][0][j]&(a[mid][1]<=a[mid+1][0]);
			t[x][i][j]|=t[x<<1][i][1]&t[x<<1|1][1][j]&(a[mid][1]<=a[mid+1][1]);
		}
}
void build(int x,int l,int r){
	if (l==r) {t[x][0][0]=t[x][1][1]=1;return;}
	int mid=l+r>>1;build(x<<1,l,mid);build(x<<1|1,mid+1,r);
	pushup(x,l,r,mid);
}
void update(int x,int l,int r,int p){
	if (l==r) return;int mid=l+r>>1;
	if (p<=mid) update(x<<1,l,mid,p);
	else update(x<<1|1,mid+1,r,p);
	pushup(x,l,r,mid);
}
int main(){
	n=gi();
	for (int i=1;i<=n;++i) a[i][0]=gi(),a[i][1]=gi();
	build(1,1,n);
	m=gi();while (m--){
		int x=gi(),y=gi();
		swap(a[x][0],a[y][0]);swap(a[x][1],a[y][1]);
		update(1,1,n,x);update(1,1,n,y);
		puts(t[1][0][0]|t[1][0][1]|t[1][1][0]|t[1][1][1]?"TAK":"NIE");
	}
	return 0;
}

[BZOJ3827][Poi2014]Around the world

原来写的并查集，结果在洛谷上\(T\)了，就换成了这种。

破环成链，每个点向前选尽量长的一段，如果接起来长度超过了\(n\)就直接输出答案。

#include<cstdio>
#include<algorithm>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
const int N = 2e6+5;
int n,m,mx,dis[N],f[N],g[N];
int main(){
	n=gi();m=gi();
	for (int i=1;i<=n;++i) g[i]=i,dis[i]=dis[i+n]=gi(),mx=max(mx,dis[i]);
	for (int i=1;i<=n+n;++i) dis[i]+=dis[i-1];
	while (m--){
		int d=gi();if (d<mx) {puts("NIE");continue;}
		for (int i=n+1,j=1;i<=n+n;++i){
			while (dis[i]-dis[j]>d) ++j;
			f[i]=f[j]+1;g[i]=g[j];
			if (i-g[i]>=n) {printf("%d\n",f[i]);break;}
		}
	}
	return 0;
}

[BZOJ3828][Poi2014]Criminals

枚举相遇点的位置，向左向右贪心匹配子序列。设\(L_i,R_i\)分别表示如果以\(i\)位置为相遇点，向左匹配第一个子序列的最大结束位置与向右匹配第二个子序列最小结束位置。然后就只要判\(L_i\)左边跟\(R_i\)右边有没有相同颜色就可以了。

#include<cstdio>
#include<algorithm>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
const int N = 1e6+5;
int n,k,c[N],C,m,l,a[N],b[N],pos[N],f[N],L[N],R[N],vis[N],cnt[N],tot,ans,fg[N];
int main(){
	n=gi();k=gi();
	for (int i=1;i<=n;++i) c[i]=gi();
	m=gi()-1;l=gi()-1;
	for (int i=1;i<=m;++i) a[i]=gi();C=gi();
	for (int i=1;i<=l;++i) b[i]=gi();gi();
	for (int i=1;i<=m;++i) pos[a[i]]=i;
	for (int i=1;i<=n;++i){
		L[i]=m?f[m]:i;
		if (pos[c[i]])
			if (pos[c[i]]==1) f[1]=i;
			else f[pos[c[i]]]=f[pos[c[i]]-1];
	}
	for (int i=1;i<=k;++i) pos[i]=0;
	for (int i=1;i<=l;++i) pos[b[i]]=i,f[i]=n+1;
	for (int i=n;i;--i){
		R[i]=l?f[l]:i;
		if (pos[c[i]])
			if (pos[c[i]]==1) f[1]=i;
			else f[pos[c[i]]]=f[pos[c[i]]-1];
	}
	int x=1;while (x<=n&&L[x]<=1) ++x;
	for (int i=n;i>R[x];--i) ++cnt[c[i]];
	for (int i=1;i<L[x];++i) if (!vis[c[i]]&&cnt[c[i]]) vis[c[i]]=1,++tot;
	if (tot&&c[x]==C) ++ans,fg[x]=1;
	for (++x;x<=n;++x){
		for (int i=R[x];i>R[x-1];--i) if (!--cnt[c[i]]&&vis[c[i]]) --tot;
		for (int i=L[x-1];i<L[x];++i) if (!vis[c[i]]&&cnt[c[i]]) vis[c[i]]=1,++tot;
		if (tot&&c[x]==C) ++ans,fg[x]=1;
	}
	printf("%d\n",ans);
	for (int i=1;i<=n;++i) if (fg[i]) printf("%d ",i);
	puts("");return 0;
}

[BZOJ3829][Poi2014]FarmCraft

设\(f_i\)表示\(i\)子树内的最晚结束时间，那么按照一定顺序访问每个儿子，每个儿子\(j\)的代价就是\(f_j+1+2\times\)前面所有儿子的大小。可以发现应该按照\(f_i+2\times sz_i\)对所有儿子排序，先访问大的再访问小的。

#include<cstdio>
#include<algorithm>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
const int N = 5e5+5;
int n,m,to[N<<1],nxt[N<<1],head[N],cnt,f[N],sz[N],tmp[N];
bool cmp(int i,int j){return f[i]-sz[i]>f[j]-sz[j];}
void dfs(int u,int fa){
	sz[u]=2;int len=0;
	for (int e=head[u];e;e=nxt[e])
		if (to[e]!=fa) dfs(to[e],u),sz[u]+=sz[to[e]];
	for (int e=head[u];e;e=nxt[e])
		if (to[e]!=fa) tmp[++len]=to[e];
	sort(tmp+1,tmp+len+1,cmp);
	for (int i=1,s=0;i<=len;++i)
		f[u]=max(f[u],f[tmp[i]]+1+s),s+=sz[tmp[i]];
}
int main(){
	n=gi();f[1]=2*n-2+gi();
	for (int i=2;i<=n;++i) f[i]=gi();
	for (int i=1;i<n;++i){
		int u=gi(),v=gi();
		to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
		to[++cnt]=u;nxt[cnt]=head[v];head[v]=cnt;
	}
	dfs(1,0);printf("%d\n",f[1]);return 0;
}

[BZOJ3830][Poi2014]Freight

最优策略下一定是划分成若干连续段，每段内的车全部开过去再依次返回。列个转移式子：\(f_i=\min_{j<i}\{\max\{t_i,f_j+i-j-1\}+2S+i-j-1\}\)，

考虑如果那个\(\max\)里面取的是\(t_i\)，则一定\(j\)越大越优，而如果取得是\(f_j+i-j-1\)则一定\(j\)越小越优。所以每个\(i\)只有两个转移点，而且\(j\)又是单调的，所以维护一下\(j\)就可以了。

#include<cstdio>
#include<algorithm>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
#define ll long long
const int N = 1e6+5;
int n;ll S,t[N],f[N];
int main(){
	n=gi();S=gi()<<1;t[0]=-1;
	for (int i=1;i<=n;++i) t[i]=gi(),t[i]=max(t[i],t[i-1]+1);
	for (int i=1,j=0;i<=n;++i){
		while (j<i&&f[j]+i-j-1<=t[i]) ++j;
		f[i]=t[i]+S+i-j;
		if (j<i) f[i]=min(f[i],f[j]+i-j-1+S+i-j-1);
	}
	printf("%lld\n",f[n]);return 0;
}

[BZOJ3831][Poi2014]Little Bird

转移式子是这样的：

\(f_i=\min\{f_j|i-j\le k,h_j>h_i\},f_i=\min\{f_j+1|i-j\le k,h_j\le h_i\}\)

发现\(h\)值至多的影响至多为\(1\)，所以还是可以用单调队列维护\(dp\)，维护\(f_i\)单调递增的单调队列，\(f_i\)相同时按高度递减即可。

#include<cstdio>
#include<algorithm>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
const int N = 1e6+5;
int n,m,k,a[N],q[N],hd,tl,f[N];
int main(){
	n=gi();
	for (int i=1;i<=n;++i) a[i]=gi();
	m=gi();while (m--){
		k=gi();q[hd=tl=1]=1;
		for (int i=2;i<=n;++i){
			if (i-q[hd]>k) ++hd;f[i]=f[q[hd]]+(a[i]>=a[q[hd]]);
			while (hd<=tl&&(f[i]<f[q[tl]]||f[i]==f[q[tl]]&&a[i]>=a[q[tl]])) --tl;
			q[++tl]=i;
		}
		printf("%d\n",f[n]);
	}
	return 0;
}

[BZOJ3832][Poi2014]Rally

新建源汇,源点向所有点连边,所有点向汇点连边。两遍\(dp\)预处理出\(f_i , g_i\)表示到\(i\)的最长路和\(i\)出发的最长路。

对于一条边\(i \to j\),它所在的最长路的长度就是\(f_i+g_j\)。

对于一个点\(u\),它的答案其实就是：\(\max\{f_i + g_j |id_i < id_u < id_j \}\)

所以我们只需要用一个支持插入删除取最大值的数据结构来维护

边集就可以了。这里使用的是可删除堆。

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
const int N = 5e5+5;
int n,m,to[N<<2],nxt[N<<2],head[N],cnt,in[N],q[N],hd,tl,f[N],g[N],mn=1<<30,pos;
vector<int>P[N];
void link(int u,int v){
	to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
	++in[v];P[v].push_back(u);
}
priority_queue<int>Q1,Q2;
int top(){
	while (!Q2.empty()&&Q1.top()==Q2.top()) Q1.pop(),Q2.pop();
	return Q1.top();
}
int main(){
	n=gi();m=gi();
	for (int i=1,u,v;i<=m;++i) u=gi(),v=gi(),link(u,v);
	for (int i=1;i<=n;++i) link(n+1,i),link(i,n+2);
	q[hd=tl=1]=n+1;
	while (hd<=tl){
		int u=q[hd++];
		for (int e=head[u];e;e=nxt[e]){
			f[to[e]]=max(f[to[e]],f[u]+1);
			if (!--in[to[e]]) q[++tl]=to[e];
		}
	}
	for (int i=tl;i;--i){
		int u=q[i];
		for (int e=head[u];e;e=nxt[e])
			g[u]=max(g[u],g[to[e]]+1);
	}
	for (int e=head[n+1];e;e=nxt[e]) Q1.push(f[n+1]+g[to[e]]);
	for (int i=2;i<=n+1;++i){
		int u=q[i];
		for (int j=0,sz=P[u].size();j<sz;++j)
			Q2.push(f[P[u][j]]+g[u]);
		if (top()<mn) mn=top(),pos=u;
		for (int e=head[u];e;e=nxt[e])
			Q1.push(f[u]+g[to[e]]);
	}
	printf("%d %d\n",pos,mn-1);return 0;
}

[BZOJ3833][Poi2014]Solar lamps

如果\((x_1,y_1)\)与\((x_2,y_2)\)不共线，那么就可以用这两个向量表示出平面上的任意一点，所以我们把每个点的坐标在新的坐标轴下表示出来，这样一来能照亮某个点的点就一定在它的左下方。

可以整体二分，每次计算一下每一盏灯会不会在\(mid\)时刻之前被点亮。

#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
int gi(){
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
const int N = 2e5+5;
int n,len,c[N];ll o[N];
struct node{
	ll x,y;int id,k,ans;
	bool operator < (const node &b) const
		{return x==b.x?y<b.y:x<b.x;}
}a[N];
void mdf(int k,int v){while(k<=n)c[k]+=v,k+=k&-k;}
int qry(int k){int s=0;while(k)s+=c[k],k^=k&-k;return s;}
void solve(int l,int r,int L,int R){
	if (L>R) return;
	if (l==r) {for (int i=L;i<=R;++i) a[i].ans=l;return;}
	sort(a+L,a+R+1);int mid=l+r>>1,p=L-1;
	for (int i=L;i<=R;++i){
		int tmp=qry(a[i].y);
		if (a[i].id<=mid||tmp>=a[i].k) mdf(a[i].y,1),swap(a[++p],a[i]);
		else a[i].k-=tmp;
	}
	for (int i=L;i<=p;++i) mdf(a[i].y,-1);
	solve(l,mid,L,p);solve(mid+1,r,p+1,R);
}
bool cmp(node i,node j){return i.id<j.id;}
int main(){
	n=gi();int x1=gi(),y1=gi(),x2=gi(),y2=gi();
	if (1ll*x1*y2-1ll*x2*y1==0){
		int mx=max(abs(x1),abs(y1)),d=(2000000000+mx-1)/mx;
		x1*=d;y1*=d;++x1;
	}
	if (1ll*x1*y2-1ll*x2*y1<0) swap(x1,x2),swap(y1,y2);
	for (int i=1;i<=n;++i){
		int x=gi(),y=gi();
		a[i]=(node){1ll*x*y2-1ll*y*x2,1ll*y*x1-1ll*x*y1};
	}

	for (int i=1;i<=n;++i) o[i]=a[i].x;
	sort(o+1,o+n+1);len=unique(o+1,o+n+1)-o-1;
	for (int i=1;i<=n;++i) a[i].x=lower_bound(o+1,o+len+1,a[i].x)-o;
	for (int i=1;i<=n;++i) o[i]=a[i].y;
	sort(o+1,o+n+1);len=unique(o+1,o+n+1)-o-1;
	for (int i=1;i<=n;++i) a[i].y=lower_bound(o+1,o+len+1,a[i].y)-o;

	for (int i=1;i<=n;++i) a[i].k=gi(),a[i].id=i;
	solve(1,n,1,n);sort(a+1,a+n+1,cmp);
	for (int i=1;i<=n;++i) printf("%d%c",a[i].ans,i==n?'\n':' ');
	return 0;
}

[BZOJ3834][Poi2014]Solar Panels

枚举\(\gcd\)，如果满足\(\lfloor\frac bi\rfloor>\lfloor\frac {a-1}i\rfloor\)且\(\lfloor\frac di\rfloor>\lfloor\frac {c-1}i\rfloor\)则合法。

其中\(\lfloor\frac bi\rfloor\)与\(\lfloor\frac di\rfloor\)至多只会变化\(O(\sqrt n)\)次，所以数论分块就好了。

#include<cstdio>
#include<algorithm>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
int main(){
	int n=gi();while (n--){
		int a=gi()-1,b=gi(),c=gi()-1,d=gi(),ans=0;
		for (int i=1,j;i<=b&&i<=d;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);
	}
	return 0;
}

[BZOJ3835][Poi2014]Supercomputer

考虑一下选择的过程。一开始瓶颈在于深度，一次操作可能选不满\(k\)个。当达到某个阈值时，瓶颈变为\(k\)，即每次都可以选满\(k\)个点。

我们可以枚举那个阈值\(i\)，设\(s_i\)表示深度大于\(i\)的点的个数，那么\(ans=\max\{i+\lceil\frac{s_i}{k}\rceil\}\)。（所有的\(i\)中有且仅有一个\(i\)作为阈值是合法的，而不合法的情况都会把答案算小，所以就取\(\max\)啦。）

然后把\(i\)也放到上面去，得到\(ans=\max\{\lceil\frac{ik+s_i}{k}\rceil\}\)。实际上就是要最大化\(ik+s_i\)。

把\(k\)视作自变量，那么我们就只需要维护直线\(y=ix+s_i\)构成的上凸壳就行了。

复杂度\(O(n\log n+q\log n)\)。

#include<cstdio>
#include<algorithm>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
#define ll long long
const int N = 1e6+5;
int n,m,d,k[N],dep[N],s[N],top;
struct node{int p,l,r;}q[N];
ll cal(int p,int x){return 1ll*p*x+s[p];}
int binary(int x,int y){
	int l=q[top].l,r=n,res=0;
	while (l<=r){
		int mid=l+r>>1;
		if (cal(x,mid)<cal(y,mid)) res=mid,r=mid-1;
		else l=mid+1;
	}
	return res;
}
int main(){
	n=gi();m=gi();
	for (int i=1;i<=m;++i) k[i]=gi();
	for (int i=2;i<=n;++i) ++s[dep[i]=dep[gi()]+1],d=max(d,dep[i]+1);
	for (int i=d;i;--i) s[i]+=s[i+1];
	for (int i=1;i<=d;++i){
		while (top&&cal(q[top].p,q[top].l)<cal(i,q[top].l)) --top;
		if (!top) q[++top]=(node){i,1,n};
		else{
			int x=binary(q[top].p,i);
			q[top].r=x-1;q[++top]=(node){i,x,n};
		}
	}
	for (int i=1;i<=m;++i){
		int l=1,r=top,res=0;
		while (l<=r){
			int mid=l+r>>1;
			if (q[mid].l<=k[i]) res=mid,l=mid+1;
			else r=mid-1;
		}
		printf("%lld ",(cal(q[res].p,k[i])+k[i]-1)/k[i]);
	}
	puts("");return 0;
}

[BZOJ3836][Poi2014]Tourism

建出\(dfs\)树后树高不超过\(10\)。

可以\(3^{dep}\)状压所有祖先的选取情况，三进制下每一位\(0\)表示未被覆盖，\(1\)表示已被覆盖但是没有在此处选，\(2\)表示在此处选了。

#include<cstdio>
#include<algorithm>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
const int N = 60000;
const int inf = 1<<30;
int pw[12],n,m,a[N],to[N],nxt[N],head[N],cnt,dep[N],q[N],f[12][N],ans;
void link(int u,int v){
	to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
	to[++cnt]=u;nxt[cnt]=head[v];head[v]=cnt;
}
int bit(int x,int y){return x/pw[y]%3;}
void upt(int &x,int y){if(x>y)x=y;}
void dfs(int u,int d){
	dep[u]=d;
	if (!d) f[0][2]=a[u],f[0][1]=inf,f[0][0]=0;
	else{
		int tl=0;
		for (int e=head[u];e;e=nxt[e])
			if (dep[to[e]]>-1&&dep[to[e]]<d) q[++tl]=dep[to[e]];
		for (int i=0;i<pw[d+1];++i) f[d][i]=inf;
		for (int i=0;i<pw[d];++i){
			int k=i,t=0;
			for (int j=1;j<=tl;++j)
				if (bit(i,q[j])==2) t=1;
				else if (bit(i,q[j])==0) k+=pw[q[j]];
			upt(f[d][i+t*pw[d]],f[d-1][i]);
			upt(f[d][k+2*pw[d]],f[d-1][i]+a[u]);
		}
	}
	for (int e=head[u];e;e=nxt[e])
		if (!~dep[to[e]]){
			dfs(to[e],d+1);
			for (int i=0;i<pw[d+1];++i)
				f[d][i]=min(f[d+1][i+2*pw[d+1]],f[d+1][i+pw[d+1]]);
		}
}
int main(){
	for (int i=pw[0]=1;i<12;++i) pw[i]=pw[i-1]*3;
	n=gi();m=gi();
	for (int i=1;i<=n;++i) a[i]=gi(),dep[i]=-1;
	for (int i=1;i<=m;++i) link(gi(),gi());
	for (int i=1;i<=n;++i) if (!~dep[i]) dfs(i,0),ans+=min(f[0][2],f[0][1]);
	printf("%d\n",ans);return 0;
}

[BZOJ3872][Poi2014]Ant colony

对每个点求：如果这个点到达根后数量为K则到这个点的蚂蚁数量的范围是多少，乘爆了可以直接设成\(\inf\)，对于每个叶子节点二分即可。

#include<cstdio>
#include<algorithm>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
const int N = 1e6+5;
const int inf = 1<<30;
int n,m,k,val[N],S,T,to[N<<1],nxt[N<<1],head[N],cnt;long long ans;
void calc(int &L,int &R,int son){
	long long l=1ll*L*son,r=1ll*R*son+son-1;
	if (l>inf) l=inf;if (r>inf) r=inf;L=l;R=r;
}
void getans(int L,int R){
	ans+=upper_bound(val+1,val+m+1,R)-lower_bound(val+1,val+m+1,L);
}
void dfs(int u,int f,int L,int R){
	int son=0;
	for (int e=head[u];e;e=nxt[e]) if (to[e]!=f) ++son;
	if (!son) {getans(L,R);return;}
	calc(L,R,son);
	for (int e=head[u];e;e=nxt[e]) if (to[e]!=f) dfs(to[e],u,L,R);
}
int main(){
	n=gi();m=gi();k=gi();
	for (int i=1;i<=m;++i) val[i]=gi();sort(val+1,val+m+1);
	S=gi();T=gi();
	for (int i=1;i<n-1;++i){
		int u=gi(),v=gi();
		to[++cnt]=v;nxt[cnt]=head[u];head[u]=cnt;
		to[++cnt]=u;nxt[cnt]=head[v];head[v]=cnt;
	}
	dfs(S,0,k,k);dfs(T,0,k,k);printf("%lld\n",1ll*ans*k);
	return 0;
}