正文 

当前位置： 首页 > 程序 > java教程

[bzoj1926]粟粟的书架(代码片段)

NewErA NewErA     2022-11-15     272

关键词：

BZOJ:https://www.lydsy.com/JudgeOnline/problem.php?id=1926

Luogu:https://www.luogu.org/problemnew/show/P2468

BZOJ的sillyB评测机各种无故CE，只好去Luogu上A了o(╯□╰)o

 

Algorithm:

从数据范围可以发现，这其实是2道题：

1、一个R×C的矩形，每次询问一个子矩形的结果，R,C≤200，A[i][j]≤1000。 
2、一个C个数的序列，每次询问一个区间的结果，C≤5e5。

 

1、前缀和+二分答案

找到此题的数据特点：A[i][j]极小，只有1000，使得O（RC*1000）的算法可行

于是我们维护1~i，1~j的矩形中大于k的数的个数及它们的总和，从而O（1）得出目标矩形的结果

cnt[i][j][k]表示行号在[1,i]，列号在[1,j]，厚度大于等于k的书的数目。 
sum[i][j][k]表示行号在[1,i]，列号在[1,j]，厚度大于等于k的书的厚度之和。 

 

每一次询问二分最小厚度（最小厚度是否可行具有单调性），求出值t，表示满足条件的情况下，最大的最小厚度。 
然而由于有相同厚度，因此还要计算出厚度为t的书有多少本没有用上。 

 

2、主席树

主席树解决的一类经典问题是求区间第K大的数，

其实在这种背景下主席树的应用和线段树的性质关系并不大，可以理解为带了前缀和的二分查找树

由于其处理的区间具有对应关系，于是维护前缀的线段树间是可以相加减的，从而得到当前区间的信息

 

此题中厚度仅为1000，于是在每个点维护：

cnt：该前缀版本中，这个节点对应厚度区间内的书的数量。 
sum：该前缀版本中，这个节点对应厚度区间内的书的厚度之和。 

 

这样对答案在root[end]-root[start-1]的线段树中类似二分查找树地确定是进入左子树还是右子树即可

 

Code:

#include <bits/stdc++.h>

using namespace std;

inline int read()

    char ch;int num,f=0;
    while(!isdigit(ch=getchar())) f|=(ch==‘-‘);
    num=ch-‘0‘;
    while(isdigit(ch=getchar())) num=num*10+ch-‘0‘;
    return f?-num:num;


const int MAXN=205,MAXM=1005;
const int N=5e5+10,M=1e7+10;

struct FunSeg

    int ls,rs,sum,cnt;
seg[M];
int root[N],S[N],cnt;

int n,m,q,dat[MAXN][MAXN],f[MAXN][MAXN][MAXM],g[MAXN][MAXN][MAXM];

int cal_f(int x1,int y1,int x2,int y2,int k)

    return f[x2][y2][k]-f[x1-1][y2][k]-f[x2][y1-1][k]+f[x1-1][y1-1][k];


int cal_g(int x1,int y1,int x2,int y2,int k)

    return g[x2][y2][k]-g[x1-1][y2][k]-g[x2][y1-1][k]+g[x1-1][y1-1][k];


void solve1()

    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) dat[i][j]=read();
        
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        
            for(int k=1;k<=1000;k++)
                f[i][j][k]=f[i-1][j][k]+f[i][j-1][k]-f[i-1][j-1][k],
                g[i][j][k]=g[i-1][j][k]+g[i][j-1][k]-g[i-1][j-1][k];
            f[i][j][dat[i][j]]+=dat[i][j];g[i][j][dat[i][j]]++;
        
                
    for(int k=999;k>=1;k--)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                f[i][j][k]+=f[i][j][k+1],g[i][j][k]+=g[i][j][k+1];
    
    while(q--)
    
        int x1=read(),y1=read(),x2=read(),y2=read(),h=read(),l=1,r=1000;
        
        while(l<=r)
        
            int mid=(l+r)>>1;
            if(cal_f(x1,y1,x2,y2,mid)>=h) l=mid+1;
            else r=mid-1;
        
        
        if(!r)puts("Poor QLW");continue;;
        cout << cal_g(x1,y1,x2,y2,r)-(cal_f(x1,y1,x2,y2,r)-h)/r << endl;  //将这个厚度中多余的书减掉
    


