关键词:
1926: [Sdoi2010]粟粟的书架
Time Limit: 30 Sec Memory Limit: 552 MBSubmit: 807 Solved: 321
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
14 15 9 26 53
58 9 7 9 32
38 46 26 43 38
32 7 9 50 28
8 41 9 7 17
1 2 5 3 139
3 1 5 5 399
3 3 4 5 91
4 1 4 1 33
1 3 5 4 185
3 3 4 3 23
3 1 3 3 108
Sample Output
15
2
Poor QLW
9
1
3
HINT
Source
前50%:二位前缀和差分+二分答案
后50%:主席树维护[l,r]的Σkth+二分答案
对于第一问(R,C<=200);
预处理sum[x][y][k],num[x][y][k].表示从(1,1)到(x,y)中大于等于k的数的和与大于等于k的数的个数。
然后二分最小的数即可。
注意最后如果最小的数有多个需要稍微调整一下答案。
对于第二问(R=1):
我们还是二分最小数。
判断就变成了询问一段区间内大于等于x的数的和以及它们的个数。
显然主席树可以处理这个。
#include<cstdio> #define set(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout); using namespace std; int n,m,Q; inline int read(){ int x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f; } namespace cas1{ static const int N=201,Z=1000; int sum[N][N][Z],num[N][N][Z]; void work(){ for(int i=1,x;i<=n;i++){ for(int j=1;j<=m;j++){ x=read(); for(int k=1;k<=1000;k++){ sum[i][j][k]=sum[i-1][j][k]+sum[i][j-1][k]-sum[i-1][j-1][k]; num[i][j][k]=num[i-1][j][k]+num[i][j-1][k]-num[i-1][j-1][k]; if(x>=k) sum[i][j][k]+=x,num[i][j][k]++; } } } for(int x1,x2,y1,y2,h,l,r,mid,ans,cnt1,cnt2;Q--;){ x1=read();y1=read();x2=read();y2=read();h=read(); l=1,r=1000,ans=r+1; while(l<=r){ mid=l+r>>1; if(sum[x2][y2][mid]-sum[x1-1][y2][mid]-sum[x2][y1-1][mid]+sum[x1-1][y1-1][mid]>=h){ l=mid+1;ans=mid; } else{ r=mid-1; } } if(ans>1000) puts("Poor QLW"); else{ cnt1=sum[x2][y2][ans]-sum[x1-1][y2][ans]-sum[x2][y1-1][ans]+sum[x1-1][y1-1][ans]-h; cnt2=num[x2][y2][ans]-num[x1-1][y2][ans]-num[x2][y1-1][ans]+num[x1-1][y1-1][ans]; printf("%d ",cnt2-cnt1/ans); } } } } namespace cas2{ static const int N=5e5+5,M=N*20; int sz,tot[N],sum[M],siz[M],ls[M],rs[M],root[N]; void insert(int &k,int last,int l,int r,int x){ k=++sz; siz[k]=siz[last]+1; sum[k]=sum[last]+x; if(l==r) return ; ls[k]=ls[last]; rs[k]=rs[last]; int mid=l+r>>1; if(x<=mid) insert(ls[k],ls[last],l,mid,x); else insert(rs[k],rs[last],mid+1,r,x); } int query(int k,int last,int l,int r,int kth){ if(l==r) return (sum[k]-sum[last])/(siz[k]-siz[last])*kth; int mid=l+r>>1,cnt=siz[ls[k]]-siz[ls[last]]; if(kth<=cnt) return query(ls[k],ls[last],l,mid,kth); return sum[ls[k]]-sum[ls[last]]+query(rs[k],rs[last],mid+1,r,kth-cnt); } void work(){ for(int i=1,x;i<=m;i++){ x=read(); insert(root[i],root[i-1],1,1000,x); tot[i]=tot[i-1]+x; } for(int x1,x2,y1,y2,h,l,r,mid,up,ans,K;Q--;){ x1=read();y1=read();x2=read();y2=read();h=read(); if(tot[y2]-tot[y1-1]<h){puts("Poor QLW");continue;} l=1,r=up=y2-y1+1,ans=r; while(l<=r){ mid=l+r>>1;K=up-mid+1; if(tot[y2]-tot[y1-1]-query(root[y2],root[y1-1],1,1000,K)>=h){ r=mid-1;ans=mid-1; } else{ l=mid+1; } } printf("%d ",ans); } } } int main(){ set(susu); n=read();m=read();Q=read(); if(n<=200&&m<=200) cas1::work(); else cas2::work(); return 0; }
bzoj1926sdoi2010粟粟的书架[主席树]
粟粟的书架TimeLimit: 30Sec MemoryLimit: 552MB[Submit][Status][Discuss]Description 幸福幼儿园B29班的粟粟是一个聪明机灵、乖巧可爱的小朋友,她的爱好是画画和读书,尤其喜欢ThomasH.Cormen的文章。 粟粟家中有一个R行C列... 查看详情
bzoj1926[sdoi2010]粟粟的书架
Description幸福幼儿园B29班的粟粟是一个聪明机灵、乖巧可爱的小朋友,她的爱好是画画和读书,尤其喜欢ThomasH.Cormen的文章。粟粟家中有一个R行C列的巨型书架,书架的每一个位置都摆有一本书,上数第i行、左数第j列摆放的... 查看详情
刷题bzoj1926[sdoi2010]粟粟的书架
Description幸福幼儿园B29班的粟粟是一个聪明机灵、乖巧可爱的小朋友,她的爱好是画画和读书,尤其喜欢ThomasH.Cormen的文章。粟粟家中有一个R行C列的巨型书架,书架的每一个位置都摆有一本书,上数第i行、左数第j列摆放的书有P... 查看详情
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]粟粟的书架
题解:这是两道题前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... 查看详情
[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]粟粟的书架
题目大意:网址:https://daniu.luogu.org/problemnew/show/2468大意:本题有两问:[1]给定一个(R*C)的带权矩阵,询问(2×10^5)次在一个子矩阵内至少选择多少个点使他们的权值和大于(H)。[2]给定长度为L的一条链,询问(2×10^4)次在一个区间([L,... 查看详情
[sdoi2010]粟粟的书架(代码片段)
[SDOI2010]粟粟的书架题意:一个R*C的矩阵,每个位置都有个数page[ij],现在选定一个小矩阵范围(给左上角坐标,和右下角坐标),问这个范围内的数总和是否大于h,如果大于h的话最少选几个数aij对于50%的数... 查看详情
[bzoj1926]粟粟的书架(代码片段)
BZOJ:https://www.lydsy.com/JudgeOnline/problem.php?id=1926Luogu:https://www.luogu.org/problemnew/show/P2468BZOJ的sillyB评测机各种无故CE,只好去Luogu上A了o(╯□╰)o Algorithm:从数据范围可以发现,这其实是2道题:1、一个R×C的矩形,每次询问一个子矩... 查看详情
[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的总... 查看详情
粟粟的书架题解(代码片段)
粟粟的书架题解第一次见到这种二合一的题,开始的时候居然死磕二维主席树,又是屈辱看题解系列,其实很比较好做第一部分(R,C≤200,M≤200000,1≤Pi,j≤1,000)这一部分可以用两个数组来记录:(num[i][j][k]):代表1~i,1~j的矩形中小于... 查看详情
可持久化汇总(讲解+题目)
...OI2016]神秘数CF484ESignonFenceCF1080FKatyaandSegmentsSetsP2468[SDOI2010]粟粟的书架P3302[SD 查看详情
1927:[sdoi2010]星际竞速
1927:[Sdoi2010]星际竞速TimeLimit: 20Sec MemoryLimit: 259MBSubmit: 2040 Solved: 1257[Submit][Status][Discuss]Description 10年一度的银河系赛车大赛又要开始了。作为全银河最盛大的活动之一,夺得这个项目的冠 查看详情
[sdoi2010]地精部落
1925:[Sdoi2010]地精部落TimeLimit: 10Sec MemoryLimit: 64MBSubmit: 1300 Solved: 800[Submit][Status][Discuss]Description传说很久以前,大地上居住着一种神秘的生物:地精。地精喜欢住在连绵不绝的山脉中。具体地说,一 查看详情
bzoj1975:[sdoi2010]魔法猪学院
二次联通门: BZOJ1975:[Sdoi2010]魔法猪学院 /*BZOJ1975:[Sdoi2010]魔法猪学院k短路统计一下在能量用完之前走了多少条到终点的路即可*/#include<cstdio>#include<queue>#include<iostream>#include<cstring 查看详情