-->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...
评论 (0)
