淘淘摘苹果
题解
分块大法好!
每一个块内维护单调上升序列
然后块之间暴力lower_bound
复杂度$n*sqrt n log(sqrt n)$
代码
#include<bits/stdc++.h> using namespace std; #define ll int #define A 100005 ll t,n,m,t2; ll bl[A],h[A],mx[410],sz[410]; ll st[410][410];//但是复杂度不对啊! int main(){ freopen("TaoPApp.in","r",stdin); freopen("TaoPApp.out","w",stdout); scanf("%d%d",&n,&m); t=sqrt(n); for(ll i=1;i<=n;i++){ scanf("%d",&h[i]); bl[i]=(i-1)/t+1; t2=max(t2,bl[i]); } for(ll i=1;i<=n;i++){ ll belong=bl[i]; mx[belong]=max(mx[belong],h[i]); if(!sz[belong]){ sz[belong]++; st[belong][sz[belong]]=h[i]; continue ; } else if(h[i]>st[belong][sz[belong]]){ sz[belong]++; st[belong][sz[belong]]=h[i]; } } for(ll i=1;i<=m;i++){ ll pla,hnow,lst; scanf("%d%d",&pla,&hnow); ll belong=bl[pla],maxnow=0,cnt=0; lst=h[pla];h[pla]=hnow; for(ll j=1;j<=t2;j++){ if(j==belong){ for(ll k=(j-1)*t+1;k<=min(j*t,n);k++){ if(h[k]>maxnow){ maxnow=h[k]; cnt++; } } } else { if(mx[j]>maxnow){ cnt+=(sz[j]-(upper_bound(st[j]+1,st[j]+sz[j]+1,maxnow)-st[j])+1); maxnow=mx[j]; } } } h[pla]=lst; printf("%d ",cnt); } }
或者可以线段树
代码
#include<bits/stdc++.h> using namespace std; #define ll long long #define A 5555555 struct node{ ll l,r,max,val; }tr[A]; ll a[A]; ll n,m,lst; void built(ll x,ll l,ll r){ tr[x].l=l,tr[x].r=r; if(l==r){ return ; } ll mid=(l+r)>>1; built(x<<1,l,mid); built(x<<1|1,mid+1,r); } ll ask(ll x,ll val){ if(tr[x].l==tr[x].r) return tr[x].max>val; ll mid=(tr[x].l+tr[x].r)>>1; if(tr[x<<1].max<=val) return ask(x<<1|1,val); else return ask(x<<1,val)+tr[x].val-tr[x<<1].val; } void up(ll x){ tr[x].max=max(tr[x<<1].max,tr[x<<1|1].max); tr[x].val=tr[x<<1].val+ask(x<<1|1,tr[x<<1].max); } void change(ll x,ll pla,ll val){ if(tr[x].l==tr[x].r){ tr[x].val=1; tr[x].max=a[pla]; return ; } ll mid=(tr[x].l+tr[x].r)>>1; if(mid>=pla) change(x<<1,pla,val); else change(x<<1|1,pla,val); up(x); } int main(){ freopen("TaoPApp.in","r",stdin); freopen("TaoPApp.out","w",stdout); scanf("%lld%lld",&n,&m); built(1,1,n); for(ll i=1;i<=n;i++){ scanf("%lld",&a[i]); change(1,i,a[i]); } for(ll i=1;i<=m;i++){ ll p,h; scanf("%lld%lld",&p,&h); lst=a[p]; a[p]=h; change(1,p,a[p]); printf("%lld ",tr[1].val); a[p]=lst; change(1,p,a[p]); } }
然而分块比线段树快的多
开心的金明
题解
dp不可做就要往贪心二分上想了
贪心考虑每原材料
val[1]=s1[1].c; for(ll i=2;i<=k;i++){ val[i]=min(val[i-1]+s2[i-1].R,s1[i].c); }
我们先把所有电脑生产出来,等卖出时再计算生产消耗,能生产就生产
贪心卖就是卖出生产代价最小的
证明:如果最后生产代价大生产代价小都卖出去了,那么和先卖生产代价小再卖生产代价大,情况一样
如果生产代价小没卖出去,而卖出生产代价大的肯定不优
于是拿个堆维护一下
这种费用滞后计算思想还是要见一见
#include<bits/stdc++.h> using namespace std; #define ll long long #define A 111111 ll read(){ ll x;scanf("%lld",&x);return x; } ll tot,n,k,tot2,ans; ll val[A]; struct node{ ll val,sum; node(){} node(const ll &a,const ll &b){val=a;sum=b;} friend bool operator < (const node &a,const node &b){ return a.val<b.val; } }tmp[A],now[A]; struct some{ ll c;//原材料价格 ll d;//至少d个电脑 ll m;//生产电脑费用 ll p;//可以生产p台 ll e;//最多储存e台 ll R;//储存消耗R ll E;//储存电脑消耗 }s1[A],s2[A]; int main(){ freopen("happy.in","r",stdin); freopen("happy.out","w",stdout); scanf("%lld",&k); for(ll i=1;i<=k;i++){ scanf("%lld%lld%lld%lld",&s1[i].c,&s1[i].d,&s1[i].m,&s1[i].p); } for(ll i=1;i<=k-1;i++){ scanf("%lld%lld%lld",&s2[i].e,&s2[i].R,&s2[i].E); } val[1]=s1[1].c; for(ll i=2;i<=k;i++){ val[i]=min(val[i-1]+s2[i-1].R,s1[i].c); } for(ll i=1;i<=k;i++){ for(ll j=1;j<=tot;j++) tmp[j].val+=s2[i-1].E; tmp[++tot]=node(val[i]+s1[i].m,s1[i].p); // printf("s1.d=%lld ",s1[i].d); sort(tmp+1,tmp+tot+1); ll ned=s1[i].d,cun=s2[i].e; for(ll j=1;j<=tot;j++){ if(tmp[j].sum<=ned){ ans+=tmp[j].sum*tmp[j].val; // printf("i=%lld val=%lld sum=%lld ",i,tmp[j].val,tmp[j].sum); ned-=tmp[j].sum; tmp[j].sum=0; } else { ans+=ned*tmp[j].val; // printf("val=%lld ned=%lld ",tmp[j].val,ned); tmp[j].sum-=ned; ned=0; } } if(ned){ puts("-1"); return 0; } // printf("ans=%lld ",ans); tot2=0; for(ll j=1;j<=tot;j++){ if(tmp[j].sum==0) continue ; if(tmp[j].sum<=cun){ now[++tot2]=tmp[j]; cun-=tmp[j].sum; } else { now[++tot2]=node(tmp[j].val,cun); cun=0; } } tot=tot2; for(ll j=1;j<=tot;j++) tmp[j]=now[j]; } printf("%lld ",ans); }
笨小猴
题解
发现check是O1的(维护前缀和)然而可能初始给定序列根本组不成
然后可以每random_shuffle1次再check500000次
进行上述操作50次就AC了
代码
#include<bits/stdc++.h> using namespace std; #define ll long long #define A 1111111 struct node{ ll a,b,id; }c[A]; ll suma[A],sumb[A],sa,sb,n; ll random(ll x){ return rand()%x; } int main(){ freopen("grandmaster.in","r",stdin); freopen("grandmaster.out","w",stdout); srand((unsigned)time(0)); scanf("%lld",&n); for(ll i=1;i<=2*n+1;i++){ scanf("%lld%lld",&c[i].a,&c[i].b); c[i].id=i; sa+=c[i].a,sb+=c[i].b; } for(ll i=1;i*n<=1000000;i++){ random_shuffle(c+1,c+2*n+2); for(ll j=1;j<=2*n+1;j++) suma[j]=suma[j-1]+c[j].a, sumb[j]=sumb[j-1]+c[j].b; for(ll j=1;j<=n;j++){ ll l=random(n+1)+1; if(suma[l+n]-suma[l-1]>sa-(suma[l+n]-suma[l-1])) if(sumb[l+n]-sumb[l-1]>sb-(sumb[l+n]-sumb[l-1])){ for(ll k=l;k<=l+n;k++) printf("%lld ",c[k].id); return 0; } } if(clock()>990000){ printf("-1 "); return 0; } } }