void Update(int x,int &y,int val,int l,int r)

    y=++cnt;seg[y]=seg[x];  //不用改变的节点沿用上一次已经完全构造完的
    seg[y].sum+=val;seg[y].cnt++;
    if(l==r) return;
    
    int mid=(l+r)>>1;
    if(val<=mid) Update(seg[x].ls,seg[y].ls,val,l,mid);
    else Update(seg[x].rs,seg[y].rs,val,mid+1,r);


int Query(int x,int y,int val,int l,int r)

    if(l==r) return val/l+(val%l>0);  //对整除情况特殊处理
    
    int mid=(l+r)>>1;
    int t=seg[seg[y].rs].sum-seg[seg[x].rs].sum;
    if(t>=val) return Query(seg[x].rs,seg[y].rs,val,mid+1,r);  //厚度范围是(mid+1,r)时足够
    else return Query(seg[x].ls,seg[y].ls,val-t,l,mid)+seg[seg[y].rs].cnt-seg[seg[x].rs].cnt;  //不够时


void solve2()

    for(int i=1;i<=m;i++)
        S[i]=read(),Update(root[i-1],root[i],S[i],1,1000),S[i]+=S[i-1];   //以1~i-1的前缀树为模板建树
        
    while(q--)
    
        int x1=read(),y1=read(),x2=read(),y2=read(),h=read();
        if(S[y2]-S[y1-1]<h) puts("Poor QLW");
        else cout << Query(root[y1-1],root[y2],h,1,1000) << endl;
    


int main()

    n=read();m=read();q=read();
    if(n>1) solve1();
    else solve2();
    return 0;

 

1、注意数据范围的特点

　  如每个点数值的范围不大，可以考虑将 大于等于k的个数/总和 这样与数值范围相关的条件加入递推式中

 

2、如果  一个量是否符合要求  具有单调性，可以对这个量二分答案

 

3、主席树：

大多数时候是离线的数据结构

需要知道数据的范围。每个节点维护的是1~i个数中处于数据范围[L,R]的数的信息。

也就是说每棵前缀树中维护的是数据范围[1,1000]的区间信息

bzoj1926sdoi2010粟粟的书架[主席树]

粟粟的书架TimeLimit: 30Sec  MemoryLimit: 552MB[Submit][Status][Discuss]Description　　幸福幼儿园B29班的粟粟是一个聪明机灵、乖巧可爱的小朋友，她的爱好是画画和读书，尤其喜欢ThomasH.Cormen的文章。　　粟粟家中有一个R行C列... 查看详情

ac日记——[sdoi2010]粟粟的书架bzoj1926

1926 思路：　　主席树+二分水题； 代码：#include<bits/stdc++.h>usingnamespacestd;#definemaxn500005#definemaxr205#definemaxn_maxn*13#defineFalseAns"PoorQLW"intn,m,q,lc[maxn_],rc[maxn_],num[maxn_],ci[max 查看详情

bzoj1926[sdoi2010]粟粟的书架

 Description幸福幼儿园B29班的粟粟是一个聪明机灵、乖巧可爱的小朋友，她的爱好是画画和读书，尤其喜欢ThomasH.Cormen的文章。粟粟家中有一个R行C列的巨型书架，书架的每一个位置都摆有一本书，上数第i行、左数第j列摆放的... 查看详情

刷题bzoj1926[sdoi2010]粟粟的书架

Description幸福幼儿园B29班的粟粟是一个聪明机灵、乖巧可爱的小朋友，她的爱好是画画和读书，尤其喜欢ThomasH.Cormen的文章。粟粟家中有一个R行C列的巨型书架，书架的每一个位置都摆有一本书，上数第i行、左数第j列摆放的书有P... 查看详情

bzoj1926[sdoi2010]粟粟的书架

题解：这是两道题前50%:发现p[i][j]很小，于是记录f[i][j][k]表示（1，1）~（i，j）这个子矩阵内>=k的书的总高度,g[i][j][k]记录本数查询是二分答案就好了后50%:主席树，右子树够了就向右走，否则向左走 #include<iostream>#includ... 查看详情

bzoj1926[sdoi2010]粟粟的书架主席树+二分+前缀和

