menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[单调栈+线段树]HackerRank(101 Hack 50)【Boxes for Toys】题解
apps HackerRank
local_offer 查看标签
comment 0 条评论

题目概述

有 $n$ 个箱子,每个箱子的长宽高为 $(a_i,b_i,c_i)$(可以任意旋转),把 $[l,r]$ 的箱子装入一个大箱子需要满足区间内任意的箱子三维都小于等于大箱子,求所有区间最小体积大箱子的期望体积。

解题报告

首先要想到贪心:将每个盒子的长宽高排序,那么 $[l,r]$ 的最小体积大箱子就是 $max_amax_bmax_c$ 。

这样的话就不难想到用单调栈维护三维的最大值,然后用线段树维护以 $j$ 结尾的所有 $[i,j]$ 的答案,每次加入节点的时候就是区间乘除,询问就是区间求和。

示例程序

#include<cstdio>
#include<cctype>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=300000,MOD=1e9+7;

int n,a[maxn+5][3],top[3],stk[3][maxn+5],sum[(maxn<<2)+5],tag[(maxn<<2)+5],ans;

#define Eoln(x) ((x)==10||(x)==13||(x)==EOF)
inline char readc(){
    static char buf[100000],*l=buf,*r=buf;
    return l==r&&(r=(l=buf)+fread(buf,1,100000,stdin),l==r)?EOF:*l++;
}
template<typename T> inline int readi(T &x){
    T tot=0;char ch=readc(),lst='+';
    while (!isdigit(ch)) {if (ch==EOF) return EOF;lst=ch;ch=readc();}
    while (isdigit(ch)) tot=(tot<<3)+(tot<<1)+(ch^48),ch=readc();
    return lst=='-'?x=-tot:x=tot,Eoln(ch);
}
#define ADD(x,y) (((x)+(y))%MOD)
#define MUL(x,y) ((LL)(x)*(y)%MOD)
inline int Pow(int w,int b) {int s;for (s=1;b;b>>=1,w=MUL(w,w)) if (b&1) s=MUL(s,w);return s;}
#define Pushup(p) (sum[p]=ADD(sum[(p)<<1],sum[(p)<<1|1]))
void Build(int L,int R,int p=1){
    tag[p]=1;if (L==R) {sum[p]=MUL(a[L][0],MUL(a[L][1],a[L][2]));return;}
    int mid=L+(R-L>>1);Build(L,mid,p<<1);Build(mid+1,R,p<<1|1);Pushup(p);
}
inline void Addtag(int p,int k) {tag[p]=MUL(tag[p],k);sum[p]=MUL(sum[p],k);}
inline void Pushdown(int p) {if (tag[p]>1) Addtag(p<<1,tag[p]),Addtag(p<<1|1,tag[p]),tag[p]=1;}
void Update(int L,int R,int k,int l=1,int r=n,int p=1){
    if (L==l&&r==R) return Addtag(p,k);int mid=l+(r-l>>1);Pushdown(p);
    if (R<=mid) Update(L,R,k,l,mid,p<<1); else if (L>mid) Update(L,R,k,mid+1,r,p<<1|1);
    else Update(L,mid,k,l,mid,p<<1),Update(mid+1,R,k,mid+1,r,p<<1|1);Pushup(p);
}
int Ask(int L,int R,int l=1,int r=n,int p=1){
    if (L==l&&r==R) return sum[p];int mid=l+(r-l>>1);Pushdown(p);
    if (R<=mid) return Ask(L,R,l,mid,p<<1); else if (L>mid) return Ask(L,R,mid+1,r,p<<1|1);
    else return ADD(Ask(L,mid,l,mid,p<<1),Ask(mid+1,R,mid+1,r,p<<1|1));
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    readi(n);for (int i=1;i<=n;i++) readi(a[i][0]),readi(a[i][1]),readi(a[i][2]);
    for (int i=1;i<=n;i++) sort(a[i],a[i]+3);Build(1,n);
    for (int i=1;i<=n;ans=ADD(ans,Ask(1,i)),i++)
        for (int j=0;j<3;stk[j][++top[j]]=i,j++)
            while (top[j]&&a[stk[j][top[j]]][j]<a[i][j]){
                int now=MUL(a[i][j],Pow(a[stk[j][top[j]]][j],MOD-2));
                Update(stk[j][top[j]-1]+1,stk[j][top[j]],now);top[j]--;
            }
    printf("%lld\n",MUL(ans,Pow(((LL)n*(n+1)>>1)%MOD,MOD-2)));return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTeX数学公式
sentiment_very_satisfied
keyboard_arrow_up