12
18
2015
0

[bzoj]4345: [POI2016]Korale

-->http://www.lydsy.com/JudgeOnline/problem.php?id=4345

 

首先考虑第一个问题

定义二元组$(x,y)$表示当前价值为$x$,位置在$y$,则$(x,y)$可以转移到$(x+a[y+1],y+1)$以及$(x-a[y]+a[y+1],y+1)$两个状态,这个先把$a$数组排序,再加个小根堆维护就行了,复杂度$\mathcal{O}\left(k\log k\right)$

再考虑第二问字典序暴搜,由第一问可以知道答案相同但字典序比所求小的串的个数,于是假设一起点$l$,在$l~n$中搜可以选的珠子,这个可以二分+询问区间最小值实现,然后状态不会超过$k$次,所以复杂度是$\mathcal{O}\left(k\log n\right)$

#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
#define N 1000010
#define LL long long
int i,j,k,m,n,x,y,a[N],b[N],cnt,ans[N],mn[N][22],l[22],ll,len[N];LL f[N];
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
struct node{
	LL x;int y;
	bool operator <(const node&b)const{return x>b.x;}
};
priority_queue<node>q;
inline int min(int a,int b){return a<b?a:b;}
inline void build(){
	for(int i=1;i<=n;++i)mn[i][0]=a[i];
	int m=floor(log((double)n)/log(2.0));
	for(int i=0,o=1;i<=m;++i,o<<=1)l[i]=o;
	for(int i=1;i<=m;++i)
		for(int j=1;j<=n;++j){
			int t=j+l[i-1];
			if(t<=n)mn[j][i]=min(mn[j][i-1],mn[t][i-1]);
			else mn[j][i]=mn[j][i-1];
		}
}
inline int rmq(int l,int r){
	int m;if(len[r-l+1]!=-1)m=len[r-l+1];
	else m=len[r-l+1]=floor(log((double)(r-l+1))/log(2.0));
	return min(mn[l][m],mn[r-::l[m]+1][m]);
}
inline int ask(int x,LL s){
	int l=x,r=n,mid;
	if(rmq(l,r)>s)return 0;
	for(;l<r;m=l+r>>1,rmq(l,m)<=s?r=m:l=m+1);
	return r;	
}
void dfs(int x,LL s){
	if(!cnt)return;
	if(!s){
		if(!(--cnt))for(int i=1;i<=ll;++i)printf("%d ",ans[i]);
		return;
	}
	for(;x<=n;++x){
		if(!(x=ask(x,s)))return;
		ans[++ll]=x,dfs(x+1,s-a[x]),--ll;
	}
}
int main(){
	for(n=read(),k=read()-1,i=1;i<=n;++i)b[i]=a[i]=read();
	for(sort(b+1,b+n+1),q.push((node){b[1],1}),i=1;i<=k;++i){
		node o=q.top();q.pop(),f[i]=o.x;if(o.y==n)continue;
		q.push((node){o.x+b[o.y+1],o.y+1}),q.push((node){o.x-b[o.y]+b[o.y+1],o.y+1});
	}
	printf("%lld\n",f[k]);
	for(i=k;f[i--]==f[k];++cnt);
	memset(len,-1,sizeof len),build(),dfs(1,f[k]);
}
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
#define N 1000010
#define LL long long
inline int min(int a,int b){return a<b?a:b;}
int i,j,k,m,n,x,y,a[N],b[N],cnt,ans[N],ll;LL f[N];
const int oo=1<<30;
struct Splay *null;
struct Splay{
	Splay *ch[2];int v,s,mn;
	Splay(int _v=0):v(_v),s(1),mn(oo){ch[0]=ch[1]=null;}
	inline int cmp(int k)const{k-=ch[0]->s;if(k==1)return -1;return k<=0?0:1;}
	inline void ups(){
		s=ch[0]->s+ch[1]->s+1,mn=v;
		if(ch[0]!=null)mn=min(mn,ch[0]->mn);
		if(ch[1]!=null)mn=min(mn,ch[1]->mn);
	}
}*root,Null;
#define nc() getchar()
inline int read(){
	int x=0;char ch=nc();for(;ch<'0'||ch>'9';ch=nc());
	for(;ch<='9'&&ch>='0';x=x*10+ch-48,ch=nc());return x;
}
struct node{LL x;int y;bool operator <(const node&b)const{return x>b.x;}};
priority_queue<node>q;
inline void rotate(Splay *&o,int d){Splay *k=o->ch[d^1];o->ch[d^1]=k->ch[d],k->ch[d]=o,o->ups(),k->ups(),o=k;}
void splay(Splay *&o,int k){
	int d=o->cmp(k);
	if(d==1)k-=o->ch[0]->s+1;
	if(d!=-1){
		Splay *p=o->ch[d];
		int d2=p->cmp(k),k2=d2?k-p->ch[0]->s-1:k;
		if(d2!=-1){
			splay(p->ch[d2],k2);
			d==d2?rotate(o,d^1):rotate(o->ch[d],d);
		}
		rotate(o,d^1);
	}
}
inline int ask(int x,LL s){
	int l=x,r=n,ans=0;Splay *o;
	if(l!=1)splay(root,l-1),o=root->ch[1];
	else o=root;
	if(o->mn>s)return 0;
	while(o!=null){
		if(o->ch[0]->mn<=s)o=o->ch[0];
		else{
			if(o->v<=s){ans+=o->ch[0]->s;break;}
			else ans+=o->ch[0]->s+1,o=o->ch[1];
		}
	}
	splay(root,x+ans);
	return x+ans;
}
void dfs(int x,LL s){
	if(!cnt)return;
	if(!s){if(!(--cnt))for(int i=1;i<=ll;++i)printf("%d ",ans[i]);return;}
	for(;x<=n;++x){
		if(!(x=ask(x,s)))return;
		ans[++ll]=x,dfs(x+1,s-a[x]),--ll;
	}
}
Splay *build(int l,int r){
	if(l>=r)return null;
	int m=l+r>>1;Splay *o=new Splay();o->v=o->mn=a[m];
	if(l<m)o->ch[0]=build(l,m);
	if(m+1<r)o->ch[1]=build(m+1,r);
	return o->ups(),o;
}
inline void init(){null=&Null,null->s=0,null->mn=oo,root=build(1,n+1);}
int main(){
	for(n=read(),k=read()-1,i=1;i<=n;++i)b[i]=a[i]=read();
	for(sort(b+1,b+n+1),q.push((node){b[1],1}),i=1;i<=k;++i){
		node o=q.top();q.pop(),f[i]=o.x;if(o.y==n)continue;
		q.push((node){o.x+b[o.y+1],o.y+1}),q.push((node){o.x-b[o.y]+b[o.y+1],o.y+1});
	}
	printf("%lld\n",f[k]);
	for(i=k;f[i]==f[k];--i);cnt=k-i;
	init(),dfs(1,f[k]);
}

 

loading...

Category: bzoj | Tags: 线段树 暴力 | Read Count: 1180

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com