题目幸福幼儿园B29班的粟粟是一个聪明机灵、乖巧可爱的小朋友，她的爱好是画画和读书，尤其喜欢ThomasH.Cormen的文章。粟粟家中有一个R行C列的巨型书架，书架的每一个位置都摆有一本书，上数第i行、左数第j列摆放的书有Pi,j... 查看详情

1926:[sdoi2010]粟粟的书架

1926:[Sdoi2010]粟粟的书架TimeLimit: 30Sec  MemoryLimit: 552MBSubmit: 807  Solved: 321[Submit][Status][Discuss]Description幸福幼儿园B29班的粟粟是一个聪明机灵、乖巧可爱的小朋友，她的爱好是画画和读书，尤其喜欢 查看详情

[sdoi2010]粟粟的书架(代码片段)

Description幸福幼儿园B29班的粟粟是一个聪明机灵、乖巧可爱的小朋友，她的爱好是画画和读书，尤其喜欢ThomasH.Cormen的文章。粟粟家中有一个R行C列的巨型书架，书架的每一个位置都摆有一本书，上数第i行、左数第j列摆放的书有P... 查看详情

sdoi2010粟粟的书架(代码片段)

传送门代码1#include<iostream>2#include<cstring>3#include<cstdio>4#include<algorithm>5#include<math.h>6#definemaxn5000057usingnamespacestd;8intR,C,M;9intcont[1005];10inthe[205] 查看详情

[sdoi2010]粟粟的书架(代码片段)

[SDOI2010]粟粟的书架题意：一个R*C的矩阵，每个位置都有个数page[ij]，现在选定一个小矩阵范围(给左上角坐标，和右下角坐标)，问这个范围内的数总和是否大于h，如果大于h的话最少选几个数aij对于50%的数... 查看详情

粟粟的书架题解(代码片段)

粟粟的书架题解第一次见到这种二合一的题，开始的时候居然死磕二维主席树，又是屈辱看题解系列，其实很比较好做第一部分(R,C≤200，M≤200000,1≤Pi,j≤1,000)这一部分可以用两个数组来记录：(num[i][j][k]):代表1~i,1~j的矩形中小于... 查看详情

[sdoi2010]粟粟的书架

题目大意：网址：https://daniu.luogu.org/problemnew/show/2468大意：本题有两问：[1]给定一个(R*C)的带权矩阵，询问(2×10^5)次在一个子矩阵内至少选择多少个点使他们的权值和大于(H)。[2]给定长度为L的一条链，询问(2×10^4)次在一个区间([L,... 查看详情

[sdoi2010]粟粟的书架[主席树](代码片段)

[SDOI2010]粟粟的书架考虑暴力怎么做显然是提取出来(x2-x1+1)*(y2-y1+1)个数字拿出来然后从大到小排序然后就可以按次取数了…然而接下来看数据范围(50\%r,cleq200)(50\%r=1,cleq5*10^5)值域(in[1,1000])对于前50%可以用个前缀和搞定…令(sum_i,j,k)... 查看详情

sdoi2010粟粟的书架lg2468（可持久化，前缀和）(代码片段)

题面见https://www.luogu.org/problemnew/show/P2468然后这道题属于合二为一题，看一眼数据范围就能发现首先我们先考虑50分，二维前缀和维护一下（反正我不记得公式，手推了半天）tot[i][j][k]表示矩阵（1,1）到（i，j）中数值大等于k的总... 查看详情

bzoj1861书架(代码片段)

题目链接思路用一个平衡树维护点的编号和权值。这里的权值是自己赋上去的。操作1，就把x从平衡树中删掉，然后将其权值变为最小值，重新插入。操作2，与操作1类似，只要将其权值变为最大值再重新插入就行了。操作3，其... 查看详情

可持久化汇总(讲解+题目)

...OI2016]神秘数CF484ESignonFenceCF1080FKatyaandSegmentsSetsP2468[SDOI2010]粟粟的书架P3302[SD 查看详情

bzoj1861[zjoi2006]book书架——splay

【题目分析】  模板题目。  首尾两个虚拟结点，十分方便操作。【代码】#include<cstdio>#include<cstring>#include<cmath>#include<cstdlib>#include<map>#include<set>#include<queue& 查看详情

bzoj1861书架splay版

单点插入删除以及求前缀#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;constintM=100055,inf=1000000000;intread(){intans=0,f=1,c=getchar();while(c<‘0‘||c>‘9‘){if(c==‘- 查看详情