关键词:
粟粟的书架
Time Limit: 30 Sec Memory Limit: 552 MB[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
Main idea
求给定矩阵(第二问是序列)中至少要取几个数加起来可以大于给定的值。
Solution
分为两部分实现:
第一部分n,m<=200,发现值<=1000,可以令tal表示到i,j位置为止的矩阵数值>=k的权值和与个数。每次二分最小值,判断是否可行,最后注意最小值不一定要取满。
第二部分为序列,用主席树求一段区间内>=某个值的权值和与个数,然后在主席树上二分,类似静态查询Kth,如果往左子树走则加上右子树的权值与个数,最后走到叶子节点的时候判断是否需要取满即可。
Code
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cstring> 5 #include<cstdlib> 6 #include<cmath> 7 using namespace std; 8 9 const int ONE=205; 10 const int TWO=5500005; 11 const int INF=1005; 12 13 int n,m,T; 14 int x,Need,cnt; 15 int res_num,res_value; 16 int a[ONE][ONE]; 17 int X1,X2,Y1,Y2; 18 19 struct power 20 { 21 int root; 22 int left,right; 23 int value,num; 24 }Node[TWO]; 25 26 struct point 27 { 28 int num; 29 int value; 30 }tal[ONE][ONE][INF]; 31 32 33 int get() 34 { 35 int res,Q=1; char c; 36 while( (c=getchar())<48 || c>57) 37 if(c=='-')Q=-1; 38 if(Q) res=c-48; 39 while((c=getchar())>=48 && c<=57) 40 res=res*10+c-48; 41 return res*Q; 42 } 43 44 void Update(int &x,int y,int l,int r,int Val) 45 { 46 x=++cnt; 47 Node[x].value=Node[y].value+Val; 48 Node[x].num=Node[y].num+1; 49 Node[x].left=Node[y].left; 50 Node[x].right=Node[y].right; 51 if(l==r) return; 52 int mid=(l+r)/2; 53 if(Val<=mid) Update(Node[x].left,Node[y].left,l,mid,Val); 54 if(mid+1<=Val) Update(Node[x].right,Node[y].right,mid+1,r,Val); 55 } 56 57 void Query(int x,int y,int l,int r,int Need) 58 { 59 if(l==r) 60 { 61 if(Need && l) 62 { 63 int num=Need/l; 64 res_num+=num; 65 Need-=num*l; 66 if(Need>0) res_num++,Need-=l; 67 } 68 res_value=Need; 69 return; 70 } 71 72 int mid=(l+r)/2; 73 int value=Node[ Node[y].right ].value-Node[ Node[x].right ].value; 74 if(value > Need) 75 Query(Node[x].right,Node[y].right,mid+1,r,Need); 76 else 77 { 78 res_num+=Node[ Node[y].right ].num-Node[ Node[x].right ].num; 79 Query(Node[x].left,Node[y].left,l,mid,Need-value); 80 } 81 } 82 83 84 int Getvalue(int Val) 85 { 86 return tal[X2][Y2][Val].value + tal[X1-1][Y1-1][Val].value - tal[X1-1][Y2][Val].value - tal[X2][Y1-1][Val].value; 87 } 88 89 int Getnum(int Val) 90 { 91 return tal[X2][Y2][Val].num + tal[X1-1][Y1-1][Val].num - tal[X1-1][Y2][Val].num - tal[X2][Y1-1][Val].num; 92 } 93 94 void Deal(int ans) 95 { 96 res_num=Getnum(ans+1); 97 res_value=Getvalue(ans+1); 98 Need-=res_value; 99 if(Need>=0) 100 { 101 int num=Need/ans; 102 res_num+=num; 103 Need-=num*ans; 104 if(Need>0) res_num++,Need-=ans; 105 } 106 } 107 108 109 void PartOne() 110 { 111 for(int i=1;i<=n;i++) 112 for(int j=1;j<=m;j++) 113 { 114 a[i][j]=get(); 115 } 116 117 for(int k=0;k<=1000;k++) 118 { 119 for(int i=1;i<=n;i++) 120 { 121 for(int j=1;j<=m;j++) 122 { 123 tal[i][j][k].value=tal[i][j-1][k].value; 124 tal[i][j][k].num=tal[i][j-1][k].num; 125 if(a[i][j]>=k) tal[i][j][k].value+=a[i][j],tal[i][j][k].num++; 126 } 127 128 for(int j=1;j<=m;j++) 129 { 130 tal[i][j][k].value+=tal[i-1][j][k].value; 131 tal[i][j][k].num+=tal[i-1][j][k].num; 132 } 133 } 134 } 135 136 137 while(T--) 138 { 139 Need=0; 140 X1=get(); Y1=get(); X2=get(); Y2=get(); Need=get(); 141 if(Getvalue(0)<Need) 142 { 143 printf("Poor QLW\n"); 144 continue; 145 } 146 int l=0,r=1001; 147 148 int ans=1; 149 while(l<=r) 150 { 151 int mid=(l+r)/2; 152 if(Getvalue(mid)>Need) 153 { 154 ans=mid; 155 l=mid+1; 156 } 157 else r=mid-1; 158 } 159 160 if(!ans) ans=1; 161 res_num=res_value=0; 162 Deal(ans); 163 printf("%d\n",res_num); 164 } 165 } 166 167 void PartTwo() 168 { 169 for(int i=1;i<=m;i++) 170 { 171 x=get(); 172 Update(Node[i].root,Node[i-1].root,0,INF,x); 173 } 174 175 int x1,x2,y1,y2; 176 while(T--) 177 { 178 x1=get(); y1=get(); x2=get(); y2=get(); Need=get(); 179 int l=0,r=1000; 180 181 res_num=res_value=0; 182 Query(Node[y1-1].root,Node[y2].root,0,INF,Need); 183 if(res_value>0) printf("Poor QLW\n"); 184 else 185 printf("%d\n",res_num); 186 } 187 } 188 189 int main() 190 { 191 n=get(); m=get(); T=get(); 192 if(n!=1) PartOne(); 193 else PartTwo(); 194 }
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]粟粟的书架
1926:[Sdoi2010]粟粟的书架TimeLimit:30Sec MemoryLimit:552MBSubmit:1013 Solved:396[Submit][Status][Discuss]Description幸福幼儿园B29班的粟粟是一个聪明机灵、乖巧可爱的小朋友,她的爱好是画画和读书,尤其喜欢ThomasH.Cormen的文章。粟... 查看详情
bzoj1926[sdoi2010]粟粟的书架
Description幸福幼儿园B29班的粟粟是一个聪明机灵、乖巧可爱的小朋友,她的爱好是画画和读书,尤其喜欢ThomasH.Cormen的文章。粟粟家中有一个R行C列的巨型书架,书架的每一个位置都摆有一本书,上数第i行、左数第j列摆放的... 查看详情
刷题bzoj1926[sdoi2010]粟粟的书架
Description幸福幼儿园B29班的粟粟是一个聪明机灵、乖巧可爱的小朋友,她的爱好是画画和读书,尤其喜欢ThomasH.Cormen的文章。粟粟家中有一个R行C列的巨型书架,书架的每一个位置都摆有一本书,上数第i行、左数第j列摆放的书有P... 查看详情
1926:[sdoi2010]粟粟的书架
1926:[Sdoi2010]粟粟的书架TimeLimit: 30Sec MemoryLimit: 552MBSubmit: 807 Solved: 321[Submit][Status][Discuss]Description幸福幼儿园B29班的粟粟是一个聪明机灵、乖巧可爱的小朋友,她的爱好是画画和读书,尤其喜欢 查看详情
[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)... 查看详情
[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]粟粟的书架(代码片段)
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%的数... 查看详情
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的矩形中小于... 查看详情
bzoj1878:[sdoi2009]hh的项链(主席树)
题目传送门:QWQ 分析莫队也能做,但我想练练主席树。求k-th一样维护第i个时候的线段树,线段树来维护区间不同数。然后查询时可以通过上下界小优化一波。但是我的代码丑陋无比,常数巨大(捂脸 代码#include<b... 查看详情
bzoj3123[sdoi2013]森林主席树启发式合并
我们直接按父子关系建主席树,然后记录倍增方便以后求LCA,同时用并查集维护根节点,而且还要记录根节点对应的size,用来对其启发式合并,然后每当我们合并的时候我们都要暴力拆小的一部分重复以上部分,总时间复杂度... 查看详情
bzoj3123sdoi2013森林
...,那么每次启发式合并就可以了。查询路径(k)小似乎需要主席树,那么把主席树和倍增表一起暴力重构就好了。 然后发现这样的空间复杂度是(O(nlog^2n))的。感觉非常不靠谱,于是滚去写了个节点回收站……然后发现主席树节... 查看详情
bzoj3123:[sdoi2013]森林
如果题号没记错的话,2588是一个树上的主席树查询。这个题就是多了个合并而已。每一次都把小的合并到大的上就好了(所谓启发式2333)(主席树真是个好东西2333)(上部分为本蒟蒻不知道为什么RE到死都RE的代码,,,挖坑... 查看详情